Antes de passar uma tarde escrevendo isso sozinho, pensei em perguntar se já havia uma implementação disponível - mesmo que apenas como referência. A primeira imagem é um exemplo de máscara de bitmap que eu gostaria de transformar em uma lista de retângulos. Um algoritmo ruim retornaria cada pixel definido como um retângulo 1x1. Um bom algoritmo se pareceria com a segunda imagem, onde retorna as coordenadas dos retângulos laranja e vermelho. O fato de os retângulos se sobreporem não importa, apenas existem apenas dois retornados.
Para resumir, o resultado ideal seria estes dois retângulos (x, y, w, h): [ { 3, 1, 2, 6 }, { 1, 3, 6, 2 } ]
Esse problema está subespecificado. Como você forneceu um exemplo simples e simplista, perdeu algumas das importantes possibilidades lógicas e casos extremos aqui (ou simplesmente não os excluiu explicitamente). Por exemplo, como você não mencionou o aplicativo proposto para isso, não especificou o que é mais importante: dividir o mapa inteiro em retângulos exclusivos com uma área tão grande possível (o Problema de Embalagem, que possui um código arbitrário). número de soluções) ou simplesmente obtendo retângulos correspondentes às arestas em cada um de x e y, como você sugere acima. Eu assumo o último.
Considere o caso em que você preenche cada um dos 4 blocos que ficam imediatamente nos cantos da máscara de bit em forma de "sinal de mais" que você desenhou acima ([2, 2] é o mais alto). Agora, quais são os retângulos ideais? Considerando apenas as colunas, você prefere estreitos, rects mais longos com os mais finos para os lados, ou o quadrado maior e mais largo que agora pode ser encontrado no meio da imagem, com quadrados de agachamento acima e abaixo?
De qualquer forma, assumindo o maior número possível de rects correspondentes à borda, considere isso como uma solução de primeira tentativa:
Repita as duas etapas acima para linhas, exatamente como para colunas (usando x0 e x1 em vez disso, e uma lista separada, é claro).
Agora você deve ter algumas listas de retângulos com arestas limpas. No entanto, eles podem não ser ideais para a sua aplicação; se for esse o caso, você precisará de um sistema de heurísticas que permita empacotamento mais eficiente. Veja o Problema de Embalagem para mais informações.
fonte