Dom Jama ustna Metoda pustej kuli Delaunaya. Konstrukcja w ogólnym przypadku

Jama ustna

Metoda pustej kuli Delaunaya. Konstrukcja w ogólnym przypadku

20 sierpnia 2012 o 22:41

Optymalizacja algorytmu sprawdzania warunku Delaunaya poprzez równanie okręgu opisanego i jego zastosowanie

Zdradzę Ci sekret jak szybko sprawdzić warunek Delaunaya dla dwóch trójkątów.
Właściwie samą optymalizację opisano nieco niżej (patrz „Optymalizacja algorytmu sprawdzania warunku Delaunaya za pomocą równania opisanego na okręgu”), ale opowiem ci o wszystkim po kolei.

W moim przypadku triangulacja jest używana w śledzeniu obrazu w celu podzielenia płaszczyzny na prymitywne sektory (trójkąty). Jak wiadomo, dzieli się on również na kilka etapów: dostosowanie, identyfikowanie granic, obchodzenie granic, zamiatanie konturów. To jest w samym ogólna perspektywa. Myślę, że naprawdę chciałbym przestać trudny etap: zamiatanie samolotu.

Przy wejściu

Po wykryciu i przekroczeniu granic otrzymałem na wyjściu wiele zewnętrznych pętli. Każdy dotykający kontur ma różne kolory. Każdy taki obwód zawiera również znaną liczbę obwodów wewnętrznych.
Zatem z punktu widzenia „omiatania płaszczyzny”, jeśli osobno rozważymy kontury zewnętrzne, mamy zbiór punktów, z których każdy ma jednego sąsiada po prawej i lewej stronie. Te. wszystkie punkty są zamknięte w łańcuch, nie ma ani jednego punktu „wiszącego”, a każdy łańcuch zawiera co najmniej 3 punkty (ryc. 1).

Obrazek 1

Co trzeba zrobić

Musisz pokryć figurę trójkątami.

Szukaj

Po przeczytaniu książki nie znalazłem ani jednej (przynajmniej jednej) metody konstruowania triangulacji Delaunaya, która byłaby choć w pewnym stopniu odpowiednia dla mojego przypadku. Nie szukałam innych książek. I to wystarczyło, uporządkowało myśli w mojej głowie. W rezultacie wymyślił własny „rower”.

Algorytm

1) Załóżmy na początek, że na rozważanym rysunku występuje tylko jedna sekwencja. Potem wszystko sprowadza się do sekwencyjnego brania trójkątów. Bierzemy dowolny punkt i próbujemy zbudować trójkąt z sąsiadującymi punktami. Jeżeli nie udało się zbudować trójkąta (linia łącząca te dwa punkty przecina się z już zbudowanymi lub linia przechodzi w strefie wykluczenia (rys. 2), przechodzimy do kolejnego punktu, powiedzmy w prawo. Kiedy następny trójkąt zostanie znaleziony, dodajemy go do listy (rysunek 3) i usuwamy punkt, z którego został zbudowany (rysunek 4).

Rysunek 2

Rysunek 3

Rysunek 4

Jeszcze jedno: zapisując kolejny trójkąt należy zapisać wierzchołki w ruchu zgodnym z ruchem wskazówek zegara (w prawym układzie współrzędnych). Przyda się to w przyszłości, aby zmniejszyć zasoby obliczeniowe.

2) Powtarzaj krok 1, aż ominiemy całą płaszczyznę.

3) Jeśli jest kilka sekwencji, tj. jeden, a wewnątrz niego znajduje się jeden lub więcej konturów wewnętrznych (ryc. 1). Tutaj należy rozważyć każdą sekwencję osobno. Weźmy kolejny kontur wewnętrzny. Z jednego zewnętrznego i jednego wewnętrznego wykonamy dwa pojedyncze obwody. Aby to zrobić, musisz znaleźć dwa „porty” z jednego obwodu do drugiego. Warunek dla „portów”: nie powinny one się ze sobą przecinać (nawet ich końce nie powinny się stykać) i nie powinny przecinać się z liniami konturowymi (rys. 5).

Rysunek 5

Rysunek 6
4) Następnie należy wprowadzić po kolei wszystkie ciągi wewnętrzne do już utworzonych, oddzielonych od siebie ciągów (punkt 3). Musisz połączyć go z tym, który zawiera nowy. Z definicji żaden ciąg wewnętrzny nie styka się ani nie przecina z innymi (zarówno zewnętrznym, jak i wszystkimi możliwymi wewnętrznymi), więc wszystko przebiegnie gładko.
Po znalezieniu portów (rysunek 6) łatwo jest skonstruować nowe ciągi i ominąć je wykorzystując punkty 1 i 2 aktualnego algorytmu (rysunek 7).

Rysunek 7

