Digamos que eu tenha uma grade de retângulos de diferentes formas e cores e que eu queira reduzir (razoavelmente próximo de ótimo é bom, ideal não é necessário) o número de retângulos para representar o mesmo layout de cores.
A imagem acima é um caso muito simplificado e o espaço em branco entre os retângulos é apenas para visualização - eles seriam realmente compactados.
O que é um nome de abordagem ou algoritmo (feliz pelo google) que pode me ajudar a fazer isso?
algorithm
geometry
space-partitioning
xaxxon
fonte
fonte
Respostas:
Primeiro, podemos converter os retângulos de origem em células na grade subjacente, para tornar a entrada mais uniforme. (Efetivamente rasterizando o problema)
Isso nos permitirá encontrar otimizações que podem não ser óbvias ao trabalhar diretamente com os retângulos de origem - principalmente quando se trata de dividir vários retângulos de origem para recombiná-los de maneira diferente.
Em seguida, podemos encontrar regiões conectadas da mesma cor, usando algoritmos de profundidade de primeira pesquisa ou preenchimento de inundação. Podemos considerar cada região conectada (um poliomino ) isoladamente - nada do que fazemos em uma região diferente precisa influenciar essa região.
Efetivamente, queremos encontrar uma maneira de dissecar esse poliomino em retângulos (infelizmente, a maior parte da literatura que encontro é sobre o problema oposto: dissecar retângulos em poliamino! Isso dificulta a pesquisa de leads ...)
Um método simples é combinar trechos horizontais de quadrados adjacentes em retângulos finos e longos. Em seguida, podemos comparar com a linha acima e combiná-la se nossa execução começar e terminar de acordo - ou ao finalizarmos cada execução / linha ou quando considerarmos que cada célula será adicionada à execução atual.
Ainda não sei até que ponto esse método chega ao ideal. Parece que pode ter problemas quando uma linha que ainda não considerou sugere uma divisão diferente das linhas vistas até agora:
Detectar quando uma corrida / retângulo é exatamente coberta por corridas acima e abaixo, depois dividi-las e mesclá-las resolverá esse caso em particular, mas não explorei o quão geral é o problema.
Também examinei métodos nos quais percorremos o perímetro do polyomino e atravessamos toda vez que encontramos um canto côncavo, mas essa abordagem me parece mais propensa a erros. A obtenção de resultados ideais parece exigir cortes priorizados que se juntam a dois cantos côncavos, e as formas que contêm cavidades precisam de tratamento especial; portanto, o método de varredura de linhas parece ter a vantagem da simplicidade.
Outro método que estou procurando é fazer a primeira execução encontrada na linha superior e estendê-la o mais longe possível. Em seguida, faça a primeira corrida na linha superior do que resta ... Isso ocorre em formas T invertidas, portanto, também não é o ideal.
Sinto que provavelmente existe uma maneira de usar a programação dinâmica para encontrar a divisão ideal, mas ainda não a encontrei.
fonte