Алгоритм для подгонки 2D полигонов в области?

Question

Есть ли для этого стандарт? Имя алгоритма?

Скажи: У меня 10 полигонов разных размеров. У меня есть область определенного размера.

Я хочу знать, как заполнить большинство полигонов в этой области и как они размещаются.

Примечание: Полигоны могут вращаться в зависимости от установленного ограничения.

Answer 1

Одно из возможных имен - Проблема с упаковкой . Это связано с проблемой Рюкзак . Эти проблемы имеют тенденцию быть NP-сложными, и многие требуют эвристики. Если вы можете ограничить разрешенные формы полигонов и области, может существовать более эффективный алгоритм для вашего особого случая.

Answer 2

Вы можете взглянуть на «Танцующие ссылки» в Википедии, чтобы найти решение Дональда Кнута о точном покрытии - включая плитку - ваш вопрос можно рассматривать как проблему листов * *

Answer 3

ЕСЛИ (это большое, если) все ваши многоугольники были прямоугольниками, и область, в которую они должны поместиться, также является прямоугольником, то это будет называться упаковкой в ​​мусорное ведро, Google завалит вас информацией об этом. Если это не так, то я думаю, что вы ищете вариант бин-упаковки, и еще немного, что вы столкнулись с проблемой NP, для которой «попробуй и протестируй» - лучший алгоритм из всех.