TRIANGULACJA


od trójkąta do geometrii obliczeniowej

Podział wielokąta

Triangulacja dowolnego wielokąta to jego rozkład na trójkąty przez maksymalny zbiór nieprzecinających się przekątnych. Zbiór nieprzecinających się przekątnych musi być maksymalny po to, by zagwarantować, że żaden trójkąt nie ma wierzchołka we wnętrzu którejś ze swoich krawędzi. Triangulacje są zwykle niejednoznaczne, co zostało zilustrowane poniżej.

Sposoby podziału pięciokąta

Wykorzystując liczby Cantala możemy sprawdzić ile jest sposobów podziału wielokąta wypukłego o n wierzchołkach, za pomocą wzoru:

Cn=1n+12nn=2n!n+1 !n!

KALKULATOR

Podaj liczbę wierzchołków wiekokata

Ten wielokąt można podzielić na
0 sposobów

Możemy striangulować każdy wielokąt, zarówno wklęsły jak i wypukły, a każda triangulacja prostego wielokąta o n wierzchołkach składa się dokładnie z n-2 trójkątów. Triangulację możemy również wykonać na wielokątach z dziurami. Z tym, że prosty wielokąt o n wierzchołkach można striangulować w czasie On log n z pomocą algorytmu używającego On pamięci, a dla triangulacji podziału z dziurami istnieje ograniczenie dolne Ωn log n

Metoda ucha

Bardzo prosty, intuicyjny podział wielokąta na trójkąty. Ucha występujące w nazwie tego algorytmu są to trójkąty, których dwa boki są również bokami danego wielokąta, a ich trzeci bok zawiera się wewnątrz wielokąta. Każdy wielokąt nie będący trójkątem ma przynajmniej dwa „ucha”. Algorytm działa w sposób następujący:

Algorytm znajduje „ucho”, czyli trójkąt i „obcina” je, w rezultacie czego otrzymujemy mniejszy wielokąt mający o jeden wierzchołek mniej. Następnie powtarzamy procedurę dla tego nowego wielokąta, w wyniku czego dostajemy kolejny wielokąt itd. Schemat ten kontynuujemy aż do momentu, gdy zostanie nam już tylko trójkąt.

Wykonaj proste ćwiczenie:

  1. Wylosuj figurę.
  2. Pojedyncze kliknięcie myszą w oknie aplikacji spowoduje zaznaczenie białego punktu. Jest to początek rysowanej przez ciebie przekątnej.
  3. Kliknięcie w innym miejscu spowoduje zaznaczenie punktu końcowego i wyrysowanie całej przekątnej.
  4. Jeśli stwierdzisz, że chcesz wykonać inny rysunek, możesz wyczyścić otrzymane dotychczas rezultaty naciskając przycisk „Wyczyść”.

Metoda punktów

Jest znacznie bardziej skomplikowana niż metoda ucha. Szczegółowo została opisana w zakładce Triangulacja Delone. Intuicyjnie działa następująco:

  1. Wybieram punkt wewnątrz wielokąta i łączę go z każdym z jego wierzchołków.
  2. Powstaje podział wielokąta na trójkąty, który mogę kontynuować.
  3. We wnętrzu każdego z powstałych trójkątów wybieram ponownie punkt i łączę go z jego wierzchołkami itd.

Tą metodą, podobnie jak metodą ucha, triangulację zbioru zawierającego n punktów na płaszczyźnie można obliczyć w oczekiwanym czasie On z pomocą algorytmu używającego On pamięci, z tym że oczekiwana liczba trójkątów tworzonych przez algorytm wynosi 9n+1.

Zobacz, jak wygląda triangulacja wielokątów.

  1. Korzystając z animacji obok wybierz jeden z wielokątów: trójkąt, czworokąt, pięciokąt lub sześciokąt.
  2. Następnie wylosuj wybrany przez siebie wielokąt.
  3. Wybierz liczbę punktów pośrednich, które zostaną zaznaczone we wnętrzu wielokąta.
  4. Naciśnij przycisk „Podziel figurę”. Resztę program wykona za ciebie.
Podaj ilość punktów ( max: 4)

Podział wielościanu

Trójwymiarowy odpowiednik triangulacji wielokąta jest następujący:

Rozłóż dany wielościan na nienachodzące na siebie czworościany, gdzie wierzchołki czworościanu muszą być wierzchołkami początkowego wielościanu.

Taki rozkład nazywamy tetrahedralizacją wielościanu. Nie zawsze jednak jest możliwy rozkład wielościanu na czworościany bez użycia dodatkowych wierzchołków. B. Chazele, pokazał, że dla prostych wielościanów o n wierzchołkach, może być potrzebnych Θn2 dodatkowych wierzchołków, które zawsze wystarczają do otrzymania rozkładu na czworościany. Oszacowanie to zostało udoskonalone przez Chazelle’a i Paliosa do Θn+r2, gdzie r jest liczbą wklęsłych krawędzi w wielościanie. Algorytm obliczający rozkład działa w czasie Onr+r2 log r.

W okienku obok możesz zobaczyć przykładowe tetrachedralizacje sześcianu, prostopadłościanu, ostrosłupa czworokątnego i czworościanu. Wybierz najpierw wielościan z listy, a następnie obróć go w celu dokładnego prześledzenia podziału.