Triangulacja (grafika komputerowa)

Triangulacja to technika stosowana w grafice komputerowej polegająca na rozbiciu bardziej złożonych obiektów (każdej figury geometrycznej prócz koła) na trójkąty. Szablon:Informatyka stub Dzieki triangulacji operacje graficzne sa wykonywane szybciej.

Z triangulacją, czyli podziałem wielokąta na trójkąty można się często spotkać przy rozwiązywaniu zagadnień związanych z grafiką komputerową. Operacja ta okaże się szczególnie pomocna przy realizacji takich zadań, jak wypełnianie obszarów czy zasłanianie lub oświetlanie obiektów. Ja zetknąłem się z zagadnieniem triangulacji właśnie podczas rozwiązywania problemu zasłaniania jednych obiektów przez inne w AutoCAD-zie. W programie tym można tworzyć polipowierzchnie, które ukrywają inne obiekty znajdujące się pod nimi, jednak przy ograniczeniu liczby wierzchołków do czterech. Zatem w celu uzyskania bardziej skomplikowanych wieloboków, które mają zasłaniać znajdujące się pod nimi obiekty, należy je najpierw podzielić na trójkąty, a następnie zrealizować wiele trójkątnych polipowierzchni, które w sumie odwzorują wyjściowy wielokąt. Znalezienie algorytmu podziału dowolnego wielokąta na trójkąty okazało się jednak zadaniem bardzo trudnym. W literaturze odkryłem jedynie trywialny przypadek podziału wielokąta wypukłego. W tym wypadku wystarczy połączyć dowolny wierzchołek z pozostałymi. Wykonujemy to ?kosztem liniowym rzędu n operacji? (n - liczba wierzchołków wielokąta). Dlatego zostałem zmuszony do opracowania ogólnego algorytmu, który przedstawiam w dalszej części artykułu.

Interesuje nas podział dowolnego n-kąta (również z tak zwanymi wysepkami) na minimalną, równą n - 2, liczbę trójkątów, których wierzchołkami mogą być tylko wierzchołki danego wielokąta. Algorytm ten rozwiązuje praktycznie wszystkie przypadki (wielokąty wklęsłe, z wysepkami, o wierzchołkach, których współrzędne są takie same itd.). Przykładem złożonego wielokąta może być figura przedstawiona na rysunku.

Algorytm podziału dowolnego wielokąta (o n wierzchołkach) na trójkąty jest następujący: Tworzymy tablicę wierzchołków wielokąta V[n] w ten sposób, że kolejne wierzchołki następują w tablicy po sobie, oraz ustalamy start algorytmu od pierwszego wierzchołka i=1. (1) Zaczynając od wierzchołka i, bierzemy trzy kolejne wierzchołki V[i], V[i+1], V[i+2], a następnie łączymy V[i] z V[i+2].(2) Sprawdzamy, czy odcinek V[i]V[i+2] nie przecina żadnego z n-boków wielokąta. Jeśli tak, to bierzemy następny wierzchołek, czyli i=(i+1)%n i wracamy do punktu 2. W przeciwnym wypadku sprawdzamy, czy odcinek ten leży wewnątrz wielokąta (n-kąta). Jeśli nie, to bierzemy następny wierzchołek i=(i+1)%n i wracamy do punktu 2. Jeśli odcinek leży wenątrz wielokąta, przechodzimy do punktu 4. (3) Zapamiętujemy trójkąt (V[i], V[i+1], V[i+2]), zwiększamy o jeden licznik powstałych trójkątów, zmniejszamy liczbę wierzchołków o 1 (n=n-1) i wyrzucamy z tablicy wierzchołków wielokąta V[i+1], a resztę przesuwamy o jedno miejsce w tablicy. Następnie bierzemy kolejny wierzchołek i=(i+1)%n i wracamy do punktu 2. Operację tę powtarzamy, dopóki liczba wierzchołków wielokąta jest większa od trzech, czyli dopóki n > 3. (4)