Rovinné triangulace a jejich využití

Rovinné triangulace a jejich využití. Greedy Triangulation. Delaunay Triangulation. Constrained Delaunay Triangulation. Data Dependent Triangulation. DMT.

Tomáš Bayer | [email protected] ˇ Katedra aplikované geoinformatiky a kartografie. Pˇrírodovedecká fakulta UK.

ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

1 / 109

Obsah pˇrednášky 1

Ukázka použití

2

Formulace problému

3

Vlastnosti triangulací

4

Greedy triangulace

5

Delaunay triangulace Metoda inkrementální konstrukce Metoda inkrementálního vkádání

6

Triangulace se vstupní podmínkou

7

Datoveˇ závislé triangulace Lokální optimalizace triangulace

8

Digitální model terénu Polyedrický model terénu Lineární nterpolace vrstevnic Analýza sklonu Analýza orientace


2 / 109

Ukázka použití

1. Tvorba digitálního modelu terénu


3 / 109

Formulace problému

2. Formulace problému Dáno:

Množina bodu˚ P = {p1 , p2 , ..., pn } v R2 .

Hledáme:

Triangulaci T nad množinou P.

Definice: ˇ Triangulace T nad množinou bodu˚ P pˇredstavuje takové planární rozdelení, které vytvoˇrí soubor m trojúhelníku˚ t = {t1 , t2 , ..., tm } a hran tak, aby platilo: Libovolné dva trojúhelníky ti , tj ∈ T , (i 6= j ), mají spoleˇcnou nejvýše hranu. Sjednocení všech trojúhelníku˚ t ∈ T tvoˇrí H(p). Uvnitˇr žádného trojúhelníku neleží žádný další bod z P. Vztah mezi poˇctem bodu˚ n, poˇctem hrannh a poˇctem trojúhelníku˚ nt v rovineˇ pro triangulaci T , pokud k bodu˚ leží na H: nh

=

3n − 3 − k ,

nt

=

2n − 2 − k .

Vztah lze zjednodušit, je pouze funkcí n: nh

≤

3n − 6

nt

≤

2n − 5


4 / 109

Formulace problému

3. Použití triangulací ˇ aplikace triangulací: Nejˇcastejší Kartografie & GIS: tvorba digitálních modelu˚ terénu (DMT). Zpracování obrazu: segmentace, rozpoznávání vzoru. ˚ DPZ: tvorba prostorových modelu˚ z dat laserového skenování. Poˇcítaˇcová grafika: vizualizace prostorových dat ve scénách. FEM (tzv. metoda koneˇcných prvku): ˚ analýza vlastností a struktury materiálu, ˚ simulace. Kartografická generalizace. Plánování pohybu robotu: ˚ vozítka na Marsu. Modelování pˇrírodních jevu: ˚ eroze. Interpolaˇcní techniky: pˇrevod bodových jevu˚ na plošné Biometrie: detekce otisku˚ prstu. ˚ ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

5 / 109

Formulace problému

4. Rekonstrukce terénu z dat leteckého laserového skenování


6 / 109

Formulace problému

5. Aplikace triangulací v biometrii Detekce otisku˚ prstu˚ (Bebis et al., 2000)


7 / 109


6. Požadavky na triangulaci T Požadavky na triangulaˇcní algoritmus: Jednoduchost algoritmu, snadná implementace. Dostateˇcná rychlost pro velká P (n > 1E6) bodu, ˚ požadavek na O (n · log(n)) algoritmus. Malá citlivost na singulární pˇrípady, kdy T není jednoznaˇcná (popˇr. ji nelze provést). Pˇrevod do vyšších dimenzí. Schopnost paralelizace algoritmu. ˇ Optimální tvar trojúhelníkové síte. ˇ Nekteré body v kontrastu: jednoduchost implementace x rychlost. Triangulaˇcní algoritmy patˇrí mezi jedny z nejvíce teoreticky rozpracovaných postupu. ˚ ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

8 / 109


ˇ 7. Volba triangulace a jejich delení ˇ triangulace T nutno zohlednit: Pˇri výberu Tvar trojúhelníku: ˚ ˇ produkovat pravidelné trojúhelníky vhodných tvaru˚ (blížící Triangulace by mela se rovnostranným). Kritérium je duležité ˚ pˇri tvorbeˇ DMT, trojúhelníková sít’ se musí co nejvíce pˇrimykat k terénu. Povinné hrany: ˇ Schopnost vkládat povinné hrany a modifikovat tvar triangulace. Ovlivnení ˇ tvaru terénu, vkládání kosterních car, tj. hˇrbetnic, údolnic, spádnic. Triangulace nekonvexní oblasti: Schopnost triangulace nekonvexní oblasti cˇ i oblasti obsahující díry. ˇ V mapách nejsou triangularizovány nekteré oblasti, napˇr. vodní plochy, budovy.


9 / 109


8. Ukázka triangulace nekonvexní oblasti obsahující díry


10 / 109


ˇ 8. Delení triangulací ˇ Delení triangulací dle geometrické konstrukce: Greedy triangulace. Delaunay triangulace. MWT (Minimum Weight Triangulation). Constrained triangulace (triangulace s povinnými hranami). Datoveˇ závislé triangulace. ˇ Delení triangulací dle použitých kritérií: Lokálneˇ optimální triangulace. Globálneˇ optimální triangulace. Multikriteriálneˇ optimalizované triangulace. ˇ Vlastnosti triangulace T se posuzují ve vztahu k temto kritériím. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

11 / 109


9. Lokálneˇ vs. globálneˇ optimální triangulace Lokálneˇ optimální triangulace T : Každý cˇ tyˇrúhelník tvoˇrený dvojicí trojúhelníku˚ se spoleˇcnou stranou triangularizován optimálneˇ vzhledem k zadanému kritériu. Pro množinu P existuje více lokálneˇ optimálních triangulací, každá z nich optimalizuje jiné kritérium. Globálneˇ optimální triangulace T Všechny trojúhelníky triangulace T optimální vzhledem k zadanému kritériu. Neexistuje jiná triangulace T 0 , která by dosáhla alesponˇ u jednoho trojúhelníku lepší hodnoty posuzovaného kritéria. Globálneˇ optimální triangulace je souˇcasneˇ lokálneˇ optimální. Multikriteriálneˇ optimalizované triangulace T : ˇ Kombinace nekolika lokálních cˇ i globálních kritérií. ˇ Vycházejí z Delaunay triangulace, která je optimalizována k temto kritériím. Dlouhé výpoˇcetní cˇ asy, doposud nejsou známy efektivní algoritmy, použití genetických algoritmu. ˚ ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

12 / 109


10. Hodnocení triangulace Necht’ P je množina bodu˚ tvoˇrena prvky p1 , p2 , p3 , p4 . Necht’ ∀pi ∈ H (konvexní cˇ tyˇrúhelník). ˇ pro n = 4, k = 4 platí:nh = 5, nt = 2. Pak dle Eulerovy vety Dusledek: ˚ nad P existují pouze dva trojúhelníky {t1 , t2 } a dveˇ ruzné ˚ triangulace T (P ) a T 0 (P ):

