minimizando la superposición en rectángulos aleatorios

Question

Tengo un número de rectángulos posiblemente superpuestos, de tamaño y posición aleatorios dentro de un plano fijo. Dado que estos rectángulos son aleatorios, algunos no pueden superponerse:

 
|----- 
| | |----| 
|----| | | 
      |----| 

Algunos pueden solaparse con sólo una esquina:

 
|-----| 
| |--|--| 
|--|--| | 
    |-----| 

Algunos pueden estar contenidos dentro de otro rectángulo:

 
|----------------| 
|    | 
| |-----|  | 
| |  |  | 
| |-----|  | 
|----------------| 

Algunos pueden pasar a través de otro rectángulo:

 
    |----------------| 
    |    | 
|--|-------------------| 
| |    | | 
|--|-------------------| 
    |----------------| 

etc.

Estoy tratando de encontrar un algoritmo que me proporcione un conjunto de rectángulos que representen la misma área que el conjunto de entrada, pero sin superposición. Algunos casos son obvios: los rectángulos que se encuentran dentro de un rectángulo más grande se pueden descartar, y los rectángulos que se superponen en una esquina se pueden dividir en tres rectángulos, al igual que los rectángulos que pasan a través de otro rectángulo. Lo que estoy buscando, es un algoritmo genérico que se ocupa de todos estos casos. No me importa mucho si no es brillantemente eficiente - el conjunto de entrada es bastante pequeño (25 rectángulos como máximo)

Encontrar rectángulos que se superponen es fácil, pero se vuelve más difícil a partir de ahí, especialmente cuando se considera un rectángulo puede superponerse con muchos otros rectángulos.

Esto me está metiendo la cabeza. ¿Alguna sugerencia?

Actualización:

me he dado cuenta de una cosa más:

que puede ejecutar este algoritmo en el momento en que los rectángulos se añaden tot puso, uno a uno, o después de todos los rectángulos Ha sido agregado. Puede ser más fácil hacerlo a medida que se agregan los rectángulos, ya que solo tiene que considerar un rectángulo, pero aún necesita tener en cuenta la situación en la que un solo rectángulo se superpone a otros muchos rectángulos.

Answer 1

son los rectángulos paralelos a los ejes x & Y? Supongo que lo son.

Puedes probar usando KD-Trees.

O si quieres algo de cosecha propia y no necesariamente eficiente, podrías 'rectangular' y luego, si es necesario, fusionar rectángulos.

Por 'rectangular' me refiero a que primero encuentras un rectángulo más grande en el que encajan todos los rectángulos (básicamente el rectángulo formado por el borde izquierdo, el borde derecho, el borde inferior, el borde superior).

Ahora extienda todos los bordes de los rectángulos para cortar el rectángulo grande. Ahora tiene una 'rectangular'. Básicamente, todo esto significa que usted ordena los bordes verticales y los bordes horizontales y selecciona pares adyacentes para formar un pequeño rectángulo. Para cada rectángulo pequeño, ahora puede verificar si esto es parte del área interesante o no y rechazarlo si no lo está (está completo o completamente afuera).

Ahora tiene una lista de pequeños rectángulos (posiblemente O (n^2), en su caso tal vez ~ 2500) que constituyen el área de su interés. Si el número es lo suficientemente pequeño como para procesarlo en el futuro, puede usarlo o fusionarlo para reducir el número de rectángulos.

Para fusionar puede considerar un rectángulo y considerar 4 posibilidades para una fusión (rectángulo adyacente de la misma altura a la derecha o izquierda, o rectángulo adyacente del mismo ancho a la parte superior o inferior).

Puede acelerar algún proceso (no solo durante la fusión) al mantener una lista ordenada de bordes (tanto horizontales como paralelos) y tal vez algunas tablas hash.

Answer 2

Primero cree el conjunto de todos los rectángulos "atómicos" en la composición, es decir, áreas formadas por las intersecciones rectangulares y que no se subdividan. Cada rectángulo real cubre 1 o más rectángulos atómicos. Luego ejecute un algoritmo de optimización combinatoria, p. SETCOVER para calcular la cantidad mínima de rectángulos que necesita para cubrirlos todos.

Aquí una ilustración del enfoque. Tienes tres rectángulos (A, B, C). Crean 5 regiones atómicas (1-5):

+---------+A 
|  1 | 
| +----+-----+B 
| | 2 | 3 | 
| | +-+---+C| 
| | |4| | | 
+----+--+-+ 5 | | 
     | +-----+ | 
     +--+-------+ 

Los rectángulos cubren las regiones atómicas de acuerdo con la siguiente tabla:

