Podręcznik Grafika komputerowa i wizualizacja

Rys.3.12. Podział na trójkąty:  a) wielokąta wypukłego b) wielokąta typu gwiazda.
Wielokąt typu gwiazda jest wielokątem, dla którego można pokazać taki punkt wewnątrz,
którego połączenie odcinkiem z dowolnym wierzchołkiem jest całkowicie zawarte w wielokącie.

Innym przypadkiem wielokąta dla którego można wskazać dość prosty i efektywny algorytm podziału na trójkąty jest wielokąt monotoniczny.

Rys.3.13. Dla wielokąta monotonicznego można wskazać taką prostą,
że rzutowanie wierzchołków na tę prostą zachowuje ich kolejność (w dwóch łańcuchach).

Innym przypadkiem wielokąta dla którego można wskazać dość prosty i efektywny algorytm podziału na trójkąty jest wielokąt monotoniczny.

Niech dany będzie wielokąt zwykły o n węzłach P₁...P_n,P_n+1 = P₁ . Wielokąt nazywamy monotonicznym, jeżeli istnieje prosta l taka, że rzuty prostokątne wierzchołków P_i na l są uporządkowane w dwóch grupach w takiej samej kolejności jak punkty P_i (rys.3.13).

Rys.3.14. Podział na trójkąty wielokąta monotonicznego zgodnie z zaproponowanym algorytmem.
Czytelnik może prześledzić kolejne kroki łączenia wierzchołków.

ALGORYTM PODZIAŁU WIELOKĄTA MONOTONICZNEGO

Przedstawiony algorytm triangulacji wielokąta monotonicznego jest algorytmem przeglądania wierzchołków zgodnie z ich kolejnością wynikającą z monotoniczności. Jednocześnie branie pod uwagę kolejnego wierzchołka jest związane z połączeniem go z innym wierzchołkiem tak, aby „odciąć” trójkąt. Ze względu na wzajemne położenie wierzchołków możliwe są trzy różne (i wykluczające się !) konfiguracje. Kroki 4., 5. i 6. algorytmu opisują postępowanie w odpowiednich przypadkach. Czytelnik może przeanalizować geometrię rozpatrywanych konfiguracji wierzchołków. W książce M.Jankowskiego [6] można znaleźć szczegóły przedstawionego algorytmu.

Warto zwrócić uwagę na problem złożoności obliczeniowej triangulacji wielokąta monotonicznego. Monotoniczność zapewnia odpowiednie posortowanie wierzchołków. A zatem krok 1. algorytmu nie wymaga sortowania. W związku z tym asymptotyczna złożoność obliczeniowa całego algorytmu wynosi O(n).

Przedstawiony algorytm triangulacji nie zapewnia możliwości podziału na trójkąty dowolnego wielokąta. Istnieje jednak twierdzenie, które mówi, że dowolny wielokąt można rozciąć na sumę wielokątów monotonicznych.

Rozpatrzmy wielokąt wklęsły, który nie jest monotoniczny. Jeśli przetniemy go prostymi równoległymi przechodzącymi przez wszystkie wierzchołki (rys.3.15), to można przeprowadzić analizę, które wierzchołki „psują” monotoniczność. Rozpatrzmy pasy (warstwy) pomiędzy sąsiednimi prostymi tnącymi. Jeśli prosta brzegowa pasa przechodzi przez wierzchołek wielokąta, to mogą zaistnieć dwa przypadki. Albo krawędź wielokąta wychodząca z tego wierzchołka przecina pas (P1 na rys.3.15), albo nie (P2 na rys.3.15). W tym drugim przypadku mamy do czynienia z ekstremum lokalnym, które „psuje” monotoniczność. W takiej sytuacji należy połączyć ten wierzchołek z dowolnym wierzchołkiem po drugiej stronie pasa. Połączenia mogą być dowolne i wielokrotne, ale istotne jest aby każdy wierzchołek „psujący” monotoniczność w danym pasie był przynajmniej raz połączony z wierzchołkiem z przeciwległego brzegu (prostej) pasa. Każde, tak wykreowane połączenie rozcina wielokąt.

ALGORYTM PODZIAŁU NA WIELOKĄTY MONOTONICZNE

Rys.3.15. Rozcięcie wielokąta na wielokąty monotoniczne. Po połączeniu punktów „psujących”
z wierzchołkami po drugiej stronie pasa (zielone odcinki) powstają trzy wielokąty monotoniczne.

Posortowanie wierzchołków w 1. kroku algorytmu ułatwia późniejsze wyszukiwanie odpowiednich wierzchołków i jednocześnie powoduje, że rozcięte w wyniku działania algorytmu wielokąty monotoniczne mają również posortowane wierzchołki. Oczywiście asymptotyczna złożoność obliczeniowa algorytmu podziału na wielokąty monotoniczne wynosi O(nlogn) .

Biorąc pod uwagę przedstawione algorytmy podziału, można zaproponować rozwiązanie dwuetapowe zadania triangulacji wielokąta dowolnego:

ALGORYTM TRIANGULACJI WIELOKĄTA