¿Cómo dividir un área compuesta de cuadrados pequeños en rectángulos más grandes?

Question

¿Dónde debería buscar algoritmos que toman una cuadrícula 2d de valores que son 0 o 1 como entrada y luego identifica todos los posibles rectángulos que no se superponen?

En una explicación más práctica: estoy dibujando una cuadrícula que está representada por un número de cuadrados, y deseo encontrar una manera de combinar tantos cuadrados adyacentes en rectángulos como sea posible, con el fin de reducir el tiempo dedicado a recorrer cada cuadrado y dibujarlo.

No se necesita la máxima eficiencia, la velocidad es más importante.

Adición: Aparentemente, lo que estoy buscando parece ser una técnica llamada Tesselation. Ahora solo necesito encontrar una buena descripción para este caso específico.

Addendum 2: El límite de los cuadrados "1" será irregular y en algunos casos ni siquiera se conectará, ya que la distribución de los cuadrados "1" será completamente aleatoria. Necesito que estas formas irregulares sean identificadas y divididas en rectángulos regulares.

Respuesta correcta: Para obtener el mejor equilibrio entre velocidad y eficiencia, es óptimo utilizar los datos de la cuadrícula para llenar un árbol cuádruple con cada nodo con un estado de vacío/parcialmente lleno/lleno.

Answer 1

He hecho algo similar para una visualización vóxel rápida y sucia de cuadros 3D con OpenGL.

Comencé desde el cuadro superior izquierdo y guardé el indicador vacío/lleno. Luego traté de expandir el rectángulo hacia la derecha hasta que golpeé una casilla con una bandera diferente. Hice lo mismo en dirección hacia abajo.

Dibuje el rectángulo, si está lleno.

Si hay remaing cajas, recursivamente repita el procedimiento para los tres rectángulos remaing inducidos por el último rectángulo, que son la derecha, abajo y de abajo a la derecha:

xxxx 1111 
xxxx 1111 
xxxx 1111 

2222 3333 
2222 3333 
2222 3333 

Answer 2

¿Está buscando el límite rectangular de las casillas 'ON'?
¿Quieres el límite interno o externo?
es decir. ¿El límite solo debe tener cuadrados "ENCENDIDOS" o quiere que el rectángulo contenga todos los cuadrados "ENCENDIDOS" en un grupo?

Answer 3

Como no está buscando el número mínimo de cuadrados, le sugiero usar un compromiso que mantenga su algoritmo simple.

Cuál es la mejor solución depende de sus datos, pero una alternativa simple es simplemente juntar cajas a lo largo de una fila. Es decir:

0 0 1 1 1 0 0 0 1 1 1 1 0 

resultará en:

skip 2 
draw 3 
skip 3 
draw 4 
skip 1 

Esto reducirá el número de llamadas de cuadro para dibujar sin necesidad de almacenamiento en caché (es decir, usted puede construir su carga sobre la marcha).

Si desea crear cajas más grandes, le sugiero un algoritmo de retroceso allí encontrará el primer 1 y trate de expandir el cuadro en todas las direcciones. Crea una lista de cuadros y borra el 1: s como los has usado.

Answer 4

Tenga una mirada en this article from Dr Dobb's Portal en la búsqueda de un máximo rectángulo en su situación. Es una discusión muy detallada de un algoritmo extremadamente eficiente, y creo que repetirlo iterativamente posiblemente resolvería su problema.

Answer 5

que tenía que resolver un problema similar, mi algoritmo de soporte a matrices dentadas, en gran medida que he probado y comentado, pero es más lento que la sugerencia de Joel-en-Go: https://stackoverflow.com/a/13802336