algorithm - Área de intersección de dos rectángulos girados
graphics geometry (6)
Tengo dos rectángulos 2D, definidos como un origen (x, y) un tamaño (altura, anchura) y un ángulo de rotación (0-360 °). Puedo garantizar que ambos rectángulos son del mismo tamaño.
Necesito calcular el área aproximada de intersección de estos dos rectángulos.
El cálculo no necesita ser exacto , aunque puede serlo. Estaré comparando el resultado con otras áreas de intersección para determinar el área de intersección más grande en un conjunto de rectángulos, por lo que solo debe ser preciso en relación con otros cálculos del mismo algoritmo.
Pensé en usar el área del cuadro delimitador de la región intersectada, pero tengo problemas para obtener los vértices de la región intersecada debido a todos los diferentes casos posibles:
Estoy escribiendo este programa en Objective-C en el marco de Cocoa, para lo que vale la pena, por lo que si alguien conoce algún acceso directo utilizando NSBezierPath o algo así, también puede sugerirlo.
En cualquier caso, calcular el polígono de intersección exacto de dos polígonos convexos es una tarea fácil, ya que cualquier polígono convexo se puede ver como una intersección de semiplanos. "Corte secuencial" hace el trabajo.
Elija un rectángulo (cualquiera) como el rectángulo de corte. Iterar a través de los lados del rectángulo de corte, uno por uno. Corte el segundo rectángulo por la línea que contiene el lado actual del rectángulo de corte y descarte todo lo que se encuentra en el semiplano "exterior".
Una vez que termine de recorrer todos los lados de corte, el resultado es lo que queda del otro rectángulo.
Para complementar las otras respuestas, su problema es una instancia de recorte de línea , un tema muy estudiado en gráficos de computadora, y para el cual hay muchos algoritmos disponibles. Si rota su sistema de coordenadas para que un rectángulo tenga un borde horizontal, entonces el problema es exactamente el recorte de líneas a partir de ahí.
Puedes comenzar en el artículo de Wikipedia sobre el tema e investigar desde allí.
Tome cada segmento de línea de cada rectángulo y vea si se intersecan. Habrá varias posibilidades:
Si ninguno se interseca, el área compartida es cero, a menos que todos los puntos de uno estén dentro del otro. En ese caso, el área compartida es el área de la más pequeña.
a Si dos bordes consecutivos de un rectángulo se intersecan con un solo borde de otro rectángulo, esto forma un triángulo. Calcular su área.
segundo. Si los bordes no son consecuentes, esto forma un cuadrilátero. Calcula una línea desde dos esquinas opuestas del cuadrilátero, esto forma dos triángulos. Calcula el área de cada uno y suma.
Si dos bordes de uno se intersecan con dos bordes de otro, entonces tendrá un cuadrilátero. Calcular como en 2b.
Si cada borde de uno se cruza con cada borde del otro, tendrá un octágono. Divídalo en triángulos (por ejemplo, dibuje un rayo de un vértice a cada otro vértice para hacer 4 triángulos)
@edit: Tengo una solución más general.
Compruebe el caso especial en 1.
Luego comience con cualquier vértice que se cruce, y siga los bordes desde allí hasta cualquier otro punto de intersección hasta que vuelva al primer vértice que se cruza. Esto forma un polígono convexo. dibuja un rayo desde el primer vértice a cada vetex opuesto (por ejemplo, salta el vértice hacia la izquierda y hacia la derecha). Esto lo dividirá en un montón de triángulos. Calcula el área para cada uno y suma.
Un algoritmo simple que dará una respuesta aproximada es el muestreo.
Divide uno de tus rectángulos en cuadrículas de pequeños cuadrados. Para cada punto de intersección, verifique si ese punto está dentro del otro rectángulo. El número de puntos que se encuentran dentro del otro rectángulo será una aproximación bastante buena al área de la región superpuesta. Aumentar la densidad de puntos aumentará la precisión del cálculo, a costa del rendimiento.
Una forma de fuerza bruta:
- tomar todos los puntos del conjunto de [esquinas de rectángulos] + [puntos de intersección de bordes]
- quite los puntos que no están dentro o en el borde de ambos rectángulos.
- Ahora tienes esquinas de intersección. Tenga en cuenta que la intersección es convexa.
- ordene los puntos restantes por ángulo entre el punto arbitrario del conjunto, el otro punto arbitrario y el punto dado.
- Ahora tienes los puntos de intersección en orden.
- Calcular el área de la manera habitual (por producto cruzado)
.