Como dividir uma área composta de pequenos quadrados em retângulos maiores?

Question

Para onde eu iria olhar para os algoritmos que levam uma grade 2d de valores que são 0 ou 1 como entrada e, em seguida, identifica todos os possíveis retângulos não sobrepostas dentro?

Em uma explicação mais prático: Eu estou desenhando uma grade que é representado por um número de quadrados, e gostaria de encontrar uma maneira de combinar o número de quadrados adjacentes em retângulos quanto possível, a fim de reduzir o tempo gasto em percorrer cada praça e puxando-o.

eficiência máxima não é necessária, a velocidade é mais importante.

Adenda: Aparentemente o que eu estou procurando parece ser uma técnica chamada Tesselation. Agora eu só precisa encontrar uma boa descrição para este caso específico.

Adenda 2: O limite dos "1" quadrados será irregular e em alguns casos nem mesmo relacionados, como a distribuição de "1" quadrados será totalmente aleatória. Eu preciso dessas formas irregulares sejam identificados e divididos em retângulos regulares.

Resposta correta: Para obter o melhor equilíbrio entre velocidade e eficiência, é ideal para usar os dados da grade para encher um quad-árvore com cada nó com um valor de status de qualquer vazio / parcialmente cheio / preenchida.

Answer 1

Eu fiz algo semelhante para uma visualização rápida e suja voxel de caixas 3d com OpenGL.

Eu comecei a partir de top box a esquerda e armazenado a bandeira vazia / cheia. Então eu tentei expandir o retângulo para a direita até que eu bati uma caixa com uma bandeira diferente. Eu fiz o mesmo na direção para baixo.

Desenhar o retângulo, se for preenchido.

Se houver caixas remaing, repita recursivly o procedimento para todos os três retângulos remaing induzidas pela última retângulo, que são direito, inferior e direita inferior:

xxxx   1111
xxxx   1111
xxxx   1111

2222   3333
2222   3333
2222   3333

Answer 2

Tenha um olhar em este artigo a partir do Dr. Dobb Portal em encontrar um retângulo maximal na sua situação. É uma discussão muito detalhada de um algoritmo extremamente eficiente, e eu acho que repeti-lo de forma iterativa possivelmente iria resolver o seu problema.

Answer 3

Como você não está olhando para o número mínimo de praças, sugiro usar um compromisso que ainda mantém o seu algoritmo simples.

O que a melhor solução é depende de seus dados, mas uma alternativa simples é caixas de apenas coletar ao longo de uma linha. Ou seja:

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

resultará em:

skip 2
draw 3
skip 3
draw 4
skip 1

Isto irá reduzir o número de chamadas caixa de desenhar sem qualquer necessidade de caching (isto é, você pode construir suas caixas na mosca).

Se você quiser criar caixas maiores Gostaria de sugerir um algoritmo de retrocesso lá você encontra o primeiro 1 e tentar expandir a caixa em todas as direções. Construir uma lista de caixas e limpar os 1:. S como você utilizá-los

Answer 4

Então você está olhando para o limite retangular das praças 'on'?
Você quer o interno ou externo ligado?
ie. Deve a fronteira só tem praças 'on' ou você quer o retângulo para conter quadrados todo o 'on' em um grupo?

Answer 5

Eu tive que resolver um problema semelhante, meu algoritmo suportes irregulares matrizes, tenho fortemente testado e comentou isso, mas é mais lento do que a sugestão de joel-in-Go: https://stackoverflow.com/a/13802336