Podział wielokątów na trójkąty
2008-04-27 21:39
Kolega rr- rzucił dzisiaj na kanale #warsztat ciekawy problem rysowania dowolnych wielokątów za pomocą samych trójkątów. Jak wiadomo, karty graficzne posługują się właśnie trójkątami, zatem w celu wyświetlenia wielokąta należy go odpowiednio podzielić. Matematycy dowodzą, że jest to zawsze możliwe, i podają prosty sposób dla wielokątów wypukłych: należy po prostu narysować wszystkie przekątne wychodzące z jednego wierzchołka. Nie jest trudno przełożyć ten przepis na kod.
Co jednak z dowolnymi wielokątami? Tu sprawa wydaje się bardziej skomplikowana, chociaż – jak się ukazuje – rysowanie przekątnych można na ten przypadek uogólnić. Wpadłem jednak na inny pomysł, polegający na odpowiednim “chodzeniu” po wierzchołkach naszego wielokąta i “odcinaniu” od niego kolejnych trójkątów brzegowych. Wygląda to mniej więcej tak:
- Startujemy od dowolnego wierzchołka wielokąta.
- Mając i-ty wierzchołek sprawdzamy, czy da się go połączyć z (i+2)-im (modulo liczba wierzchołków) tak, aby powstały przy tym odcinek mieścił się w wielokącie:
- jeśli tak, to z wierzchołków: i-tego, (i+1)-ego i (i+2)-ego tworzymy nowy trójkąt, wierzchołek (i+1)-szy usuwamy z wielokąta i przechodzimy do (i+2)-ego
- jeśli nie da się tak połączyć wierzchołków, przechodzimy do wierzchołka (i+1)-ego i próbujemy dalej
- Po wykonaniu pełnego cyklu kontynuujemy przechodzenie po wielokącie, usuwanie wierzchołków i tworzenie trójkątów – aż do momentu, gdy sam nasz wielokąt stanie się trójkątem. Będzie to oczywiście ostatni składający się na niego trójkąt.
Na tym rysunku można prześledzić, jak wyglądają kolejne cykle spaceru po krawędziach wielokąta – oznaczyłem je różnymi kolorami:
Z tym sposobem wiąże się oczywiście problem stwierdzenia, czy dany odcinek należy do wielokąta – co w ogólności nie musi być takie proste ani efektywne (może mieć złożoność liniową). Dodatkowo wielokąt może być “wredny” i niezbyt dobrze poddawać się operacji obcinania trójkątów. Na szczęście można udowodnić, że w każdym cyklu da się przynajmniej jeden taki trójkąt wyodrębnić. Te dwa fakty powodują, że cała operacja może mieć złożoność sięgającą nawet O(n3), chociaż pewnie da się ją zaimplementować lepiej.
Jest naturalnie bardzo możliwe, że algorytm ten jest znany od dawna, a ja po prostu nie przeczesałem Internetu dość dokładnie w poszukiwaniu już istniejącego opisu. Jednak biorąc pod uwagę to, co przed chwilą powiedziałem o jego możliwej “efektywności”, nie jest to znów takie pewne ;-) Istnieje aczkolwiek szansa, że może się on przydać komuś, kto implementuje bibliotekę graficzną 2D w oparciu o API w rodzaju DirectX czy OpenGL.
Author: Xion, posted under Programming »
-
moriturius:
April 28th, 2008 o 6:58No no, może dodam do AGE jakąś funkcję DrawPoly ;)
Ale przy takiej zlozonosci to raczej musialoby byc: CreatePoly(), a potem rysowac juz tylko to co ta funkcja zwroci, bo wywolywanie jej w kazdej petli byloby raczej nierozsadne ^^Z drugiej strony – jak wielki wielokat moze programista chciec narysowac ;)
-
Zed:
April 29th, 2008 o 10:40Ale przecież da się spokojnie zejść do O(n^2) wykonując jednocześnie wyznaczanie potencjalnych krawędzi i sprawdzanie czy są one wewnątrz wielokąta.
Ustalasz pierwszy skrajnie lewy wierzchołek i tworzysz prostą z następnym wierzchołkiem (ClockWise) i jedziesz po następnych wierzchołkach. Jeżeli są po lewej stronie prostej, to taka krawędź (od wybranego do aktualnego) nie leży w środku. Jeżeli jest na prawo to dodajesz tą krawędź do listy potencjalnych krawędzi, podmieniasz prostą (na pierwszy wybrany i aktualny wierzchołek) i jedziesz dalej.
Teraz generujesz identyczną listę ale jadąc tym razem w drugą stronę (CounterClockWise) i także wyznaczając listę. Teraz wyznaczamy część wspólną tych dwóch list (są posortowane więc O(n)). I mamy już wyznaczone wszystkie krawędzie które dało się zrobić z danego wierzchołka (największą figure wypukłą zawierającą dany wierzchołek). Tniemy wielokąt według wyznaczonych krawędzi i dla każdego nie trójkąta powtarzamy proces na nowo. Chyba nie ma buga :-)Pozdrawiam,
ZedP.S. W optymistycznym przypadku powinno działać całkiem szybko, jakies O(n log n)
-
revo:
April 29th, 2008 o 22:44Xion, z taką złożonością jesteś lata świetlne za informatyką ;)
Bernard Chazelle, 1991r – “Triangulating a Simple Polygon in Linear Time”
Po tym jak ostatnio czytałem o kompleksie widzialności, to boję się teraz otwierać prace z geometrii obliczeniowej z wyśrubowanymi czasami, takie jak ta ;)
-
Xion:
April 29th, 2008 o 23:34Zdaje się, że nieświadomie zacząłem uprawiać algorytmiczną silnikologię. Czyli: sposób wolny, skomplikowany i przekombinowany – ale za to własny! ;]
-
I:
April 30th, 2008 o 1:36Ja uprawiam “algorytmiczna silnikologię” – przynajmniej tak mi sie wydaje :> Czemu utożsamiasz to z wolnym działaniem, skomplikowaniem i przekombinowaniem?
-
Xion:
April 30th, 2008 o 11:48Temu, że istniejące i dobrze opisane rozwiązania algorytmiczne typowych problemów są zwykle szybsze, mniej skomplikowane i bardziej intuicyjne :)
-
Anonymous:
April 30th, 2008 o 19:49Zgadzam sie z tym ze najlepsze to co wlasnie, nie wazne ze jest wolne czy skomplikowane.
-
Reg:
May 4th, 2008 o 11:46Xion: Ja bym powiedział że ta silnikologia to jest raczej “napiszę swoje chociaż takie już napisali”, ale korzystając ze znanych technik i algorytmów, a nie wynajdywanie nowych.
-
Anonymous:
January 24th, 2009 o 19:19bbbbbbbbbbbbbbb
-
Triangulator:
September 22nd, 2011 o 22:33Witam,
a jak opisać za pomocą trójkątów – wielokąt z ‘otworami’ ?
-
kotnis_m:
November 15th, 2012 o 10:03Triangulator: Dobre pytanie. Własnie nad tym problemem teraz siedzę. Mam nadzieję, że znajdę na to gotowca :)
Recent posts