T (P ), kde t1 = p1 , p2 , p3 a t2 = p1 , p3 , p4 . T 0 (P ), kde t1 = p1 , p2 , p4 a t2 = 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íku. ˚ ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

13 / 109


11. Ilustrace T (P ) a T 0 (P )


14 / 109


12. Lokální kritéria Mají geometrický podtext, snaha o generování trojúhelníku˚ “rozumných” tvaru. ˚ ˇ používaných lokálních kritérií: Pˇrehled nejˇcasteji Minimální/maximální úhel v trojúhelníku α. Minimální/maximální výška v trojúhelníku v . ˇ vesané kružnice r . Minimální/maximální polomer ˇ opsané kružnice R. Minimální/maximální polomer Minimální/maximální plocha trojúhelníku S. Úhel mezi normálami sousedních trojúhelníku. ˚ ˇ používáno první kritérium (Delaunay triangulace maximalizuje Nejˇcasteji minimální úhel). Kritérium úhlu mezi normálami používáno u datoveˇ závislých triangulací. Od každého kritéria dispozici min-max varianta cˇ i max-min varianta. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

15 / 109


13. Kritérium minimálního/maximálního úhlu v trojúhelníku Triangulace nemá generovat trojúhelníky s pˇríliš ostrými/tupými úhly, které jsou tvaroveˇ ˇ úhel v trojúhelníku ti . nevhodné. Necht’ αmin pˇredstavuje nejmenší úhel a αmax nejvetší Min-max kritérium: Eliminace trojúhelníku˚ s pˇríliš tupými úhly. Triangulace T (P ) je vzhledem k tomuto kritériu na ˇ α úhel generovaný triangulací T (P ) menší než nejvetší ˇ rozdíl od T 0 (P ) optimální, je–li nejvetší úhel α0 generovaný triangulací T 0 (P ).

αmax = max(αi (T )) 0 = max(αi0 (T 0 )) αmax

(1)

0

αmax < αmax

Max-min kritérium: Eliminace trojúhelníku˚ s pˇríliš ostrými úhly. Triangulace T (P ) je vzhledem k tomuto kritériu na ˇ než rozdíl od T 0 (P ) optimální, je–li nejmenší α úhel generovaný triangulací T (P ) vetší nejmenší úhel α0 generovaný triangulací T 0 (P ).

αmin = min(αi (T )) 0 αmin = min(αi0 (T 0 ))

α

>α

0

ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a jejich Pˇrírodovedecká fakulta UK.) min a kartografie. min využití.

(2) 16 / 109


14. Globální kritéria Optimalizují geometrické parametry všech trojúhelníku˚ v triangulaci T (P ). ˇ používaná kritéria: Nejˇcasteji Suma délek stran: P ˇ Zohlednuje celkovou délku stran s vytvoˇrené triangulace ⇒minimalizace. Nh X

si = min.

(3)

i =1

T (P ) minimalizující sumu délek stran: MWT (Minimum Weight Triangulation). Pro obecný pˇrípad polohy bodu˚ v R2 nevyˇrešeno, pˇribližné ˇrešení genet. algoritmy. MWT se blíží GT. Povinné hrany: Pˇredem definované hrany uvnitˇr triangulace, tzv. Constrained Triangulation. Taková T (P ) není lokálneˇ optimální. Použití: pˇri tvorbeˇ DMT lze do triangulace zadat charakteristické terénní tvary a umožnit lepší modelování terénu. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

17 / 109

Greedy triangulace

15. Greedy triangulace Patˇrí do skupiny hladových algoritmu˚ (Greedy Algorithms). Vlastnosti triangulace: Pokud se v P nevyskytují hrany se stejnou délkou, je triangulace jednoznaˇcná. Snaží se však vytváˇret trojúhelníky s nejkratšími stranami, trojúhelníky nemusí ˇ splnovat žádnou speciální geometrickou podmínku. Jednoduchá implementace. Složitost je O (n3 ), lze optimalizovat na O (n2 · log(n)). Dusledek: ˚ Sít’ trojúhelníku˚ není z tvarového hlediska optimalizována⇒ do triangulace tak mohou být pˇridány tvaroveˇ nevhodné trojúhelníky. V kartografii není pˇríliš cˇ asto používána. Výsledná triangulace se blíží MWT. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

18 / 109

Greedy triangulace

16. Algoritmus Greedy triangulace Algoritmus 1: Greedy Triangulation (S, Q) 1: Opakuj pro ∀pi , i ∈ h1, ni: 2: Opakuj pro j ∈ hi + 1, ni: 3: Vytvoˇr hranu e = (pi , pj ). 4: Pro e urˇci d (pi , pj ) a ulož do Q. 5: Setˇrid’ Q dle d. 6: Odeber Q [0] a pˇridej do T . 7: Dokud Q není prázdná: 8: e =pop(Q ). 9: Opakuj pro ∀ei ∈ T : 10: test, zda e protíná ei ∈ T . 11: Pokud e neprotíná žádné ei ∈ T : 12:

Pˇridej e do T .


19 / 109

Greedy triangulace

ˇ Greedy triangulace 17. Grafické znázornení


20 / 109

Delaunay triangulace

18. Delaunay triangulace DT a její vlastnosti ˇ používaná triangulace, v oblasti GIS de-facto standart. Nejˇcasteji Existuje v R2 i v R3 . V1: Uvnitˇr kružnice k opsané libovolnému trojúhelníku tj ∈ DT neleží žádný jiný bod množiny P. V2:

DT maximalizuje minimální úhel v ∀t, avšak DT neminimalizuje maximální úhel v t. V3:

DT je lokálneˇ optimální i globálneˇ optimální vuˇ ˚ ci kritériu mnimálního úhlu. V4:

DT je jednoznaˇcná, pokud žádné cˇ tyˇri body neleží na kružnici. Výsledné trojúhelníky se pˇri porovnání ze všemi známými triangulacemi nejvíce blíží rovnostranným trojúhelníkum. ˚ ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

21 / 109


19. Ukázka DT


22 / 109


20. Srovnání GT a DT


23 / 109


21. Geometrické vlastnosti DT Necht’ k je kružnice l pˇrímka protínající k v bodech a, b, a p, q , r , s jsou body ležící na stejné straneˇ od l. Platí:

∠arb > ∠apb = ∠aqb > asb. ˇ Dusledek ˚ Tháletovy vety.


24 / 109


22. Edge Flip, legalizace Necht’ P = {pi , pj , pk , pl } je množina bodu˚ tvoˇrící vrcholy konvexního cˇ tyˇrúhelníku, tj P ∈ H(P ) a hrana pi , pj pˇredstavuje úhlopˇríˇcku P. Edge Flip (Swap) Prohození diagonály pi , pj cˇ tyˇrúhelníku {pi , pj , pk , pl } za diagonálu pk , pl . Pˇrechod z DT (P ) na D T 0 (P ), výsledkem stav, kdy jsou oba trojúhelníky legální, tj. lokálneˇ optimální vzhledem ke kritérium max-min. ˇ Operace je opakovaneˇ provádena nad všemi konvexními cˇ tyˇrúhelníky DT a je nazývána legalizací.


