Algoritmo para a montagem polígonos 2D em uma área?

Question

Existe um padrão para isso? algoritmo nome?

Say: Eu tenho 10 polígonos de diferentes tamanhos. Eu tenho uma área de tamanho específico.

Eu quero saber como preencher o maior número de polígonos nessa área, e como eles são montados.

Nota: Polígonos podem ser rodado dependendo do conjunto de restrição.

Answer 1

Um nome possível é uma embalagem Problema . Ela está relacionada com a Problema da Mochila . Estes problemas tendem a ser NP-duro, e muitos exigem heurísticas. Se você pode restringir as formas permitidas de polígonos e da área, pode existir um algoritmo mais eficiente para o seu caso particular.

Answer 2

Você pode dar uma olhada em "Links de dança" na Wikipedia para solução de Donald Knuth para o problema de cobertura exata - que inclui ladrilhos - a sua pergunta pode ser encarado como um problema azulejos

Answer 3

IF (que é um grande se) todos os seus polígonos eram retângulos, e a área em que os mesmos devem ajuste também é um retângulo, então este seria chamado bin-packing, o Google vai oprimi-lo com informações sobre isso. Se eles não são, então eu acho que você está procurando uma variante do bin-packing, e eu acho que um pouco mais de que você está em um problema NP para o qual 'experimentar e testar' é sobre o melhor algoritmo de volta.