Triangulace · 2010. 1. 22. · Triangulace Definice Triangulace nad množinou bodů v rovině...

TriangulaceVýznam triangulace

trojúhelník je základní grafický elementaproximace plochpředzpracování pro jiné algoritmy…

Počítačová geometrie Petra Surynková

příklad triangulace

TriangulaceDefiniceTriangulace nad množinou bodů v roviněpředstavuje takové planární rozdělení, které vytvoří soubor trojúhelníků tak, aby platilo

libovolné dva trojúhelníky mají společnou nejvýše hranu nebo vrcholsjednocení trojúhelníků je souvislá množina ve 2D (obecněnemusí být konvexní a může obsahovat díry)

(uvnitř žádného trojúhelníku neleží žádný další bod z P)


1 2{ , ,..., }nP p p p=m

1 2{ , ,..., }mT t t t=, ,i jt t T i j∈ ≠

T

Triangulace


ukázky vzájemných poloh trojúhelníků, které tato definice vylučuje

TriangulacePro triangulaci nad množinou bodův rovině platí

- počet trojúhelníků- počet hran- počet vrcholů konvexní obálky- počet děr

vztahy lze odvodit z Eulerovy formule


1 2{ , ,..., }nP p p p=T

2 2 23 3 3

KO D

H KO D

m n n nn n n n= − + −

= − + −

KOnHn

m

Dn

TriangulaceNejčastější aplikace triangulací

kartografie – tvorba digitálního modelu terénuaproximace plochzpracování obrazu – segmentace, rozpoznávání vzorutvorba prostorových modelů z dat laserového skenovánípočítačová grafika – vizualizace prostorových dat ve scénáchkartografická generalizacemodelování přírodních jevů – erozeinterpolační technikybiometrie – detekce otisků prstůpředzpracování pro jiné algoritmy




rekonstrukce terénu z dat leteckého laserového skenování





výšková mapa



výšková mapahttp://www.natur.cuni.cz/~bayertom/



triangulace povrchu

TriangulaceKritéria kvality triangulace

jednoduchost algoritmu, snadná implementacepřevod do vyšších dimenzíoptimální tvar trojúhelníkové sítěmalá citlivost na singulární případy, kdy triangulace neníjednoznačná nebo ji nelze sestrojittriangulace by měla produkovat pravidelné trojúhelníky vhodných tvarů (blížící se rovnostranným)

některé požadavky v kontrastutriangulační algoritmy patří mezi jedny z nejvíce teoreticky rozpracované postupy


TriangulaceVolba triangulace – co je nutné zohlednit

tvar trojúhelníkůtriangulace by měla produkovat pravidelné trojúhelníky(důležité při tvorbě digitálního modelu terénu)

povinné hranymožnost vkládat povinné hrany a modifikovat tvar triangulace

triangulace nekonvexní oblasti nebo oblasti obsahující díry

v mapách se triangulace neprovádí např. pro vodní plochy, budovy, …


TriangulaceDělení triangulací

podle geometrické konstrukceDelaunay triangulaceGreedy triangulaceMWT – Minimum Weight Triangulationtriangulace s povinnými hranami – Constrained Triangulationdatově závislé triangulace

podle použitých kritériílokálně optimální triangulaceglobálně optimální triangulacemultikriteriálně optimalizované triangulace

vlastnosti triangulace se posuzují ve vztahu k těmto kritériím


TriangulaceLokálně optimální triangulace

každý čtyřúhelník tvořený dvojicí trojúhelníků se společnou stranou je triangularizován optimálně vzhledem k zadanému kritériupro danou množinu bodů v rovině existuje více lokálně optimálních triangulací, každá z nich optimalizuje jiné kritérium

Globálně optimální triangulacevšechny trojúhelníky triangulace jsou optimální vzhledem k zadanému kritériuneexistuje jiná triangulace, která by dosáhla alespoň u jednoho trojúhelníku lepší hodnoty posuzovaného kritériaje současně lokálně optimální

