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

Question

¿A dónde iré para buscar algoritmos que tomen una cuadrícula 2d de valores que sean 0 o 1 como entrada y luego identifiquen 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, para reducir el tiempo empleado Recorriendo cada plaza y dibujando.

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

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

Anexo 2: el límite de la " 1 " los cuadrados serán irregulares y en algunos casos ni siquiera estarán conectados, ya que la distribución de " 1 " Los cuadrados serán completamente aleatorios. Necesito identificar estas formas irregulares y dividirlas 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 que tenga un valor de estado vacío o parcialmente lleno / lleno.

Answer 1

He hecho algo similar para una visualización voxel rápida y sucia de cajas 3d con OpenGL.

Comencé desde el cuadro superior izquierdo y almacené la bandera vacía / llena. Luego intenté expandir el rectángulo a la derecha hasta que golpee un cuadro con una bandera diferente. Hice lo mismo en la dirección hacia abajo.

Dibuja el rectángulo, si está lleno.

Si hay recuadros restantes, repite el procedimiento para los tres rectángulos remanentes inducidos por el último rectángulo, que están a la derecha, abajo y abajo a la derecha:

xxxx   1111
xxxx   1111
xxxx   1111

2222   3333
2222   3333
2222   3333

Answer 2

Eche un vistazo a este artículo del Portal del Dr. Dobb sobre cómo encontrar un rectángulo máximo en su situación. Es una discusión muy detallada de un algoritmo extremadamente eficiente, y creo que repetirlo de forma iterativa posiblemente resuelva su problema.

Answer 3

Como no está buscando el número mínimo de cuadrados, sugeriría usar un compromiso que aún mantiene su algoritmo simple.

La mejor solución depende de sus datos, pero una alternativa simple es simplemente recolectar 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 al cuadro de sorteo sin necesidad de almacenamiento en caché (es decir, puede crear sus cuadros sobre la marcha).

Si desea crear cuadros más grandes, le sugeriría un algoritmo de seguimiento. Encontrará el primer 1 e intentará expandir el cuadro en todas las direcciones. Cree una lista de cuadros y borre los 1: s como los ha usado.

Answer 4

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

Answer 5

Tuve que resolver un problema similar, mi algoritmo admite matrices irregulares, lo he probado y comentado, pero es más lento que la sugerencia de joel-in-gö: https://stackoverflow.com/a/13802336