algorithm - guia - Fusionando y dividiendo rectángulos superpuestos para producir los que no se superponen

qgis manual

Question

Estoy buscando un algoritmo de la siguiente manera:

Dado un conjunto de rectángulos posiblemente superpuestos (todos los cuales "no se rotan", se pueden representar de manera uniforme como (izquierda, arriba, derecha, abajo) tupletes, etc.), devuelve un conjunto mínimo de (sin rotación) rectángulos no superpuestos, que ocupan la misma área.

A primera vista parece lo suficientemente simple, pero resulta ser complicado (al menos para ser hecho de manera eficiente).

¿Hay algunos métodos conocidos para este / ideas / punteros?

Los métodos para conjuntos no necesariamente mínimos, pero heurísticamente pequeños, también son interesantes, por lo que son métodos que producen un conjunto de resultados válido.

Answer 1

Algo basado en un algoritmo de barrido de línea funcionaría, creo:

• Ordene todas las coordenadas min y max x de sus rectángulos en una matriz, como eventos "start-rectangle" y "end-rectangle"
• Paso a través de la matriz, agregando cada nuevo rectángulo encontrado (evento de inicio) en un conjunto actual
• Simultáneamente, mantenga un conjunto de "rectángulos no superpuestos" que serán su conjunto de salida
• Cada vez que te encuentres con un nuevo rectángulo puedes verificar si ya está completamente contenido en el conjunto actual / salida (bastará con las comparaciones simples de las coordenadas y )
• Si no es así, agregue un nuevo rectángulo a su conjunto de salida, con las coordenadas y establecidas en la parte del nuevo rectángulo que no está cubierta.
• Cada vez que golpee un evento final rectangular, detenga cualquier rectángulo en su conjunto de salida que ya no cubra nada.

No estoy completamente seguro de que esto cubra todo, pero creo que con algunos ajustes debería hacer el trabajo. O al menos darte algunas ideas ... :)

Answer 2

Entonces, si estuviera tratando de hacer esto, lo primero que haría sería crear un espacio de grilla unificado. Encuentre todas las coordenadas xey únicas y cree una asignación a un espacio de índice. Entonces, si tiene x valores {-1, 1.5, 3.1}, asigne esos a {0, 1, 2}, y asimismo para y. Entonces cada rectángulo se puede representar exactamente con estas coordenadas enteras empaquetadas.

Luego asignaría un bitvector o algo que cubra toda la grilla, y rasterice sus rectángulos en la grilla. Lo bueno de tener una grilla es que es muy fácil trabajar con ella, y al limitarla a coordenadas únicas xey es mínima y exacta.

Una forma de encontrar una solución bastante rápida es simplemente volcar cada "píxel" de su cuadrícula ... ejecútelos a través de su mapeo, y listo. Si está buscando una cantidad más óptima de rectángulos, entonces tiene algún tipo de problema de búsqueda en sus manos.

Veamos 4 píxeles vecinos, un pequeño cuadrado de 2x2. Cuando escribo algoritmos como estos, normalmente pienso en términos de verts, bordes y caras. Entonces, estas son las caras alrededor de un vert. Si 3 de ellos están encendidos y 1 está apagado, entonces tienes una esquina cóncava. Este es el único caso inválido. Por ejemplo, si no tengo esquinas cóncavas, solo tomo las extensiones y vuelco todo como un único rectángulo. Para cada esquina cóncava, debe decidir si dividir horizontalmente, verticalmente o ambos. Pienso en la división como bordes de marcado para no cruzar cuando se encuentran extensiones. También podría hacerlo coloreando conjuntos, lo que sea más fácil para usted.

Las esquinas cóncavas y sus direcciones divididas son su espacio de búsqueda. Puede usar cualquier algoritmo de optimización que desee. Branch / bound podría funcionar bien. Apuesto a que podría encontrar una heurística simple que funciona bien (por ejemplo, si hay otra esquina cóncava directamente enfrente de la que está considerando, siempre divida en esa dirección. De lo contrario, divida en la dirección más corta). Podrías ir codicioso. O podría dividir cada vert cóncavo en ambas direcciones, lo que generalmente le daría menos rectángulos que la salida de cada ''píxel'' como rect, y sería bastante simple.

Al leer esto, me doy cuenta de que puede haber áreas que no están claras. Avísame si quieres que aclare algo.