25 / 109


23. Legalizace, shrnutí poznatku˚ Vztahy mezi úhly v trojúhelnících pˇred/po legalizaci

αjl < βjl

αli < βli

αkj < βkj

αli , αik < βkl

αik < βik

αkj , αjl < βkl

ˇ 1: Veta Necht’ hrana pi pj inciduje s trojúhelníkem t1 tvoˇreným vrcholy pi , pj , pk a trojúhelníkem t2 tvoˇreným vrcholem pi pj , pl a kružnice k procházející body pi , pj , pk . Hrana pi , pj je nelegální tehdy a práveˇ jen tehdy, jestliže bod pl leží uvnitˇr k. ˇ 2: Veta Pokud body pi , pj , pk , pl tvoˇrí konvexní cˇ tyˇrúhelník a neleží na opsané kružnici k, pak jedna z hran pi pj nebo pk pl je nelegální.


26 / 109


24. Cline-Renka test legality ˇ rující legalitu dvojice trojúhelníku˚ pi , pj , pk a pi pj , pl ležících v Numericky robustní test oveˇ konvexním cˇ tyˇrúhelníku pi , pj , pk , pl . Necht’ α je protilehlý úhel straneˇ pi , pk vrcholu :   < π α+β =π   >π

ležící u vrcholu pj a β protilehlý úhel straneˇ pi , pk ležící u DT (P ) je legální. Body pi , pj , pk , pl leží na kružnici. DT (P ) je nelegální.

K Edge Flip dojde pokud sin(α + β) = cos(α) sin(β) + cos(β) sin(α) < 0. Upravené testovací kritérium:

(xik xjk + yik yjk )(xjl yil − xil yjl ) < (xjk yik − xik yjk )(xjl xil + yjl yil ), kde xik = xi − xk

yik = yi − yk ,

xjk = xj − xk

yjk = yj − yk ,

xjl = xj − xl

yjl = yj − yl ,

xil = xi − xl

yil = yi − yl .


27 / 109


25. Active Edge List (AEL) Datová struktura používaná pˇri konstrukci DT , uchovává topologii trojúhelníku˚ v DT . Necht’ dva incidující trojúhelníky ti , tj ∈ DT mají spoleˇcnou stranu oznaˇcenou v ti jako eij a v tj jako eji . Strany trojúhelníku: ˚ ˇ hodinových ruˇciˇcek Každá strana eij (Active Edge) v trojúhelníku ti orientovaná proti smeru uchovává: pointer na následující hranu ei +1,j v ti . pointer na stranu eji v incidujícím trojúhelníku tj (hrany ležící na H mají pointer inicializovaný na NULL). S výjimkou stran ležících na H je každá hrana e ∈ DT popsána dvakrát (jako eij a eji ), vždy s opaˇcnou orientací. Tyto zdvojené hrany nazývány Twin Edges. Trojúhelníky: Díky datovému modelu každý trojúhelník ti popsán trojicí hran (eij , ei +1,j , ei +2,j ) orientovaných ˇ hodinových ruˇciˇcek tvoˇrících kruhový seznam (Circular List) . proti smeru ˇ Seznam všech techto hran (nikoliv trojúhelníku˚ !) tvoˇrí Active Edge List. Pro každou hranu lze snadno nalézt pˇredcházející/následující hranu a incidující trojúhelníky. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

28 / 109


26. Ukázka datového modelu AEL


29 / 109


27. Metody konstrukce DT Metody pˇrímé konstrukce DT : Lokální prohazování. Inkrementální konstrukce. Inkrementální vkládání. ˇ a panuj. Rozdel Sweep Line. Nepˇrímá konstrukce: pˇres Voronoi diagram, v praxi není používána. Metoda lokálního prohazování: Metoda je použitelná pouze ve 2D, obtížneˇ lze pˇrevést do vyšší dimenze. Pˇrevod libovolné triangulace T na DT . Prohazování nelegálních hran v dvojicích trojúhelníku˚ tvoˇrících konvexní cˇ tyˇrúhelník. Složitost algoritmu je O (N ), nutno pˇripoˇcítat složitost na triangulaˇcního algoritmu. Lze použít vzhledem k libovolnému kritériu, napˇr. DDT.


30 / 109


28. Algoritmus lokálního prohazování

Algoritmus 2: Delaunay Triangulation Local(P) 1: Vytvoˇr pomocnou triangulaci T (P ). 2: legal=false 3: while T (P ) !legal 4: legal=true; 5: Opakuj pro ∀ei ∈ T (P ) 6: Vezmi hranu ei ∈ T (P ) 7: Nalezni trojúhelníky t1 , t2 incidující s ei . 8: if (t1 ∪ t2 ) konvexní a nelegální 9: Legalize (t1 , t2 ). 10: legal=false;


31 / 109


Metoda inkrementální konstrukce

29. Metoda inkrementální konstrukce Algoritmus lze použít ve 2D i 3D. ˇ r. 2D varianta pracuje s prázdnou kružnicí, 3D varianta s prázdnou koulí o polomeru Založena na postupném pˇridávání bodu˚ do již vytvoˇrené DT . Nad existující Delaunayovskou hranou e = p1 , p2 hledán takový bod p, pro který má od p1 , p2 minimální Delaunay vzdálenost dD (p1 p2 , p). Každá Delaunayovská hrana je orientována, bod p hledáme pouze vlevo od ní. ˇ hodinových ruˇciˇcek Používá se test orientace vrcholu˚ trojúhelníku proti smeru (determinant test, viz 2. pˇrednáška). Do DT pˇridány hrany trojúhelníku 4(p1 , p2 , p). ˇ Není-li bod p nalezen (e ∈ H(P )), zmeníme orientaci hrany e a hledání opakujeme. Složitost je O (n2 ), metodu lze vylepšit, ale algoritmus je pak nestabilní. Pˇri 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.


32 / 109



30. Delaunay vzdálenost Necht’ k (S , r ) je kružnice a l pˇrímka protínající k v bodech a, b, a p bod ležící na k . Delaunay vzdálenost bodu p od hrany a, b oznaˇcujeme jako dD (h, p), kde dD (h, p) =

