Posts tagged ‘triangles’

Podział wielokątów na trójkąty

2008-04-27 21:39

Podział wypukłego wielokąta na trójkątyKolega 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:

  1. Startujemy od dowolnego wierzchołka wielokąta.
  2. 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
  3. 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:

Podział dowolnego wielokąta na trójkąty

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.

 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.