5) Po czwartym etapie mamy listę trójkątów (Rysunek 8). To tak, jakby zadanie zostało już wykonane, ale pozostaje tylko upiększyć obraz: sprawdź, czy spełniony jest warunek Delaunaya (rysunek 9).

Cyfra 8

Rysunek 9

6) Patrząc w przyszłość, opowiem Ci o szóstym punkcie. Polega na sekwencyjnym przeglądaniu listy uzyskanych trójkątów za pomocą kroku nr 5. Najpierw zaznaczamy wszystkie trójkąty jako „brudne”. W każdym cyklu sprawdzamy warunek Delaunaya dla każdego trójkąta. Jeśli warunek nie jest spełniony, to odbudowujemy i oznaczamy sąsiadów oraz bieżący trójkąt jako „brudny”. Jeśli warunek jest spełniony, oznaczamy go jako czysty. W mojej implementacji algorytmu każdy trójkąt ma połączenie z sąsiadami. W tym przypadku najszybciej działa punkt 6.

Więcej o piątym etapie

Teraz, o ile wiem, są dwa możliwe sposoby ustal, czy trójkąty spełniają warunek Delaunaya, czy nie: 1) Sprawdź sumę przeciwległych kątów. Musi być mniejsza niż 180. 2) Oblicz środek opisanego okręgu i oblicz odległość do 4. punktu. Wszyscy wiedzą, że warunek Delaunaya jest spełniony, jeśli punkt znajduje się poza okręgiem opisanym.

Moc obliczeniowa nr 1: 10 mnożenia/dzielenie i 13 dodawania/odejmowania.
Moc obliczeniowa nr 2: 29 operacji mnożenia/dzielenie i 24 operacje dodawania/odejmowania.

Z punktu widzenia mocy obliczeniowej, która jest wyliczana np. w książce, opcja nr 1 jest bardziej opłacalna. Zaimplementowałbym to, gdyby nie... (Rysunek 10). Jak się okazało po produkcji Ta metoda na „przenośnik taśmowy”, efektem była niepewność. Jest to opcja, gdy sam kąt A jest większy niż 180 stopni. Jest ona uważana w książce za jedną z indywidualnych metod prywatnych. A wraz z tym znika cała jego elegancja, przejrzystość i wydajność. I później okazało się, że metodę nr 2 można bardzo znacząco zoptymalizować.

Rysunek 10

Optymalizacja algorytmu sprawdzania warunku Delaunaya poprzez równanie okręgu opisanego

Następna jest czysta matematyka.

Więc mamy:
Sprawdzanie warunku dla punktu M(X, Y) za pomocą równania okręgu przechodzącego przez punkty A(x1, y1), B(x2, y2), C(x3, y3) można zapisać jako:

(a ⋅ (X^2 + Y^ 2) - b ⋅ X + do ⋅ Y - d) ⋅ znak a ≥ 0

Szczegóły można znaleźć w znakomitej książce. (Nie, nie jestem autorem)
Zatem znak a jest znakiem kierunku przejścia, od samego początku budowałem trójkąty zgodnie z ruchem wskazówek zegara, więc można go pominąć (jest równy jedności).

A(x1 - X, y1 - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);

D>=0

Rysunek 11

Proste, prawda?

Jak wynika z książki, ponownie

(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)* (y1*x2 - x1*y2)<= 0

Mamy: 15 operacji mnożenia/dzielenie i 14 operacji dodawania/odejmowania.

Dziękuję za uwagę. Czekam na krytykę.

Bibliografia

1. Skvortsov A.V. Triangulacja Delaunaya i jej zastosowanie. – Tomsk: Wydawnictwo Tom. Uniwersytet, 2002. – 128 s. ISBN 5-7511-1501-5

Modele GRID to modele regularnych komórek.

Niech zostanie wprowadzony układ współrzędnych
I I
. Zestawy użytkownika
i etapy pobierania próbek
.

- współrzędne fizyczne punktu.

Obliczamy
I
,
- 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,
- ilość 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 konstrukcji 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.

20 sierpnia 2012 o 22:41

Optymalizacja algorytmu sprawdzania warunku Delaunaya poprzez równanie okręgu opisanego i jego zastosowanie

Przetwarzanie obrazu ,
Programowanie

W moim przypadku triangulacja jest używana w śledzeniu obrazu w celu podzielenia płaszczyzny na prymitywne sektory (trójkąty). Jak wiadomo, dzieli się on również na kilka etapów: dostosowanie, identyfikowanie granic, obchodzenie granic, zamiatanie konturów. To tak w najbardziej ogólnym ujęciu. Chciałbym zatrzymać się, jak sądzę, na najtrudniejszym etapie: zamiataniu samolotu.

Przy wejściu