Multikriteriálně optimalizované triangulacekombinace několika lokálních či globálních kritériídoposud nejsou známy efektivní algoritmy, dlouhé výpočetní časy


TriangulacePř. 4 body v rovině (všechny leží na konvexní obálce) a jejich možné triangulace

existují pouze dvě různé triangulace

vzhledem k posuzovanému kritériu je jedna z triangulacíoptimální


TriangulaceLokální kritéria

jsou založeny na geometrických zákonitostechnejčastěji užívaná kritéria

minimální/maximální úhel v trojúhelníkuminimální/maximální výška v trojúhelníkuminimální/maximální poloměr vepsané kružniceminimální/maximální poloměr opsané kružniceminimální/maximální plocha trojúhelníkuúhel mezi normálami sousedních trojúhelníků…

nejčastěji užíváno první kritérium


TriangulaceLokální kritéria

hodnota nejmenšího úhlutrojúhelníky by neměly mít malé úhly, tzv. max-min úhlové kritérium

je optimální jsou možné triangulace

triangulace je vzhledem k tomuto kritériu narozdíl od optimální, je-li nejmenší úhel generovaný triangulací větší než nejmenší úhel generovaný triangulací

hodnota maximálního úhlutrojúhelníky by neměly mít tupé úhly, tzv. min-max úhlové kritérium

je optimální jsou možné triangulace

triangulace je vzhledem k tomuto kritériu narozdíl od optimální, je-li největší úhel generovaný triangulací menší než největší úhel generovaný triangulací


( )Tα

*T ( *) ( ),i iT T Tα α≥

( )Tβ

*T ( *) ( ),i iT T Tβ β≤*T iT

*TiT

*T iT*T

iT

TriangulaceGlobální kritéria

optimalizují geometrické parametry všech trojúhelníků v triangulacinejčastěji užívaná kritéria

součet délek hranpovinné hrany…


TriangulaceGlobální kritéria

Součet délek hransoučet délek hran – minimálnítriangulace minimalizující součet délek hran – MWT (MinimalWeight Triangulation)

Povinné hranypředem definované hrany uvnitř triangulace – ConstrainedTriangulationtaková triangulace není lokálně optimálnípři tvorbě digitálního modelu terénu lze do takové triangulace zadat charakteristické terénní tvary a vylepšit tak modelováníterénu


TriangulaceGreedy triangulace

hladová triangulacetriangulace složená z nejkratších možných neprotínajících se hranvlastnosti GT

jednoznačné za předpokladu, že neexistují stejně dlouhé hranynecitlivá na úhlová kritéria – vytváří trojúhelníky s nejkratšími stranami, trojúhelníky tak nemusí splňovat žádnou speciálnígeometrickou podmínkusíť trojúhelníků není z tvarového hlediska optimalizována –do triangulace tak mohou být přidány tvarově nevhodnétrojúhelníkyjednoduchá implementacevýsledná triangulace se blíží MWT


TriangulaceGreedy triangulace

algoritmusvytvoří všechny potenciální hranysetřídí vzestupně hrany podle délky seznam hran

do výsledné triangulace se postupně přidávají hrany –začíná se nejkratší

dokud seznam hran není prázdný nebo dokud počet hran v triangulaci je menší nežhrana ze seznamu se do triangulace přidá, pokud neprotínážádnou hranu, která už v triangulaci je


( 1) / 2n n −

3 6n −

Triangulace


6n = 6(6 1) / 2 15− = hran

1. přidávaná hrana - nejkratšívšechny potenciální hrany

Triangulace


postupně přidáváme hrany do triangulace …

Triangulace



Triangulace



Triangulace



Triangulace


nelze přidat, protínáhrany v triangulaci



Triangulace



poslední přidaná hrana, dalšíby protínaly hrany v triangulaci


TriangulaceDelaunay triangulace

nejčastěji používaná triangulaceexistuje i ve 3D – Delaunay tetrahedronizacevlastnosti DT

