Как упаковать полигоны внутри другого полигона?

Я заказал несколько кожаных листов, из которых я хотел бы собрать шары для жонглирования, сшивая края вместе. Я использую платоновские тела для формы шаров.

Я могу отсканировать кожаные листы и создать многоугольник, который приблизительно соответствует форме кожаного листа (как вы знаете, это кожа животного происхождения, а не прямоугольники).

Так что теперь я хотел бы увеличить размер моего мяча для жонглирования.

В моем примере полигоны являются правильными, но я ищу решение с простыми полигонами.

Какой самый большой масштабный коэффициент я могу применить к своим полигонам, чтобы они все умещались внутри листа?

Я стараюсь свести к минимуму отходы, используя как можно больше материала.

Очевидно, что разрезание сетки многогранника на отдельный многоугольник увеличит пространство возможной комбинации, но также уменьшит качество окончательной геометрии, потому что здесь больше шитья и накапливаются ошибки. Но этот вопрос не о перечислении различных способов разворачивания многогранника. Их можно рассматривать независимо. Таким образом, полигоны являются простыми полигонами.

Формально:

Входные данные:

• $P$ : простой многоугольник (цель)
• $S$ : набор полигонов, которые я хочу разместить
• $G$ : график из простых многоугольников - каждый узел представляет простой многоугольник в , и между каждой парой многоугольников, которые имеют общее ребро, есть одно ребро ребра $n$$S$
• $\alpha >= 0, \beta >= 0$ (использование материалов и связности)

Выход:

• масштабный коэффициент$f$
• $H$ , подграф$G$
• $Loc$ : местоположение и угол для каждого многоугольника в$V(G)$
• мера качества решения:$m$$m = \alpha.f + \beta. {|E(H)|\over|E(G)|}$

Максимизировать учетом этих условий:$m$

• $| V(H) | = |V(G)|$ (1)
• $| E(H) | <= |E(G)|$ (2)
• для каждого многоугольника в , масштабированное по коэффициенту в местоположении находится внутри (3)$S_i$$S$$S_i$$f$$Loc(S_i)$$P$
• многоугольники в не перекрываются (4)$V(H)$

(V (G) - вершины графа, а S - множество многоугольников, но они описывают один и тот же набор объектов. Может быть, есть более компактный способ сделать это.)

Объяснение условий:

• (1) Я хочу, чтобы все полигоны были в окончательном макете
• (2) Некоторые соединения могут быть разорваны при необходимости
• (3) (4) мяч сделан из кожи

Вот целевой полигон

Вот набор полигонов, которые я хочу упаковать:

Это относится к классу задач оптимизации, называемых задачами упаковки . В вашем случае, вместо обычного многоугольника в качестве контейнера, у вас есть неправильный многоугольник, но идея остается той же.
Эти проблемы оптимизации, как правило, сложны для NP, поэтому я не думаю, что есть простой способ получить точное решение, и пробовать все комбинации было бы слишком дорого.
Есть некоторые люди, заинтересованные в подобных проблемах; Я нашел эту ссылку некоторых решенных проблем с упаковкой: http://www2.stetson.edu/~efriedma/packing.html

Самый простой способ, который я вижу, - определить приблизительный центр кожаного листа, переместить туда набор полигонов и, увеличив и уменьшив масштаб и проверив, находится ли набор полигонов внутри целевого многоугольника, чтобы получить все ближе и ближе масштабный коэффициент «F» для желаемого набора полигонов.

Но, если вы не собираетесь использовать этот фактор для крупномасштабного производства мячей для жонглирования, вероятно, достаточно было бы сделать это вручную.