A {1,2,4} 
B {2,3,4,5} 
C {4,5} 

El problema es ahora SETCOVER para seleccionar un subconjunto mínimo de los rectángulos { A, B, C} para que todas las regiones atómicas estén cubiertas cuando se juntan las regiones atómicas cubiertas por los rectángulos. La solución mínima es (obviamente)

A {1,2,4} + B {2,3,4,5} = {1,2,3,4,5} 

Tenga en cuenta que aquí las áreas no son rectangulares, p. Ej. el área 3 tiene una forma compleja.Puede deshacerse de este problema con el siguiente enfoque: tome todas las coordenadas X distintas de los puntos de esquina de los rectángulos originales y considérelos como coordenadas X de una cuadrícula y haga lo mismo para las coordenadas Y; entonces cada rectángulo cubra un conjunto de cuadrículas que nunca se subdivide, es decir .:

+---------+A  - 
|  1 | 
| +----+-----+B - 
| | 2 | 3 | 
| | +-+---+C| - 
| | |4| | | 
+----+--+-+ 5 | | - 
     | +-----+ | - 
     +--+-------+ - 

| | | | | | 

que le da la siguiente cuadrícula de 5x5:

AAA  A = rectangle A only 
A**BB B = rectangle B only 
A*#CB * = A and B 
    BCCB C = rectangles C and B 
    BBBB # = All 

De esto se puede extraer fácilmente las 5 regiones; como cuestión de hecho, ya han sido marcados :) (A, B, C, *, #)

Answer 3

Si aún no tiene un conjunto de rectángulos, puede abordarlo desde el otro lado - comience con un rectángulo grande y subdividirlo hasta que tenga un conjunto con el que pueda trabajar, eso garantizará que no haya superposiciones.

de inicio con todo un rectángulo

-------- 
|  | 
|  | 
|  | 
|  | 
|  | 
-------- 

Split en un punto aleatorio y almacenar los dos rectángulos.

-------- 
|  | 
|------| 
|  | 
|  | 
|  | 
-------- 

Dividir un rectángulo azar en un punto aleatorio

-------- 
|  | 
|------| 
| | | 
| | | 
| | | 
-------- 

repetición. . .

-------- 
|  | 
|------| 
| | | 
| |----| 
| | | 
-------- 

Detener cuando tenga el número requerido de rectángulos.

Se podría hacer que este produzca el tipo de 'aleatoriedad' que puede obtener seleccionando con más cuidado el rectángulo que se va a dividir cada vez ETCC

Answer 4

Pregunta muy interesante: creo que es mejor resolver el problema un par de rectángulos a la vez en lugar de mirar 3 o más a la vez. Comience por descartar aquellos dentro de otros rectángulos. Ahora solo tiene 3 tipos de intersecciones: superposición de esquina y superposición de traslape y superposición parcial (donde el rectángulo no atraviesa por completo). Cada uno de ellos crea un nuevo conjunto de rectángulos, ¿verdad?

Numere los rectángulos de inicio de 1 a N. Comience con el rectángulo 1 hasta encontrar un rectángulo que se intersecte. Crea nuevos rectángulos. Elimine los dos rectángulos que se cruzan y agregue los 3 o más rectángulos recién creados a su conjunto y comience nuevamente.

El resultado será un conjunto completo de rectángulos que no se superponen. ¿Esto crea la menor cantidad de rectángulos? Probablemente no, pero no especificaste que minimizar la cantidad de rectángulos era importante. ¿Toma tiempo de o (n^2)? Probablemente.

Answer 5

Si no tiene ninguna restricción sobre la cantidad de rectángulos que su algoritmo debería producir, definitivamente puede ser imprudente en su tratamiento.

1. La solución más fácil siempre

crear un conjunto de todos los cuadrados (de área 1) que están cubiertos por los rectángulos del conjunto de entrada. Un cuadrado es un rectángulo ... ¡ahí estás!

2. ¿Solución minimalista?

Bien, eso fue precipitado, sin embargo, no creo que deba preocuparse por el conjunto de entrada. Su problema es de hecho diferente:

Elija un área contigua con una forma compleja e intente cubrirlo exactamente con rectángulos, minimizando su número y para que no se superpongan.

Por supuesto, su área puede no ser contigua, pero solo significa que tiene varias áreas contiguas en las que puede trabajar de forma independiente.

Ahora, reconozco abiertamente que no conozco la mejor solución para este problema, hay varios enfoques que puedo imaginar y no conozco sus resultados o resultados. KD-Tree debería dar una solución, ¡aunque no sé si es minimalista!