Área de intersección rectángulo-rectángulo

Debajo hay 2 rectangularjs . Dadas las coordenadas de los vértices del rectángulo – (x1, y1) … (x8, y8), ¿cómo se puede abarcar el área de la región superpuesta (blanca en la figura siguiente)?

Tenga en cuenta que:

  1. Las coordenadas de puntos pueden ser cualquier
  2. Los rectangularjs pueden superponerse o no
  3. Supongamos que el área es 0 cuando los rectangularjs no se superponen, o se superponen en un punto o línea.
  4. Si un rectángulo está dentro del otro, entonces calcule el área del rectángulo más pequeño.

enter image description here

Como usted indicó que los rectangularjs pueden no estar alineados, las respuestas posibles pueden ser nada, un punto, un segmento de línea o un polígono con 3-8 lados.

La forma habitual de realizar esta 2d boolean operación 2d boolean es elegir un orden en sentido antihorario de los bordes, y luego evaluar los segmentos de borde entre los puntos críticos (intersecciones o esquinas). En cada intersección cambia de un segmento de borde del primer rectángulo a un borde del segundo, o viceversa. Siempre eliges el segmento a la izquierda del segmento anterior.

enter image description here

Hay MUCHOS detalles, pero el algoritmo básico es encontrar todas las intersecciones y ordenarlas en sus bordes con una estructura de datos apropiada. Elija una intersección (si hay una) y elija un segmento de línea que se aleje de esa intersección. Encuentra el segmento del otro rectángulo a la izquierda del segmento de inicio elegido. En la imagen, elegimos el segmento verde en la intersección a (en la dirección indicada por la flecha) como el segmento de referencia. El segmento del otro rectángulo que está a la derecha, es el segmento de aa b . Úselo como el siguiente segmento de referencia, y elija un segmento verde a la izquierda de él. Ese es el segmento de b a c . Encuentra segmento cd de la misma manera. El siguiente segmento va desde d hasta la esquina, por lo que la esquina también se encuentra en la lista de vértices de la intersección. Del maíz volvemos a a .

Para elegir el lado izquierdo cada vez, usa el determinado de las coordenadas de los vectores de dirección para los bordes que se encuentran. Si el determinante para el par ordenado de bordes dirigidos es positivo, usted va por el camino correcto.

Ahora que tiene los vértices del polígono de intersección, puede usar la fórmula del topógrafo para obtener el área.

Algunos de los detalles que te dejo son:

  • ¿Qué sucede si una esquina es coincidente con un borde o vértice del otro triángulo?

  • ¿Qué pasa si no hay intersecciones? (un rectángulo está dentro del otro, o son disjuntos; puede usar comprobaciones de punto en polígono para resolverlo. Consulte el artículo de Wikipedia sobre polígonos .

  • ¿Qué pasa si la intersección es un solo punto o un segmento?

Hay otra manera que puede encontrar interesante, pero quizás no aplicable en este caso, y es que:

  1. determinar el rectángulo mínimo (cuyos lados son paralelos a los ejes de coordenadas) que contiene ambos rectangularjs dados, vamos a llamar a ese nuevo un cuadro delimitador.
  2. elige un punto aleatorio que esté en el cuadro delimitador y comprueba si está en ambos rectangularjs o no
  3. repita el paso 2 todo el tiempo que desee (depende de la precisión que desee para su resultado) y tenga dos contadores, uno para realizar un seguimiento del número de puntos dentro de ambos rectangularjs y el otro que es el número de repeticiones del paso 2
  4. la solución final es el área del cuadro delimitador multiplicado por el número de puntos dentro de ambos rectangularjs y luego dividido por el número de repeticiones del paso 2, o en forma de fórmula:

    intersection_area = bounding_box_area * num_of_dots_inside_both / num_of_repetitions

El resultado será, por supuesto, más preciso cuando el número de repeticiones sea mayor. Por cierto, este método se llama método de Monte Carlo.

Puede calcular los puntos de intersección resolviendo ecuaciones de intersección para todos los pares de lados de las figuras: / frac {x – a} {b – a} = / frac {x – c} {d – c}

Los puntos que obtienes de esa manera pueden estar a los lados de la paralelepide, aunque no deben. Debe verificar si los puntos de intersección que obtuvo al resolver las ecuaciones se encuentran en los lados de la figura o no. Si lo hacen, puedes calcular la longitud de los lados de la figura que se extiende hacia el interior de ambas figuras, y calcular el cuadrado de la intersección tomando su múltiple.

Creo que mi método suena un poco complicado, pero este es el primer pensamiento que se me vino a la mente.

Puede ayudar pensar en el problema en términos de triangularjs en lugar de rectangularjs. Encontrar el área de un triángulo dados tres puntos en el espacio es relativamente sencillo.

Puede encontrar el área de intersección restando el área del rectángulo por la sum de las áreas de los triangularjs como se muestra en la imagen a continuación.

Triangulación

Esencialmente se convierte en un problema de triangulación .

Aquí hay una buena introducción con algunos consejos sobre estructuras de datos y algoritmos.

EDITAR:

Hay algunas librerías de triangulación gratuitas que puedes reutilizar.

Si conoces el área de los dos triangularjs con los que comienzas, puedes encontrar el área total de la unión de los rectangularjs, por lo que la intersección sería el área total de ambos rectangularjs: el área de unión.

Si usa Qt , la intersección se puede calcular como la intersección QPolygonF . Aproximadamente así:

 QPolygonF p1,p2, intersected; p1 << QPointF(r1x1,r1y1) << ... << QPointF(r1x4, r1y4); p2 << QPointF(r2x1,r2y2) << ... << QPointF(r2x4, r2y4); intersected = p1.intersected(p2); float area = polyArea(intersected); // see code block below 

(r1 = rectángulo 1, r2 = rectángulo 2, con 4 coordenadas xey respectivas).

Ahora calcule el área (usando la fórmula de Shoelace ya mencionada):

 inline float polyArea(const QPolygonF& p) { //https://en.wikipedia.org/wiki/Polygon#Area_and_centroid const int n = p.size(); float area = 0.0; for (int i=0; i 

Mi código aquí: dominio público

Quizás necesites usar opencv. Use la función fillPoly () para generar un rectángulo. Asegúrese de que el rectángulo de relleno sea blanco (255, 255, 255). Luego use la función copyTo () y obtendrá el área de superposición. Luego, verifique el valor de cada píxel, si es blanco y luego +1.