11 Triangulace
RNDr. Petra Surynková, Ph.D. Katedra didaktiky matematiky
Univerzita Karlova v Praze
Matematicko-fyzikální fakulta
http://surynkova.info
Triangulace
Význam triangulace
trojúhelník je základní grafický element
aproximace ploch
předzpracování pro jiné algoritmy
…
Počítačová geometrie Petra Surynková
příklad triangulace
Triangulace
Definice
Triangulace nad množinou bodů v rovině představuje
takové planární rozdělení, které vytvoří soubor trojúhelníků
s vrcholy z množiny P, přičemž platí
libovolné dva trojúhelníky mají společnou nejvýše hranu
nebo vrchol
sjednocení 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
Počítačová geometrie Petra Surynková
1 2{ , ,..., } nP p p p
m 1 2{ , ,..., } mT t t t
, , i jt t T i j
T
Triangulace
Počítačová geometrie Petra Surynková
ukázky vzájemných poloh
trojúhelníků, které tato definice
vylučuje
Triangulace
Pro 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
Počítačová geometrie Petra Surynková
1 2{ , ,..., } nP p p pT
2 2 2
3 3 3
KO D
H KO D
m n n n
n n n n
KOnHn
m
Dn
Triangulace
Nejčastější aplikace triangulací
kartografie – tvorba digitálního modelu terénu
aproximace ploch
zpracování obrazu – segmentace, rozpoznávání vzoru
tvorba prostorových modelů z dat laserového skenování
počítačová grafika – vizualizace prostorových dat ve scénách
kartografická generalizace
modelování přírodních jevů – eroze
interpolační techniky
biometrie – detekce otisků prstů
předzpracování pro jiné algoritmy
Počítačová geometrie Petra Surynková
Triangulace
Nejčastější aplikace triangulací
Počítačová geometrie Petra Surynková
rekonstrukce terénu z dat leteckého laserového skenování
Triangulace
Nejčastější aplikace triangulací
Počítačová geometrie Petra Surynková
Triangulace
Nejčastější aplikace triangulací
Počítačová geometrie Petra Surynková
výšková mapa
Triangulace
Nejčastější aplikace triangulací
Počítačová geometrie Petra Surynková
výšková mapa http://www.natur.cuni.cz/~baye
rtom/
Triangulace
Nejčastější aplikace triangulací
Počítačová geometrie Petra Surynková
triangulace
povrchu
Triangulace
Nejčastější aplikace triangulací
Počítačová geometrie Petra Surynková
triangulace
povrchu
Triangulace
Kritéria kvality triangulace
jednoduchost algoritmu, snadná implementace
př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 sestrojit
triangulace by měla produkovat pravidelné trojúhelníky vhodných tvarů
(blížící se rovnostranným)
některé požadavky v kontrastu
triangulační algoritmy patří mezi jedny z nejvíce teoreticky rozpracované
postupy
Počítačová geometrie Petra Surynková
Triangulace
Volba 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é hrany
mož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, …
Počítačová geometrie Petra Surynková
Triangulace
Dělení triangulací
podle geometrické konstrukce
Delaunay triangulace
Greedy triangulace
MWT – Minimum Weight Triangulation
triangulace s povinnými hranami – Constrained Triangulation
datově závislé triangulace
podle použitých kritérií
lokálně optimální triangulace
globálně optimální triangulace
multikriteriálně optimalizované triangulace
vlastnosti triangulace se posuzují ve vztahu k těmto kritériím
Počítačová geometrie Petra Surynková
Triangulace
Loká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ériu
pro 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í triangulace
všechny trojúhelníky triangulace jsou optimální vzhledem k zadanému
kritériu
neexistuje jiná triangulace, která by dosáhla alespoň u jednoho
trojúhelníku lepší hodnoty posuzovaného kritéria
je současně lokálně optimální
Multikriteriálně optimalizované triangulace
kombinace několika lokálních či globálních kritérií
doposud nejsou známy efektivní algoritmy, dlouhé výpočetní časy
Počítačová geometrie Petra Surynková
Triangulace
Př. 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í
Počítačová geometrie Petra Surynková
Triangulace
Lokální kritéria
jsou založeny na geometrických zákonitostech
nejčastěji užívaná kritéria
minimální/maximální úhel v trojúhelníku
minimální/maximální výška v trojúhelníku
minimální/maximální poloměr vepsané kružnice
minimální/maximální poloměr opsané kružnice
minimá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
Počítačová geometrie Petra Surynková
Triangulace
Lokální kritéria
hodnota nejmenšího úhlu
trojú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 na rozdíl od optimální, je-li
nejmenší úhel generovaný triangulací větší než nejmenší úhel generovaný
triangulací
hodnota maximálního úhlu
trojú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 na rozdíl od optimální, je-li
největší úhel generovaný triangulací menší než největší úhel generovaný
triangulací
Počítačová geometrie Petra Surynková
( ) T
*T ( *) ( ), i iT T T
( ) T
*T ( *) ( ), i iT T T
*T
*TiT
*T
iT
iT
*T
iT
Triangulace
Globální kritéria
optimalizují geometrické parametry všech trojúhelníků v triangulaci
nejčastěji užívaná kritéria
součet délek hran
povinné hrany
…
Počítačová geometrie Petra Surynková
Triangulace
Globální kritéria
Součet délek hran
součet délek hran – minimální
triangulace minimalizující součet délek hran – MWT (Minimal Weight
Triangulation)
Povinné hrany
předem definované hrany uvnitř triangulace – Constrained Triangulation
taková 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
Počítačová geometrie Petra Surynková
Triangulace
Greedy triangulace
hladová triangulace
triangulace složená z nejkratších možných neprotínajících se hran
vlastnosti GT
jednoznačné za předpokladu, že neexistují stejně dlouhé hrany
necitlivá na úhlová kritéria – vytváří trojúhelníky s nejkratšími stranami,
trojúhelníky tak nemusí splňovat žádnou speciální geometrickou podmínku
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
jednoduchá implementace
výsledná triangulace se blíží MWT
Počítačová geometrie Petra Surynková
Triangulace
Greedy triangulace
algoritmus
vytvoří všechny potenciální hrany
setří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
Počítačová geometrie Petra Surynková
( 1) / 2n n
3 6n
Triangulace
Počítačová geometrie Petra Surynková
6n 6(6 1) / 2 15 hran
1. přidávaná hrana - nejkratší všechny potenciální hrany
Triangulace
Počítačová geometrie Petra Surynková
postupně přidáváme hrany do triangulace …
Triangulace
Počítačová geometrie Petra Surynková
postupně přidáváme hrany do triangulace …
Triangulace
Počítačová geometrie Petra Surynková
postupně přidáváme hrany do triangulace …
Triangulace
Počítačová geometrie Petra Surynková
postupně přidáváme hrany do triangulace …
Triangulace
Počítačová geometrie Petra Surynková
nelze přidat, protíná
hrany v triangulaci
nelze přidat, protíná
hrany v triangulaci
postupně přidáváme hrany do triangulace …
Triangulace
Počítačová geometrie Petra Surynková
nelze přidat, protíná
hrany v triangulaci poslední přidaná hrana, další
by protínaly hrany v triangulaci
postupně přidáváme hrany do triangulace …
Triangulace
Delaunay triangulace
nejčastěji používaná triangulace
existuje i ve 3D – Delaunay tetrahedronizace
vlastnosti DT
uvnitř kružnice opsané libovolnému trojúhelníku neleží žádný jiný bod
z množiny
maximalizuje minimální úhel, avšak neminimalizuje maximální úhel
je lokálně optimální i globálně optimální vůči kritériu minimálního úhlu
je jednoznačná, pokud žádné čtyři body neleží na kružnici
hranice je konvexní obálka
výsledné trojúhelníky se v porovnání se všemi známými triangulacemi nejvíce
blíží rovnostranným trojúhelníkům
Počítačová geometrie Petra Surynková
1 2{ , ,..., } nP p p pit T
Triangulace
Delaunay triangulace
Počítačová geometrie Petra Surynková
opsaná kružnice
libovolnému
trojúhelníku
neobsahuje žádný
jiný bod
Triangulace
Delaunay triangulace
algoritmy
metoda lokálního zlepšování prohazováním hran
algoritmus radiálního zametání
inkrementální vkládání
metoda rozděl a panuj
(nepřímá konstrukce pomocí Voronoi diagramu)
…
Počítačová geometrie Petra Surynková
Triangulace
Delaunay triangulace
Metoda lokálního zlepšování
metoda je použitelná pouze ve 2D, obtížně převeditelné do vyšší dimenze
vychází se z libovolné triangulace
prová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 hran
výsledkem je stav, kdy jsou oba trojúhelníky legální, tj. lokálně
optimální vzhledem ke kritériu vnitřního úhlu
Počítačová geometrie Petra Surynková
Triangulace
Delaunay triangulace
Metoda lokálního zlepšování
Počítačová geometrie Petra Surynková
uvnitř opsané kružnice
neleží žádný jiný vrchol
Triangulace
Delaunay triangulace
Platí
Nechť hrana inciduje s trojúhelníkem tvořeným vrcholy
a trojúhelníkem tvořeným vrcholy .
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í.
Počítačová geometrie Petra Surynková
,i jp p1t , ,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
Triangulace
Delaunay triangulace
Algoritmus radiálního zametání
Počítačová geometrie Petra Surynková
spojení bodu vstupní
množiny s bodem uvnitř doplnění obrysových hran
Triangulace
Delaunay triangulace
Algoritmus radiálního zametání
Počítačová geometrie Petra Surynková
konvexní obálka lokální optimalizace
Triangulace
Delaunay triangulace
Inkrementální vkládání
často používaná metoda, lze použít i ve 3D
klasický případ rekurzivní úlohy – fáze legalizace
princip algoritmu – zjednodušeně
konstrukce obalujícího trojúhelníku (simplexu) – body
– obsahuje všechny body vstupní množiny (může být i konvexní obálka,
ale přidává čas navíc a komplikuje algoritmus)
hledání počátečního simplexu může být komplikovaná úloha
žádný z bodů vstupní množiny neleží vně obalujícího simplexu
DT konstruujeme nad sjednocením množin – vstupní množiny a vrcholů
simplexu
vrcholy simplexu musí být dostatečně daleko od bodů vstupní množiny, aby
neovlivňovaly trojúhelníky vznikající nad body vstupní množiny
Počítačová geometrie Petra Surynková
3 2 1, ,p p p
Triangulace
Delaunay triangulace
Inkrementální vkládání
souřadnice vrcholů simplexu se odvozují od min-max boxu
v teoretických popisech leží tyto body v nekonečnu
v praxi mohou být zvoleny například takto
je střed min-max boxu
je nejdelší hrana min-max boxu
je konstanta – velmi těžké odhadnout, pokud je tato konstanta příliš
malá, může být hranice triangulace po odebrání vrcholů simplexu
nekonvexní, pokud je příliš velká, trpí numerická stabilita
experimenty ukazují, že tato hodnota bývá volena mezi 10 a 20
Počítačová geometrie Petra Surynková
3 2 1, , p p p
3 2 1( , ), ( , ), ( , )x y x y x yp s Kd s p s s Kd p s Kd s Kd
[ , ] x yS s sd
K
Triangulace
Delaunay triangulace
Inkrementální vkládání
konstrukce obklopujícího trojúhelníku
Počítačová geometrie Petra Surynková
3p
2p
1p
opakujeme,
dokud v
triangulaci
nejsou
všechny
body
Triangulace
Delaunay triangulace
Inkrementální vkládání
přidání bodu do triangulace
nalezení trojúhelníku, se kterým přidávaný bod inciduje
legalizace nově vytvořené triangulace
odstranění obklopujícího trojúhelníku
oříznutí na konvexní obálku
Počítačová geometrie Petra Surynková
Delaunay triangulace
Inkrementální vkládání
přidání bodu do triangulace a nalezení trojúhelníku, se kterým přidávaný bod
inciduje
nalezení trojúhelníku, se kterým přidávaný bod inciduje, je kritická pasáž algoritmu,
výpočetně nejnáročnější krok
vyhledání musí být rychlé, nelze prohledávat všechny trojúhelníky, množství
procházených trojúhelníku nutno minimalizovat
dvě nejčastěji používané metody vyhledávání incidujícího trojúhelníku
metoda procházky
procházením okolních trojúhelníku se postupně blížíme k hledanému
trojúhelníku
DAG Tree (konstrukce ternárního stromu)
Triangulace
Počítačová geometrie Petra Surynková
Delaunay triangulace
Triangulace
Počítačová geometrie Petra Surynková
Delaunay triangulace
Triangulace
Počítačová geometrie Petra Surynková
Delaunay triangulace
Triangulace
Počítačová geometrie Petra Surynková
Delaunay triangulace
Inkrementá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 polohy
bod 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 vrcholem
bod 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
Počítačová geometrie Petra Surynková
Triangulace
Delaunay triangulace
Inkrementální vkládání
Počítačová geometrie Petra Surynková
1p
obklopující trojúhelník postupné vkládání bodů
ukázka vkládání bodů
Triangulace
Delaunay triangulace
Inkrementální vkládání
Počítačová geometrie Petra Surynková
1p
2p
3p1p
2p
postupné vkládání bodů
Triangulace
Delaunay triangulace
Inkrementální vkládání
Počítačová geometrie Petra Surynková
legalizace po přidání bodu – klasický
případ rekurzivní úlohy
1p
2p
3p1p
2p
3p
Triangulace
Delaunay triangulace
Inkrementální vkládání
Počítačová geometrie Petra Surynková
1p
2p
3p1p
2p
3p
legalizace po přidání bodu – klasický
případ rekurzivní úlohy
Triangulace
Delaunay triangulace
Inkrementální vkládání
legalizace nově vytvořené triangulace
testuje se pomocí opsané kružnice – všechny vnější hrany nově vzniklých
trojúhelníků - zda vrchol sousedního trojúhelníku neleží uvnitř kružnice
pokud neleží, testování v tomto směru nepokračuje, pokud leží, triangulace
musí být opravena
= prohazování hran
v síti se objeví nové trojúhelníky a ověřování platnosti hran musí pokračovat –
opět se ověřují všechny vnější hrany (může dojít ke změně celé triangulace)
Počítačová geometrie Petra Surynková
Triangulace
Delaunay triangulace
Inkrementální vkládání
Počítačová geometrie Petra Surynková
odstranění
simplexových hran
Triangulace
Delaunay triangulace
Inkrementální vkládání
Počítačová geometrie Petra Surynková
výsledná DT
Triangulace
Delaunay triangulace ve 3D - tetrahedronizace
definuje se analogicky
koule opsaná libovolnému tetrahedronu neobsahuje ve svém vnitřku žádný
další bod ze vstupní množiny bodů
vlastnosti
minimalizuje maximální poloměr
Počítačová geometrie Petra Surynková
zadaná množina
bodů jsou vrcholy
krychle a její střed