Triangulacja wielokątów — Polygon triangulation
W geometrii obliczeniowej , wielokąt triangulacji jest dekompozycja z wielobocznym obszaru ( wielokąt prosty ) P na zbiór trójkątów , czyli znalezienie zbiór trójkątów z parami nie przecinających wnętrzach, których Unia jest P .
Triangulacje można traktować jako szczególne przypadki płaskich grafów prostoliniowych . Gdy nie ma otworów ani dodanych punktów, triangulacje tworzą maksymalne grafy zewnętrzne .
Triangulacja wielokątów bez dodatkowych wierzchołków
Z biegiem czasu zaproponowano szereg algorytmów do triangulacji wielokąta.
Przypadki specjalne
.svg)
Triangulacja dowolnego wielokąta wypukłego w czasie liniowym w triangulację wachlarzową przez dodanie przekątnych jednego wierzchołka do wszystkich innych wierzchołków jest banalna .
Całkowita liczba sposobów triangulacji wypukłego n- kąta przez nie przecinające się przekątne to ( n −2) liczba katalońska , która równa się
- ,
formuła znaleziona przez Leonharda Eulera .
Monotoniczne wielokąta może być trójkątnej w czasie liniowo z każdym algorytmie A. Fournier i dy Montuno lub algorytmu Godfried Toussaint .
Metoda obcinania uszu
Jeden ze sposobów triangulacji prostego wielokąta opiera się na twierdzeniu o dwóch uszach , ponieważ każdy prosty wielokąt z co najmniej 4 wierzchołkami bez otworów ma co najmniej dwa „ uszy ”, które są trójkątami o dwóch bokach będących krawędziami wielokąta i trzeci całkowicie w środku. Algorytm polega następnie na znalezieniu takiego ucha, usunięciu go z wielokąta (co skutkuje powstaniem nowego wielokąta, który nadal spełnia warunki) i powtarzaniu, aż zostanie tylko jeden trójkąt.
Ten algorytm jest łatwy do zaimplementowania, ale wolniejszy niż niektóre inne algorytmy i działa tylko na wielokątach bez dziur. Implementacja, która przechowuje oddzielne listy wierzchołków wypukłych i wklęsłych, będzie działać w czasie O( n 2 ) . Ta metoda jest znana jako obcinanie uszu, a czasem przycinanie uszu . Wydajny algorytm odcinania uszu odkryli Hossam ElGindy, Hazel Everett i Godfried Toussaint .
Triangulacja wielokątów monotonicznych
Prosty wielokąt jest monotoniczny w stosunku do linii L , jeśli jakakolwiek linia prostopadła do L przecina wielokąt co najwyżej dwa razy. Wielokąt monotoniczny można podzielić na dwa łańcuchy monotoniczne . Wielokąt, który jest monotoniczny względem osi y, nazywa się y-monotone . Wielokąt monotoniczny z n wierzchołkami może być triangulowany w czasie O( n ) . Zakładając, że dany wielokąt jest y-monotone, zachłanny algorytm zaczyna chodzić po jednym łańcuchu wielokąta od góry do dołu, dodając przekątne, gdy tylko jest to możliwe. Łatwo zauważyć, że algorytm można zastosować do dowolnego wielokąta monotonicznego.
Triangulacja wielokąta niemonotonicznego
Jeśli wielokąt nie jest monotoniczny, może zostać podzielony na monotonne subwielokąty w czasie O ( n log n ) przy użyciu podejścia typu sweep-line . Algorytm nie wymaga, aby wielokąt był prosty, dlatego można go zastosować do wielokątów z otworami. Ogólnie rzecz biorąc, ten algorytm może triangulować podpodział planarny z n wierzchołkami w czasie O( n log n ) przy użyciu przestrzeni O( n ) .
Podwójny wykres triangulacji
Użytecznym grafem, często kojarzonym z triangulacją wielokąta P, jest graf dualny . Biorąc triangulacji T P o P , definiuje się wykres G ( T P ) , jak na wykresie, którego wierzchołek jest zbiór trójkątów T P , dwa wierzchołki (trójkąty) przylega wtedy i tylko wtedy, gdy mają one przekątnej. Łatwo zauważyć, że G ( T P ) jest drzewem o maksymalnym stopniu 3.
Złożoność obliczeniowa
Do 1988 roku, czy prosty wielokąt może być triangulowany szybciej niż czas O( n log n ) był otwartym problemem w geometrii obliczeniowej. Następnie Tarjan i Van Wyk (1988) odkryli algorytm triangulacji w czasie O( n log log n ) , później uproszczony przez Kirkpatricka, Klawe i Tarjan (1992) . Następnie zastosowano kilka ulepszonych metod o złożoności O( n log * n ) (w praktyce nie do odróżnienia od czasu liniowego ).
Bernard Chazelle wykazał w 1991 roku, że każdy prosty wielokąt może być triangulowany w czasie liniowym, chociaż proponowany algorytm jest bardzo złożony. Znany jest również prostszy algorytm randomizowany z liniowym oczekiwanym czasem.
Algorytm dekompozycji Seidela i metoda triangulacji Chazelle'a zostały szczegółowo omówione w Li i Klette (2011) .
Złożoność czas triangulacji wystąpienia n -Vertex wielokąta z otworami ma Ohm ( n log n ) dolna granica , w algebraicznych drzew obliczeń modeli obliczeniowych. Możliwe jest obliczenie liczby różnych triangulacji prostego wielokąta w czasie wielomianowym za pomocą programowania dynamicznego i (na podstawie tego algorytmu zliczania) wygenerowanie jednorodnie losowych triangulacji w czasie wielomianowym. Jednak liczenie triangulacji wielokąta z otworami jest #P-zupełne , co sprawia, że jest mało prawdopodobne, aby można było to zrobić w czasie wielomianowym.
Powiązane obiekty i problemy
- Oba problemy triangulacji są szczególnym przypadkiem triangulacji (geometrii) i szczególnym przypadkiem podziału wielokąta .
- Triangulacja o minimalnej wadze to triangulacja, której celem jest zminimalizowanie całkowitej długości krawędzi.
- Wskaż zestaw triangulacji jest triangulacji wielokąta kadłuba wypukłej zbioru punktów. Delaunay triangulacji jest kolejnym sposobem, aby stworzyć w oparciu o triangulacji zbioru punktów.
- Associahedron jest Polytope którego wierzchołki odpowiadają triangulacyjnych wielokąta wypukłego.
- Pokrycie trójkąta wielokąta , w którym trójkąty mogą się pokrywać.
- Tiling by polygons , gdzie celem jest pokrycie całej płaszczyzny wielokątami o określonych kształtach.
Zobacz też
Bibliografia
Zewnętrzne linki
- Demo jako Flash swf , algorytm Sweep Line.
- Wyjaśnienie Song Ho dotyczące tesselatora OpenGL GLU