Wydajny algorytm pakowania dla nieregularnych wielokątów

Question

Szukam algorytmu upakowania, który zredukuje nieregularny wielokąt w prostokąty i trójkąty prostokątne. Algorytm powinien starać się wykorzystać jak najmniej takich kształtów i powinien być stosunkowo łatwy do wdrożenia (biorąc pod uwagę trudność wyzwania). W miarę możliwości powinien również preferować prostokąty nad trójkątami.

Jeśli to możliwe, odpowiedź na to pytanie powinna wyjaśniać ogólną heurystykę używaną w sugerowanym algorytmie.

Powinno to działać w czasie deterministycznym dla nieregularnych wielokątów z mniej niż 100 wierzchołkami.

Celem jest stworzenie "rozsądnego" rozkładu nieregularnego wielokąta dla laika.

Pierwsza heurystyka zastosowana do rozwiązania określi, czy wielokąt jest regularny czy nieregularny. W przypadku regularnego wielokąta, będziemy używać podejścia przedstawionego w moim podobnym stanowisku o regularnych polys: Efficient Packing Algorithm for Regular Polygons

alt text http://img401.imageshack.us/img401/6551/samplebj.jpg

Answer 1

ja nie wiem, czy będzie to dają optymalną odpowiedź, ale to by przynajmniej daj odpowiedź:

1. Wyznacz triangulację Delaunaya dla danego wielokąta. Są to standardowe algorytmy, które będą działać bardzo szybko dla 100 wierzchołków lub mniej (patrz na przykład this library here.). Korzystanie z triangulacji Delaunay powinno zapewnić, że nie masz zbyt wielu długich, cienkich trójkątów.
2. Podziel trójkąty niewspółprawne na dwa trójkąty po prawej stronie, upuszczając wysokość od największego kąta na przeciwną.
3. Wyszukaj trójkąty, które można łączyć w prostokąty: dwa przystające trójkąty prostokątne (nie lustrzane), które mają wspólną przeciwprostokątną. Podejrzewam, że nie będzie ich zbyt wiele w ogólnym przypadku, chyba że twój nieregularny wielokąt miał dużo prostopadłych do rozpoczęcia.

Zdaję sobie sprawę, że jest dużo szczegółów do wypełnienia, ale myślę, że rozpoczęcie od triangulacji Delaunaya jest prawdopodobnie drogą do zrobienia. Triangulacje Delaunaya w płaszczyźnie można obliczyć efektywnie i generalnie wyglądają całkiem "naturalnie".

EDYCJA DO ADD: skoro jesteśmy w ad-hoc heuristicville, oprócz chciwych algorytmów omawianych w innych odpowiedziach powinieneś rozważyć także strategię podziału i podboju. Jeśli kształt nie jest wypukły, jak na przykład, podziel go na kształty wypukłe, wielokrotnie wycinając od wierzchołka odruchu do innego wierzchołka w taki sposób, aby zbliżyć się maksymalnie do kąta odbicia. Po podzieleniu kształtu na wypukłe kawałki, rozważę następnie podzielenie wypukłych kawałków na kawałki z ładnymi "podstawami", części z co najmniej jedną stroną mającą dwa ostre lub proste kąty na końcach. Jeśli jakikolwiek element nie ma takiej "podstawy", powinieneś być w stanie podzielić go na dwie części na średnicy kawałka i otrzymać dwie nowe części, z których każda ma "podstawę" (chyba). Powinno to zredukować problem związany z wypukłymi wielokątami, które są trapezoidalne, a stamtąd chciwy algorytm powinien dobrze się spisywać. Myślę, że ten algorytm podzieli pierwotny kształt w dość naturalny sposób, dopóki nie dotrzesz do kawałków trapezowych kinda-sorta.

Answer 2

Żałuję, że nie miałem czasu na zabawę, ponieważ brzmi to jak zabawny problem!

Moja pierwsza myśl (patrząc na powyższy diagram) polega na szukaniu 2 sąsiednich kątów prostych obracających się w tym samym kierunku.Jestem pewien, że nie złapie każdego przypadku, w którym prostokąt pomoże, ale z punktu widzenia użytkownika jest to oczywisty przypadek (kwadratowe rogi na zewnątrz = to powinien być prostokąt).

Po znalezieniu sąsiedniej pary kątów prostych, weź długość krótszej nogi, a tam jest jeden prostokąt. Odejmij to od wielokąta w lewo, aby ułożyć i powtórz. Kiedy nie ma już oczywistych zewnętrznych prostokątów do usunięcia, to rób to, co zwykle robisz w kafelkach (odpowiedź Petera brzmi świetnie).

Disclaimer: Nie jestem ekspertem w tej sprawie, a ja nawet nie próbował go ...