Buscando un algoritmo que no sea "fuerza bruta" para eliminar las áreas que se cruzan de una colección de Rectos

Question

Tengo una colección de Rectos de tamaño n, la mayoría de los cuales se cruzan entre sí. Me gustaría eliminar las intersecciones y reducir los Rect intersección en rects más pequeños que no se cruzan.

Podría forzar fácilmente una solución bruta, pero estoy buscando un algoritmo eficiente.

Aquí es una visualización:

original:

Procesado:

Lo ideal sería que la firma del método se vería así:

public static List<RectF> resolveIntersection(List<RectF> rects); 

la salida sería mayor o igual que la entrada, donde la salida resuelve la representación visual anterior.

Answer 1

este es un problema que he resuelto en el pasado. Lo primero es ordenar los rectángulos usando el valor x o y de uno de los bordes. Digamos que ordena en la dirección y y utiliza el borde superior. El rectángulo superior en su ejemplo es primero en orden ordenado. Para cada rectángulo, conoce su tamaño en la dirección y.

Ahora, para cada entrada (llámala la entrada actual, corresponde a un rectángulo) en la lista ordenada que buscas en la lista hasta llegar a una entrada mayor que la entrada actual + el tamaño del rectángulo correspondiente. (llámelo la entrada de detención)

Cualquier entrada en la lista ordenada entre la entrada actual y esta entrada de parada serán posibles intersecciones. Simplemente verifica si los rectángulos X-Rangos se cruzan.

Al elegir ordenar en la dirección xo y, será mejor elegir la dimensión que sea más grande ya que esto implicará una menor intersección en promedio, por lo tanto, menos control.

Aquí hay un ejemplo. Los rectángulos se definen como R (x1, x2, y1, y2), donde x1 es el lado izquierdo, x2 es lado derecho, y1 es superior y y2 es inferior

rectangle 1 (1,5,0,4) 
rectangle 2 (7,9,6,8) 
rectangle 3 (2,4,2,3) 
rectangle 4 (3,6,3,7) 
rectangle 5 (3,6,9,15) 

tipo de acuerdo con y1 para dar

#    y1 size 
rectangle 1  0 4 
rectangle 3  2 3 
rectangle 4  3 4 
rectangle 2  6 2 
rectangle 5  9 6 

, el rectángulo 1 tiene y1 + tamaño = 0 + 4 = 4 lo que implica que potencialmente intersectará el rectángulo 3 (valor y1 = 3 < 4) y el rectángulo 4 (valor y1 = 3 < 4) pero no el rectángulo 2 (valor y1 = 6> 4) ... no hay necesidad de verificar ningún rectangels en la lista después de 2

Rectángulo 3 tiene y2 + tamaño = 2 + 3 = 5 lo que implica que potencialmente intersecará el rectángulo 4 (valor y1 = 3 < 5) pero no recanallar 2 (valor y1 = 6> 5) no es necesario verificar ningún rectangels en la lista después de 2

Rectángulo 4 tiene y2 + tamaño = 3 + 4 = 7 lo que implica que potencialmente intersecará el rectángulo 2 (valor y1 = 6 < 7) pero no volverá a conectar 5 (valor y1 = 9> 7)

Por supuesto, con un gran número de rectángulos generalmente solo tendrá que verificar una fracción de los pares posibles para la intersección.

Answer 2

lo que estás descrbing es el problema de embalaje, echar un vistazo a wikipedia

se refiere a this artículo que describe un algoritmo para rectángulos de embalaje en rectángulos

se trata del artículo de:

Este artículo describe un algoritmo rápido para empaquetar una serie de rectángulos de diferentes anchuras y alturas en un único rectángulo delimitador, sin superposición y de una manera que minimiza la cantidad de espacio desperdiciado en el rectángulo circundante .

Answer 3

Los algoritmos Sweepline son buenos para procesar intersecciones en universos 2D. Me refiero a considerar una línea horizontal que se mueve desde un borde rectangular al borde del rectángulo siguiente. La línea golpea una cantidad de rectángulos, formando las llamadas listas activas. La lista activa se mantiene actualizada en cada movimiento.

Al estudiar los rangos de abscisas a lo largo de la línea horizontal, puede detectar las superposiciones.

Un estudio cuidadoso de todas las configuraciones debería permitirle dividir los rectángulos de la forma que desee en un solo barrido, con menor complejidad que la fuerza bruta (más cerca de N^1.5 que de N^2).