10. Delaunayova triangulace
Motivace. Uvažujme funkci / : IR2 —y IR. Její hodnoty známe pouze v konečné množině bodů P. Jeden způsob, jak takovou funkci aproximovat, je rozdělit konvexní obal množiny P na trojúhelníky s vrcholy v bodech množiny P a na těchto trojúhelnících aproximovat funkci / lineárně. To znamená následující: Každý bod x trojúhelníka PíPjPk je konvexní kombinací bodů pÍ7 pj, p^
x = txpx + t2p2 + t3p3,     kde tx + t2 + t3 = 1, tx >0,t2> 0, t3 > 0,
a proto položíme
Graf aproximace funkce / je tedy tvořen v IR2 x IR trojúhelníky s vrcholy (pi,f(pi), (Pj,f(Pj) a (Pk,f(Pk))-
OBR 10.1 Lineární aproximace funkce /
Tato aproximace podstatně závisí na tom, jakým způsobem provedeme triangulaci konvexního obalu naší množiny. Zdá se, že dobrá triangulace je taková, kde nejsou trojúhelníky a malými úhly. Takovým triangulacím se budeme věnovat v následujícím textu.
Úhlově optimální triangulace. Nejdříve ukážeme, že pro danou konečnou množinu P bodů v rovině mají všechny triangulace jejího konvexního obalu stejný počet trojúhelníků. To nám dá možnost porovnávat různé triangulace lexikograficky podle velikosti úhlů.
Věta 10.1. Nechť P je množina n bodů v rovině. Nechť konvexní obal množiny P má k hran. Potom je každá triangulace konvexního obalu tvořena 2n — 2 — k trojúhelníky a má 3n — 3 — k hran.
Důkaz. Označme počet trojúhelníků v triangulaci jako m. Každý trojúhelník má tři hrany. Ze všech hran je k hranou pouze jednoho trojúhelníku, zbývající jsou hranou právě dvou trojúhelníků. Celkový počet hran je tedy roven
tif(Pi)+t2f(p2)+t3f(P3).
h
3m + k
2
Eulerova věta říká, že
n - h + (m + 1) = 2. Dosazením za h odvodíme po krátké úpravě
m = 2n — 2
k.
Odtud dosazením do výrazu pro h dostaneme
h
3n — 3
k.
□
l
2
Nechť je tedy T nějaká triangulace množiny P s m = 2n — 2 — k trojúhelníky. Trojúhelníky této triangulace mají 3m úhlů. Seřaďme je podle velikosti do posloupnosti
a(T) = («1, a2,..., a3m),    ctx < a2 < ■ ■ ■ < a3m.
Na těchto posloupnostech úhlů definujme lexikografické uspořádání
a{T) < a(T),
jestliže existuje i E {1,2,..., 3m} tak, že
a j = a j    pro j < i    a    on < a^.
Triangulace T se nazývá úhlově optimální, jestliže je maximální v tomto uspořádání.
Legální hrany a legální triangulace. Pro účely našeho algoritmu na vytváření vhodné triangulace budeme potřebovat pojem legální hrany a legální triangulace. Před tím, než je budeme definovat, si krátce zopakujme to, co ze středoškolské geometrie víme o obvodových úhlech.
Na kružnici /C se středem s uvažujme body p a q. Ty rozdělují kružnici na dva oblouky. Na jednom z nich zvolme bod a, na druhém bod b. Uhly v trojúhelnících pqa a pqb u vrcholů a a b označme postupně jako a a (3. Nazýváme je obvoáovými úhly tětivy pq pro jednotlivé oblouky kružnice /C. Obvodové úhly mají tyto dvě důležité vlastnosti:
• Velikost úhlů a a (3 nezávisí na poloze bodů a a b v daných obloucích.
• Součet a + f3 = 180°.
Odtud lze snadno odvodit, že každý trojúhelník pqc, kde bod c leží v polorovině pqa uvnitř kružnice /C, má u vrcholu c úhel
7 > a
a každý trojúhelník pqd, kde bod d leží v polorovině pqa vně kružnice /C, má u vrcholu d úhel
5 < a.
OBR 10.2 Obvodové úhly
Dále lze z vlastností obvodových úhlů ukázat, že čtyřúhelníku lze opsat kružnici, právě když má součet protilehlých úhlů roven 180°.
Nyní uvažujme triangulaci T a v ní hranu pq, která má v triangulaci T dva přilehlé trojúhelníky, a to pqr a pqt. Takovou hranu nazveme ilegální hranou triangulace T, jestliže bod t leží uvnitř kružnice opsané trojúhelníku pqr. To je ekvivalentní s tím, že součet úhlů při vrcholech r a t obou trojúhelníků je větší než 180° a tedy také s tím, že bod r leží uvnitř kružnice opsané trojúhelníku pqt.
OBR 10.3 Ilegální hrana pq
Hrany triangulace T, které nejsou ilegální nazýváme legálním triangulaci bez ilegálních hran nazýváme legální triangulací. Bezprostředním důsledkem této definice je následující charakterizace legální triangulace:
3
Lemma 10.2. Triangulace je legální, právě káyž pro kažáou hranu pq s přilehlými trojúhelníky pqr a pqt neleží boá t uvnitř kružnice opsané trojúhelníku pqr.
Zásadní význam pro náš algoritmus má následující tvrzení.
Lemma 10.3. Nechť T je triangulace s ilegální hranou pq, která má v T přilehlé trojúhelníky pqr a pqt. Vytvořme z triangulace T novou triangulaci T' tak, že hranu pq nahraáíme hranou rt. Tato hrana buáe v triangulaci T' legální a navíc v uspořááání áefinovaném v přeáchozím paragrafu buáe
a{T) < a{T). Výše uveáená výměna hrany pq za rt se nazývá flipem.
OBR 10.4 Flip
Důkaz. Protože hrana pq je ilegální hranou triangulace T, je součet úhlů u vrcholů r a t ve čtyřúhelníku prqt větší než 180° a tedy součet úhlů u vrcholů p a q v temže čtyřúhelníku je menší než 180°. (Součet všech úhlů ve čtyřúhelníku je 360°.) Proto je hrana rt v triangulaci T' legální.
Označme úhly před flipem a po něm podle následujícího obrázku:
OBR 10.5 Označení úhlů str 4
Protože všechny další trojúhelníky mají obě triangulace stejné, stačí nám k tomu, aby
a(T) < a(T),
dokázat že
minjoíj, i = 1,2,... ,6} < min{fy, i = 1,2,..., 6}. Ukážeme postupně, že každé fy je větší než některé Zřejmě
fy > Cti      a      fy > a5-
Dále fy je obvodový úhel pro tětivu pr v kružnici opsané trojúhelníku prt, zatímco bod q leží vně této kružnice, proto
fy > a5.
Obdobně fy je obvodový úhel pro tětivu pt v kružnici opsané trojúhelníku prt, proto
fy > OLA.
Analogicky, pomocí kružnice opsané trojúhelníku qrt se přesvědčíme, že
fy > «i    a    fy > a2.
□
Důsledek 10.4. Uhlově optimální triangulace je legální.
Důkaz. Kdyby úhlově optimální triangulace měla nějakou ilegální hranu, pak jejím flipem bychom dostali triangulaci, která v námi definovaném uspořádání je nad původní triangulací, což je spor s definicí úhlově optimální triangulace. □
4
Legální triangulace nemusí být úhlově optimální triangulace, jak ukazuje následující obrázek dvou triangulací pětiúhelníka p1p2p3p4p5, kterému lze opsat kružnici. Navíc P1P2P3P5 je čtverec a p^pzp^ rovnoramenný trojúhelník. Obě triangulace T i T' jsou legální, ale protože a(T) < a(T'), není triangulace T úhlově optimální.
OBR 10.6 Příklad legální triangulace, která není úhlově optimální.
Delaunayův graf a triangulace. Kromě úhlově optimální a legální triangulace zavedeme ještě pojem Delaunayovy triangulace. Nejdřív ale definujme, co je Delaunayův graf.
Delaunayův graf'je graf, který má jako uzly body množiny P. Dva uzly pi, pj jsou spojeny hranou, právě když existuje kružnice, na které leží tyto dva body a všechny další body z množiny P leží vně této kružnice. To znamená, že střed této kružnice leží na hraně diagramu Voronoia, která prochází mezi oblastí určenou bodem pi a oblastí určenou bodem pj. Tedy Delaunayův graf je duální k diagramu Voronia.
OBR 10.7 Dualita diagramu Voronia (čárkovaný) a Delaunayova grafu (červený)
Lemma 10.5. Delaunayův graf je rovinným grafem.
Důkaz. Předpokládejme, že piPj a pkPi jsou dvě hrany Delaunayova grafu, které se jako úsečky protínají ve vnitřním bodě. Nechť čtyřúhelník PiPkPjPi má součet úhlů u vrcholů pk a pi aspoň 180°. Potom bod pi leží uvnitř každé kružnice, která má tětivu PiPj a bod pk leží v jejím vnějšku. (Kdyby ležel vně, tak součet protilehlých úhlů u Pk a pi by byl menší než 180°.) To je ale spor s tím, že piPj je hranou Delaunayova grafu. □
OBR 10.8 Ilustrace k důkazu lemmatu 10.5
Omezené oblasti Delaunayova grafu jsou tedy mnohoúhelníky. Nechť body p±,P2, ■ ■ ■, Pk tvoří vrcholy jednoho z těchto mnohoúhelníků. Tento mnohoúhelník určuje vrchol v v duálním grafu, tedy v diagramu Voronoia. Tedy body p±,P2, ■ ■ ■ ,Pk mají stejnou vzdálenost od vrcholu v a proto leží na jediné kružnici se středem v.
OBR 10.9 Čtyřúhelník p1p2p3p4 v Delaunayově grafu (černě) a diagram Voronoia (červeně)
Delaunayova triangulace je potom definována jako libovolná triangulace, která vznikne rozdělením těchto mnohoúhelníků v Delaunayově grafu na trojúhelníky. Delaunayova triangulace tedy nemusí být určena jednoznačně. Nicméně platí, že středy kružnic opsaných trojúhelníkům v Delaunayově triangulaci vytvářejí množinu vrcholů diagramu Voronoia.
OBR 10.10 Delaunayův graf (černě) a Delaunayova triangulace (černě a červeně)
5
Jestliže žádné čtyři body množiny P neleží na kružnici, pak je Delaunayův graf již triangulací. V takovém případě je Delaunayova triangulace určena jednoznačně. Říkáme, že body množiny P jsou v obecné poloze.
Každou Delaunayovu triangulaci lze charakterizovat následující vlastností.
Lemma 10.6. Triangulace konvexního obalu množiny P je Delaunayova, právě když pro každou její hranu piPj platí: kružnice opsaná přilehlému trojúhelníku PiPjPk neobsahuje uvnitř žádný další bod množiny P.
Důkaz. K důkazu použijeme dualitu mezi Delaunayovým grafem a diagramem Voro-noia.
Nechť je triangulace Delaunayova. Pak trojúhelník PiPjPk vznikl rozdělením nějakého mnohoúhelníka Delaunayova grafu na trojúhelníky. Pak střed kružnice opsané trojúhelníku PiPjPk je rovněž středem tohoto mnohoúhelníka a vrcholem diagramu Voronoia. Proto uvnitř této kružnice nemůže ležet žádný další bod množiny P.
Nechť obráceně uvnitř kružnice opsané trojúhelníku PiPjPk leží bod pi G P. Potom střed této kružnice není vrcholem diagramu Voronoia na hranici oblastí bodů pi, p j a pk, neboť má k těmto bodům větší vzdálenost než k pi. A tedy trojúhelník PiPjPk nemohl vzniknout triangulací mnohoúhelníkových oblastí Delaunayova grafu (duálního k diagramu Voronoia). □
Použijeme-li toto lemma a charakterizaci legální triangulace pomocí lemmatu 10.2, dostáváme okamžitě, že každá Delaunayova triangulace je legální. Trochu obtížnější je dokázat, že každá legální triangulace je Delaunayova.
Věta 10.7. Množina legálních triangulací se rovná množině Delaunayových triangulací.
Důkaz. Dokažme sporem, že každá legální triangulace je Delaunayova. Nechť T je legální triangulace, která není Delauneyova. V této triangulaci tedy existuje trojúhelník PiPjPk a bod pi tak, že p\ leží uvnitř kružnice opsané trojúhelníku PiPjPk a úhel ZpiPiPj je maximální pro všechny takové trojúhelníky a body. Nechť PíPjPm je trojúhelník přilehlý k trojúhelníku PiPjPk v triangulaci T. Protože je tato triangulace legální, neleží bod pm uvnitř kružnice opsané trojúhelníku PiPjPk- Bod pi nemůže ležet uvnitř trojúhelníku PiPjpm. Nechť pi leží na opačné straně přímky Pjpm než bod Potom je z následujícího obrázku vidět, že pro veliklosti úhlů platí:
^PmPlPj > ^PiPlPj,
což je ve sporu s volbou trojúhelníka PiPjPk a bodu pi. □
OBR 10.11 K důkazu věty 10.7
Odtud a z důsledku 10.4 plyne:
Důsledek 10.8.      (1) Každá úhlově optimální triangulace je Delaunayova.
(2) Jsou-li body množiny P v obecné poloze, tj. žádné čtyři neleží na jedné kružnici, pak existuje právě jedna Delaunayova triangulace, právě jedna legální triangulace a právě jedna úhlově optimální triangulace a tyto triangulace jsou totožné.
6
Základní idea náhodnostního přírůstkového algoritmu. Jedna možnost algoritmicky konstruovat Delaunayovu triangulaci je využít algoritmus k nalezení diagramu Voronoia, k němu najít duální graf a jeho A;-úhelníky rozdělit na trojúhelníky.
My si zde ukážeme jiný přístup, který je založen na tom, že každá legální triangulace je Delaunayova, a který spočívá v postupném odstraňování nelegálních hran.
Naivní verze takového algoritmu je následující: Vytvoříme nějakou triangulaci a v ní procházíme její hrany. Když nalezneme ilegální hranu, vyměníme ji flipem za hranu legální a stejným postupem pokračujeme dál. Tento proces je konečný, neboť po každém flipu dostaneme triangulaci, která je v popsaném lexikografickém uspořádání větší než ta předchozí. Vzhledem k tomu, že triangulací je konečný počet, musí tento proces někdy skončit.
Sofistikovanou verzí tohoto přistupuje náhodnostní přírůstkový algoritmus. Základní idea tohoto algoritmu je následující:
(1) K bodům množiny P přidáme body p_i a p_2 tak, aby s bodem pq G P, který má v P maximální y-ovou souřadnici (případně maximální rr-ovou souřadnici), tvořily trojúhelník, v němž leží všechny ostatní body množiny P.
(2) Tyto body uspořádáme náhodně do posloupnosti p\, p2,..., pn. Body pr pro r = 1,2,... ,n postupně přidáváme k legální triangulaci Tr-i trojúhelníka PoP-iP-2? kde vrcholy jednotlivých trojúhelníků jsou
P-2,P-l,P0,Pl, ■ ■ -,Pr-l-
(3) Pomocí současně konstruované vyhledávací struktury zjistíme do vnitřku kterého trojúhelníku PiPjPk nebo do které hrany piPj triangulace Tr-i bod pr padne. Potom hranami spojíme bod pr s vrcholy tohoto trojúhelníku nebo s vrcholy přilehlých trojúhelníků, padne-li na hranu. Nově vzniklou triangulaci trojúhelníku P0P-1P-2 s vrcholy trojúhelníků v množině
{P-2,P-l,P0,Pl, - ■ ■ ,Pr-l,Pr}
"legalizujeme", tj. pomocí flipů měníme ilegální hrany za legální. Po odstranění všech ilegálních hran dostaneme triangulaci %.
(4) Na závěr z legální triangulace Tn množiny P U {p_ 1,^-2} odstraníme body p_i a p_2 a hrany z nich vycházející. Díky vhodné volbě těchto dvou bodů, bude zbylá triangulace legální, tedy i Delaunayovou triangulací konvexního obalu množiny P = {p0,Pi,P2, ■ ■ -,Pn}-
OBR 10.12 Množina P v trojúhelníku PoP-iP-2-
Nyní jednotlivé kroky popíšeme podrobněji. Začneme krokem (2) a (3).
Legalizace. Uvažujme legální triangulaci %-i popsanou v bodě (2). Jestliže pomocí vyhledávací struktury zjistíme, že bod pr leží uvnitř trojúhelníka PiPjPk, spojíme jej hranami s jednotlivými vrcholy.
OBR 10.13 Bod pr v trojúhelníku PiPjPk-
7
Tím vznikne nová triangulace. Podstatné je, že nově přidané hrany vycházející z bodu pr jsou legální. To dokážeme takto: Nechť /C je kružnice opsaná trojúhelníku PiPjPk- Protože je triangulace Tr-i legální a tedy i Delaunayova, neleží uvnitř kružnice /C žádný z bodů z množiny Pr-i = {P-2,P-i,Po, ■ ■ ■ ,Pr-i}- Nechť C je kružnice stejnolehlá s /C, která má tětivu prPi- Viz obrázek. Uvnitř této kružnice neleží rovněž žádné další body Pr-±. Tedy hrana prpi je hranou Delaunayova grafu pro množinu Pr a ta musí být legální. Analogicky se dokáže, že i hrany prpj a prpk jsou legální.
OBR 10.14 K důkazu, že prpi je legální.
Může se ale stát, že některá z hran PíPj, PiPk a PjPk se v nové triangulaci stane ilegální hranou. Pak je potřeba ji pomocí flipu nahradit hranou vycházející z bodu pr. Nechť například PíPj je ilegální. Pak je to hrana nejen trojúhelníku PiPjpr ale také dalšího trojúhelníku PiPjPi- Nahradíme ji tedy hranou prpi, která je již legální. Teď se ale může stát ilegální některá z hran pipi a PjPi. Proto ji opět pomocí flipu nahradíme hranou vycházející z bodu pr.
OBR 10.15 Hrana p^j je ilegální.
V tomto postupu pokračujeme tak dlouho, až v triangulaci nebude žádná ilegální hrana. (Po každém flipu je nová triangulace v daném lexikografickém uspořádání větší než ta předchozí.) Postup zachycuje následující animace a pseudokód. Vstupem pse-dokódu je bod pr, hrana PíPj a legální triangulace Tr-i-
ANIMACE
PSEUDOKÓD 37 z pseudo.pdf Prosím nepsat pruh nad úsečkami, místo T použít TT-\ a místo pk psát p\.
Jestliže pomocí vyhledávací struktury zjistíme, že bod pr leží na hraně PiPj, pak hranu PíPj nahradíme hranami prpi a prpj a vytvoříme další hrany spojením bodu pr s vrcholy pk a pi přilehlých trojúhelníků ke hraně PíPj. Stejně jako v předchozím se dokáže, že nové hrany prPi, PrPj, PrPk a PrPi jsou legální. Nelegálními se ale mohou stát hrany PiPk, PjPk, PiPi a PjPi- To opravíme postupným prováděním flipů stejně jako v předchozím případě.
OBR 10.16 Bod pr na hraně PiPj.
Vyhledávací struktura. V průběhu algoritmu máme ke každé triangulaci příslušnou vyhledávací strukturu. Je to orientovaný graf, jehož listy jsou trojúhelníky aktuální triangulace a vnitřními uzly jsou trojúhelníky předchozích triangulací.
Na začátku má triangulace To jediný trojúhelník poP-iP-2 a vyhledávací struktura T>o jediný uzel, který je listem a odpovídá tomuto trojúhelníku. Pro triangulaci Tr-i máme vyhledávací strukturu XV-1- Nyní triangulaci Tr-i postupně měníme způsobem
8
popsaným v předchozí části. Každému přechodu od jedné triangulace k další triangulaci odpovídá jednoznačně určený přechod od jedné vyhledávací struktury k další vyhledávací struktuře. Ukažme si to na obrázku:
OBR 10.17 Změna vyhledávací struktury při vytvoření hran uvnitř trojúhelníku.
OBR 10.18 Změna vyhledávací struktury při flipu.
Tímto postupem tedy současně s postupným vytvořením triangulace % vytvoříme postupně i vyhledávací strukturu Dr. Ta závisí pouze na pořadí bodů p1}p2, ■ ■ ■ ,pr-
Počáteční volba bodů p0, p_2. Nyní si blíže objasníme kroky (1) a (4) našeho algoritmu. Budeme se přitom pro lepší pochopení odvolávat na geometrickou představu. Body p_i a p_2 budou určeny svými vlastnostmi, žádné jejich konkrétní souřadnice určovat nebudeme. Rovněž o tom, zdaje nějaká hrana legální či ilegální, a mezi čtyřmi body, které vstupují do hry, bude některý z bodů p_2, nebude rozhodovat výpočet, ale pouze pravidla, které vyplývají z vlastností bodů p_i a p_2-
Jak jsme již řekli, za bod pq zvolíme ten z bodů množiny P, který je maximální v lexikografickém uspořádání prvně podle souřadnice y a pak podle souřadnice x.
Bod p_i zvolíme vpravo dole od množiny P. (Exaktněji řečeno, jeho y-ová souřadnice je menší než minimum y-ových souřadnic bodů množiny P a jeho rr-ová souřadnice je větší než maximum rr-ových souřadnic bodů množiny P.) Přitom volbu p_i provedeme tak,
• aby ležel vně všech kružnic určených každou trojicí bodů z množiny P, které neleží na přímce,
• aby všechny body množiny P ležely pod přímkou PoP-i-
Bod p_2 zvolíme vlevo nahoře od množiny P tak,
• aby ležel vně všech kružnic určených každou trojicí bodů z množiny P U {p-i}, které neleží na přímce,
• aby všechny body množiny P ležely pod přímkou poř>-2,
• aby všechny body množiny P ležely nad přímkou p_ip_2-
Tedy všechny body množiny P leží uvnitř trojúhelníka P0P-1P-2, každý čtyřúhelník P-2PiP-iPj je nekonvexní a v důsledku toho bod p_2 leží vně všech kružnic opsaných trojúhelníkům P-2PiPj-
OBR 10.19 Množina P v trojúhelníku poP-iP-2-
Za těchto předpokladů je každá Delaunayova (legální) triangulace složena
(1) ze spojnic bodu p_\ s vrcholy pravé části hranice konvexního obalu množiny
(2) ze spojnic bodu p_2 s vrcholy levé části hranice konvexního obalu množiny P,
(3) z Delaunayovy triangulace množiny P.
Díky tomu, získáme Delaunayovu triangulaci množiny P tak, jak je popsáno v kroku (4).
9
Pravidla pro práci s algoritmem vycházejí z lemmatu:
Lemma 10.9. Při výše popsané volbě bodů pq, p_i a p_2 jsou následující tvrzení ekvivalentní:
• p j leží vlevo od orientované přímky PiP-\.
• p j leží vlevo od orientované přímky p _2P i-
• Pj > Pí v lexikografickém uspořádání njedřív podle y, pak podle x. Místo provádění důkazu demonstrujme situaci obrázkem.
OBR 10.20 K lemmatu 10.9. Body p_i a p_2 jsou vybrány tak, že v barevně vyznačených úhlech neleží žádný další bod množiny P.
Při zjišťování, zda je hrana legální či ilegální postupujeme takto:
• Všechny hrany trojúhelníka P0P-1P-2 Jsou legální.
• Hrana P-2Pj s přilehlými vrcholy p_i a pk je legální.
OBR 10.21 Ilustrace předchozího tvrzení.
• Hrana p-iPj s přilehlými vrcholy p_2 a pk je legální.
• Nechť hrana piPj má přilehlé vrcholy pk a pi, čtyřúhelník PiPkPjPi je konvexní a mezi čísly i,j,k,l je právě jedno záporné. Pak je hrana p^j legální, právě když
min(A;./) < min(i,j). OBR 10.22 min(—2,1) < min(i,j), hrana piPj je legální.
OBR 10.23 min(A;,/) > min(—1, j), hrana p-iPj je ilegální.
Pseudokód algoritmu a jeho očekávaná časová náročnost. Stručný pseudokód algoritmu popsaného detailněji v předchozích částech můžeme podat takto:
PSEODOKÓD číslo 36 z pseudo.pdf
Bez důkazu, který lze najít v [Berg et al], uvedeme větu o očekávané časové náročnosti tohoto náhodnostního algoritmu.
Věta 10.10. Očekávaná časová náročnost náhodnostního přírůstkového algoritmu pro Delaunayovu triangulaci množiny o n + 1 prvcích je 0(n\ogn).