Algoritmo para "curar" múltiples rectángulos en un número menor de rectángulos?

13

ingrese la descripción de la imagen aquí

Digamos que tengo una cuadrícula de rectángulos de diferentes formas y colores y quiero reducir (razonablemente cerca de lo óptimo está bien, lo óptimo no es necesario) el número de rectángulos para representar el mismo diseño de colores.

La imagen de arriba es un caso muy simplificado y el espacio en blanco entre los rectángulos es solo para visualización, en realidad estarían muy apretados.

¿Qué es un enfoque o nombre de algoritmo (feliz de google) que me puede ayudar a hacer esto?

algorithm geometry space-partitioning xaxxon
fuente
3
¿Puedes contarnos un poco sobre de dónde provienen estos rectángulos? ¿Tienden a alinearse (aproximadamente) con alguna cuadrícula subyacente, o comparten algún bloque de construcción común, o algún rectángulo de "átomo" más pequeño? ¿Se pueden rotar? Este parece ser el tipo de problema que puede ser muy espinoso en el caso más general, pero puede ser mucho más fácil si podemos explotar algunas restricciones o puntos en común en su escenario particular.
DMGregory
Hay una cuadrícula de cuadrados subyacente (como un tablero de ajedrez) y cada rectángulo comparte límites con esos cuadrados subyacentes. es decir, puede usar un número entero para describir arriba / abajo / izquierda / derecha de cada rectángulo. Por lo tanto, no se pueden girar en ángulos no divisibles por 90 grados. Además, la cuadrícula NxM está completamente poblada con rectángulos: no hay posiciones de cuadrícula descubiertas.
xaxxon
Solo trato de evitar el caso que se parece al ejemplo anterior (desde una perspectiva de coloración), pero está compuesto por una tonelada de rectángulos 1x1 y estoy procesando cada uno de ellos cuando puedo manejar el espacio en muchos Menos llamadas.
xaxxon
Estoy adivinando algún tipo de "solo comience en algún lugar y siga probando rectángulos cada vez más grandes en una dimensión (digamos verticalmente) hasta que toque un borde de color, luego haga crecer la otra dimensión (horizontalmente) hasta que toque un borde. Luego intente primero horizontalmente Entonces, tal vez intente solo cuadrados (creciendo en diagonal). Pero no estoy seguro si simplemente seleccionando la mayor de las 3 posibilidades anteriores es el enfoque correcto.
xaxxon
¿Es aceptable dividir un rectángulo existente, si resulta en menos rectángulos al final? ¿O el algoritmo solo debería fusionarse alguna vez? Además, ¿es el recuento total el único criterio, o prefiere formas más cuadradas sobre astillas largas y delgadas / rectángulos más grandes sobre las más pequeñas?
DMGregory

Respuestas:

15

Primero, podemos convertir sus rectángulos de origen en celdas en su cuadrícula subyacente, para hacer que la entrada sea más uniforme. (Efectivamente rasterizando el problema)

Esto nos permitirá encontrar optimizaciones que pueden no ser obvias cuando se trabaja directamente con los rectángulos de origen, particularmente cuando se trata de dividir múltiples rectángulos de origen para recombinarlos de manera diferente.

Ejemplo de conversión de rectángulos en celdas de cuadrícula y viceversa

A continuación, podemos encontrar regiones conectadas del mismo color, utilizando algoritmos de búsqueda de profundidad o de inundación. Podemos considerar cada región conectada (un poliomino ) de forma aislada; nada de lo que hagamos a una región diferente debe influir en esta.

Efectivamente, queremos encontrar una manera de diseccionar este poliomino en rectángulos (desafortunadamente, la mayor parte de la literatura que puedo encontrar trata sobre el problema opuesto: ¡diseccionar rectángulos en poliominoes! Esto hace que sea difícil buscar pistas ...)

Un método sencillo es combinar tramos horizontales de cuadrados adyacentes en rectángulos largos y delgados. Luego, podemos comparar con la fila de arriba y combinar si nuestra ejecución comienza y finaliza, ya sea cuando terminamos cada ejecución / fila, o cuando consideramos que cada celda se agrega a la ejecución actual.

Descomponiendo un poliomino en corridas horizontales, luego fusionando verticalmente

Todavía no sé qué tan cerca este método llega a ser óptimo Parece que puede tener algunos problemas cuando una fila que aún no ha considerado sugiere una división diferente de las filas que se han visto hasta ahora:

Ejemplo de un caso con una solución de 3 rectángulos, donde el método anterior encuentra 4

Detectar cuándo una corrida / rectángulo está exactamente cubierta por corridas arriba y abajo, luego dividirla y fusionarlas resolverá este caso particular, pero no he explorado cuán general es el problema.

También he mirado métodos en los que caminamos por el perímetro del poliomino y los atravesamos cada vez que nos encontramos con una esquina cóncava, pero este enfoque me parece más propenso a errores. Obtener resultados óptimos parece requerir priorizar cortes que unen dos esquinas cóncavas, y las formas que contienen huecos necesitan un manejo especial, por lo que el método de escaneo de filas parece tener la ventaja de la simplicidad.

Un método más que estoy viendo es tomar la primera carrera que se encuentra en la fila superior y extenderla hacia abajo todo lo que pueda. Luego tome la primera carrera en la fila superior de lo que queda ... Sin embargo, esto se dispara en formas de T invertidas, por lo que tampoco es óptimo.

Siento que probablemente haya una forma de usar la programación dinámica para encontrar la división óptima, pero aún no la he encontrado.

DMGregory
fuente
Gracias por la increíble respuesta! esa solución parece lo suficientemente rápida como para poder ejecutar algunas direcciones diferentes y elegir cuál parece mejor: horizontal izquierda-> derecha, horizontal derecha-> izquierda, y luego vertical en cada sentido también.
xaxxon
2
El problema es que podemos construir formas que engañarán al algoritmo desde cada dirección de barrido. Es probable que no aparezcan en el uso real, pero todavía me molesta. Creo que todavía hay una solución simple ... Algo así como notar en cada carrera, si hay esquinas cóncavas por encima a mitad de carrera. Luego, si una carrera posterior termina exactamente en ese punto, retrocedemos a través de las carreras anteriores dividiéndolas verticalmente. Sin embargo, no he resuelto todos los detalles.
DMGregory
1
Además, no estoy seguro de por qué es necesario el paso de llenado de inundación. Al pasar de una cuadrícula positino a un rectángulo largo y delgado, simplemente puede recorrer la fila o columna completa de la cuadrícula (en cualquier dirección) para crear esos rectángulos 1xN. No es necesario saber nunca el poliomino, ¿verdad?
xaxxon
Tienes razón, el relleno de inundación no es un paso necesario. Lo incluí para justificar el enfoque en una sola región de color a la vez en los pasos posteriores, pero podría aplicar fácilmente el método de escaneo de filas a múltiples regiones de color intercaladas. Sin embargo, el método basado en el perímetro debe funcionar en el perímetro de una forma a la vez.
DMGregory