( −r

Body S , p v opaˇcné polorovineˇ vzhledem k l .

r

Body S , p ve stejné polorovineˇ vzhledem k l .


33 / 109



31. Konstrukce s využitm delaunay vzdálenosti


34 / 109



32. Ilustrace inkrementální konstrukce (1/3)


35 / 109





36 / 109





37 / 109



35. Algoritmus inkrementální konstrukce DT (1/2) Algoritmus 2: Delaunay Triangulation Incremental (S, AEL, DT ) 1: p1 = náhodný bod z P, p2 =nejbližší bod k p1 . 2: Vytvoˇr hranu e = p1 p2 3: p = dD (e), bod s nejmenší Delaunay vzdáleností vlevo od e. 4: Pokud p = NULL, prohod’ orientaci e = p1 p2 ⇒ e = p2 p1 . 5: e2 = p2 p, e3 = pp1 . 6: Add e, e2 , e3 do AEL. 7: while AEL not empty do: 9:

e = p1 p2 první hrana AEL.

10:

ˇ Zmena orientace hrany e = p1 p2 ⇒ e = p2 p1 .

11:

Bod p s nejmenší Delaunay vzdáleností dD (e) vlevo od e.

12:

if p! = NULL :

13:

e2 = p2 p, e3 = pp1 .

14:

Add e, e2 , e3 do AEL. Add e do DT .

15: 16:

pop (e)


38 / 109



36. Algoritmus inkrementální konstrukce DT (2/2) Algoritmus pˇridání hrany e do AEL kontroluje, zda není v AEL pˇrítomna hrana s opaˇcnou orientací e0 . ˇ Pokud ano, je e odstranena z AEL. Pokud ne, je e pˇridána do AEL. Hrana e je v obou pˇrípadech pˇridána do DT . Triangulace ukládána po trojúhelnících. Algoritmus 3: Add (e = a, b, AEL,DT ) 1: Vytvoˇr hranu e0 = ba 2: if (e0 ∈ AEL) 3: remove a, b → AEL. 4: else: 5: push a, b → AEL. 6: push a, b → DT . ˇ eˇ V praxi není používán z duvodu ˚ kvadratické složitosti, výhodou je však pomern jednoduchá implementace. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

39 / 109


Metoda inkrementálního vkádání

37. Metoda inkrementálního vkládání ˇ Casto používaná metoda konstrukce DT . Lze použít v R2 i R3 . Složitost je O (n2 ), po úpravách lze dosáhnout O (n · log(n)). Klasický pˇrípad rekurzivní úlohy (fáze legalizace). Princip algoritmu: V každém kroku do DT pˇridán jeden bod a provedena legalizace DT . Necht’ S pˇredstavuje podmnožinu datasetu P obsahující m bodu˚ a p pˇridávaný bod

DT m+1 = DT m ∩ p. Algoritmus tvoˇren 4 fázemi: Konstrukce simplexu Ω oblasti P (obalový trojúhelník). Pˇridání p do DT m . Legalizace triangulace DT m+1 . ˇ simplexových hran. Odstranení ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

40 / 109



38. Fáze1: Konstrukce simplexu Ω Žádný z bodu˚ P neleží vneˇ simplexu Ω s vrcholy p−1 , p−2 , p−3 . DT bude probíhat nad sjednocením obou množin, tj. DT (P ∪ Ω). ˇ Zaruˇcíme tak, že pˇridání každého bodu pi do DT m probehne v souladu s souladu s níže uvedenými pravidly. ˇ Vrcholy simpexu p−1 , p−2 , p−3 dostateˇcneˇ daleko od P, aby neovlivnovaly trojúhelníky nad body P. Souˇradnice vrcholu˚ simplexu Ω vcházejí z MBR zkonstruovaného nad P. M = max(xmax − xmin , ymax − ymin ) Pak p−1 = [−3M , 0], p−2 = [0, 3M ], p−31 = [−3M , −3M ]. Pˇri legalizaci nutné upravit simplexové trojúhelníky (tj. takové, jejichž alesponˇ jeden vrchol pi ∈ Ω. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

41 / 109



39. Ilustrace simplexu Ω


42 / 109



40. Fáze 2: Pˇridání p do DT Nalezení trojúhelníku/trojúhelníku, ˚ se kterými p inciduje. ˇ krok. Kritická pasáž algoritmu, výpoˇcetneˇ nejnároˇcnejší Vyhledání musí být rychlé, nelze prohledávat všechny trojúhelníky, množství procházených trojúhelníku˚ nutno minimalizovat. Vyhledání incidujícího trohúhelníku: ˇ používané metody vyhledávání incidujícího trojúhelníku: Dveˇ nejˇcasteji Metoda procházky (heuristika ,O (n2 )). ˇ DAG Tree (konstrukce ternárního stromu, efektivnejší, O (n · log(n))). Metoda procházky (Lawson Oriented Walk): Procházením okolních trojúhelníku˚ se postupneˇ blížíme k hledanému trojúhelníku ti . Testujeme polohu pˇridávaného bodu p vzhledem k hraneˇ eij v AEL. Testování lze zaˇcít ˇ vhodnejší ˇ e použít heuristiku. Pokud na libovolné hraneˇ e v AEL nebo pro pˇredvýber

( p

vlevo od ei ,j v ti ,

testujeme ei +1,j v ti

vpravo od ei ,j v ti ,

testujeme ej ,i v tj

Bod p leží vuˇ ˚ ci všem stranám hledaného trojúhelníku ti vlevo. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

43 / 109



41. Ukázka Lawson Oriented Walk (1/6)


44 / 109





45 / 109





46 / 109





47 / 109





48 / 109





49 / 109



47. Vztah bodu p a nalezeného ti Existují tˇri ruzné ˚ varianty vzájemné polohy pˇridávaného bodu p a nalezeného trojúhelníku ti : Bod p leží ve vrcholu ti Bod neovlivní již vytvoˇrenou triangulaci DT m , bude zanedbán. ˇ Triangulace ponechána beze zmeny, DT m+1 = DT m . Bod p ∈ ti Zkonstruovány tˇri nové hrany spojující p s vrcholy ti . Trojúhelník t se rozpadne na tˇri nové trojúhelníky se spoleˇcným vrcholem. Bod p leží ve straneˇ ti , tj Oba incidující trojúhelníky ti , tj , v jejichž spoleˇcné hraneˇ pˇridávaný bod ˇ leží, rozdeleny dvojicí úseˇcek jdoucích z p do protilehlých vrcholu˚ ti , tj . Vzniknou cˇ tyˇri nové trojúhelníky se spoleˇcným vrcholem.


50 / 109



48. Bod p ∈ ti Vytvoˇrení nových hran: e12 , e13 , e21 , e23 , e31, e32 . Vytvoˇrení topologie: provázení všech hran s použitím pointeru. ˚


51 / 109



49. Bod p leží ve straneˇ ti , tj ˇ Zmena koncových bodu˚ hran: e12 , e21 , e23 . Zrušení hrany e13 . Vytvoˇrení nových hran: e14 , e32 , e33 , e34 , e41, e43 , e44 . Vytvoˇrení topologie: provázení všech hran s použitím pointeru. ˚


52 / 109



50. Fáze 3: Legalizace noveˇ vytvoˇrené triangulace Takto vzniklá triangulace nemusí být delaunayovská, triangulaci je proto nutno legalizovat. p ∈ ti Pokud pˇridávaný bod p ∈ ti , legalizujeme noveˇ vzniklé trojúhelníky t1 , t2 , t3 s incidujícími trojúhelníky DT (celkem 3 legalizace). Bod p leží ve straneˇ ti , tj Pokud pˇridávaný bod p leží ve straneˇ ti , legalizujeme noveˇ vzniklé trojúhelníky t1 , t2 , t3 , t4 s incidujícími trojúhelníky DT (celkem 4 legalizace). ˇ Tím proces legalizace nekonˇcí, pˇrehození úhlopˇríˇcky v nekterém z výše uvedených pˇrípadu˚ vyvolá potˇrebu legalizace k jejich incidujícím trojúhelníkum. ˚ Pokud alesponˇ jeden z vrcholu˚ trojúhelníka pˇredstavuje bod Ω, nutno upravit legalizaˇcní pravidla. Tento krok je vyvolává potˇrebu rekurzivního ˇrešení problému. V nepˇríznivém pˇrípadeˇ muže ˚ vložený bod p zpusobit ˚ pˇregenerování znaˇcného množství t v DT .


53 / 109



51. Ilustrace procesu legalizace, p ∈ ti


54 / 109



52. Ilustrace procesu legalizace, p leží ve straneˇ ti , tj


55 / 109



53. Pravidla legalizace pro vrcholy Ω (1/2) Jsou reakcí na situaci, že do DT je zahrnut i simplexový trojúhelník Ω. ˇ oblasti P oblastí Ω, mohou být do Aby nedošlo k nevhodnému ovlivnení DT (P ∪ Ω) pˇridány i nelegální hrany. Hrany nelegální v DT (P ∪ Ω) však budou legální DT (P ). Jedná se o hrany ležící na H(P ). Necht’ pi , pj , pk a pi , pj , pl pˇredstavují dva incidující troúhelníky a pi , pj pˇredstavuje testovanou hranu. Nutno uvažovat následující pˇrípady: indexy i , j jsou záporné: Hrana pi , pj je legální. všechny indexy i , j , k , l > 0: ˇ ˇ Normální pˇrípad, provádeno bežné testování. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

56 / 109



54. Pravidla legalizace pro vrcholy Ω (1/2) jeden z indexu˚ i , j , k , l záporný: Pokud jeden z bodu˚ pi , pj ∈ Ω, pak je strana pi , pj je nahrazena pk , pl , v opaˇcném pˇrípadeˇ je ponechána Výsledná hrana nemusí být legální vzhledem k DT (P ∪ Ω), leží na H(P ), leží na H(P ). dva z indexu˚ i , j , k , l jsou záporné Jeden z indexu˚ i , j a jeden z indexu˚ k , l záporný. ˇ než negativní index Pokud je negativní index i , j menší (v abs. hodnote) k , l , je pi , pj v poˇrádku; V opaˇcném pˇrípadeˇ je pi , pj nahrazena pk , pl . Výsledná hrana nemusí být legální vzhledem k DT (P ∪ Ω), leží na H(P ). tˇri z indexu˚ i , j , k , l jsou záporné Situace nemuže ˚ nastat. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

57 / 109



55. Ilustrace legalizaˇcních pravidel pro vrcholy Ω Vlevo indexy i , j záporné. Uprostˇred 2 z indexu˚ i , j , k , l záporné, swap nelegální vzhledem DT (P ∪ Ω). Vpravo dva z indexu˚ i , j , k , l záporné, swap ˇ (bod Ω ∈ k nebrán v potaz). není tˇreba provádet


58 / 109



ˇ simplexových hran 56. Fáze 4: Odstranení ˇ všech stran DT (P ∪ Ω) které incidují z Ω, výsledkem DT (P ). Odtranení Výsledkem oˇríznutí na konvexní obálku.


59 / 109



57. Implementace algoritmu inkrementálního vkládání (1/2) Algoritmus 3: DT Incremental Inserton (a, b, AEL,DT ) 1: Vytvoˇrení obalového trojuhelniku p−1 ,p−2 , p−3 nad P. 2: Opakuj pro i ∈ 1, ..., n : 3: Pˇridej p do DT . 4: Najdi t s vrcholy pi , pj , pk takový, že p ∈ t. 5: Jestliže p uvnitˇr t: 6: Pˇridání hrany pi , p. 7: Pˇridání hrany pj , p. 8: Pˇridání hrany pk , p. 9: Legalizace hrany p, pi , pj , t. 10: Legalizace hrany p, pj , pk , t. 11: Legalizace hrany p, pk , pl , t.


60 / 109



58. Implementace algoritmu inkrementálního vkládání (2/2)

Algoritmus 3: DT Incremental Inserton (a, b, AEL,DT ) 12: Jinak jestliže p leží na hraneˇ pi , pj trojúhelníku˚ t1 , t2 : 13: Pˇridání hrany pi , p. 14: Pˇridání hrany pj , p. 15: Pˇridání hrany pk , p. 16: Pˇridání hrany pl , p. 17: Legalizace hrany p, pj , pk , t. 18: Legalizace hrany p, pk , pi , t. 19: Legalizace hrany p, pi , pl , t. 20: Legalizace hrany p, pl , pj , t. ˇ simplexových hran z DT . 21: Odstranení


61 / 109



59. Algoritmus legalizace hrany Pˇridávaný bod oznaˇcen jako p. Strana pi , pj pˇredstavuje stranu v trojúhelníku t, která má být prohozena. Incidující trojúhelník t 0 tvoˇren hranami pi , pj , pl . Rekurzivní procedura, legalizace volána souˇcasneˇ na dveˇ nové strany. Algoritmus 4: DT Legalizace hrany (p, pi , pj ,t) 1: if (pl , pj ) nelegální 2: najdi trojúhelník t 0 incidující s hranou pi , pj trojúhelníku t. 3: Prohod’ pi , pj za p, pk . 4: Legalizace hrany p, pi , pk . 5: Legalizace hrany p, pk , pj .


62 / 109


60. Triangulace se vstupní podmínkou Oznaˇcová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ˇri triangulaci již nesmí menit. Povinné hrany pˇri konstrukci triangulace kˇríží jiné možné hrany, které jsou vzhledem k ˇ ˇ nejakému kritériu lokálneˇ optimální (a pro triangulaci vhodnejší), avšak tyto hrany nejsou použity. Triangulace se vstupní podmínkou proto nejsou lokálneˇ optimální. ˇ protínat. Geometrický pˇredpoklad: povinné hrany se nesmejí ˇ Široké použití v kartografii tvorbeˇ digitálních modelu˚ terénu, povinné hrany umožnují lepší modelování morfologie terénu. Zástupci: Greedy triangulace se vstupní podmínkou (Constrained Greedy Triangulation). Delaunay triangulace se vstupní podmínkou (Constrained Delaunay Triangulation). ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

63 / 109


61. Greedy triangulace se vstupní podmínkou Greedy triangulace se vstupní podmínkou CGT (P ) není pˇríliš cˇ asto používána. Tvorba CGT (P ) probíhá ve dvou krocích: Pˇridání povinných hran Do prázdné triangulace pˇridány povinné hrany. Žádná z povinných hran nemuže ˚ být pˇri triangulaci nahrazena možnou kratší stranou. Tvorba GT (P ) Konstrukce Greedy triangulace nad P.


64 / 109


62. Delaunay triangulace se vstupní podmínkou ˇ triangulace v geoinformatice. Nejpoužívanejší Na rozdíl od CGT (P ) nutná redefinice triangulace: pˇres 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ˇcního algoritmu. ˇ Možné geometrické problémy: povinná hrana kolineární s nejakou hranou ˇ DT (P ) ⇒rozdelení povinné hrany na 3 cˇ ásti, povinná hrana protíná bod ˇ DT (P ) ⇒rozdelení povinné hrany na 2 cˇ ásti. Konstrukce probíhá ve tˇrech krocích: Vytvoˇrení DT (P ). Zadání povinných hran do DT (P ). Pˇrevod DT (P ) na CDT (P ). Pro bod 3 existuje ˇrada algoritmu, ˚ napˇr. Sloan (1992). ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

65 / 109


63. Pˇrevod DT (P ) na CDT (P ) Algoritmus pˇrevodu DT (P ) na CDT (P ) je rekurzivní. Necht’ každá povinná hrana je definována dvojicí vrcholu˚ vi , vj . Seznam protnutých hran oznaˇcen S. Seznam noveˇ vytvoˇrených hran H. Postup je tvoˇren následujícími kroky: Nalezení stran DT (P ) protínajících povinnou hranu vi vj . Zrušení všech stran v DT (P ) protínajících povinnou hranu vi vj Vytvoˇrení pomocné triangulace. Obnovení DT (P ). ˇ nadbyteˇcných trojúhelníku. Odstranení ˚ Nalezení stran DT (P ) protínajících povinnou hranu vi vj : Testujeme, zda hrana vi vj není již v DT (P ). Pokud nikoliv, nalezneme v DT (P ) všechny strany, které protínají vi vj , odtraníme je z DT (P ) a pˇridáme je do S. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

66 / 109


64. Nalezení stran DT (P ) protínajících povinnou hranu vi vj


67 / 109


ˇ stran protínajících povinnou hranu vi vj z 65. Odstranení DT (P ) Výsledkem pˇrevod DT (P ) na pomocnou triangulaci, jejíž hrany neprotínají vi vj . Necht’ hrana protínající vi vj je oznaˇcena vk vl : ˇ Necht’ vm vn je úhlopˇríˇcka v konvexním cˇ tyˇrúhelníku tvoˇreném dvema 4 se spoleˇcnou stranou vk vl . Algoritmus 5: CDT, remove intersecting edges (S ,H) 1: Opakuj, dokud S není prázdný 2: 3: 4: 5: 6: 7: 8: 9: 10:

Odeber ze seznamu hranu vk vl . Pokud incidující 4 se spoleˇcnou hranou vk vl netvoˇrí konvexní 4-úhelník Pˇridej vk vl do S a jdi na 2). Pokud tvoˇrí konvexní 4-úhelník: Prohodíme diagonálu vk vl v tomto 4 úhelníku za vm vn . Pokud vm vn neprotíná vi vj : Pˇridej vm vn do H. Pokud vm vn protíná vi vj : Pˇridej vm vn do S.


68 / 109


ˇ stran protínajících povinnou hranu 66. Ilustrace odstranení vi vj (1/3)


69 / 109




70 / 109




71 / 109


69. Obnovení DT (P ) Triangulace vytvoˇrená v pˇredchozím kroku není Delaunayovská. Tuto triangulaci je proto nutné pˇrevést na Delaunayovskou. Nad noveˇ vytvoˇrenými hranami je provedena legalizace vzhledem k incidujícím trojúhelníkum. ˚ Algoritmus 6: CDT, Restore DT (S ,H) 1: Opakuj, dokud existuje alesponˇ jeden swap 2: Naˇcti ze seznamu H hranu vk vl . 3: Pokud vk vl 6= vi vj 4: Pokud incidující 4 se spoleˇcnou hranou vk vl není legální 5: Prohození diagonály vk vl v tomto 4 úhelníku za vm vn . 6:

Nahrazení vk vl hranou vm vn v H.


72 / 109


70. Ilustrace obnovení DT (P )


73 / 109


71. Triangulace nekonvexní oblasti a oblasti s otvory Triangulace nekonvexní oblasti: Triangulace množiny bodu˚ ohraniˇcené nekonvexním polygonem. ˇ všechny trojúhelníky vneˇ polygonu (tj. takové, jejichž Z triangulace odstraneny ˇ težišt eˇ je vneˇ polygonu). U DMT, triangulace probíhá pouze uvnitˇr nekonvexní oblasti se vstupními daty, vneˇ oblasti by si algoritmus DMT “vymýšlel”. Využití Ray Algoritmu. Triangulace oblastí s otvory: ˇ Oblast obsahuje podoblasti (otvory), uvnitˇr kterých nebude provádena triangulace. Otvory popsány v opaˇcném poˇradí, než nadˇrazená oblast. Použití pˇri tvorbeˇ DMT, místa bez vrstevnic: vodní plochy, stavební objekty, místa s pˇríliš velkým spádem...


74 / 109


72. Triangulace DT (P )


75 / 109


73. Selekce trojúhelníku˚ uvnitˇr oblasti


76 / 109


ˇ trojúhelníku˚ vneˇ oblasti 74. Odstranení


77 / 109

Datoveˇ závislé triangulace

75. Datoveˇ závislé triangulace ˇ U všech výše uvedených 2D triangulací tvar trojúhelníkové síteˇ ovlivnuje pouze poloha bodu, souˇradnice z nehraje roli. Takové triangulace nejsou bez dodateˇcných informací o terénu (kosterní cˇ áry) vhodné k jeho modelování. ˇ Data Dependent Triangulation (DDT) tyto nedostatky odstranuje. ˇ DT) s využitím heuristik cˇ i genetických algoritmu. Vznikají optimalizací vstupní triangulace (nejˇcasteji ˚ Výhody: ˇ DDT berou v potaz výšku bodu, snaha o optimalizaci tvaru trojúhelníkové síte. ˇ Trojúhelníkový model lépe zohlednuje skuteˇcný tvar terénu. Automatická detekce terénních zlomu, ˚ netˇreba zadávat povinné hrany. Nevýhody: ˇ Optimalizace heuristikou rychlá, zlepšení vetšinou nebývá významné. Optimalizace genetickými algoritmy kvalitní, avšak výpoˇcetneˇ nároˇcné, vhodné pouze pro malé množiny (n < 50000). Dveˇ metody optimalizace: lokální optimalizace, modifikovaná lokální optimalizace. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

78 / 109


76. DT, nevhodné vystižení terénní hrany


79 / 109


77. DDT, lepší vystižení terénní hrany


80 / 109


78. Srovnání vrstevnic DT a DDT


81 / 109


Lokální optimalizace triangulace

79. 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á” cˇ ást triangulace: Edge Based Optimization ˇ Provádena vzhledem ke každé hraneˇ sdílené dvojicí trojúhelníku. ˚ ˇ ˇ varianta. Castejší Vertex Based Optimization ˇ Provádena vzhledem ke každému vrcholu sdíleného trojúhelníky. Rychlé, avšak nepˇríliš významné zlepšení. Možné uvíznutí v lokálním minimum, nepˇripouští doˇcasné zhoršení stavu. Vysoká rychlost konstrukce.


82 / 109



80. Edge Based vs Vertex Based Optimization


83 / 109



81. Edge Based Optimization Každé hraneˇ ei trojúhelníka 4 pˇriˇradí ohodnocovací funkce c pˇriˇradí ohodnocení ci ci = c (4, ei ). ˇ rí ostrost pˇrechodu mezi trojúhelníky. Ohodnocovací funkce meˇ Globální ohodnocení triangulace s m vnitˇrními hranami C=

m X i =1

p

|ci | =

m X

|c (4, ei )|p , p = 1, 2

i =1

Použity L1 a L2 normy. Optimální triangulace minimalizuje globální kritérium C, snaha o co nejvíce hladkou triangulaci. Globální kritérium nejsme schopni exaktneˇ minimalizovat. Heuristika minimalizující v každém kroku lokální kritérium vztažené ke hraneˇ a blízkému okolí s cílem minimalizovat globální kritérium. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

84 / 109



82. Lokální swap kritérium ˇ Vztaženo k hraneˇ ei sdílené dvema trojúhelníky a k jejich incidujícím hranám (celkem 4). Výchozí triangulace DT (P ): Necht’ hrana ei , inciduje s 4 t1 , t2 , sousedící hrany v t1 oznaˇcme ei1 , ei2 , sousedící hrany v t2 oznaˇcme ei3 , ei4 . Swap: Triangulace D T 0 (P ) s trojúhelníky t10 a t20 . Lokální swapovací kritérium: D T 0 je optimální vzhledem k c práveˇ když

|c (4, ei )|p +

4 4 X X c (4, eik ) p > c (40 , ei0 ) p + c (40 , eik ) p . k =1

k =1


85 / 109



83. Ukázka lokální optimalizace


86 / 109



84. Algoritmus lokální optimalizace

Algoritmus provádí opakované swapování nad všemi hranami triangulace. Výsledná triangulace nebude globálneˇ optimální k žádnému kritériu. Algoritmus 7: DDT, LOP (4,e) 1: Opakuj, dokud existuje alesponˇ jeden swap 2: Vezmi hranu ei .

= |c (4, ei )|p +

3:

Spoˇcti ci

4:

Swap (ei → ei0 )

5:

Spoˇcti ci0

6:

if ci < ci0

7:

P4

= |c (40 , ei0 )|p +

k =1

P4

c (4, ek ) p

k =1

i

c (40 , ek ) p i

Swap (ei0 → ei ).


87 / 109



85. Lokální kritéria pro DDT Pˇrehled kritérií: Angle Between Normals (ABN) Distance From Planes (DFP) Smoothnes of Contours (SCO)


88 / 109



86. Pˇrehled kritérií Rovina %i

%i (x , y ) = ai x + bi y + ci z Angle Between Normals: Úhel mezi normálami n(1) , n(2) trojúhelníku˚ t1 , t2

cABN (4, ei ) = ϕ = cos

−1

n(1) · n(2) ∂ρi ∂ρi ∂ρi , kde n(i ) = ( , , ) = (−ai , −bi , 1) ∂ xi ∂ yi ∂ zi kn(1) k kn(2) k

Distance From Planes: Souˇcet vzdálenost bodu˚ pk , pl od rovin %1 , ρ2 . p

p

cDFP (4, ei ) = (d (pk , ρ1 ) + d (pl , ρ2 ) ),

kde

p = 1, 2

Smoothness Of Contours: Úhly mezi pruseˇ ˚ cnicemi v (1) , v (2) trojúhelníku˚ t1 , t2 a vodorovné roviny. cSCO (4, ei ) = ϕ = cos

−1

a1 a2 + b1 b2 v (1) · v (2) p = cos−1 p . kv (1) k kv (21) k a12 + b12 a22 + b22


89 / 109

Digitální model terénu

ˇ 87. Zemský povrch a jeho znázornení ˇ Zemský povrch má nepravidelný, komplikovaný prub ˚ eh: Hladký: Konvexní cˇ i konkávní. Formován prostˇrednictvím pˇrírodních jevu. ˚ ˇ pro matematické modelování. Snadnejší Ostrý: ˇ Zlomy, záˇrezy, hrany, stupne. ˇ Formován cˇ inností cˇ loveka. ˇ terénní tvary tvoˇrí singularity, obtížnejší ˇ pro matematické modelování. Umelé 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).


90 / 109


88. 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 CÚ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 CÚ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 CÚZK). ˇ ˇradu analýz a výpoˇctu: ˇ Nad digitální modely lze provádet ˚ analýza sklonu, osvetlení, expozice, barevná hypsometrie, konstrukci vrstevnic. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

