Przestrzenna triangulacja Delaunaya
Zagadnienie budowy sieci niezachodzących na siebie trójkątów jest jednym z podstawowych w geometrii obliczeniowej i jest szeroko stosowane w grafice komputerowej i systemach informacji geograficznej do modelowania powierzchni i rozwiązywania problemów przestrzennych.
Problem budowy sieci niezachodzących na siebie trójkątów po raz pierwszy postawiono w 1934 roku w pracy radzieckiego matematyka B. N. Delone, który sformułował odpowiednie warunki.
W matematyce zadaniem zbudowania triangulacji z danych punktów jest zadanie połączenia ich parami za pomocą nie przecinających się odcinków, tak aby powstała sieć trójkątów. Jego głównymi elementami są (ryc. 5.3): węzły (wierzchołki trójkątów), krawędzie (boki) i ściany (same trójkąty). Skonstruowana triangulacja może być wypukła (jeśli jest to minimalny wielokąt obejmujący obszar modelowania), niewypukła (jeśli triangulacja nie jest wypukła) i optymalna (jeśli suma długości wszystkich krawędzi jest minimalna).
Sieć takich trójkątów nazywa się triangulacją Delaunaya, jeśli spełnia pewne warunki:
Żaden z pierwotnych punktów nie mieści się w okręgu opisanym na dowolnym trójkącie (ryc. 5.3);
Triangulacja jest wypukła i spełnia sformułowany powyżej warunek Delaunaya;
Suma minimalnych kątów wszystkich trójkątów jest maksimum wszystkich możliwych triangulacji;
Suma promieni okręgów opisanych wokół trójkątów jest minimalna spośród wszystkich możliwych triangulacji.
Pierwsze z powyższych kryteriów konstruowania triangulacji Delaunaya, zwane kołowym, jest jednym z głównych i jest sprawdzane pod kątem dowolnej pary trójkątów o wspólnych ścianach. Matematyczna interpretacja kryterium wynika z rys. 5.3:
(5.2)
Istnieje wiele sposobów konstruowania triangulacji Delaunaya, która jest jedną z najpopularniejszych ostatnio metody konstruowania siatki triangulacyjnej. Jest stosowany w wielu systemach GIS do budowy modeli reliefowych.
W odniesieniu do przestrzeni dwuwymiarowej formułuje się ją w następujący sposób: układ połączonych ze sobą, nie nakładających się na siebie trójkątów ma najmniejszy obwód, jeśli żaden z wierzchołków nie mieści się w żadnym z okręgów opisanych wokół utworzonych trójkątów (ryc. 5.4).
Ryż. 5.4. Triangulacja Delaunaya
Oznacza to, że powstałe trójkąty przy takiej triangulacji są jak najbliżej trójkątów równobocznych, a każdy z boków powstałych trójkątów z przeciwnego wierzchołka jest widoczny pod maksymalnym kątem ze wszystkich możliwych punktów odpowiedniej półpłaszczyzny. Jest to dokładnie optymalna triangulacja wzdłuż krawędzi, której zwykle wykonuje się interpolację liniową w celu skonstruowania izolinii.
Wiele algorytmów konstruowania triangulacji Delaunaya wykorzystuje następujące twierdzenie.
Twierdzenie 1. Triangulację Delaunaya można uzyskać z dowolnej innej triangulacji wykorzystującej ten sam układ punktów, przestawiając sekwencyjnie pary sąsiednich trójkątów ABC i BCD, które nie spełniają warunku Delaunaya, w pary trójkątów ABD i ACD (ryc. 5.5).
Ryż. 5.5.. Rekonstrukcja trójkątów niespełniających warunku Delaunaya
Ta operacja odbudowy jest często nazywana odwróceniem. Twierdzenie to pozwala konstruować triangulację Delaunaya sekwencyjnie, najpierw konstruując pewną triangulację, a następnie sukcesywnie ją poprawiając w sensie warunku Delaunaya. Sprawdzając warunek Delaunaya dla par sąsiednich trójkątów, można bezpośrednio skorzystać z definicji, ale czasami stosuje się inne metody w oparciu o warunki wymienione powyżej.
W tych warunkach pojawia się całkowita charakterystyka całej triangulacji (suma minimalnych kątów lub suma promieni), optymalizując, którą można uzyskać triangulację Delaunaya.
Jak wspomniano powyżej, jeden z operacje krytyczne wykonywane przy konstruowaniu triangulacji polega na sprawdzeniu warunku Delaunaya dla danych par trójkątów. W oparciu o definicję triangulacji Delaunaya i odpowiadające jej warunki w praktyce stosuje się zwykle kilka metod weryfikacji:
– sprawdzenie równania okręgu opisanego;
– sprawdź za pomocą wcześniej obliczonego okręgu opisanego;
– sprawdzenie sumy kątów przeciwnych;
– zmodyfikowane sprawdzenie sumy przeciwległych kątów.
Wiele systemów przeprowadza test z wcześniej obliczonym okręgiem opisanym. Główną ideą algorytmu weryfikacji poprzez wstępnie obliczone okręgi jest wstępne obliczenie dla każdego skonstruowanego trójkąta środka i promienia opisanego wokół niego okręgu, po czym sprawdzenie warunku Delaunaya zostanie zredukowane do obliczenia odległości do środka tego okręgu i porównanie wyniku z promieniem. Środek i promień r okręgu opisanego wokół można znaleźć jako , , , r 2 = (b 2 + c 2 - 4аd)/4а 2, gdzie wartości a, b, c, d określone wzorami (5.3)
(5.3)
Inny zapis równania tego okręgu to:
(5.5.)
(5.6)
Wtedy warunek Delaunaya dla będzie spełniony tylko wtedy, gdy dla dowolnego innego punktu triangulacji będzie:
(x 0 – x C) 2 + (y 0 – y C) 2 ≥ r 2 . (5.7)
Obecnie istnieje wiele algorytmów konstruowania triangulacji Delaunaya. Wiele dobrze znanych algorytmów wykorzystuje definicję triangulacji Delaunaya jako drugorzędną cechę triangulacji. Dlatego w takich algorytmach odnotowuje się następujące słabości:
– algorytmy wykorzystują stale obliczane funkcje trygonometryczne, co drastycznie spowalnia proces;
– podczas badania relacji między punktami a odcinkiem podstawowym powstają bardzo małe kąty i podczas używania funkcje trygonometryczne Istnieje ciągłe niebezpieczeństwo zaniku porządku i dzielenia przez 0 ze względu na ograniczoną dokładność reprezentacji danych w komputerze; sytuacja ta wymaga ciągłego dodatkowego przetwarzania.
Najbardziej znane oprogramowanie buduje triangulację Delaunaya przy użyciu twierdzenia o pustej kuli jako głównej, podstawowej zasady konstruowania trójkątów. Algorytm wygląda następująco:
– cały zbiór punktów dzielimy na trójkąty, tj. tworzone są kombinacje trzech punktów;
– dla każdej kombinacji znajduje się opisany okrąg i współrzędne jego środka;
– jeśli w okręgu aktualnej kombinacji nie pozostał ani jeden punkt, wówczas kombinacja ta jest trójkątem – częścią triangulacji Delaunaya.
Do zalet tego algorytmu zalicza się:
– brak wykorzystania funkcji trygonometrycznych, co nie spowalnia procesu konstrukcji;
– bezpośrednia konstrukcja triangulacji Delaunaya, bez jakichkolwiek konstrukcji wstępnych;
– prostota wszelkich obliczeń i przekształceń;
– w rezultacie siatka triangulacyjna jest reprezentowana przez wiele trójkątów, a nie pojedyncze linie.
Zbudowana w ten sposób triangulacja stanowi geometryczną podstawę do konstruowania izolinii.
Algorytmy konstruowania triangulacji Delaunaya można podzielić na kilka grup, różniących się strukturą wykorzystywanych danych wejściowych, objętością operacji obliczeniowych, przesłankami początkowymi itp. Rozważmy niektóre z nich.
Algorytmy łączenia polegają na podzieleniu zbioru punktów źródłowych na podzbiory, skonstruowaniu triangulacji na każdym z nich, a następnie połączeniu ich w jedną sieć. Istota jednego z tych algorytmów sprowadza się do następujących kwestii.
Zbiór punktów początkowych dzieli się liniami pionowymi na dwie lub więcej części, po czym każdą z nich dzieli się liniami poziomymi i pionowymi na w przybliżeniu równe części. W rezultacie cały obszar punktów początkowych jest podzielony na prymitywy składające się z trzech lub czterech punktów (ryc. 2.4), wzdłuż których budowany jest jeden lub dwa trójkąty.
Łączenie tych trójkątów w jedną sieć odbywa się poprzez skonstruowanie dwóch linii bazowych (P 0 P 1 i P 2 P 3, ryż. 5.7.a), rysowanie okręgów o zmiennym promieniu, których środek znajduje się na dwusiecznej prostopadłej do linii bazowej (rys. 5.7, b), szukanie węzła przypadającego na okrąg (punkt A, ryż. 5.7. c) i konstrukcja nowego trójkąta (P 0 P 1 A). W takim przypadku może być konieczne usunięcie istniejącego trójkąta (np. P 0 AB).
Algorytmy iteracyjne opierają się na idei sekwencyjnego dodawania punktów do częściowo skonstruowanej triangulacji z jednoczesnym jej ulepszaniem i rekonstrukcją zgodnie z kryteriami Delaunaya. W widok ogólny składają się z kilku etapów i sprowadzają się do zbudowania trójkąta na pierwszych trzech punkty startowe i zbadanie kilku opcji umieszczenia następnego punktu. W szczególności rozważane są opcje, aby wypadła ona poza granicę obszaru modelowania, na istniejący węzeł lub krawędź, wewnątrz skonstruowanego trójkąta itp. Każda z tych opcji wiąże się z wykonaniem określonej operacji: podzielenia krawędzi na dwie, ścian na trzy itd.; po czym sprawdza się powstałe trójkąty pod kątem zgodności z warunkiem Delaunaya i niezbędnych rekonstrukcji.
Algorytmy dwuprzebiegowe polegają najpierw na konstrukcji pewnej triangulacji, ignorując warunki Delaunaya, a następnie na jej rekonstrukcji zgodnie z tymi warunkami. Przykład zastosowania algorytmu pokazano na rys. 5.8.
Aby utworzony model reliefu był bardziej zbliżony do rzeczywistego, wprowadza się do niego dodatkowe elementy, które zapewniają uwzględnienie i wyświetlenie jego liniowych i powierzchniowych elementów konstrukcyjnych. Takimi dodatkowymi elementami są szeroko stosowane w topografii linie strukturalne, które definiują „szkielet reliefowy”: zlewiska, wzgórza, grzbiety, klify, półki, jeziora, wąwozy, linie brzegowe, granice sztucznych konstrukcji itp., których całość tworzy rodzaj układ triangulacji Delaunaya. Te linie konstrukcyjne wprowadza się do triangulacji jako krawędzie trójkątów, co pozwala na modelowanie rzeczywistych elementów reliefowych na tle ogólnych nierówności powierzchni ziemi. Takie krawędzie nazywane są strukturalnymi (stałymi, nierekonfigurowalnymi), nie przecinają się z krawędziami innych trójkątów i nie zmieniają się później.
Problem budowy modelu powierzchni z uwzględnieniem linii nieciągłości nazywa się ograniczoną triangulacją Delaunaya, jeśli warunki Delaunaya są spełnione dla dowolnej pary sąsiednich trójkątów, które nie są oddzielone liniami nieciągłości. Naukowcy uważają, że najskuteczniejszym sposobem jest zbudowanie takiej triangulacji przy użyciu algorytmów iteracyjnych.
Fragment triangulacji Delaunaya wraz z zawartymi w niej dodatkowymi elementami pokazano na ryc. 5.9, gdzie po prawej stronie pokazano węzły, krawędzie, krawędzie i linie strukturalne, a po lewej stronie linie strukturalne terenu (linie brzegowe, krawędzie wąwozów itp.) oraz punkty ze znanymi znakami.
Algorytmy konstruowania triangulacji Delaunaya realizowane są z rzeczywistą lub całkowitą reprezentacją współrzędnych węzłów, co może znacznie zwiększyć szybkość i dokładność przetwarzania, ale rodzi problemy z wyszukiwaniem i wykluczaniem pasujących węzłów.
Model TIN można łatwo edytować poprzez przesuwanie węzłów, wstawianie nowych, usuwanie istniejących, zmianę położenia jednej lub kilku krawędzi, wprowadzanie nowych linii konstrukcyjnych itp. Zmiany takie zawsze dotyczą małej grupy sąsiadujących ze sobą trójkątów, nie wymagają przebudowy całej sieci i odbywają się on-line, poprzez najechanie kursorem na odpowiedni element.
O dokładności:
Umieszczając pikiety na charakterystycznych elementach reliefowych (na przykład zlewiska i talwegi), ignorujemy mniejsze elementy w szczelinach. Przy konstruowaniu warstwic1 wzdłuż takich krawędzi trójkątów pojawia się błąd zależny od wielkości nierówności terenu i kąta nachylenia terenu. Przykładowo średni błąd pomiaru reliefu nie powinien przekraczać 1/3 przekroju reliefu przy kątach nachylenia powierzchni od 2 do 10 stopni. Można obliczyć, że przy przekroju reliefowym 0,5 m maksymalna wartość pominiętych nierówności (czyli odchylenie powierzchni gruntu od linii prostej przechodzącej przez sąsiednie paliki) nie powinna przekraczać (0,5/3) * cos10° = 0,16 m.
Dla dokładności określenia objętości transportowanej gleby ważna jest również powierzchnia zajmowana przez nieuwzględniony szczegół rzeźby. Załóżmy, że w kwadracie o wymiarach 20x20 m pomiędzy dwiema parami pików znajduje się cylindryczna wypukłość o maksymalnej wysokości 0,15 m. Łatwo obliczyć, że nieuwzględnienie jej przy przedstawianiu tej powierzchni tylko dwoma trójkątami doprowadzi do: błąd około 40 m3. Niewiele, ale na działkę o powierzchni 1 hektara, położoną na wzniesieniu lub w górnej (zwykle wypukłej) części zbocza, uzyskuje się 40 * 25 = 1000 m3 nadmiaru gleby. Jeśli pikiety będziemy przeprowadzać dwa razy częściej (czyli co 10 m), błąd zmniejszy się czterokrotnie i wyniesie 250 m3 na hektar. Czynnik ten można wziąć pod uwagę z góry, ponieważ pozytywne formy płaskiego reliefu mają zwykle kształt wypukły, podczas gdy formy negatywne mają kształt wklęsły. Jeśli badany obszar posiada przybliżone dane dotyczące rzeźby, wówczas promień krzywizny powierzchni i wymaganą gęstość palików można łatwo obliczyć na podstawie wartości warstwic lub poszczególnych wzniesień.
Podstawowe definicje i właściwości
Triangulacja to graf planarny, którego wszystkie obszary wewnętrzne są trójkątami.
Właściwości:
· Triangulacja Delaunaya odpowiada diagramowi Woronoja w stosunku jeden do jednego dla tego samego zbioru punktów.
· W konsekwencji: jeśli żadne cztery punkty nie leżą na tym samym okręgu, triangulacja Delaunaya jest unikalna.
· Triangulacja Delaunaya maksymalizuje minimalny kąt pomiędzy wszystkimi kątami wszystkich skonstruowanych trójkątów, unikając w ten sposób „cienkich” trójkątów.
· Triangulacja Delaunaya maksymalizuje sumę promieni kul wpisanych.
· Triangulacja Delaunaya minimalizuje dyskretny funkcjonał Dirichleta.
· Triangulacja Delaunaya minimalizuje maksymalny promień minimalnej sfery otoczenia.
· Triangulacja Delaunaya na płaszczyźnie ma minimalną sumę promieni okręgów opisanych wokół trójkątów spośród wszystkich możliwych triangulacji.
Rysunek 1. Triangulacja.
Triangulacja wypukła to triangulacja, w której minimalny wielokąt obejmujący wszystkie trójkąty jest wypukły. Triangulację, która nie jest wypukła, nazywamy niewypukłą.
Problem konstruowania triangulacji z danego zbioru punktów dwuwymiarowych nazywany jest problemem połączenia dane punkty nieprzecinających się segmentów, w wyniku czego powstaje triangulacja.
Mówi się, że triangulacja spełnia warunek Delaunaya, jeśli żaden z podanych punktów triangulacji nie mieści się w okręgu opisanym na dowolnym skonstruowanym trójkącie.
Triangulację nazywa się triangulacją Delaunaya, jeśli jest wypukła i spełnia warunek Delaunaya.
Rysunek 2. Triangulacja Delaunaya.
Metoda pustej kuli Delaunaya. Konstrukcja w przypadku ogólnym
Wykorzystajmy pustą kulę, którą będziemy przesuwać, zmieniając jej rozmiar tak, aby dotykała punktów układu (A), ale zawsze pozostawała pusta.
Umieśćmy więc w układzie punktów (A) pusta piłka Delaunaya. Jest to zawsze możliwe, jeśli wybierzesz wystarczająco małą kulkę. Zacznijmy zwiększać jego promień, pozostawiając środek kuli na miejscu. W pewnym momencie powierzchnia kuli zetknie się z pewnym punktem i układu (A). Tak się na pewno stanie, bo w naszym układzie nie ma nieskończenie dużych pustek. Będziemy nadal zwiększać promień pustej kuli, tak aby punkt i pozostał na jej powierzchni. Aby to zrobić, będziesz musiał przesunąć środek kuli z punktu i. Prędzej czy później piłka dotrze swoją powierzchnią do innego punktu układu (A).
Ryc.3
Simpleksy Delaunaya wypełniają przestrzeń bez przerw i zakładek.
Opisana kula dowolnego sympleksu nie zawiera w sobie innych punktów układu.
Niech to będzie punkt j. Kontynuujmy zwiększanie promienia naszej kuli, utrzymując oba punkty na jej powierzchni. W miarę wzrostu piłki dotrze do trzeciego punktu układu, punktu k. W przypadku dwuwymiarowym nasze „puste koło” zostanie w tym momencie ustalone, tj. Dalsze zwiększanie jego promienia przy pozostawieniu pustego koła stanie się niemożliwe. Jednocześnie identyfikujemy elementarną dwuwymiarową konfigurację trzech punktów (i, j, k), definiującą pewien trójkąt, którego osobliwością jest to, że wewnątrz jego okręgu opisanego nie ma innych punktów układu (A). W przestrzeni trójwymiarowej kula nie jest definiowana przez trzy punkty. Kontynuujmy zwiększanie jego promienia, zachowując wszystkie trzy punkty znalezione na jego powierzchni. Będzie to możliwe do momentu, gdy powierzchnia kuli zetknie się z czwartym punktem l układu. Następnie ruch i wzrost pustej kuli staną się niemożliwe. Znaleziono cztery punkty (i,j,k,l) określają wierzchołki czworościanu, który charakteryzuje się tym, że wewnątrz jego ograniczonej kuli nie ma innych punktów układu (A). Taki czworościan nazywa się sympleksem Delaunaya.
W matematyce sympleks to najprostsza figura w przestrzeni o danym wymiarze: czworościan - w przestrzeni trójwymiarowej; trójkąt - w dwóch wymiarach. Dowolne trzy (cztery) punkty układu, które nie leżą w tej samej płaszczyźnie, zawsze definiują pewien sympleks. Będzie to jednak sympleks Delaunaya tylko wtedy, gdy opisana przez niego kula będzie pusta. Innymi słowy, uproszczenia Delaunaya wyznaczane są poprzez specjalny wybór trójek (czwórek) punktów w układzie (A).
Skonstruowaliśmy jeden sympleks Delaunaya, ale umieszczając pustą kulę w różnych miejscach i powtarzając tę samą procedurę, możemy zdefiniować inne. Stwierdza się, że zbiór wszystkich uproszczeń Delaunaya układu (A) wypełnia przestrzeń bez zakładek i przerw, tj. realizuje podział przestrzeni, ale tym razem na czworościany. Ta partycja nazywa się Płytki Delaunaya(ryc. 3).
Zastosowanie triangulacji Delaunaya
Triangulacje Delaunaya są często stosowane w przestrzeni euklidesowej. Gwarantujemy, że minimalne drzewo rozpinające euklidesowe leży na triangulacji Delaunay'a, więc niektóre algorytmy korzystają z triangulacji. Ponadto, dzięki triangulacji Delaunay'a, problem euklidesowego komiwojażera został w przybliżeniu rozwiązany.
W interpolacji 2D triangulacja Delaunaya dzieli płaszczyznę na możliwie najgrubsze trójkąty, unikając zbyt ostrych i zbyt rozwartych kątów. Korzystając z tych trójkątów, można zbudować na przykład interpolację dwuliniową.
Kolejnym często spotykanym problemem w geoinformatyce jest konstrukcja ekspozycji zboczy. W tym przypadku konieczne jest określenie dominujących kierunków zboczy według kierunku kardynalnego i podzielenie powierzchni na obszary, w których dominuje określony kierunek. Ponieważ określanie narażenia nie ma sensu w przypadku poziomych obszarów powierzchni, obszary poziome lub o niewielkim nachyleniu są przydzielane do osobnego obszaru, np.<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.
Ryc.4.
Zagadnienie obliczania ekspozycji zboczy jest zwykle wykorzystywane do analizy oświetlenia Ziemi. W związku z tym często istnieje potrzeba dodatkowego uwzględnienia aktualnej pozycji Słońca, tj. ekspozycję oblicza się jako kierunek pomiędzy normalną do trójkąta a kierunkiem do Słońca.
Zatem każdy trójkąt triangulacyjny można sklasyfikować zgodnie z zasadą przynależności do określonego regionu. Następnie wystarczy wywołać algorytm wyboru regionu.
Triangulacja to przybliżanie powierzchni modelowanego obiektu za pomocą trójkątnych płytek oddalonych od niego na odległość nie przekraczającą określonej wartości 6. Wszystkie trójkątne płytki muszą być ze sobą połączone. Ich wierzchołki leżą na powierzchni. Łatwiej jest pracować z zestawem trójkątnych płytek niż z ogólną powierzchnią. Płytki trójkątne będziemy nazywać trójkątami. W przypadku trójkąta szybko obliczana jest odległość do danego punktu lub punktu przecięcia z daną linią w przestrzeni. Triangulację ścian wykonuje się w celu wizualnej percepcji modelu geometrycznego, dlatego boki trójkątów dobiera się tak, aby oko nie zauważyło załamań.
Podczas wyświetlania obiektów geometrycznych za pomocą trójkątów na parametrycznych płaszczyznach powierzchni należy skonstruować przestrzenną triangulację ścian ciała poprzez obliczenie układu punktów w przestrzeni i układu normalnych do powierzchni ciała w tych punktach przy użyciu układu punkty dwuwymiarowe Aby szybko wyświetlić ciała, ich twarze są aproksymowane za pomocą trójkątnych płytek zbudowanych na punktach Normalnych, które służą do określenia zachowania promieni świetlnych oddziałujących z powierzchniami ciała. Rysunki tonów w poprzednich rozdziałach i w tym rozdziale zostały wykonane przy użyciu triangulacji.
W wyniku triangulacji powierzchniowej chcemy mieć tablicę dwuwymiarowych punktów na płaszczyźnie parametrycznej oraz tablicę trójek liczb całkowitych, które są numerami punktów w pierwszej wymienionej tablicy. Zatem każdy trójkąt będzie reprezentowany przez trzy liczby jego wierzchołków w tablicy parametrów. Dla każdego dwuwymiarowego punktu dziedziny parametrycznej można obliczyć punkt przestrzenny na powierzchni i znajdującą się w nim normalną do powierzchni. Punkty przestrzenne i normalne można przechowywać w tablicach podobnych do tablicy punktów 2D.
Przyjrzyjmy się niektórym metodom triangulacji. W przypadku powierzchni płaskich istnieją ekonomiczne metody triangulacji, w których konstruuje się trójkąty w punktach granicznych powierzchni i nie ma potrzeby poszukiwania punktów wewnątrz obszaru parametrycznego.
Triangulacja Delaunaya.
Rozważmy pewien obszar na płaszczyźnie. Obszar nazwiemy wypukłym, jeżeli poruszając się wzdłuż jego granicy trzeba skręcić tylko w jedną stronę (tylko w lewo lub tylko w prawo). Algorytm Delaunaya można zastosować do triangulacji wypukłych obszarów płaskich. Nie będziemy w stanie bezpośrednio zastosować tego algorytmu do triangulacji powierzchni o swobodnych kształtach, ale wykorzystamy jego metodę do konstruowania trójkątów.
Ryż. 9.7.1. Obszar wypukły z podanymi punktami wewnątrz
Niech będzie dany wypukły dwuwymiarowy obszar ograniczony zamkniętą linią przerywaną i zbiór punktów wewnątrz tego obszaru (rys. 9.7.1).
Należy podzielić wyznaczony obszar na trójkąty, których wierzchołkami są dane punkty wewnątrz obszaru oraz wierzchołki ograniczającej go linii łamanej. Trójkąty nie mogą na siebie zachodzić, a ich boki mogą przecinać się tylko w wierzchołkach.
Można skonstruować kilka różnych zestawów trójkątów, aby wypełnić określony obszar. We wszystkich przypadkach liczba trójkątów jest równa , gdzie K jest liczbą wierzchołków ograniczającej polilinii, I jest liczbą danych punktów wewnątrz obszaru.
Ryż. 9.7.2. Wybór trzeciego punktu algorytmu Delaunaya
Triangulacja obszaru będzie triangulacją Delaunaya, jeśli wewnątrz okręgu opisanego wokół każdego trójkąta nie ma wierzchołków innych trójkątów. Triangulacja Delaunaya buduje trójkąty możliwie najbardziej zbliżone do równokątnych (nie pozwala na budowę nieracjonalnie wydłużonych trójkątów).
Można to nazwać zrównoważonym. Triangulacja Delaunaya będzie wyjątkowa, jeśli żadne cztery wierzchołki nie leżą na tym samym okręgu.
Rozważmy triangulację Delaunaya. Wierzchołki polilinii ograniczającej obszar oraz dane punkty wewnątrz obszaru będziemy nazywać wierzchołkami triangulacji. Boki trójkątów będziemy nazywać krawędziami. Spośród krawędzi wybieramy segmenty ograniczającej polilinii, które nazwiemy krawędziami granicznymi. Zorientujmy wszystkie krawędzie graniczne tak, aby obszar wypukły znajdował się po lewej stronie każdej krawędzi. Niech będzie konieczne zbudowanie trójkąta, którego bok będzie krawędzią graniczną AB, jak pokazano na ryc. 9.7.2.
Przez wierzchołki A, B i dowolny wierzchołek, który nie leży z nimi na tej samej prostej, można poprowadzić okrąg. Jako trzeci wierzchołek trójkąta wybieramy wierzchołek V, odpowiadający mu okrąg nie zawiera innych wierzchołków po tej samej stronie w stosunku do odcinka AB, na którym leży punkt V. Dla krawędzi granicznej w ogólnym przypadku może być jeden taki wierzchołek odnaleźć się. Nazwiemy go najbliższym. Środek okręgu przechodzącego przez punkty A, B i V leży na przecięciu prostopadłych ze środkami odcinków AB, BV i VA. Położenie środka okręgu będzie charakteryzowane parametrem t odcinka MN, prostopadłego do krawędzi AB, równej długości i przechodzącego przez środek krawędzi AB.
Ryż. 9.7.3. Proces triangulacji Delaunaya
Dla wszystkich wierzchołków leżących na lewo od odcinka AB najbliższy wierzchołek ma najmniejszy parametr t. Okrąg odpowiadający najbliższemu wierzchołkowi nie zawiera innych wierzchołków na lewo od odcinka AB. Niech wierzchołki A, B i V będą opisane odpowiednio dwuwymiarowymi wektorami promieni. Wektory promieni środków odcinków AB i BV będą równe
Wartość parametru t prostej odpowiadającej położeniu na niej środka okręgu przechodzącego przez punkty A, B i V jest równa
Dla wierzchołka najbliższego na lewo od odcinka AB parametr t ma wartość minimalną.
Zorientujmy wszystkie krawędzie granicy tak, aby obszar do triangulacji znajdował się na lewo od każdej z nich. Konstrukcję trójkątów zaczynamy od dowolnej krawędzi granicznej. Znajdźmy dla niego najbliższy wierzchołek, którego odpowiedni okrąg nie zawiera innych wierzchołków. Znajdźmy najbliższy wierzchołek V dla krawędzi granicznej AB. Następnie konstruujemy trójkąt ABV i przenosimy krawędź AB do kategorii nieaktywnej. Nieaktywne krawędzie i wierzchołki, które nie biorą udziału w algorytmie triangulacji, będziemy wywoływać. Jeżeli pomiędzy krawędziami granicznymi nie ma krawędzi BV, to nową krawędź graniczną konstruujemy na odcinku VB. Jeżeli wśród krawędzi granicznych znajduje się krawędź BV, to przenosimy ją wraz z wierzchołkiem B do kategorii nieaktywnych. Jeśli pomiędzy krawędziami granicznymi nie ma krawędzi VA, wówczas skonstruujemy nową krawędź graniczną na odcinku AV. Jeżeli wśród krawędzi granicznych znajduje się krawędź VA, to przenosimy ją wraz z wierzchołkiem A do kategorii nieaktywnych. Proces triangulacji pokazano na ryc. 9.7.3.
Ryż. 9.7.4. Triangulacja Delaunaya
Kończymy triangulację, gdy wszystkie wierzchołki i krawędzie staną się nieaktywne. Wynik triangulacji danego obszaru pokazano na rys. 9.7.4.
Triangulacja metodą korekcyjną.
Rozważmy triangulację pewnej powierzchni z dziedziną prostokątną w celu zdefiniowania parametrów. Podzielmy dziedzinę definiowania parametrów powierzchni na prostokątne komórki z liniami dwuwymiarowymi. Linie te tworzą prostokątną siatkę. Przyjmijmy, że odległości parametryczne pomiędzy sąsiednimi liniami zgodnie ze wzorem (9.4.7) są równe
Przyjmijmy, że odległości parametryczne pomiędzy sąsiednimi liniami zgodnie ze wzorem (9.4.8) są równe
Konstruując przekątne we wszystkich komórkach prostokątnych uzyskujemy triangulację powierzchni (otrzymujemy zbiór trójkątów spełniający wymagania). Na ryc. Na rys. 9.7.5 przedstawiono triangulację powierzchni obrotowej opisaną metodą.
Rozważmy triangulację powierzchni z dowolną granicą. Metodę triangulacji zbudujemy na korekcie konturami brzegowymi opisanej powyżej triangulacji powierzchni z prostokątnym obszarem do wyznaczania parametrów.
Ryż. 9.7.5. Triangulacja powierzchni o domenie prostokątnej w celu określenia parametrów
Niech granicę powierzchni w dziedzinie definicji parametrów opisz kilkoma nieprzecinającymi się dwuwymiarowymi konturami (2.12.7). Jeden z konturów jest zewnętrzny i zawiera pozostałe kontury. Za dodatni kierunek dla każdego konturu przyjmiemy kierunek, po którym podczas poruszania się obszar definicji powierzchni znajduje się zawsze na lewo od konturu, patrząc w stronę normalnej powierzchni. Skonstruujmy wielokąty w kierunku dodatnim konturów granicznych obszaru definicji powierzchni. Aby skonstruować wielokąty graniczne, należy chodzić po konturach granicznych powierzchni pewnym zmiennym krokiem i wypełnić układ dwuwymiarowych punktów, których współrzędne są parametrami powierzchni. Zbudujemy wielokąt z punktów na płaszczyźnie parametrycznej, ale krok przy przejściu z jednego punktu do drugiego zostanie określony na podstawie geometrii przestrzennej, a mianowicie pod warunkiem, że odchylenie łuku krzywej między sąsiednimi punktami nie będzie większe niż podane wartość. Obliczamy kroki parametryczne konstruowania wielokąta dla krzywej konturu granicy powierzchni, korzystając ze wzoru (9.4.4).
Każdy wielokąt składa się z uporządkowanego zbioru dwuwymiarowych punktów. Każdy odcinek wielokąta można uznać za dwuwymiarowy odcinek linii prostej zbudowany na dwóch sąsiednich punktach. Takie obszary wykorzystamy jako krawędzie graniczne, a punkty wielokątów, na których te krawędzie się opierają, posłużą jako wierzchołki triangulacji. Ponieważ obszar do wyznaczania parametrów powierzchni leży na lewo od wielokątów granicznych, konstruując trójkąty dla każdej krawędzi triangulacji granicy, należy szukać trzeciego wierzchołka trójkąta na lewo od krawędzi.
Ustalmy, które węzły leżą wewnątrz wielokątów granicznych, a które na granicy lub poza obszarem definicji powierzchni. Korzystając z tych informacji, sortujemy prostokątne komórki siatki na dwie grupy. Do pierwszej grupy zaliczają się komórki, które w całości leżą na obszarze, na którym wyznaczane są parametry powierzchni (komórki nie powinny dotykać wielokątów granicznych). Druga grupa obejmuje pozostałe komórki (leżące poza obszarem definicji powierzchni lub przecięte wielokątami granicznymi).
Ryż. 9.7.6. Niedokończona triangulacja powierzchni
Wewnątrz każdej komórki pierwszej grupy za pomocą przekątnej skonstruujemy dwa trójkąty. W ten sposób otrzymujemy niedokończoną triangulację. Przykład konstrukcji trójkątów w komórkach pierwszej grupy dla powierzchni obrotowej ograniczonej konturami pokazano na rys. 9.7.6.
Skonstruujemy krawędzie graniczne na nieprzeciętych bokach komórek drugiej grupy i skierujemy je tak, aby odpowiednia komórka znajdowała się na lewo od krawędzi. Wokół komórek pierwszej grupy zbudujemy zamkniętą linię przerywaną (ewentualnie kilka zamkniętych linii), tak aby poruszając się po niej część obszaru, która nie jest podzielona na trójkąty, znajdowała się po lewej stronie, patrząc w stronę normalnej powierzchni. Proste odcinki tej linii przerywanej wykorzystamy również jako krawędzie graniczne. Wszystkie krawędzie uznamy za równe. Aby zakończyć triangulację, musimy skonstruować trójkąty pomiędzy krawędziami granic. Dla każdej krawędzi będziemy szukać wierzchołka leżącego na lewo od niej, z którego można zbudować trójkąt. Będziemy szukać wierzchołków tylko wśród tych wierzchołków, które leżą w tej samej komórce co krawędź. Aby wybrać wierzchołek, używamy metody Delaunaya opisanej powyżej i zilustrowanej na ryc. 9.7.2. Jeśli taki wierzchołek zostanie znaleziony, należy sprawdzić, czy dwie nowe krawędzie trójkąta przecinają się z jakąkolwiek krawędzią graniczną. Znajdźmy najbliższy wierzchołek V krawędzi granicznej AB i sprawdźmy, czy odcinki BV i VA nie przecinają pozostałych krawędzi brzegowych. Następnie skonstruujemy trójkąt ABV i przeniesiemy krawędź AB do kategorii nieaktywnej. Jeśli pomiędzy krawędziami granicy nie ma krawędzi BV, to skonstruujemy nową krawędź granicy na odcinku VB, natomiast jeśli pomiędzy krawędziami granicy będzie krawędź BV, to przeniesiemy ją wraz z wierzchołkiem B do kategorii nieaktywnych. Jeśli pomiędzy krawędziami granicy nie ma krawędzi VA, to skonstruujemy nową krawędź granicy na odcinku AV, natomiast jeśli pomiędzy krawędziami granicy znajduje się krawędź VA, to przeniesiemy ją i wierzchołek A do kategorii nieaktywnych.
Jeśli odcinek lub VA przecina inne krawędzie granicy, wówczas przystępujemy do poszukiwania najbliższego wierzchołka dla innej krawędzi granicy. Triangulacja zostanie zakończona, gdy wszystkie krawędzie i wierzchołki zostaną sklasyfikowane jako nieaktywne.
Ryż. 9.7.7. Triangulacja metodą korekcyjną
Na ryc. Rysunek 9.7.7 przedstawia triangulację powierzchni metodą korygowania trójkątów w komórkach przeciętych konturami granicznymi. Na ryc. 9.7.8, wykorzystując wynikową triangulację, wyświetlana jest sama powierzchnia.
Jeżeli wielokąty graniczne i powierzchnia mają pewną symetrię, to triangulacja metodą korekcji będzie miała podobną symetrię.
Triangulacja metodą absorpcyjną.
Rozważmy inną metodę triangulacji. Pod względem szybkości ustępuje triangulacji Delaunaya i jej modyfikacjom. Aby rozpocząć procedurę triangulacji, konieczne jest przedstawienie granicy powierzchni w postaci zamkniętych wielokątów. Podczas procesu triangulacji będziemy musieli określić kroki na podstawie parametrów powierzchni. Przy znanym kierunku ruchu kroki te określa się za pomocą wzorów (9.4.6). Przybliżone kroki dotyczące parametrów powierzchni można znaleźć w następujący sposób. Zdefiniujmy obszar na płaszczyźnie parametrów wokół pewnego punktu w taki sposób, aby dowolny odcinek przestrzenny od punktu do punktu w tym obszarze znajdował się nie dalej niż o zadaną wartość S od powierzchni.
W tym celu obliczamy dopuszczalne przyrosty parametrów wzdłuż linii współrzędnych
gdzie są współczynnikami pierwszej i drugiej formy kwadratowej powierzchni w punkcie . Jako granicę żądanego obszaru przyjmujemy elipsę ze środkiem w punkcie i półosiami. Ta elipsa ma równanie
Jeżeli chcemy znaleźć punkt na płaszczyźnie obok punktu w kierunku określonym przez kąt z osią i to jego parametry będą
Rozważmy najpierw prostszy przypadek, gdy obszar parametrów powierzchni ogranicza się do jednego konturu zewnętrznego. Granicę powierzchni przybliżamy zamkniętym wielokątem w dziedzinie parametrycznej. Konstruując triangulację skorzystamy z wielokąta roboczego, który w tym przypadku przyjmiemy jako wielokąt konturu zewnętrznego. Dodamy punkty wielokąta do powstałej tablicy punktów dwuwymiarowych. Z krawędzi obszaru roboczego zbudujemy trójkąty, zwężając je, aż w obszarze roboczym pozostaną tylko trzy punkty.
Znajdźmy wierzchołek w wielokącie roboczym, w którym zamienia się on w region. Taki punkt zawsze istnieje, a kąt obrotu w nim jest mniejszy. Oznaczmy ten punkt przez O, a jego parametry przez. W pobliżu tego punktu zbudujemy jeden lub dwa trójkąty, w zależności od kąta obrotu. Jeśli kąt jest mniejszy, zbudujemy jeden trójkąt na tych trzech punktach (ryc. 9.7.9). W przeciwnym razie zbudujemy na tym dwa trójkąty, dwa sąsiednie i jeden nowy punkt (ryc. 9.7.11). Nowy punkt oznaczony jest przez P. Będziemy szukać punktu P na przekątnej równoległoboku B OS P. Jeżeli wierzchołek równoległoboku leży wewnątrz elipsy (rys. 9.7.10), to przyjmiemy go jako punkt P W przeciwnym razie przecięcie elipsy i przekątnej równoległoboku przyjmiemy jako punkt P . W tym drugim przypadku wcale nie jest konieczne szukanie przecięcia elipsy i odcinka.
Współrzędne punktu P wyznacza się poprzez współrzędne punktów O BC
Kąt odcinka OP z poziomem jest określony przez równość
(9.7.8)
Dane te pozwalają wyznaczyć położenie punktu P względem elipsy (9.7.5).
W przypadku pokazanym na rys. 9.7.9 skonstruujmy trójkąt (pamiętaj numery jego wierzchołków) i usuń punkt O z obszaru roboczego w przypadku pokazanym na ryc. 9.7.11 skonstruujemy dwa trójkąty i w obszarze roboczym zastąpimy punkt O punktem P i umieścimy ten ostatni w wynikowym układzie punktów. Na ryc. Rysunek 9.7.12 przedstawia wielokąt uzyskany po zbudowaniu dwóch trójkątów i wyeliminowaniu punktu O. W obu przypadkach punkt O zostanie usunięty z wielokąta roboczego, a wielokąt roboczy zwęzi się. Należy pamiętać, że trójkąty można konstruować tylko wtedy, gdy obszar roboczy po zwężeniu nie przecina się sam ze sobą.
Ryż. 9.7.9. Budowa trójkąta
Ryż. 9.7.10. Wynikowy wielokąt
Ryż. 9.7.11. Konstrukcja dwóch trójkątów
Ryż. 9.7.12. Wynikowy wielokąt
Sytuacje takie pokazane są na ryc. 9.7.13. Mogą wystąpić, gdy boki skonstruowanych trójkątów przecinają się z bokami obszaru roboczego, które do nich nie przylegają. Przed zbudowaniem nowego trójkąta jak w przypadku pokazanym na ryc. 9.7.9, a w przypadku pokazanym na rys. 9.7.11 należy sprawdzić, czy powstały wielokąt nie przecina się sam ze sobą.
Ponadto przy ustalaniu położenia punktu P ważne jest, aby znajdował się on w wystarczającej odległości od innych punktów obszaru roboczego i nie zbliżał się do odcinków łączących punkty obszaru. W przeciwnym razie w przyszłości mogą pojawić się trudności przy konstruowaniu trójkątów. Dlatego przed zawężeniem wielokąta roboczego należy sprawdzić powstały wielokąt pod kątem samoprzecięcia. Jeżeli w pobliżu punktu O nie da się zbudować trójkąta (trójkątów), to zamiast tego należy znaleźć inny punkt, w którym wielokąt zawija się bardziej niż w innych konturze i wykonać w nim opisane czynności.
Następnie ze zmodyfikowanym obszarem roboczym wykonamy te same czynności, które właśnie opisaliśmy. Znajdźmy punkt w wielokącie roboczym, w którym skręca on wewnątrz obszaru bardziej niż w innych punktach, sprawdźmy możliwość zawężenia w nim wielokąta poprzez zbudowanie jednego lub dwóch trójkątów i zawęź wielokąt.
Ryż. 9.7.13. W tym narożniku nie można budować trójkątów.
Kontynuując ten proces, będziemy poszerzać tablicę punktów dwuwymiarowych i tablicę trójkątów, jednocześnie zawężając wielokąt roboczy, zmniejszając jego powierzchnię i liczbę jego punktów. Na pewnym etapie tych działań otrzymamy działający wielokąt składający się z trzech punktów. Zbudujmy ostatni trójkąt w tych punktach, wyeliminujmy obszar roboczy i zakończmy triangulację. W opisywanej metodzie triangulacji obszar ograniczony polem roboczym jest niejako eliminowany poprzez odcięcie od niego trójkątów.
Rozważmy ogólny przypadek, gdy obszar parametrów powierzchni jest ograniczony przez jeden kontur zewnętrzny i kilka konturów wewnętrznych, które leżą całkowicie wewnątrz konturu zewnętrznego. Granicę powierzchni przybliżamy zamkniętymi wielokątami w dziedzinie parametrycznej. Dla każdego konturu zbudujemy własny wielokąt. Podobnie jak w przypadku konturów, w przypadku zbudowanych na nich wielokątów musi być spełniona zasada ich wzajemnego zorientowania. Orientacja wielokątów wewnętrznych musi być przeciwna do orientacji wielokąta zewnętrznego. Zacznijmy konstruować triangulację od wielokąta konturu zewnętrznego. Umieśćmy jego punkty w wynikowej tablicy dwuwymiarowych punktów i uczyńmy sam wielokąt działającym.
Trójkąty będziemy konstruować w taki sam sposób, jak w przypadku obszaru prosto połączonego. Znajdźmy punkt O w obszarze roboczym, sprawdźmy, czy w tym miejscu można zawęzić obszar roboczy i zawęź obszar. Jeżeli występują kontury wewnętrzne, sprawdzenie możliwości zawężenia pola roboczego w wybranym punkcie staje się trudniejsze. Oprócz opisanych kontroli przecięcia boków trójkątów z bokami obszaru roboczego, należy sprawdzić przecięcie boków trójkątów z bokami wszystkich wielokątów wewnętrznych.
Sprawdźmy możliwość zbudowania dwóch trójkątów w punkcie O (rys. 9.7.11) i przekonajmy się, że nowy punkt P po zbudowaniu będzie wpadał w jeden z wielokątów wewnętrznych lub będzie znajdował się w niedopuszczalnej odległości od jego odcinków. W tym przypadku nie będziemy konstruować punktu P, ale zamiast tego uwzględnimy ten wewnętrzny wielokąt w wielokącie roboczym, konstruując dwa trójkąty pokazane na ryc. 9.7.14.
Aby uwzględnić punkty jednego z wielokątów wewnętrznych w wielokącie roboczym, wśród punktów wielokąta wewnętrznego znajdujemy punkt najbliższy punktowi C (przylegający do punktu O) wielokąta roboczego.
Skonstruujmy trójkąty w punktach OCF i CEF i pomiędzy punktami O i C wielokąta roboczego wstawimy punkty wielokąta wewnętrznego, zaczynając od punktu F, a kończąc na punkcie E. W ten sposób przełamiemy wielokąt roboczy na odcinku OS, rozbij wielokąt wewnętrzny na odcinku EF i połącz go z odcinkami OF i EU.
Ryż. 9.7.14. Konstrukcja dwóch trójkątów
Ryż. 9.7.15. Łączenie wielokątów zewnętrznych i wewnętrznych
Wynik połączenia pokazano na ryc. 9.7.15. Oczywiście przed połączeniem wielokąta zewnętrznego i wewnętrznego należy dokonać sprawdzenia poprawności tej operacji.
Następnie będziemy dalej zawężać obszar roboczy w opisany sposób, aż znajdziemy się w bliskiej odległości od innego obszaru wewnętrznego i włączymy go do obszaru roboczego. W rezultacie wszystkie wielokąty wewnętrzne zostaną uwzględnione w wielokącie roboczym, który należy zawęzić do trzech ostatnich punktów. W rezultacie cały wielokrotnie spójny obszar do wyznaczania parametrów powierzchni zostanie pokryty trójkątami.
Ryż. 9.7.16. W tym narożniku nie można budować trójkątów.
Mogą zaistnieć sytuacje, w których na danych wielokątach nie będzie możliwe zbudowanie pojedynczego trójkąta. Na ryc. Rysunek 9.7.16 przedstawia obszar ograniczony dwoma wielokątami, z których każdy składa się z czterech segmentów. W przypadku wielokąta zewnętrznego nie możemy kontynuować triangulacji, ponieważ przeszkadza wielokąt wewnętrzny. W tym przypadku znajdziemy dwa sąsiednie punkty B i C wielokąta, dla których możemy skonstruować trójkąt HRV. Punkt P rzutowany jest na środek boku BC i leży w takiej odległości od niego, że nowy trójkąt nie przecina wielokątów.
Inne metody triangulacji.
Istnieją inne sposoby triangulacji. Przykładowo, po skonstruowaniu wielokątów konturów zewnętrznych i wewnętrznych obszaru definicji powierzchni, można wybrać inną strategię konstruowania trójkątów. Inną opcją jest połączenie wielokątów zewnętrznych i wewnętrznych w jeden wielokąt przed rozpoczęciem triangulacji. Za pomocą określonego algorytmu można „szkicować” punkty wewnątrz obszaru definicji parametrów i przeprowadzać triangulację Delaunay’a na ich podstawie oraz na punktach wielokątów konturu granicznego. Istnieją algorytmy, które najpierw konstruują duże trójkąty, a następnie dzielą je na łatwe do zarządzania rozmiary.
Triangulacja ciała.
Triangulacja ciała to zbiór trójkątów uzyskany przez triangulację powierzchni jego ścian. Triangulacja poszczególnych powierzchni różni się od triangulacji ścian korpusu tym, że w tym drugim przypadku wielokąty graniczne sąsiadujących ścian muszą być spójne (rys. 9.7.17).
Ryż. 9.7.17. Spójność wielokąta obwiedni ciała
Przekroje wielokątów sąsiadujących ścian przechodzących wzdłuż wspólnych krawędzi będą spójne, jeśli ich punkty pokrywają się w przestrzeni.
Zastosowanie triangulacji.
Trójkąty powstałe w wyniku triangulacji służą do uzyskania obrazów tonowych. Na ryc. Rysunki 9.7.18 i 9.7.19 przedstawiają triangulacje powierzchni korpusu arkuszowego, których obraz tonowy pokazano na ryc. 6.5.1.
Ryż. 9.7.18. Triangulacja twarzy metodą korekcji
Podział dziedziny wyznaczania parametrów powierzchni na trójkąty można zastosować w całkach (8.6.2), (8.6.3), (8.6.12), (8.7.17)-(8.7.22) przy obliczaniu charakterystyk geometrycznych ciał . Podczas całkowania numerycznego krok parametryczny dla krzywych należy obliczyć ze wzorów (8.11.5), a dla powierzchni kroki parametryczne należy obliczyć ze wzorów (8.11.1) i (8.11.2).
Triangulacja dla skończonego zbioru punktów S to problem triangulacji wypukłego kadłuba CH(S) obejmującego wszystkie punkty zbioru S. Odcinki proste w triangulacji nie mogą się przecinać - mogą spotykać się jedynie w wspólnych punktach należących do zbioru S. Ponieważ odcinki linii prostych zamykają trójkąty, rozważymy je jako żebra. Na ryc. Rysunek 1 przedstawia dwie różne wersje triangulacji dla tego samego zbioru punktów (tymczasowo zignorujemy okręgi narysowane na tych rysunkach).
Ryż. 1
Dla danego zbioru punktów S widać, że wszystkie punkty ze zbioru S można podzielić na punkty graniczne - te, które leżą na granicy wypukłego kadłuba CH(S) oraz punkty wewnętrzne - leżące wewnątrz wypukłego kadłub CH(S). Krawędzie otrzymane w wyniku triangulacji S można również klasyfikować jako żeberka skorupowe I wewnętrzne żebra. Krawędzie kadłuba obejmują krawędzie położone wzdłuż granicy kadłuba wypukłego CH(S), a krawędzie wewnętrzne obejmują wszystkie pozostałe krawędzie tworzące siatkę trójkątów wewnątrz kadłuba wypukłego. Należy pamiętać, że każda krawędź powłoki łączy dwa sąsiednie punkty graniczne, natomiast krawędzie wewnętrzne mogą łączyć dwa punkty dowolnego typu. W szczególności, jeżeli krawędź wewnętrzna łączy dwa punkty graniczne, to jest to cięciwa kadłuba wypukłego CH(S). Należy również zauważyć, że każda krawędź triangulacji jest granicą dwóch obszarów: każda wewnętrzna krawędź znajduje się pomiędzy dwoma trójkątami, a każda krawędź powłoki znajduje się pomiędzy trójkątem a nieskończoną płaszczyzną.
Dowolny zbiór punktów, z wyjątkiem kilku trywialnych przypadków, pozwala na więcej niż jedną metodę triangulacji. Istnieje jednak niezwykła właściwość: każda metoda triangulacji dla danego zbioru wyznacza tę samą liczbę trójkątów, co wynika z twierdzenia:
Twierdzenie o triangulacji zbioru punktów. Załóżmy, że zbiór punktów S zawiera n>3 punktów i nie wszystkie z nich są współliniowe. Dodatkowo i punkty z nich są wewnętrzne (tzn. leżą wewnątrz wypukłego kadłuba CH(S). Wtedy dowolna metoda triangulacji zbioru S da dokładnie n + i - 2 trójkątów.
Aby udowodnić twierdzenie, najpierw rozważymy triangulację punktów granicznych n-i. Ponieważ wszystkie są wierzchołkami wielokąta wypukłego, taka triangulacja da (n - i) - 2 trójkąty. (Nie jest to trudne do zweryfikowania, a ponadto można wykazać, że dowolna triangulacja arbitralny Wielokąt o boku m - wypukły lub niewypukły - zawiera m - 2 trójkąty). Sprawdźmy teraz co stanie się z triangulacją przy dodawaniu pozostałych i punktów wewnętrznych, po jednym za każdym razem. Twierdzimy, że dodanie każdego takiego punktu zwiększa liczbę trójkątów o dwa. Podczas dodawania punktu wewnętrznego mogą wystąpić dwie sytuacje, pokazane na ryc. 2. Po pierwsze, punkt może znajdować się wewnątrz jakiegoś trójkąta, a następnie taki trójkąt zastępuje się trzema nowymi trójkątami. Po drugie, jeśli punkt pokrywa się z jedną z krawędzi triangulacji, wówczas każdy z dwóch trójkątów sąsiadujących z tą krawędzią zostaje zastąpiony dwoma nowymi trójkątami. Wynika z tego, że po dodaniu wszystkich i punktów całkowita liczba trójkątów będzie wynosić (n - i - 2) + (2i), lub po prostu n + i - 2.
Ryż. 2
W tej części zaprezentujemy algorytm generowania specjalnego typu triangulacji, znanego jako triangulacja Delaunaya. Ta triangulacja jest dobrze zrównoważona w tym sensie, że utworzone trójkąty są zwykle równokątne. Na przykład triangulacja pokazana na ryc. 1a można przypisać typowi triangulacji Delaunaya, a na ryc. Triangulacja 1b zawiera kilka bardzo wydłużonych trójkątów i nie można jej przypisać typowi Delaunaya. Na ryc. Rysunek 3 przedstawia przykład triangulacji Delaunaya dla zbioru dużej liczby punktów.
Ryż. 3
Aby utworzyć triangulację Delaunaya, potrzebujemy kilku nowych definicji. Zbiór punktów uważa się za okrągły, jeśli istnieje okrąg, na którym leżą wszystkie punkty tego zbioru. Okrąg taki będzie opisany dla zadanego zbioru punktów. Okrąg opisany na trójkącie przechodzi przez wszystkie trzy jego (niewspółliniowe) wierzchołki. Mówi się, że okrąg będzie pozbawiony punktów w odniesieniu do danego zbioru punktów S, jeżeli wewnątrz okręgu nie ma punktów ze zbioru S. Jednakże punkty ze zbioru S mogą znajdować się na okręgu najbardziej bez punktów.
Triangulacja zbioru punktów S będzie triangulacją Delaunaya, jeśli okrąg opisany na każdym trójkącie jest wolny od punktów. Na schemacie triangulacyjnym rys. Rysunek 1a przedstawia dwa okręgi, które wyraźnie nie zawierają w sobie innych punktów (można narysować okręgi dla innych trójkątów, aby upewnić się, że są one również wolne od punktów zbioru). Zasada ta nie jest przestrzegana na schemacie na ryc. 16 - jeden punkt innego trójkąta mieści się w narysowanym okręgu, zatem ta grangulacja nie należy do typu Delaunay'a.
Można przyjąć dwa założenia dotyczące punktów zbioru S, aby uprościć algorytm triangulacji. Po pierwsze, aby triangulacja w ogóle istniała, musimy założyć, że zbiór S zawiera co najmniej trzy punkty i że nie są one współliniowe. Po drugie, aby triangulacja Delaunaya była jednoznaczna, konieczne jest, aby żadne cztery punkty ze zbioru S nie leżały na tym samym okręgu opisanym. Łatwo zauważyć, że bez takiego założenia triangulacja Delaunaya nie będzie jednoznaczna, gdyż 4 punkty na jednym opisanym okręgu pozwalają nam zrealizować dwie różne triangulacje Delaunaya.
Nasz algorytm działa poprzez ciągłe zwiększanie bieżącej triangulacji o jeden trójkąt na raz. Początkowo bieżąca triangulacja składa się z pojedynczej krawędzi powłoki; na końcu algorytmu bieżąca triangulacja staje się triangulacją Delaunaya. W każdej iteracji algorytm szuka nowego trójkąta, z którym się łączy granica bieżąca triangulacja.
Definicja granicy zależy od poniższy schemat klasyfikacja krawędzi triangulacji Delaunaya w odniesieniu do triangulacji bieżącej. Każda krawędź może być spanie, żywy Lub martwy:
- śpiące żebra: krawędź triangulacji Delaunaya jest uśpiona, jeśli nie została jeszcze wykryta przez algorytm;
- żywe żeberka: żebro jest żywe, jeśli zostanie znalezione, ale znany jest tylko jeden przylegający obszar;
- martwe żebra: Krawędź uważa się za martwą, jeśli zostanie znaleziona i znane są oba sąsiadujące obszary.
Początkowo jedyna krawędź należąca do płatka wypukłego i jest żywa - przylega do niej nieograniczona płaszczyzna, a wszystkie pozostałe krawędzie są uśpione. W miarę działania algorytmu krawędzie przechodzą od stanu uśpienia przez żywe do martwe. Granica na każdym etapie składa się z zestawu żywych krawędzi.
W każdej iteracji wybierana jest jedna z krawędzi granicy i poddawana jest ona obróbce, która polega na poszukiwaniu nieznanego obszaru, do którego należy krawędź e. Jeżeli obszar ten okaże się trójkątem f, zdefiniowanym przez punkty końcowe krawędzi e i jakiś trzeci wierzchołek v, wówczas krawędź e staje się martwa, ponieważ znane są już oba przylegające do niej obszary. Każda z dwóch pozostałych krawędzi trójkąta t zostaje przeniesiona do stanu: ze stanu uśpienia do stanu żywego lub ze stanu żywego do martwego. Tutaj zostanie wywołany wierzchołek v sprzężony z krawędzią e. W przeciwnym razie, jeśli nieznany obszar okaże się nieskończoną płaszczyzną, wówczas krawędź e po prostu umrze. W tym przypadku krawędź e nie ma wierzchołka sprzężonego.
Na ryc. Rysunek 4 przedstawia działanie algorytmu, gdzie akcja przebiega od góry do dołu, a chwała po prawej stronie. Granica na każdym etapie jest zaznaczona grubą linią.
Algorytm jest zaimplementowany w programie delaunayTriangulate. Program otrzymuje tablicę s składającą się z n punktów i zwraca listę trójkątów reprezentujących triangulację Delaunaya. Implementacja wykorzystuje klasę listy cyklicznej i klasy z sekcji Geometrycznej Struktury Danych. Klasą Dictionary może być dowolny słownik obsługujący wymagane operacje. Na przykład możesz zastąpić #define Dictionary RandomizedSearchTree .
Lista
granica(edgeCmp);
Krawędź *e = krawędź kadłuba(s, n);
Int EdgeCmp (Krawędź *a, Krawędź *b) ( if (a->org< b->org) zwróć 1;< b->if (a->org > b->org) zwróć 1;
jeśli (a->docel
det) zwraca -1;
if (a->dest > b->dest) zwraca 1;
zwróć 0; )
Funkcja updateFrontier edytuje słownik graniczny, w którym zmienia się stan krawędzi od punktu a do punktu b:
Ryż. 5< n; i++) if (s[i] < s[m]) m = i; swap(s, s[m]); for (m = 1, i = 2; i < n; i++) { int с = s[i].classify (s, s[m]); if ((c == LEFT) || (C == BETWEEN)) m = i; } return new Edge(s, s[m]); }
Unieważnij aktualizacjęFrontier (Słownik
&frontier, Punkt &a, Punkt &b) ( Edge *e = nowa krawędź (a, b); if (frontier.find (e)) frontier.remove(e); else ( e->flip(); frontier.insert( e);
Funkcja hullEdge znajduje krawędź kadłuba wśród n punktów w tablicy s. Ta funkcja faktycznie wykorzystuje etap inicjalizacji i pierwszą iterację metody pakowania prezentów:
Krawędź *hullEdge (Punkt s, int n) ( int m = 0; for (int i = 1; i 
Funkcja trójkąta po prostu generuje i zwraca wielokąt dla trzech punktów przekazanych jej jako parametry: 
Funkcja trójkąta po prostu generuje i zwraca wielokąt dla trzech punktów przekazanych jej jako parametry: 
Wielokąt *trójkąt (Punkt &a, Punkt &b, Punkt &c) ( Wielokąt *t = nowy Wielokąt; t->wstaw (a); t->wstaw (b); t->wstaw (c); return t; ) 
Modele GRID to modele regularnych komórek. 
.
,
Niech zostanie wprowadzony układ współrzędnych
I 
Funkcja trójkąta po prostu generuje i zwraca wielokąt dla trzech punktów przekazanych jej jako parametry: 
,
- siatka bitów.
- wartości skwantowane. Prawdziwy:
- parametr algorytmu – liczba punktów, 
- waga. Im bliżej punktu, tym większa waga.
- stopień odległości (1 lub 2).
Współczynnik normalizacyjny: 
Jak 
bliższa 1, tym więcej punktów o wyższych wagach jest branych pod uwagę.
Jest to metoda IDW - długa, dla każdego t konieczne jest znalezienie sąsiadów. Można sprawnie znaleźć zbiór sąsiadów - najbliższych. Każdy punkt tworzy „kołek” o określonej wysokości. Wiele zależy od nieregularności ustawienia punktu, za to biorą 
Lub 
te. podzielić na sektory i budować punkty w pobliżu.
Korzyść– prostota
Wada:
------Bilet 14. Model blaszany. Algorytmy triangulacji Delaunaya ------
1) Triangulacja (cyna).
Triangulacja– konstrukcja funkcji w postaci zbioru odcinkowo liniowych funkcji
Triangulacja– interpolacja w obszarze wypukłym.
Triangulacja– graf planarny, którego wszystkie krawędzie wewnętrzne są trójkątami; sposób przedstawienia przestrzeni w postaci trójkątów sąsiadujących ze sobą i niezachodzących na siebie. Triangulacja jest budowana na zbiorze punktów na kilka sposobów.
Do skonstruowania optymalnej triangulacji potrzebny jest algorytm.
Samolot przechodzący przez 3 punkty.
1) Znajdź trójkąt, który 
;
2)
- skonstruować równanie płaszczyzny.
Aby sprawdzić, czy punkty znajdują się wewnątrz trójkąta, czy nie, należy podstawić wartość do równania prostych - krawędzi trójkąta. Jeśli wszystkie 3 równania > 0, to wewnątrz.
Struktura prezentacji:
Każda triangulacja zawiera tę samą liczbę trójkątów.
, Gdzie 
– liczba punktów wewnętrznych, 
– liczba punktów.
Chciwa triangulacja.
Łączymy wszystkie punkty krawędziami, wybieramy minimum i dodajemy je do triangulacji. Następnie bierzemy kolejne minimum, które nie przecina się z poprzednimi itd. Rezultatem jest zachłanna triangulacja.
Triangulacja Delaunaya.
Środek okręgu opisanego na dowolnym trójkącie nie obejmuje punktów innych trójkątów. Jest zbudowany w jedyny sposób.
Flip to przeniesienie krawędzi. Umożliwia przejście od konwencjonalnej triangulacji do triangulacji Delaunaya. Aby sprawdzić, czy punkt należy do okręgu: podstaw if< R, то внутри.
Warunek Delaunaya.
Równanie okręgu przechodzącego przez trzy punkty:
Jeśli jest mniejszy od zera, to zewnętrzny, w przeciwnym razie - wewnętrzny.
– Warunek Delaunaya.
Algorytm konstruowania triangulacji Delaunaya:
1) Dodawanie kropek w trakcie badania– prosty algorytm iteracyjny:
Jest zestaw 
dodaj do trójkąta, konstrukcja jest wykonywana 
podział trójkąta 
odbudowa. Na etapie zerowym dodajemy 3-4 fikcyjne punkty, które oczywiście zakrywają naszą obwiednię, wszystkie punkty znajdujące się w środku. Następnie rzucamy punkt, patrzymy, w który trójkąt uderza, dzielimy go na 3, dla każdego trójkąta sprawdzamy warunek Delaunay'a i wykonujemy odwrotne przeniesienie krawędzi. Średnia liczba zmian pasa ruchu wynosi trzy.
Złożoność teoretyczna 
2) Metody przyspieszania. Na podstawie statystycznie zależnych punktów. Trójkąt nasienny to trójkąt, w który spadł poprzedni punkt. Następnie łączymy dwa punkty - poprzedni i nowy.
Przechodzimy od pierwszego punktu do drugiego.
