Buscando un algoritmo no "de fuerza bruta" para eliminar las áreas de intersección de una colección de rects

Question

Tengo una colección de Rects de N-Sall, la mayoría de los cuales se cruzan entre sí. Me gustaría eliminar las intersecciones y reducir los rectos de intersección en rects sin intervención más pequeños.

Fácilmente podría forzar una solución, pero estoy buscando un algoritmo eficiente.

Aquí hay una visualización:

Original:

Procesada:

Idealmente, la firma del método se vería así:

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

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

Answer 1

Este es un problema que resolví en el pasado. Lo primero es ordenar los rectángulos usando el valor X o Y de uno de los bordes. Digamos que ordene en la dirección Y y use el borde superior. El rectángulo más alto de 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ámelo la entrada actual, corresponde a un rectángulo) en la lista ordenada que busca hacia adelante a través de la lista hasta que alcanza una entrada mayor que la entrada actual + el tamaño del rectángulo correspondiente. (Llámalo la entrada de parada)

Cualquier entrada en la lista ordenada entre la entrada actual y esta entrada de detención será posible intersecciones. Simplemente verifique si los rangos X de los rectángulos se cruzan.

Al elegir ordenar en la dirección X o Y, será mejor elegir la dimensión que es mayor, ya que esto implicará menos intersección en promedio, por lo que menos verificación.

Aquí hay un ejemplo. Los rectángulos se definen como r (x1, x2, y1, y2) donde x1 es el lado izquierdo, x2 es el lado derecho, y1 es superior y y2 es la parte 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)

ordenar según 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

Entonces, el rectángulo 1 tiene y1 + tamaño = 0 + 4 = 4, lo que implica que potencialmente se cruzará 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 es necesario verificar ningún rectangelia en la lista después de 2

El rectángulo 3 tiene un tamaño Y2 + = 2 + 3 = 5, lo que implica que potencialmente se cruzará el rectángulo 4 (valor y1 = 3 <5) pero no recativará 2 (valor y1 = 6> 5) No es necesario verificar ningún rectangeles en la lista después de 2

El rectángulo 4 tiene un tamaño Y2 + = 3 + 4 = 7, lo que implica que potencialmente se cruzará el rectángulo 2 (valor y1 = 6 <7) pero no recativará 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 posibles pares para la intersección.

Answer 2

Los algoithms de barril son buenos para procesar intersecciones en universos 2D. Quiero decir, considere una línea horizontal que se mueve hacia abajo desde un borde rectángulo hasta el siguiente borde rectángulo. La línea golpea una serie 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 manera que desee en un solo barrido, con menor complejidad que la fuerza bruta (más cerca de N^1.5 que a N^2).

Answer 3

Lo que estás descriptando es el problema de embalaje, eche un vistazo a Wikipedia

se refiere a este Artículo que describe un algoritmo para empacar rectángulos en rectángulos

Esto es del artículo:

Este artículo describe un algoritmo rápido para empacar una serie de rectángulos de anchos y alturas variables en un solo rectángulo cerrado, sin superposición y de una manera que minimice la cantidad de espacio desperdiciado en el rectángulo cerrado.