91 / 109


ˇ DMT: trojúhelníková sít’ 89. Znázornení


92 / 109


ˇ DMT: barevná hypsometrie (kvantitativní 90. Znázornení použití barev)


93 / 109


91. Plátování Základem DMT aproximaˇcní plocha procházející všemi zadanými body množiny P = {pi }ni=1 , kde pi = [xi , yi , zi ]. Mimo tyto body dopoˇcítávána podle specifických matematických postupu, ˚ aby se co nejvíce blížila puvodnímu ˚ terénu. Vede ke vzniku ploch vysokých stupnˇ u, ˚ které samovolneˇ oscilují. ˇ použít techniku plátování. Vhodnejší Princip plátování: ˇ ˇ množství malých ploch nižších stupnˇ u˚ ⇒pláty. Rozdelení aproximaˇcní plochy na vetší ˇ stupneˇ tˇri⇒kubické pláty (polynomy stupneˇ 3 již vern ˇ eˇ aproximují terén, jejich Pláty nejˇcasteji ˇ eˇ snadný). výpoˇcet pomern Hranice plátu˚ jsou vedeny po singularitách. Digitální model tvoˇren velkým množstvím plošek (ˇrádoveˇ stovky tisíc, milióny), mezi nimi ostré nebo hladké pˇrechody⇒ tímto zpusobem ˚ lze vyjádˇrit jakýkoliv terén. Poprvé použito v 70. letech pˇri konstrukci letadel (Airbus=Bezierovy pláty, Boeing=Coonsovy pláty). ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

