Rovinné triangulace a jejich využití. Greedy Triangulation. Delaunay Triangulation. Constrained Delaunay Triangulation. Data Dependent Triangulation. DMT Tomáš Bayer | bayertom@natur.cuni.cz Katedra aplikované geoinformatiky a kartografie. Přírodovědecká fakulta UK. Rovinné triangulace a jejich využití. Obsah přednášky Ukázka použití Q Formulace problému O Vlastnosti triangulací Q Greedy triangulace Q Delaunay triangulace • Metoda inkrementální konstrukce • Metoda inkrementálního vkádání Q Triangulace se vstupní podmínkou Q Datově závislé triangulace • Lokální optimalizace triangulace O Digitální model terénu • Polyedrický model terénu • Lineární nterpolace vrstevnic • Analýza sklonu • Analýza orientace Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 2 /125 Ukázka použití 1. Tvorba digitálního modelu terénu Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a 2. Formulace problému Dáno: Množina bodů P = p2,Pn} v IR2. Hledáme: Triangulaci T nad množinou P. Definice: Triangulace T nad množinou bodů P představuje takové planární rozdělení, které vytvoří soubor m trojúhelníků t = {ři, fe,tm} a hran tak, aby platilo: • Libovolné dva trojúhelníky ti, ŕy G T, (/ 7^ y), mají společnou nejvýše hranu. 9 Sjednocení všech trojúhelníků t G T tvoří'H(P). 9 Uvnitř žádného trojúhelníku neleží žádný další bod z P. Vztah mezi počtem bodů n, hran rih a trojúhelníků nt v rovině pro T nh = 3n — 3 — /c, nř = 2n 2 k. k počet bodů ležících na H(P): Odhad pouze funkcí n nh < 3n- 6, nt < 2n 5. Formulace problému 3. Použití triangulací Nejčastější aplikace triangulací: • Kartografie & GIS: tvorba digitálních modelů terénu (DMT). • Zpracování obrazu: segmentace, rozpoznávání vzorů. • DPZ: tvorba prostorových modelů z dat laserového skenování. • Počítačová grafika: vizualizace prostorových dat ve scénách. • FEM (tzv. metoda konečných prvků): analýza vlastností a struktury materiálů, simulace. • Kartografická generalizace. • Plánování pohybu robotů: vozítka na Marsu. • Modelování přírodních jevů: eroze. • Interpolační techniky: převod bodových jevů na plošné • Biometrie: detekce otisků prstů. Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 5 /125 Formulace problému 4. Rekonstrukce terénu z dat leteckého laserového skenování Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 6/125 Formulace problému 5. Aplikace triangulací v biometrii Detekce otisků prstů (Bebis et al., 2000) a? Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 7/125 Vlastnosti triangulací 6. Požadavky na triangulaci T Požadavky na triangulační algoritmus: • Jednoduchost algoritmu, snadná implementace. • Dostatečná rychlost pro velká P (n > 1E6) bodů, požadavek na 0(n • log(n)) algoritmus. • Malá citlivost na singulární případy, kdy T není jednoznačná (popř. ji nelze provést). • Převod do vyšších dimenzí. • Schopnost paralelizace algoritmu. • Optimální tvar trojúhelníkové sítě. Některé body v kontrastu: jednoduchost implementace x rychlost. Triangulační algoritmy patří mezi jedny z nejvíce teoreticky rozpracovaných postupů. Rovinné triangulace a jejich využití. 8 /125 Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Vlastnosti triangulací 7. Volba triangulace a jejich dělení Při výběru triangulace T nutno zohlednit: Tvar trojúhelníků: Triangulace by měla produkovat pravidelné trojúhelníky vhodných tvarů (blížící se rovnostranným). Kritérium je důležité při tvorbě DMT, trojúhelníková síť se musí co nejvíce přimykat k terénu. Povinné hrany: Schopnost vkládat povinné hrany a modifikovat tvar triangulace. Ovlivnění tvaru terénu, vkládání kosterních čar, tj. hřbetnic, údolnic, spádnic. Triangulace nekonvexní oblasti: Schopnost triangulace nekonvexní oblasti či oblasti obsahující díry. V mapách nejsou triangularizovány některé oblasti, např. vodní plochy, budovy. Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Vlastnosti triangulací 8. Ukázka triangulace nekonvexní oblasti obsahující díry Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Vlastnosti triangulací 9. Dělení triangulací Dělení triangulací dle geometrické konstrukce: • Greedy triangulace. • Delaunay triangulace. • MWT (Minimum Weight Triangulation). • Constrained triangulace (triangulace s povinnými hranami) • Datově závislé triangulace. Dělení triangulací dle použitých kritérií: • Lokálně optimální triangulace. • Globálně optimální triangulace. • Multikriteriálně optimalizované triangulace. Vlastnosti triangulace T se posuzují ve vztahu k těmto kritériím. Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 11 /125 Vlastnosti triangulací 10. Lokálně vs. globálně optimální triangulace Lokálně optimální triangulace T: Každý čtyřúhelník tvořený dvojicí trojúhelníků se společnou stranou triangularizován optimálně vzhledem k zadanému kritériu. Pro množinu P existuje více lokálně optimálních triangulací, každá z nich optimalizuje jiné kritérium. Globálně optimální triangulace T Všechny trojúhelníky triangulace T optimální vzhledem k zadanému kritériu. Neexistuje jiná triangulace T', která by dosáhla alespoň u jednoho trojúhelníku lepší hodnoty posuzovaného kritéria. Globálně optimální triangulace je současně lokálně optimální. Multikriteriálně optimalizované triangulace T: Kombinace několika lokálních či globálních kritérií. Vycházejí z Delaunay triangulace, která je optimalizována k těmto kritériím. Dlouhé výpočetní časy, doposud nejsou známy efektivní algoritmy, použití genetických algoritmů. Rovinné triangulace a jejich využití. 12 /125 Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Vlastnosti triangulací 11. Hodnocení triangulace Množina bodů P = {pí, p2, P3, Pa}-M Pí £ H, konvexní čtyřúhelník. Pak dle Eulerovy věty pro n = 4, k = 4 platí:/?/? = 5, nř = 2. Důsledek: existují dvě různé triangulace T(P) a T'(P): T{P) = {ři(Pi,fl2JP3)Jř2(piJp3jP4)}J = {ří(Pl,P2,P4), Í2(P2,P3,P4)}. Vhledem k posuzovanému kritériu je jedna z triangulací optimální, tj. minimalizuje ho. Tato pravidla lze zobecnit pro n > 4, triangulace se tak ke každé dvojici trojúhelníků. a? Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 13/125 Vlastnosti triangulací 12. Ilustrace T{P)aT'{P) Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 13. Lokální kritéria Mají geometrický podtext, snaha o generování trojúhelníků "rozumných" tvarů. Přehled nejčastěji používaných lokálních kritérií: • Minimální/maximální úhel v trojúhelníku a. • Minimální/maximální výška v trojúhelníku v. • Minimální/maximální poloměr vesané kružnice r. • Minimální/maximální poloměr opsané kružnice Ft. • Minimální/maximální plocha trojúhelníku S. • Úhel mezi normálami sousedních trojúhelníků. Nejčastěji používáno první kritérium (Delaunay triangulace maximalizuje minimální úhel). Kritérium úhlu mezi normálami používáno u datově závislých triangulací. Od každého kritéria dispozici min-max varianta či max^min^/arianta.: Rovinné triangulace a jejich využití. 15/125 Vlastnosti triangulací 14. MIN/MAX strategie Vrcholy konvexního 4-úhelníku P = {p,, py, p/<, p/} T(p) = {HPhPi,Pj),HPhPj,Pk)}, T'{P) = {t{(pi,pi,Pk),t2ÍPi,Pj,Pk)}' Min-max kritérium: Výpočet maximálni hodnoty c nad T(P) i T'{P) c = maxíc), c' = maxíc'). Minimalizace maximální hodnoty kritéria c v triangulaci ÍT(P), č<č', r = \r(p) c > c'. Max-min kritérium: Výpočet minimální hodnoty c nad T(P) i T'(P) c = miníc), c' = miníc/Y Minimalizace maximální hodnoty kritéria c v triangulaci ÍT(P), c > c', T = 5 _ — _ • \r'(p), c tvarově nevhodné. Min-max kritérium: Eliminace trojúhelníků s příliš tupými úhly a = max(a). ot = maxía'). q- v 7 q-r v 7 Minimalizace maximálního úhlu v triangulaci r = ÍT(P), ä < a, \r(py a > a1. Max-min kritérium: Eliminace trojúhelníků s příliš ostrými úhly a = min(a), a = min(c/). r rx Minimalizace maximálního úhlu v triangulaci j = JT(P), a > a7: a < a . Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 17/125 Vlastnosti triangulací 16. Globální kritéria Optimalizují geometrické parametry všech trojúhelníků v triangulaci T(P). Nejčastěji používaná kritéria: Suma délek stran: Minimalizace celkovou délky hran hf triangulace T(P) MWT (Minimum Weight Triangulation), NP problém. Přibližné řešení: genetické algoritmy, Greedy triangulace. Povinné hrany: Předem definované hrany uvnitř triangulace, tzv. Constrained Triangulation. T(P) není lokálně optimální. Zadání charakteristických hran terénních tvarů, lepší aproximace terénu. hj = min. /=1 □ Rovinné triangulace a jejich využití. 18/125 Greedy triangulace 17. Greedy triangulace Patří do skupiny hladových algoritmů (Greedy Algorithms) W(T(P)) En* = mm /=1 kde T(P(n)) = T(P(n-1)) + AT, = arg min V/7/G/7\/7[l],...,\^[n_1] (IWIz) • Vlastnosti triangulace: Pokud se v P nevyskytují hrany se stejnou délkou, je triangulace jednoznačná. Snaží se však vytvářet trojúhelníky s nejkratšími stranami. Ttrojúhelníky nemusí splňovat žádnou speciální geometrickou podmínku. Jednoduchá implementace. Složitost je 0(n3), lze optimalizovat na 0(n2 • log(n)). Důsledek: Síť trojúhelníků není z tvarového hlediska optimalizována, Do triangulace tak mohou být přidány tvarově nevhodné trojúhelníky. V kartografii není příliš často používána. Výsledná triangulace se blíží MWT. □ Rovinné triangulace a jejich využití. 19/125 Greedy triangulace 18. Algoritmus Greedy triangulace Využití prioritní fronty PQ. Algoritmus 1: Greedy Triangulation (S, T) 1: PQ = 0 2:forVp/5 i e 3: fory e (/ + 4: Vytvor hranu /? = (p,, py). 5: PQ<- (||ft||, ft). 6: T ^ Q.pop(). 7: while PQ not empty: 8: /? =PQ.pop() 9: intersect = false 10: forVfyeT: 11: if (A? n A?/ ^ 0) 12: intersect = frx/e 13: break: 14: if (!intersect) T 5 ^) (V Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 20/125 Greedy triangulace 19. Grafické znázornění Greedy triangulace Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Delaunay triangulace 20. Delaunay triangulace VT a její vlastnosti Nejčastěji používaná triangulace, v oblasti GIS de-facto standart. Existuje v R2 i v R3. V1: Uvnitř kružnice k opsané libovolnému trojúhelníku řy G VT neleží žádný jiný bod množiny P. V2: VT maximalizuje minimální úhel v\/t, avšak VT neminimalizuje maximální úhel v t. V3: VT je lokálně optimální i globálně optimální vůči kritériu mnimálního úhlu. V4: VT je jednoznačná, pokud žádné čtyři body neleží na kružnici. Výsledné trojúhelníky se při porovnání ze všemi známými triangulacemi nejvíce blíží rovnostranným trojúhelníkům. i Rovinné triangulace a jejich využití. 22 /125 Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Delaunay triangulace 21. Ukázka VT Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Delaunay triangulace 22. Srovnání QT aVT Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Delaunay triangulace 23. Geometrické vlastnosti VT Nechť k je kružnice / přímka protínající k v bodech a, b, a p, q, r, s jsou body ležící na stejné straně od /. Platí: Zarb > Zapb = Zaqb > asb. Důsledek Thaletovy věty. Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Delaunay triangulace 23. Souvislost VT a H Projekce P na paraboloid. Konstrukce H(P). Projekce H(P) do roviny. Project onto paraboloid Compute lower convex hull Project hull laces back to plane Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Delaunay triangulace 24. Nejmenší opsaná kružnice Generuje Delaunay trojúhelník nejmenší opsanou kružnici /c(S, rmin)? Lze použít jako alternativní kritérium? Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. < = ► 27/125 Delaunay triangulace 25. Který z bodů splňuje podmínku DT (1/2) pI o Pl Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 26. Který z bodů splňuje podmínku DT (2/2)? Pozor: pf e k{phphp]), ale p) £ k(phpj,pf), ačkoliv ^ < r2! < □ ► < rS1 ► < ^ ► < ^1 ► ^ -O 27. Důsledek Korektní bod p/ nemusí generovat kružnici /c(S, rmin) Preferováno řešení v pravé polorovině před levou -r, S G Gr, r, S G a/.. Nutno testovat, ve které polorovině střed S leží. Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Delaunay triangulace 28. Edge Flip, legalizace Vrcholy konvexního 4-úhelníku P = {p/,Py,P/c,P/}, P G H(P). £>T(P) = {ři(P/,P/,P/c),ři(/,Py,P/c)}, DT'(P) = {fí(P/,P/,Py), £(P/,Py,P*)}« Edge Flip (Swap) Přechod £>T(P) =>DT'(P), prohození diagonály (p/c,P/) (P/,Py). Trojúhelníky t[(phphpk), ť2{phphpk) legální. Jsou lokálně optimální vzhledem k max-min kritériu. Poloměry opsaných kružnic k^^,^), /c(S2, r2) a ^í(sí> rí)> ^(S2; r2) r[, /53 + /?4. Vniřní úhly v trojúhelníkách, VT'(P): Q1, č*2, /?3, /?4, /Si + «4, ^2 + Qí3. Pro každý úhel po swapu existuje nejméně jeden menší před swapem Q1 > Qí2 > /?2, /?3 > «3, /?4 > «4, /?1 + «4 > «4, /?2 + «3b> Qqgi , Delaunay triangulace 31. Nejednoznačnost DT Pokud body {p„ ph pkj p,} na kružnici k(S, r), pak VT{P) = VT\P\ Vnitřní úhly v trojúhelníkách, VT(P)'. CZ\ + Qí2, Oí3, Q4, Qi , Oí2 Vnitřní úhly v trojúhelníkách, VT'(P)\ Q1 , Q2? <^35 ^ + Q4: Pi Oí3 + CK4. Oí2 + <^3- Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 34/125 Delaunay triangulace 32. Test legality, opsaná kružnice Kružnice k{&,pz,pz), kde & =[x^,y^],pz = [x2,y2], P3 = [x3,Yz]-Analyzovaný bod p = [x, y]. Předpoklad: body pí, P3 mají CW orientaci. Testovací kritérium ť. t = x y x2 + y2 x\ yi x\ + jf x2 y2 *f + y2 X3 73 4 + ň 'ŕ>0, P<£k, ) t = o, P e <9/c, ^ŕ<0, P e k. Průmyslový test, pouze +, -, *. Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 35 /125 Delaunay triangulace 33. Uhly ve čtyřúhelníku (1/2) n+a P. Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a a + ß = a + 7T — a — TT. Rovinné triangulace a jejich využití. 36/125 Delaunay triangulace 34. Uhly ve čtyřúhelníku (2/2) Legální vs nelegální triangulace a + ß { = Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a < 7T, DT(P) je legální, 7T, Body p/, py, p/c, pi leží na kružnici, > 7T, DT(P) je nelegální. Rovinné triangulace a jejich využití. 37/125 35. Test legality, úhly Numericky robustní test ověřující legalitu dvojice trojúhelníků U (p,, py, pk) a t2(piPj, pi). Nelegální swap sin(a + f3) = cos a sin f3 + cos /3 sin a < sin(7r). kde cos a = sfk + sfk sfj ZSjkSjk cos /3 = 4 + sJi ~ sl ŽSjíSji Delaunay triangulace 36. Test legality, odvození Dosazení Pak 2 cos a cos2 (3 ((x, - xk)(xj - xk) + (y - yk)(yj - yk)f ((x/ - xky + (y - yky)((Xj - Xky + (y - Yky) ((x, - xi)(xj - x,) + (y - y/)(y - y/))2 ((x, - x,)2 + (y - y/)2)((Xy - x,)2 + (y - y,)2) * 2 ? sin a = 1 — cos a sin /3 = 1 — cos2 ß = - //) + Xjjyj - yk) + Xj(yk - yj)f ((x/ - x,)2 + (y/ - y*)2)((*y - *02 + (// - y*)2) (*/(yy - y) + *y(y - y) + */(// - y/))2 ((x/ - x/)2 + (y - y/)2)((xy - x/)2 + (y - yif)' Vyjádříme sin a, sin f3, cos a, cos f3 a dosadíme do swapovací podmínky. Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 39/125 Delaunay triangulace 37. Test legality Podmínka přejde do tvaru (xjkXjk + yikyjk){xjiyu - xayji) + (xjkyik - xikyjk)(xjiXn + yy/y//) [(4 + yfk)(xfk + >£)(xf + xf)(xf + xf )]V2 < 0. Jmenovatel vždy kladný. Swapujeme, pokud (xikXjk + yikyjk){xjiyn - xayji) < (xjkyik - Xjkyjk)(xjiXji + yy,y/,), kde X* = X/ - xk y\k = y i -y/c, Xyfr = Xy - xk yjk = yy -y/c, Xy/ = Xj - x, y/ = yy -y, Xu = X, - x, y/ = y -y- Test numericky stabilní, pouze + Průmyslový standard. Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a * 5 5 Rovinné triangulace a jejich využití. 40 /125 Delaunay triangulace 38. Datový model triangulace Datová struktura používaná při konstrukci VT, uchovává topologii trojúhelníků v VT. Nechť dva incidující trojúhelníky ŕ/, tj G VT se společnou e,y G ŕ/ a e,, G ry. Strany trojúhelníků: Každá strana e,y v trojúhelníku t, v CCW orientaci uchovává: • pointer na následující hranu e,+i j v ŕ,. • pointer na stranu ey, v incidujícím trojúhelníku ŕy Strany ležící na 1-L mají pointer inicializovaný na NULL). Kromě stran na 1-L každá e popsána dvakrát (jako e\j a ey/). Strany e,y a ey, mají opačnou orientací. Tyto zdvojené strany nazývány Twin Edges. Trojúhelníky: Každý trojúhelník ŕ, popsán trojicí hran (e,y, e/+i,y, e/+2,y), CCW orientace. Tvoříkruhový seznam (Circular List). Pro každou hranu lze snadno nalézt předcházející/následující hranu a incidující trojúhelníky. Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a 41/125 Delaunay triangulace 39. Ukázka datového modelu Delaunay triangulace 40. Metody konstrukce VT Metody přímé konstrukce VT'. • Lokální prohazování. • Inkrementální konstrukce. • Inkrementální vkládání. 9 Rozděl a panuj. • Sweep Line. Nepřímá konstrukce: přes Voronoi diagram, v praxi není používána. Metoda lokálního prohazování: Metoda je použitelná pouze ve 2D, obtížně lze převést do vyšší dimenze. Převod libovolné triangulace T na VT. Prohazování nelegálních hran v dvojicích trojúhelníků tvořících konvexní čtyřúhelník. Složitost algoritmu je 0(A/), nutno připočítat složitost na triangulačního algoritmu. Lze použít vzhledem k libovolnému kritériu, např. DDT. Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Delaunay triangulace 41. Algoritmus lokálního prohazování Algoritmus 2: Delaunay Triangulation Local(P) 1: Vytvoř pomocnou triangulaci 7~(P). 2: legal=false 3: while 7"(P) llegal 4: legal=true; 5: Opakuj pro Ve, G T (P) 6: Vezmi hranu e, G 7~(P) 7: Nalezni trojúhelníky U, ř2 incidující s e,. 8: if (ři U ř2) konvexní a nelegální 9: Legalize (ři, ř2)- 10: legal=false; Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 42. Metoda inkrementální konstrukce Algoritmus lze použít ve 2D i 3D. 2D varianta pracuje s prázdnou kružnicí, 3D varianta s prázdnou koulí o poloměru r. Založena na postupném přidávání bodů do již vytvořené VT. Nad existující Delaunayovskou hranou e = (pí, pz) hledán p, minimalizující poloměr k\ = (e, p,), p, G crr(e) p = arg min r(A/), kj< = (a, b, p,), e=(a,b). Vp/Ga/.(e) Delaunayovská hrana je orientována, bod p hledáme pouze vlevo od ní. Alternativně test prázdné opsané kružnice. Do VT přidány hrany trojúhelníku A(pi, P2, p): ei (p2,p),e2 (p,Pi), pakliže hrany = (p, p2,), = (Pí >P>) neJS0U v AEI- Pokud p nalezen v crr(e), změníme orientaci hrany e a hledání opakujeme. Při konstrukci používána modifikovaná datová struktura AEL (Active Edge List). Obsahuje hrany e, ke kterým hledáme body p, neukládá se topologický model. Složitost je 0(r?2), lze vylepšit, algoritmus nestabilní. Delaunay triangulace Metoda inkrementální konstrukce 43. Ilustrace inkrementální konstrukce (1/3) zmena orientace 'mm ° Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Delaunay triangulace Metoda inkrementální konstrukce 44. Ilustrace inkrementální konstrukce (2/3) o Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Delaunay triangulace Metoda inkrementální konstrukce 45. Ilustrace inkrementální konstrukce (3/3) 46. Algoritmus inkrementální konstrukce VT (1/2) Algoritmus 2: Delaunay Triangulation Incremental (P, AEL, VT) 1: Pí = rand(P), \\p2 — pí ||2 = min. //Náhodný a nejbližší bod 2: Vytvoř hranu e = (P1P2) 3:p = argminvpí.Gť7/.(e) ^(ki),^ = (a, b,pi),e= (a, fc) 4: Pokud íp, prohoď orientaci e <— (P2P1 )■ Jdi na 3). 5: e2 = (P2,p), £3 = (p,Pí) //Zbyvajici hrany trojúhelníku 6: AEL^— e, AEL^— e2, AEL^— e3 //Přidáni 3 hran do AEL 7: £>T<- e, VT<- e2, VT<- e3 //Přidáni 3 hran do DT 8: while AEL not empty: 9: AEL —>> e, e = (P1P2) //Vezmi první hranu z AEL 10: e = (P2P1) //Prohod jeji orientaci 11: p = arg minVp.GL(e) r'(/c/), /c, = (a, fc, p,), e = (a, fc) 12: if 3p : //Takový bod existuje 13: e2 = (P2, p), £3 = (p, Pí) //Zbyvajici hrany trojúhelníku 14: £>T <- e //Přidej hranu do VT ale ne do AEL 15: aôô(e2,AEL,VT), aôô(e3,AEL,VT) //Přidej do VT i do AEL(?) Delaunay triangulace Metoda inkrementální konstrukce 47. Algoritmus inkrementální konstrukce VT (2/2) Při přidání e = (a, b) do AEL kontrola, zda neobsahuje hranu s opačnou orientací e' = (£>, a). Pokud ano, je e' odstraněna z AEL. Pokud ne, je e přidána do AEL. Hrana e je v obou případech přidána do DT. Triangulace ukládána po trojúhelnících. Algoritmus 3: Add (e = (a, b), AEL.VT) 1: Vytvoř hranu e' = (£>, a) 2: if (e' e AEL) 3: AEL e' //Odstraň z AEL 4: else: 5: AEL T (celkem 3 legalizace). • Bod p leží ve straně ř,-, řy Pokud přidávaný bod p leží ve straně th legalizujeme nově vzniklé trojúhelníky ři, Í2, fe, íi s incidujícími trojúhelníky VT (celkem 4 legalizace). Tím proces legalizace nekončí, přehození úhlopříčky v některém z výše uvedených případů vyvolá potřebu legalizace k jejich incidujícím trojúhelníkům. Pokud alespoň jeden z vrcholů trojúhelníka představuje bod Q, nutno upravit legalizační pravidla. Tento krok je vyvolává potřebu rekurzivního řešení problému. V nepříznivém případě může vložený bod p způsobit přegeneroyání značného Rovinné triangulace a jejich využití. 69 /125 Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Metoda inkrementálního vkádání 66. Ilustrace procesu legalizace, p e ř, Delaunay triangulace Delaunay triangulace Metoda inkrementálního vkádání 67. Ilustrace procesu legalizace, p leží ve straně th ts Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. "\ "O O' 71/125 Delaunay triangulace Metoda inkrementálního vkádání 68. Pravidla legalizace pro vrcholy Q (1/2) Jsou reakcí na situaci, že do VT je zahrnut i simplexový trojúhelník ft. Aby nedošlo k nevhodnému ovlivnění oblasti P oblastí ft, mohou být do VT{P U Q) přidány i nelegální hrany. Hrany nelegální v VT[P U Q) však budou legální VT(P). Jedná se o hrany ležící na H{P). Nechť p,-, p/?p/c a p,-, py?p/ představují dva incidující troúhelníky a p,-, py představuje testovanou hranu. Nutno uvažovat následující případy: • indexy /, y ysou záporné: Hrana pTTP/ je legální. • všechny indexy /, y, kj > 0: Normální případ, prováděno běžné testování. a? Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Delaunay triangulace Metoda inkrementálního vkádání 69. Pravidla legalizace pro vrcholy Q (1/2) • jeden z indexů ij,k,l záporný: Pokud jeden z bodů p,, py- G fi, pak je strana p~py je nahrazena pž^pž, v opačném případě je ponechána Výsledná hrana nemusí být legální vzhledem k VT[P U Q), leží na H{P), ležínaH(P). • dva z indexů /,y, /c, / ysou záporné Jeden z indexů /,y a jeden z indexů k, I záporný. Pokud je negativní index i J menší (v abs. hodnotě) než negativní index k, I, je p,-, p,- v pořádku; V opačném případě je p~py nahrazena p/c,P/. Výsledná hrana nemusí být legální vzhledem k VT[P U íí), leží na 7í(P). • ŕ/v z indexů /, y, /c, / ysou záporné Situace nemůže nastat. Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Delaunay triangulace Metoda inkrementálního vkádání 70. Ilustrace legalizačních pravidel pro vrcholy Q Vlevo indexy i J záporné. Uprostřed 2 z indexů /,/, /c, / záporné, swap nelegální vzhledem VT(P U Q). Vpravo dva z indexů /,/, /c, / záporné, swap není třeba provádět (bod Q e k nebrán v potaz). Delaunay triangulace Metoda inkrementálního vkádání 71. Fáze 4: Odstranění simplexových hran Odstranění všech stran VT(P U Q) které incidují z ft, výsledkem VT(P) Výsledkem oříznutí na konvexní obálku. Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Delaunay triangulace Metoda inkrementálního vkádání 72. Implementace algoritmu inkrementálního vkládání (1/2) Algoritmus 3: DT Incremental Inserton (P ,VT) 1: Vytvoření simplexu: do VT <— r(p_i, P-2, P-3) 2: Opakuj pro / G 1,n : 3: Přidej p do VT. 4: Najdi ř(p,-, py, Pk) takový, že p G ř. 5: Jestliže 3p G ř(p,-, py, p/c): 6: «— ř(p, p,-, py) //Přidáni trojúhelníku 7: £>T «— ř(p, py, Pk) //Přidáni trojúhelníku 8: VT <— ř(p, p/c, P/) //Přidáni trojúhelníku 9: Legalizace hrany (p,-, py) G ř(p, p,-, py). 10: Legalizace hrany (pj,Pk) G t(p,pj,pk). 11: Legalizace hrany (pk, pj) G ř(p, p/c, P/). Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Delaunay triangulace Metoda inkrementálního vkádání 73. Implementace algoritmu inkrementálního vkládání (2/2) Algoritmus 3: DT Incremental Inserton (a, b, AEL.VT) 12: Jinak jestliže 3p G <9ŕi(p/,py,p/c)A G <9ŕ2(p/, P/, Py): 13: «— ř(p, P/c, P/) //Přidáni trojúhelníku 14: £>T «— ř(p, Py, P/c) //Přidáni trojúhelníku 15: VT <— ř(p,-, p/, p) //Přidáni trojúhelníku 16: VT <— ř(p, P/, py) //Přidáni trojúhelníku 17: Legalizace hrany (p,-, p/) G ř(p, p,-, p/). 18: Legalizace hrany (p/,py) G ř(p, p/,py). 19: Legalizace hrany (py,p/c) G t(p,pj,pk). 20: Legalizace hrany (p^, p,) G ř(p, p/c, p,). 21: Odstranění simplexových hran z £>T. Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Delaunay triangulace Metoda inkrementálního vkádání 74. Algoritmus legalizace hrany Přidávaný bod označen jako p. Strana (p,-, py) představuje stranu v trojúhelníku ŕ, která má být prohozena. Incidující trojúhelník ť tvořen hranami p,-, py, p/. Rekurzivní procedura, legalizace volána současně na dvě nové strany. Algoritmus 4: DT Legalizace hrany ((p/,P/),r(p/,P/,P/c)) 1: Najdi trojúhelník ť(phpi,Pj) incidující s hranou (p/,Py) trojúhelníku t. 2: if (p/,py) nelegální 3: Prohoď (p/,Py) za (p/c,P/) 4: Legalizace hrany (p/? p^), ř(p/, p/? p/c). 5: Legalizace hrany (py, pk), t(ph pk, p;). Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Triangulace se vstupní podmínkou 75. Triangulace se vstupní podmínkou Označovány jako Constrained Triangulations (tj. triangulace s omezením). Do triangulace zavedeny povinné hrany spojující definované body p. Poloha povinných hran se při triangulaci již nesmí měnit. Povinné hrany při konstrukci triangulace kříží jiné možné hrany, které jsou vzhledem k nějakému kritériu lokálně optimální (a pro triangulaci vhodnější), avšak tyto hrany nejsou použity. Triangulace se vstupní podmínkou proto nejsou lokálně optimální. Geometrický předpoklad: povinné hrany se nesmějí protínat. Široké použití v kartografii tvorbě digitálních modelů terénu, povinné hrany umožňují lepší modelování morfologie terénu. Zástupci: • Greedy triangulace se vstupní podmínkou (Constrained Greedy Triangulation). 9 Delaunay triangulace se vstupní podmínkou (Constrained Delaunay Triangulation). Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 79 /125 Triangulace se vstupní podmínkou 76. Greedy triangulace se vstupní podmínkou Greedy triangulace se vstupní podmínkou CQT(P) není příliš často používána. Tvorba CQT(P) probíhá ve dvou krocích: • Přidání povinných hran Do prázdné triangulace přidány povinné hrany. Žádná z povinných hran nemůže být při triangulaci nahrazena možnou kratší stranou. • Tvorba QT{P) Konstrukce Greedy triangulace nad P. Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 77. Delaunay triangulace se vstupní podmínkou Nejpoužívanější triangulace v geoinformatice. Na rozdíl od CQT(P) nutná redefinice triangulace: přes povinné hrany neprobíhá swapování. Triangulace jako celek nemaximalizuje minimální úhel v trojúhelnících. Zavedení povinných hran sníží rychlost triangulačního algoritmu. Možné geometrické problémy: povinná hrana kolineární s nějakou hranou VT{P) ^rozdělení povinné hrany na 3 části, povinná hrana protíná bod VT{P) ^rozdělení povinné hrany na 2 části. Konstrukce probíhá ve třech krocích: • Vytvoření VT(P). • Zadání povinných hran do VT(P). • Převod VT(P) na CVT(P). Pro bod 3 existuje řada algoritmů, např. Sloan (1992).a ► < fl ► < t ► < t ► : Rovinné triangulace a jejich využití. Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Triangulace se vstupní podmínkou 78. Převod VT(P) na CVT(P) Algoritmus převodu VT(P) na CVT(P) je rekurzivní. Každá povinná hrana definována dvojicí vrcholů (vh Vj). Seznam protnutých hran: S. Seznam nově vytvořených hran: H. Postup je tvořen následujícími kroky: • Nalezení stran VT(P) protínajících povinnou hranu {vh vf). 9 Zrušení všech stran v VT(P) protínajících povinnou hranu (vh vf). 9 Vytvoření pomocné triangulace. • Obnovení VT(P). 9 Odstranění nadbytečných trojúhelníků. Nalezení stran VT{P) protínajících povinnou hranu vjvj: Testujeme, zda hrana (v,-, vj) není již v VT(P). Pokud nikoliv, v VT(P) nalezeny všechny hrany protínající (v,-, vf). Tyto odtraněny z VT(P) a přidány do S. < n ► «fl ► «i -= == Rovinné triangulace a jejich využití. 82 /125 Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Triangulace se vstupní podmínkou 79. Nalezení stran VT{P) protínajících povinnou hranu Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Triangulace se vstupní podmínkou 80. Odstranění stran protínajících povinnou hranu (v,-, vj) z VT{P) Výsledkem převod VT{P) na pomocnou triangulaci, jejíž hrany neprotínají {v-,, Vj). Nechť hrana protínající {v-,, Vj) je označena (vk, vi): Nechť (vm, vn) je úhlopříčka v konvexním čtyřúhelníku se společnou stranou (vk, vi). Algoritmus 5: CDT, remove intersecting edges (S,H) 1: Opakuj, dokud S není prázdný 2: Odeber z S protínající hranu (vk, vi). 3: Pokud incidující A se společnou hranou (vkl v/) netvoří konvexní 4-úhelník 4: Přidej (vk, vi) do S a jdi na 2). 5: Pokud tvoří konvexní 4-úhelník: 6: Prohodíme diagonálu (vk, vi) v tomto 4 úhelníku za (i/m, vn) . 7: Pokud (vm, vn) neprotíná {v-,, Vj) : 8: Přidej (vm, vn) do H. 9: Pokud (vm, vn) protíná {v-,, Vj) : 10: Přidej (i/m, vn) do S. ~= J~) Q, (V Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 84/125 Triangulace se vstupní podmínkou 81. Ilustrace odstranění stran protínajících povinnou hranu Wi(V3) Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Triangulace se vstupní podmínkou 82. Ilustrace odstranění stran protínajících povinnou hranu Wi (2/3) Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Triangulace se vstupní podmínkou 83. Ilustrace odstranění stran protínajících povinnou hranu Wi (3/3) Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 87/125 Triangulace se vstupní podmínkou 84. Obnovení VT(P) Triangulace vytvořená v předchozím kroku není Delaunayovská. Tuto triangulaci je proto nutné převést na Delaunayovskou. Nad nově vytvořenými hranami je provedena legalizace vzhledem k incidujícím trojúhelníkům. Algoritmus 6: CDT, Restore DT (S,H) 1: Opakuj, dokud existuje alespoň jeden swap 2: Načti ze seznamu H hranu (v^, ví). 3: Pokud (vk, v,) ^ (vh vf) 4: Pokud incidující A se společnou hranou (vk, ví) není legální 5: Prohození diagonály (vk, ví) ve 4 úhelníku za (vm, vn) . 6: Nahrazení (v^, ví) hranou (vm, vn) v H. Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Triangulace se vstupní podmínkou 85. Ilustrace obnovení VT(P) Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Triangulace se vstupní podmínkou 86. Triangulace nekonvexní oblasti a oblasti s otvory Triangulace nekonvexní oblasti: Triangulace množiny bodů ohraničené nekonvexním polygonem. Z triangulace odstraněny všechny trojúhelníky vně polygonu (tj. takové, jejichž těžiště je vně polygonu). U DMT, triangulace probíhá pouze uvnitř nekonvexní oblasti se vstupními daty, vně oblasti by si algoritmus DMT "vymýšlel". Využití Ray Algoritmu. Triangulace oblastí s otvory: Oblast obsahuje podoblasti (otvory), uvnitř kterých nebude prováděna triangulace. Otvory popsány v opačném pořadí, než nadřazená oblast. Použití při tvorbě DMT, místa bez vrstevnic: vodní plochy, stavební objekty, místa s příliš velkým spádem... Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Triangulace se vstupní podmínkou 87. Triangulace VT{P) Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 91/125 Triangulace se vstupní podmínkou 88. Selekce trojúhelníků uvnitř oblasti i_i r ^ I_|p Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. "\ "O O' 92/125 Triangulace se vstupní podmínkou 89. Odstranění trojúhelníků vně oblasti Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Datově závislé triangulace 90. Datově závislé triangulace U všech výše uvedených 2D triangulací tvar trojúhelníkové sítě ovlivňuje pouze poloha bodu, souřadnice z nehraje roli. Takové triangulace nejsou bez dodatečných informací o terénu (kosterní čáry) vhodné k jeho modelování. Data Dependent Triangulation (DDT) tyto nedostatky odstraňuje. Vznikají optimalizací vstupní triangulace (nejčastěji DT) s využitím heuristik či genetických algoritmů. Výhody: • DDT berou v potaz výšku bodu, snaha o optimalizaci tvaru trojúhelníkové sítě. • Trojúhelníkový model lépe zohledňuje skutečný tvar terénu. • Automatická detekce terénních zlomů, netřeba zadávat povinné hrany. Nevýhody: • Optimalizace heuristikou rychlá, zlepšení většinou nebývá významné. • Optimalizace genetickými algoritmy kvalitní, avšak výpočetně náročné, vhodné pouze pro malé množiny (n < 50000). Dvě metody optimalizace: • lokální optimalizace, • modifikovaná lokální optimalizace. Rovinné triangulace a jejich využití. 94/125 Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a DT, nevhodné vystižení terénní hrany Datově závislé triangulace 92. DDT, lepší vystižení terénní hrany Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Datově závislé triangulace 93. Srovnání vrstevnic Dl a DD1 Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Datově závislé triangulace Lokální optimalizace triangulace 94. Lokální optimalizace triangulace Optimalizace triangulace (lokální prohazování hran) vzhledem zadanému kritériu. Používána heuristika, snaha dosáhnout globálního minima oakovaným hledáním lokálního minima. V jednom kroku optimalizována "malá" část triangulace: • Edge Based Optimization Prováděna vzhledem ke každé hraně sdílené dvojicí trojúhelníků. Častější varianta. 9 Vertex Based Optimization Prováděna vzhledem ke každému vrcholu sdíleného trojúhelníky. Rychlé, avšak nepříliš významné zlepšení. Možné uvíznutí v lokálním minimum, nepřipouští dočasné zhoršení stavu. Vysoká rychlost konstrukce. Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Datově závislé triangulace Lokální optimalizace triangulace 95. Edge Based vs Vertex Based Optimization Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití Datově závislé triangulace Lokální optimalizace triangulace 96. Edge Based Optimization Každé hraně e-, trojúhelníka A přiřadí funkce c ohodnocení c, d = c(e,). Ohodnocovací funkce měří "ostrost přechodu" mezi trojúhelníky (např. úhel normál). Globální ohodnocení triangulace r s m vnitřními hranami m m /=1 /=1 Optimální triangulace minimalizuje globální kritérium C(t) = min, snaha o co nejvíce "hladkou" triangulaci. Globální kritérium neumíme exaktně minimalizovat (NP), inkrementální/hladová strategie c(T(k)) min ~ c(T(k ~ 1)) + Ac(e))^ Ac(^)) min . Minimalizace updatů: kritérium vztažené ke hraně e a blízkému okolí. Cílem nalézt globální minimum (neúspěšné). Rovinné triangulace a jejich využití. Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Datově závislé triangulace Lokální optimalizace triangulace 97. Lokální swap kritérium Výchozí triangulace T(P): Hrana e-,, inciduje s A t-\, fe. 2 varianty: 1) Hrana e,- sdílená 2 trojúhelníky Lokální swapovací kritérium: T{P) je optimální vzhledem k c právě když c(e/) < c(e-). Nízká účinnost, malé území. 2) Hrana e j sdílená 2 trojúhelníky + incidující hrany. Celkem 6 trojúhelníků, větší účinnost. Sousedící hrany v ři: e), ef, sousedící hrany v ř2 : ef ■ éf, ohodnocení C(r) = c(e,) + £ c(ef) /c=1 Swap =>- triangulace Tř(P) s trojúhelníky t\ a Z^, ohodnocení C(r/) = c(e//) + ^c(ef). /c=1 Lokální swapovací kritérium: 7~(P) je optimální vzhledem k c právě když 4 C(r) < C(r') ^ c(e,) + £ c(ef) < c^,') + £ c(ef). /c=1 /c=1 Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Datově závislé triangulace Lokální optimal 98. Ukázka lokální optimalizace Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Datově závislé triangulace Lokální optimalizace triangulace 99. Algoritmus lokální optimalizace Algoritmus provádí opakované swapování nad všemi hranami triangulace. Výsledná triangulace nebude globálně optimální k žádnému kritériu. Algoritmus 7: DDT, LOP (e) 1: Opakuj, dokud existuje alespoň jeden swap 2: Vezmi hranu e,-. 3: Spočti a = c(e/) + EÍ=1 c(ef) 4: Swap (e,- —>► e-) 5: Spočti c; = c(eO + EÍ=1 c(ef) 6: if C/ < c/ 7: Swap (e- —>► e,-). Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Datově závislé triangulace Lokální optimalizace triangulace 100. Lokální kritéria pro DDT Prehled kriterii: • Angle Between Normals (ABN). • Distance From Planes (DFP). • Smoothnes of Contours (SCO). a? Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Datově závislé triangulace Lokální optimalizace triangulace 101. Přehled kritérií Rovina g. y) = 3iX + b-,y + C/z Angle Between Normals: Úhel (f mezi normálami rP \ rP^ trojúhelníků U, Cabn(Gi) =

0, vodorovná rovina) Csco{oí) = (j) = cos -i (1) ,/(2) = cos -1 a\ Ü2 + £>i jĎ2 a? Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Digitální model terénu 102. Zemský povrch a jeho znázornění Zemský povrch má nepravidelný, komplikovaný průběh: • Hladký: Konvexní či konkávni. Formován prostřednictvím přírodních jevů. Snadnější pro matematické modelování. 9 Ostrý: Zlomy, zářezy, hrany, stupně. Formován činností člověka. Umělé terénní tvary tvoří singularity, obtížnější pro matematické modelování. Prostorové modely zemského povrchu: • Digitální model reliéfu (Digital Terrain Model). • Digitální model povrchu (Digital Surface Model). • Digitální výškový model (Digital Elevation Model). Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Digitální model terénu 103. Digitální model terénu Digitální model terénu/reliéfu: Digitální reprezentace reliéfu zemského povrchu v paměti počítače, složená z dat a interpolačního algoritmu, který umožňuje mj. odvozovat výšky mezilehlých bodů. (Terminologický slovník ČÚZK) Digitální model povrchu: Zvláštní případ digitálního modelu reliéfu konstruovaného zpravidla s využitím automatických prostředků (např. obrazové korelace ve fotogrammetrii) tak, že zobrazuje povrch terénu a vrchní plochy všech objektů na nčm (střechy, koruny stromů a pod.). (Terminologický slovník ČÚZK) Digitální výškový model: Digitální model reliéfu pracující výhradné s nadmořskými výškami bodů. (Terminologický slovník ČÚZK). Nad digitální modely lze provádět řadu analýz a výpočtů: analýza sklonu, osvětlení, expozice, barevná hypsometrie, vrstevnice. Rovinné triangulace a jejich využití. 107/125 Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Digitální model terénu 104. Znázornění DMT: trojúhelníková síť Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití Digitální model terénu 105. Znázornění DMT: barevná hypsometrie (kvantitativní použití barev) Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Digitální model terénu 106. Plátování Základem DMT aproximační plocha procházející všemi zadanými body množiny P = {p/}/Li, kde pí = [x/,y/,z/]. Mimo tyto body dopočítávána podle specifických matematických postupů, aby se co nejvíce blížila původnímu terénu. Vede ke vzniku ploch vysokých stupňů, které samovolně oscilují. Vhodnější použít techniku plátování. Princip plátování: Rozdělení aproximační plochy na větší množství malých ploch nižších stupňů^>p/ářy. Pláty nejčastěji stupně tři^>kubické pláty (polynomy stupně 3 již věrně aproximují terén, jejich výpočet poměrně snadný). Hranice plátů jsou vedeny po singularitách. Digitální model tvořen velkým množstvím plošek (řádově stovky tisíc, milióny), mezi nimi ostré nebo hladké přechody^* tímto způsobem lze vyjádřit jakýkoliv terén. Poprvé použito v 70. letech při konstrukci letadel (Airbus=Bezierovy pláty, Boeing=Coonsovy pláty). >oq,o Rovinné triangulace a jejich využití. 110 /125 Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Digitální model terénu Polyedrický model terénu 107. Polyedrický model terénu Plošky jsou představovány trojúhelníky se společnou hranou. Síť trojúhelníků vytvořena za použití triangulačních algoritmů (Constrained Delaunay Triangulation). Proložením rovin vrcholy jednotlivých trojúhelníků v IR3 vznikne nepravidelný mnohostěn, tzv. polyedr, který se přimyká k terénu. V trojúhelnících pouze lineární interpolace, což pro řadu účelů nepostačuje. Do polyedrického modelu lze zadat povinné hrany (hřbetnice, údolnice, spádnice), které zlepšují jeho aproximační vlastnosti. Vzhledem k nepravidelnému rozložení bodů je nutné při interpolaci/extrapolaci dat či různých analytických operacích z polyedrického modelu používat speciální techniky (např. IDW nebo Krigging). Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Digitální model terénu Polyedrický model terénu 108. Konstrukce polyedrického modelu Vrcholy pí = [xuyuz^p2 = [x2,y2,z2], p3 = [x3,y3,z3] každého trojúhelníku t proložíme rovinu T z = ax + by + c. Koeficienty a, b, c představující složky normálového vektoru roviny a = Z\ 1 Z2 1 Y3 yi 1 x2 y2 1 *3 /3 1 b = x^ z\ 1 x2 z2 1 x3 z3 1 X: yi i x2 y2 1 x3 /3 1 C = x^ y\ 1 x2 y2 1 X3 /3 1 yi 1 x2 y2 1 X3 ys 1 Rovnice jednotlivých rovin nejsou udržovány v paměti, jsou podle potřeby operativně určovány (on the fly) =4> výhoda pro práci s rozsáhlými modely. en Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 112/125 Digitální model terénu Lineární nterpolace vrstevnic 109. Interpolace vrstevnic Lineární interpolační algoritmy: Spád terénu mezi dvěma body, mezi kterými provádíme interpolaci, je konstantní. Rozestup vrstevnic mezi dvěna body je také konstantní. Výpočetně jednoduché, ale nevystihuje realitu. Nelineární interpolační algoritmy: Mezi interpolovanými body předpokládáme plynulou změnu sklonu terénu geomorfologická interpolace. Rozestup vrstevnic mezi dvěma body není konstantní. Zohledňuje skutečný tvar terénu (sklon okolních plošek). Využití kvadratické či kubické interpolace. Používá se v mapách velkých a středních měřítek. Postup je značně složitý a obtížně se algoritmizuje. Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 113 /125 Lineární nterpolace vrstevnic 110. Konstrukce vrstevnic lineární interpolací Digitální model terénu Dáno: Rovina plátuT(pi, P2, P3), rovina p : z = h. Hledáme: Průsečnice AB rovin paT. Založena na analytické geometrii: hledání průsečnice roviny T určené trojúhelníkem t G VT a vodorovné roviny s výškou h. Opakováno nad všemi t. z=c Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 114/125 Digitální model terénu Lineární nterpolace vrstevnic 111. Výpočet souřadnic bodů A, B Varianty vzájemné polohy gar: Nemají žádný společný bod (neřešíme), průsečnice tvoří 1 bod (neřešíme), průsečnice je úsečka. Z podobnosti trojúhelníků představujících průměty do roviny XZ a YZ platí X2 - xb- x^ y2 - yi y b - y z2 - Zi *3 - X^ z - Zi xa - x^ z2 - Zi y> -y z - Zi y a -y z3 - Zi z - Zi z2 - Zi z - Zi Výsledné souřadnice koncových bodů /A, B průsečnice určíme ze vztahů xa = -(z - Zi ) + Xi z3 - Zi /3 -yi z3 - Zi X2-XA xb = -(z - Zi ) + Xi (z - zi) + yi yö = z2 - Zi y2 -yi z2 - Zi (z - zi) + yi. Test, zda rovina £> protíná stranu (p,, p,+i) trojúhelníku: (z-z/)(z-z/+i) < 0. Rovinné triangulace a jejich využití. Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a r3" 115/125 Lineární nterpolace vrstevnic 112. Ukázka výpočtu vrstevnic lineární interpolací (DT) Digitální model terénu Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Lineární nterpolace vrstevnic Digitální model terénu 113. Vliv vložení povinné hrany do triangulace: výchoz situace Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití Digitální model terénu Lineární nterpolace vrstevnic 114. Vliv vložení povinné hrany do triangulace: lokální změna průběhu DMT Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 118/125 Digitální model terénu Analýza sklonu 115. Analýza sklonu terénu Analytická úloha realizovaná nad DMT. Použití pro analýzu hydrologických poměrů, sesuvů, lavin, návrhy komunikací, stavebních objektů. Zprostředkující hodnotou je gradient (tj. vektor max. spádu). Gradient Vf(x0, y0, z0) funkce f(x, y, z) v bodě p = [x0, ynz0] Rovnice roviny g Vř(x0,yo,z0) = (^(xo)^(yo),^(z0)) p : ax + by + cz + d = 0. Gradient Vp(x0, yo, z0) roviny p Vp(x0,y0,z0) = (^(xo),^(yo),^(z0)) = (a, o, c) Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 119/125 Digitální model terénu Analýza sklonu 116. Analýza sklonu terénu Rovina p procházející 3 body X - x^ y z - Z1 x2 - *1 -yi Z2 - z\ X3 - *1 z3 - zA = o Odchylka (p rovin p a 7r: f = arccos "1-02 "1 n2 "1 n2 (a,b, c), (0,0,1). Výpočet prováděn nad každým trojúhelníkem t DMT. Vizualizace trojúhelníků (tj. vyplnění barvou) na základě hodnoty p, Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. Digitální model terénu Analýza sklonu 117. Sklon terénu Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a 121/125 Digitální model terénu Analýza sklonu 118. Vizualizace sklonu terénu Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 122/125 Digitální model terénu Analýza orientace 119. Analýzy orientace terénu Využití ve stavebnictví, zemědělství, hydrologii. Sluneční svit ovliňuje množství tepla dopadajícího na zemský povrch, hydrologické poměry, podmínky pro růst zemědělských plodin. Orientace v bodě definována jako azimut průmětu gradientu Vp do roviny x, y. Vektor v průmětem gradientu Vp(x0, yo, z0) do roviny xy ^ = (^(Xo)'^(yo)'°) = (a'fe'0)- Azimut a vektoru v A = arctan ( - ) , A G (0, 2tt) . a Výpočet prováděn nad každým trojúhelníkem DMT. Pozor na správnou detekci kvadrantů. Tomáš Bayer | bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 123 /125 Digitální model terénu Analýza orientace 120. Orientace terénu Digitální model terénu Analýza orientace 121. Vizualizace orientace terénu L Tomáš Bayer bayertom@natur.cuni.cz (Katedra a Rovinné triangulace a jejich využití. 125/125