Jak spakować wielokąty wewnątrz innego wielokąta?

Zamówiłem kilka skórzanych prześcieradeł, z których chciałbym budować kuglarskie piłki, łącząc ze sobą krawędzie. Używam brył platońskich do kształtowania kulek.

Mogę zeskanować skórzane prześcieradła i wygenerować wielokąt zbliżony do kształtu skórzanego prześcieradła (jak wiecie, jest to skóra zwierzęca i nie ma prostokątów).

Chciałbym teraz zmaksymalizować rozmiar mojej żonglującej piłki.

W moim przykładzie wielokąty są regularne, ale szukam rozwiązania z prostymi wielokątami.

Jaki jest największy współczynnik skali, jaki mogę zastosować do moich wielokątów, aby wszystkie pasowały do arkusza?

Staram się zminimalizować marnotrawstwo, używając jak największej ilości materiału.

Oczywiście, przecięcie siatki wielościanu na indywidualny wielokąt zwiększy przestrzeń możliwej kombinacji, ale także obniży jakość ostatecznej geometrii, ponieważ wiąże się to z większą ilością szycia i nagromadzeniem błędów. Ale to pytanie nie dotyczy wyliczenia różnych sposobów rozkładania wielościanu. Można je rozpatrywać niezależnie. Wieloboki są więc prostymi wielobokami.

Formalnie:

Wkład:

: prosty wielokąt (cel) $P$
: zbiór wielokątów, które chcę umieścić $S$
: wykres prostych wielokątów - każdy węzeł reprezentuje prosty wielokąt w , a między każdą parą wielokątów, które mają wspólną krawędź, jest jedna krawędź krawędzi $G$ $n$ $S$
(zużycie materiału i łączności) $\alpha >= 0, \beta >= 0$

Wynik:

współczynnik skali $f$
, podgrupa $H$ $G$
: położenie i kąt dla każdego wielokąta w $Loc$ $V(G)$
miara jakości rozwiązania: $m$ $m = \alpha.f + \beta. {|E(H)|\over|E(G)|}$

Maksymalizuj zgodnie z następującymi warunkami: $m$

(1) $| V(H) | = |V(G)|$
(2) $| E(H) | <= |E(G)|$
dla każdego wieloboku w , skalowany przez współczynnik w miejscu $S_i$ $S$ $S_i$ $f$ znajduje się wewnątrz (3) $Loc(S_i)$ $P$
wielokąty w nie nakładają się (4) $V(H)$

(V (G) są wierzchołkami na wykresie, a S jest zbiorem wielokątów, ale opisują ten sam zestaw obiektów. Być może istnieje bardziej zwarty sposób.)

Objaśnienie warunków:

(1) Chcę, aby wszystkie wielokąty były w ostatecznym układzie
(2) Niektóre połączenia mogą zostać przerwane w razie potrzeby
(3) (4) piłka wykonana jest ze skóry

Oto docelowy wielokąt Prześcieradło skórzane

Oto zestaw wielokątów, które chcę spakować: Siatka wielościanowa

optimization computational-geometry packing

— alecail
źródło

Czy mówisz o wypukłych wielokątach, które chcesz wyciąć?

— A.Schulz

W moim przypadku wielokąty są regularne, ponieważ są powierzchniami brył platońskich. Ale pakowanie prostych wielokątów również powinno działać. Dlaczego chcesz wiedzieć, czy wielokąty, które chcę spakować, są wypukłe?

— alecail

Jeśli wielokąty są niewypukłe, zawsze możesz umieścić pojedynczy niewypukły wielokąt w oryginalnym wielokącie bez cięcia. To pytanie nie miałoby więc sensu dla ogólnych wielokątów.

— A.Schulz

Nie wiem, czy to ważne, czy nie, ale czy obwiednia wielokąta (skóry) jest wypukła, czy też może być wklęsła?

— Paresh,

Nawet o wiele prostszy problem upakowania maksymalnej liczby kwadratów w kwadracie okazuje się trudny (przepraszam, nie mam przydatnego linku, ale natknąłem się na dyskusję o tym kilka miesięcy temu). Po prostu żongluj wielokątami ręcznie, prawdopodobnie nie będziesz zbyt daleko od optymalnego.

— vonbrand

Należy to do klasy optymalizacji problemów zwanej Problemy z pakowaniem . W twoim przypadku zamiast zwykłego wielokąta jako pojemnika masz nieregularny, ale pomysł pozostaje ten sam.
Te problemy z optymalizacją są zwykle trudne dla NP, więc nie sądzę, że istnieje prosty sposób na uzyskanie dokładnego rozwiązania, a wypróbowanie wszystkich kombinacji byłoby zbyt kosztowne.
Są ludzie zainteresowani tego rodzaju problemami; Znalazłem ten link niektórych rozwiązanych problemów z pakowaniem: http://www2.stetson.edu/~efriedma/packing.html

Najłatwiejszy sposób, jaki widzę, to zdefiniowanie przybliżonego środka skórzanego prześcieradła, przeniesienie zestawu wielokątów tam i poprzez skalowanie w górę i w dół i sprawdzenie, czy zestaw wielokątów znajduje się wewnątrz wielokąta docelowego, aby uzyskać coraz bliżej współczynnik skali „f” dla pożądanego zestawu wielokątów.

Ale chyba, że zamierzasz użyć tego czynnika do produkcji piłek żonglerkowych na dużą skalę, prawdopodobnie zrobienie tego ręcznie byłoby wystarczające.

— Akronix
źródło