94 / 109


Polyedrický model terénu

92. Polyedrický model terénu Plošky jsou pˇredstavovány trojúhelníky se spoleˇcnou hranou. Sít’ trojúhelníku˚ vytvoˇrena za použití triangulaˇcních algoritmu˚ (Constrained Delaunay Triangulation). Proložením rovin vrcholy jednotlivých trojúhelníku˚ v R3 vznikne nepravidelný ˇ tzv. polyedr, který se pˇrimyká k terénu. mnohosten, V trojúhelnících pouze lineární interpolace, což pro ˇradu úˇcelu˚ nepostaˇcuje. Do polyedrického modelu lze zadat povinné hrany (hˇrbetnice, údolnice, spádnice), které zlepšují jeho aproximaˇcní vlastnosti. Vzhledem k nepravidelnému rozložení bodu˚ je nutné pˇri interpolaci/extrapolaci dat cˇ i ruzných ˚ analytických operacích z polyedrického modelu používat speciální techniky (napˇr. IDW nebo Krigging).


95 / 109


Polyedrický model terénu

93. Konstrukce polyedrického modelu Vrcholy p1 = [x1 , y1 , z1 ], 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ˇredstavující složky normálového vektoru roviny

a=

y1 y2 y3

z1 z2 z3

x1 x2 x3