uvnitř kružnice opsané libovolnému trojúhelníku neležížádný jiný bod z množinymaximalizuje minimální úhel, avšak neminimalizuje maximální úhelje lokálně optimální i globálně optimální vůči kritériu minimálního úhluje jednoznačná, pokud žádné čtyři body neleží na kružnicihranice je konvexní obálkavýsledné trojúhelníky se v porovnání se všemi známými triangulacemi nejvíce blíží rovnostranným trojúhelníkům


1 2{ , ,..., }nP p p p=it T∈



opsaná kružnicelibovolnému trojúhelníku neobsahuje žádný jiný bod


algoritmymetoda lokálního zlepšováníinkrementální vkládáníalgoritmus radiálního zametánírozděl a panuj(nepřímá konstrukce pomocí Voronoi diagramu)…



Metoda lokálního zlepšovánímetoda je použitelná pouze ve 2D, obtížně převeditelné do vyšší dimenzevychází se z libovolné triangulaceprovádí se tzv. legalizace

modifikují se hrany sdílené dvojicí trojúhelníků tvořících konvexní čtyřúhelník tak, aby bylo splněno úhlové kritérium –maximalizace minimálního úhlu = prohození diagonál = odstranění nelegálních hranvýsledkem je stav, kdy jsou oba trojúhelníky legální, tj. lokálněoptimální vzhledem ke kritériu vnitřního úhlu



Metoda lokálního zlepšování


uvnitř opsané kružnice neleží žádný jiný vrchol


PlatíNechť hrana inciduje s trojúhelníkem tvořeným vrcholy

a trojúhelníkem tvořeným vrcholy a kružnice prochází body . Hrana je nelegálníprávě tehdy, když bod leží uvnitř kružnice.

Pokud body tvoří konvexní čtyřúhelník a neleží na opsané kružnici, pak jedna z hran nebo je nelegální.


,i jp p 1t, ,i j kp p p

2t , ,i j lp p p, ,i j kp p p ,i jp p

lp

, ,i j kp p p,i jp p ,k lp p

opakujeme, dokud v triangulaci nejsou všechny body


Inkrementální vkládáníčasto používaná metoda, lze použít i ve 3Dklasický případ rekurzivní úlohy – fáze legalizaceprincip algoritmu – zjednodušeně

konstrukce obalujícího trojúhelníku (simplexu) – obsahuje všechny body vstupní množinypřidání bodu do triangulacenalezení trojúhelníku, se kterým přidávaný bod incidujelegalizace nově vytvořené triangulaceodstranění obklopujícího trojúhelníkuoříznutí na konvexní obálku



Inkrementální vkládání


1p

obklopující trojúhelník postupné vkládání bodů

ukázka vkládání bodů




1p2p

3p1p2p

postupné vkládání bodů




legalizace po přidání bodu

1p2p

3p1p

2p

3p

Delaunay triangulaceInkrementální vkládání

přidání bodu do triangulace a nalezení trojúhelníku, se kterým přidávaný bod inciduje

existují tři polohybod leží ve vrcholu – je zanedbán, již vytvořenou triangulaci neovlivníbod leží na straně – oba incidující trojúhelníky, v jejichž společnéhraně přidávaný bod leží, jsou rozděleny dvojicí úseček jdoucích z přidávaného bodu do protilehlých vrcholů – vzniknou čtyři trojúhelníky se společným vrcholembod leží uvnitř trojúhelníku – bod je spojen s jeho vrcholy –vzniknou tři trojúhelníky

dále legalizace – někdy ovlivní již vytvořené trojúhelníky –nutné překontrolovat, nutné rozlišit případy

Triangulace





odstraněnísimplexových hran




výsledná DT

Date post:	15-Dec-2020
Category:	Documents
Upload:	others
View:	1 times
Download:	0 times

Triangulace · 2010. 1. 22. · Triangulace Definice Triangulace nad množinou bodů v rovině...

Documents