Como encontrar uma quantidade mínima de subdivisões

Question

Imagine que você tem uma tela e nesta tela já existem alguns objetos. Como você pode encontrar a maneira mínima de cobrir a área "descoberta" com quadrados, não se sobrepõe, preenchendo completamente a tela.

No meu caso, a "tela" é um contêiner HTML-DIV e os objetos são aninhados Div-containers. Poderia ficar assim: http://www.encodechain.com/demo/200908_Optimize.pngÀ esquerda, há o "começo" e à direita está no possível primeiro "passo" ...

Sei que há um algoritmo para isso, mas atualmente não me lembro do nome.

Answer 1

O melhor que pude encontrar foi este artigo: Apontando um retângulo com o menor número de quadrados. O artigo é uma leitura interessante, embora, às vezes, investiga profundamente o território teoria com a conversa de "Constantes Universais". Não tenho certeza de que a questão de "um retângulo de tamanho m por n pode ser amarrado com k quadrados" é NP-complete. Conforme observado em outra resposta, sua pergunta se assemelha aos problemas de embalagem que são NP-completos. E, é claro, seu problema é uma generalização do abordado neste artigo, pois você está lidando com áreas não retangulares. Você pode começar dividindo sua área no número mínimo de retângulos, outro problema interessante em si. E, finalmente, mesmo que você pudesse fazer isso com eficiência, não tenho certeza se os retângulos de melhor maneira de amarrar o melhor resultariam em um ladrilho ideal geral.

Como observa o autor, um algoritmo ganancioso é um bom lugar para começar: basta colocar o maior quadrado que você pode até que a área esteja cheia.

Answer 2

Problema de embalagem

Problema da mochila

E um artigo Ao resolver o problema de embalagem 2D