y1 y2 y3

1 1 1 1 1 1

b=

x1 x2 x3

z1 z2 z3

1 1 1

x1 x2 x3

y1 y2 y3

1 1 1

c=

x1 x2 x3

y1 y2 y3

x1 x2 x3

y1 y2 y3

. 1 1 1 1 1 1

ˇ jsou podle potˇreby Rovnice jednotlivých rovin nejsou udržovány v pameti, operativneˇ urˇcovány (on the fly) ⇒ výhoda pro práci s rozsáhlými modely. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

96 / 109


Lineární nterpolace vrstevnic

94. Interpolace vrstevnic ˇ algoritmy: Lineární interpolacní ˇ Spád terénu mezi dvema body, mezi kterými provádíme interpolaci, je konstantní. ˇ Rozestup vrstevnic mezi dvena body je také konstantní. Výpoˇcetneˇ jednoduché, ale nevystihuje realitu. ˇ algoritmy: Nelineární interpolacní ˇ sklonu terénu ⇒ Mezi interpolovanými body pˇredpokládáme plynulou zmenu geomorfologická interpolace. ˇ ˇ Rozestup vrstevnic mezi dvema body není konstantní, zohlednuje skuteˇcný tvar terénu (sklon okolních plošek). Využití kvadratické cˇ i kubické interpolace. ˇ rítek. Používá se v mapách velkých a stˇredních meˇ Tento postup je znaˇcneˇ složitý a obtížneˇ se algoritmizuje. ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

