9990200026

2. Podstawy teoretyczne 18

Uzyskuje się w ten sposób przyspieszenia w układzie lokalnym. Przeliczenie wartości przyspieszeń z układu lokalnego na globalny wygląda następująco:

^axg		CyCZ	CzSySx — cxsz CxCzSy + sxsz		ax
^ayy	-	CySz	CXCZ + SySxSz CxSySz — CZSX		^ay
°zg.		~^sy	CySX CyCX		az

gdzie s_x — sin 03, c_x — cos 9_X itp.

Dysponując przyspieszeniem w układzie globalnym, można wyznaczyć prędkość oraz przemieszczenie w tym układzie, stosując kolejne całkowania.

V = f(a)dt    (2.28)

S = J(V)dt    (2.29)

2.10 Triangulacja Delone

Jedną z metod interpolacji wysokości jest triangulacja. Dany na płaszczyźnie zbór punków łączy się odcinkami, dzieląc ich otoczkę wypukłą na trójkąty. Po dodaniu informacji o wysokości każdego z punktów otrzymuje się przybliżenie ukształtowania terenu w postaci funkcji ciągłej przedziałami liniowej. Istnieje pewna skończona liczba możliwych triangulacji jednego zbioru punktów. W celu najlepszego przybliżenia ukształtowania terenu należy unikać tworzenia wąskich dolin. Można to osiągnąć, maksymalizując wartości kątów w grafie. Uporządkowany niemałejąco ciąg wszystkich kątów tworzących triangula-cję nazywa się jej wektorem kątów. Triangulacja danego zbioru punktów o wektorze kątów leksykograficznie największym nazywana jest legalną i jest triangulacją Delone.

Triangulacja złożona z trójkątów PiPjPk i PiPjPr jest nielegalna, jeżeli punkt pk leży wewnątrz okręgu opisanego na PiPjPr■ Wtedy też krawędź pip] nazywana jest nielegalną. W celu uczynienia triangulacji legalną, należy zastąpić krawędź pip] przez pip]. Na potrzeby tej pracy założono, że nie wystąpi przypadek, w którym cztery punkty położone są na jednym okręgu (wtedy nie byłoby możliwe jednoznaczne wskazanie triangulacji Delone).

Zaimplementowano przyrostowy algorytm 1 triangulacji Delone zaczerpnięty z pozycji |4|. Przyjęto zaproponowany tam sposób postępowania w przypadku, kiedy wstawiany punkt znajduje się w trójkącie o ujemnym wierzchołku. Kolejne punkty dodawane są na bieżąco, dlatego nie losuje się początkowej permutacji.