Po wykryciu i przekroczeniu granic otrzymałem na wyjściu wiele zewnętrznych pętli. Każdy stykający się kontur ma inny kolor. Każdy taki obwód zawiera również znaną liczbę obwodów wewnętrznych.
Zatem z punktu widzenia „omiatania płaszczyzny”, jeśli osobno rozważymy kontury zewnętrzne, mamy zbiór punktów, z których każdy ma jednego sąsiada po prawej i lewej stronie. Te. wszystkie punkty są zamknięte w łańcuch, nie ma ani jednego punktu „wiszącego”, a każdy łańcuch zawiera co najmniej 3 punkty (ryc. 1).

Obrazek 1

Co trzeba zrobić

Musisz pokryć figurę trójkątami.

Szukaj

Algorytm

Rysunek 2

Rysunek 3

Rysunek 4

2) Powtarzaj krok 1, aż ominiemy całą płaszczyznę.

Więcej o piątym etapie

O ile mi wiadomo, istnieją dwa możliwe sposoby ustalenia, czy trójkąty spełniają warunek Delaunaya, czy nie: 1) Sprawdź sumę przeciwległych kątów. Musi być mniejsza niż 180. 2) Oblicz środek opisanego okręgu i oblicz odległość do 4. punktu. Wszyscy wiedzą, że warunek Delaunaya jest spełniony, jeśli punkt znajduje się poza okręgiem opisanym.

Moc obliczeniowa nr 1: 10 mnożenia/dzielenie i 13 dodawania/odejmowania.
Moc obliczeniowa nr 2: 29 operacji mnożenia/dzielenie i 24 operacje dodawania/odejmowania.

Z punktu widzenia mocy obliczeniowej, która jest wyliczana np. w książce, opcja nr 1 jest bardziej opłacalna. Zaimplementowałbym to, gdyby nie... (Rysunek 10). Jak się okazało, po nałożeniu tej metody na „przenośnik” pojawiła się niepewność. Jest to opcja, gdy sam kąt A jest większy niż 180 stopni. Jest ona uważana w książce za jedną z indywidualnych metod prywatnych. A wraz z tym znika cała jego elegancja, przejrzystość i wydajność. I później okazało się, że metodę nr 2 można bardzo znacząco zoptymalizować.

Rysunek 10

Optymalizacja algorytmu sprawdzania warunku Delaunaya poprzez równanie okręgu opisanego

Następna jest czysta matematyka.

Więc mamy:
Sprawdzanie warunku dla punktu M(X, Y) za pomocą równania okręgu przechodzącego przez punkty A(x1, y1), B(x2, y2), C(x3, y3) można zapisać jako:

(a ⋅ (X^2 + Y^ 2) - b ⋅ X + do ⋅ Y - d) ⋅ znak a ≥ 0

A(x1 - X, y1 - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);

D>=0

Rysunek 11

Proste, prawda?

Jak wynika z książki, ponownie

(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)* (y1*x2 - x1*y2)<= 0

Mamy: 15 operacji mnożenia/dzielenie i 14 operacji dodawania/odejmowania.

Dziękuję za uwagę. Czekam na krytykę.

Bibliografia

1. Skvortsov A.V. Triangulacja Delaunaya i jej zastosowanie. – Tomsk: Wydawnictwo Tom. Uniwersytet, 2002. – 128 s. ISBN 5-7511-1501-5

Podstawowe definicje i właściwości

Triangulacja to graf planarny, którego wszystkie obszary wewnętrzne są trójkątami.

Nieruchomoś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 skonstruowania triangulacji z danego zbioru punktów dwuwymiarowych to problem połączenia danych punktów nie przecinającymi się odcinkami, tak aby powstała 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 ogólnym przypadku

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 zatem pustą kulę Delaunaya w układzie punktów (A). 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 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 nakładania się 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 normalnych punktach, które służą do określenia zachowania się 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śli 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 jeden taki wierzchołek może być znalezionym. 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 domeną prostokątną w celu wyznaczenia parametrów.Dzielimy dziedzinę definiowania parametrów powierzchni na prostokątne komórki z dwuwymiarowymi liniami.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 rozpatrywać jako 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, leżała 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 granicy AB i sprawdźmy, czy odcinki BV i VA nie przecinają pozostałych krawędzi granicy. 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żeli odcinek lub VA przecina inne krawędzie granicy, to przechodzimy do poszukiwania najbliższego wierzchołka dla kolejnej 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. 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ń z obszaru roboczego punkt O. 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 punktów dwuwymiarowych 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 istnieje możliwość zawężenia w nim obszaru roboczego 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 oraz pomiędzy punktami O i C obszaru roboczego wstawmy punkty wielokąta wewnętrznego, zaczynając od punktu F, a kończąc na punkcie E. W ten sposób przełamiemy obszar roboczy na odcinku OS, przełamiemy wielokąt wewnętrzny na odcinku EF i połączyć je z odcinkami OF i UE.

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).