97 / 109



95. Konstrukce vrstevnic lineární interpolací Dáno:

Rovina plátuT (p1 , p2 , p3 ), rovina ρ : z = h.

Hledáme:

Pruseˇ ˚ cnice AB rovin ρ a T .

Založena na analytické geometrii: hledání pruseˇ ˚ cnice roviny T urˇcené trojúhelníkem t ∈ DT a vodorovné roviny s výškou h. Opakováno nad všemi t.


98 / 109



96. Výpoˇcet souˇradnic bodu˚ A, B Varianty vzájemné polohy % a τ : nemají žádný spoleˇcný bod (neˇrešíme), pruseˇ ˚ cnice tvoˇrí 1 bod (neˇrešíme), pruseˇ ˚ cnice je úseˇcka. ˇ do roviny XZ a YZ platí: Z podobnosti trojúhelníku˚ pˇredstavujících prum ˚ ety x2 − x1 xb − x1 = z2 − z1 z − z1 xa − x1 x3 − x1 = z3 − z1 z − z1

y2 z2 y2 z2

− y1 yb − y1 = , − z1 z − z1 − y1 ya − y1 = . − z1 z − z1

Výsledné souˇradnice koncových bodu˚ A, B pruseˇ ˚ cnice urˇcíme ze vztahu˚ x3 z3 y3 ya = z3 xa =

− x1 (z − z1 ) + x1 − z1 − y1 (z − z1 ) + y1 − z1

x2 z2 y2 yb = z2 xb =

− x1 (z − z1 ) + x1 , − z1 − y1 (z − z1 ) + y1 . − z1

Test, zda rovina % protíná stranu pi , pi +1 trojúhelníku:

(z − zi )(z − zi +1 )

<

0.


99 / 109



97. Ukázka výpoˇctu vrstevnic lineární interpolací (DT)


100 / 109



98. Vliv vložení povinné hrany do triangulace: výchozí situace


101 / 109



ˇ 99. Vliv vložení povinné hrany do triangulace: lokální zmena ˇ prub ˚ ehu DMT


102 / 109


Analýza sklonu

100. Analýza sklonu terénu Analytická úloha realizovaná nad DMT. ˇ u, Použití pro analýzu hydrologických pomer ˚ sesuvu, ˚ lavin, návrhy komunikací, stavebních objektu. ˚ Zprostˇredkující hodnotou je gradient (tj. vektor max. spádu). Gradient ∇f (x0 , y0 , z0 ) funkce f (x , y , z ) v bodeˇ p = [x0 , y0 z0 ]

∇f (x0 , y0 , z0 ) = (

∂f ∂f ∂f (x0 ), (y0 ), (z0 )). ∂x ∂y ∂z

Rovnice roviny %

ρ : ax + by + cz + d = 0. Gradient ∇ρ(x0 , y0 , z0 ) roviny ρ

∇ρ(x0 , y0 , z0 ) = (

∂ρ ∂ρ ∂ρ (x0 ), (y0 ), (z0 )) = (a, b, c ). ∂x ∂y ∂z


103 / 109


Analýza sklonu

101. Analýza sklonu terénu Rovina ρ procházející 3 body

x − x1 y − y1 z − z1 x2 − x1 y2 − y1 z2 − z1 x3 − x1 y3 − y1 z3 − z1

= 0.

Odchylka ϕ rovin ρ a π :

D E n1· n2 , ϕ ∈ 0, π ϕ = arccos kn1 k kn2 k 2 n1

= (a , b , c )

n2

= (0, 0, 1)

ˇ nad každým trojúhelníkem t DMT. Výpoˇcet prováden ˇ barvou) na základeˇ hodnoty ϕ. Vizualizace trojúhelníku˚ (tj. vyplnení ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

104 / 109


Analýza sklonu

102. Sklon terénu


105 / 109


Analýza sklonu

103. Vizualizace sklonu terénu


106 / 109


Analýza orientace

104. Analýzy orientace terénu ˇ elství, ˇ Využití ve stavebnictví, zemed hydrologii. ˇ Sluneˇcní svit ovlinuje množství tepla dopadajícího na zemský povrch, ˇ podmínky pro rust ˇ elských ˇ hydrologické pomery, ˚ zemed plodin. ˇ gradientu ∇ρ do roviny x , y . Orientace v bodeˇ definována jako azimut prum ˚ etu ˇ Vektor v prum ˚ etem gradientu ∇ρ(x0 , y0 , z0 ) do roviny xy v =(

∂ρ ∂ρ (x0 ), (y0 ), 0) = (a, b, 0). ∂x ∂y

Azimut α vektoru v

A = arctan

b

a

, A ∈ h0, 2π)

ˇ nad každým trojúhelníkem DMT. Výpoˇcet prováden Pozor na správnou detekci kvadrantu. ˚ ˇ Tomáš Bayer | [email protected] (Katedra aplikované Rovinné geoinformatiky triangulace a kartografie. a jejich využití. Pˇrírodovedecká fakulta UK.)

107 / 109


Analýza orientace

105. Orientace terénu


108 / 109


Analýza orientace

106. Vizualizace orientace terénu


109 / 109

Rovinné triangulace a jejich využití

Recommend Documents