Delaunayeva triangulacija

Iz MaFiRaWiki

Vsebina

Opis

Triangulacija je razdelitev ravninskega področja na podpodročja, pri čemer so ta podpodročja trikotniki. Je planarni graf z največjim možnim številom robov, kjer se niti dva med seboj ne smeta sekati.

Delaunayeva triangulacija je taka triangulacija, da za množico točk P v ravnini velja, da nobena druga točka iz P ne leži v očrtanem krogu kateregakoli trikotnika na tej ravnini. Unija vseh povezav v triangulaciji je konveksna ovojnica danih točk.

Algoritem

Preverjanje točk

Eden izmed načinov preverjanja ali točka D leži v očrtanem krogu trikotnika ABC, je računanje naslednje determinante:

\begin{vmatrix} A_x & A_y & A_{x}^2+A_{y}^2 & 1 \\ B_x & B_y & B_{x}^2+B_{y}^2 & 1 \\ C_x & C_y & C_{x}^2+C_{y}^2 & 1 \\ D_x & D_y & D_{x}^2+D_{y}^2 & 1 \\ \end{vmatrix}

Pri tem moramo upoštevati, da točke A, B, C ležijo v smeri urinega kazalca. Determinanta je pozitivna natanko tedaj, ko točka D leži v notranjosti očrtanega kroga tega trikotnika.

Opis algoritma

Za konstruiranje Delaunayeve triangulacije bomo uporabili algoritem Sweep line.

Ideja je naslednja:

Predstavljamo si navpično črto, ki "potuje" čez ravnino od leve proti desni; krivulja, ki jo "vlečemo" za seboj, nam kaže, kje točk ni več; Najlažje si jo predstavljamo kot val morja, ki "potuje" proti obali. Krivulja nam razdeli področje na dva dela: na levi strani je že narejena triangulacija in je ni možno več spreminjati, ker ni več točk; na desni strani pa imamo še točke, ki jih moramo med seboj še pravilno povezati. Krivulja se spreminja, ko se premaknemo do naslednje točke.

Točko k že trianguliranemu delu grafa dodajamo postopoma, ter ponovno trianguliramo tisti del grafa, na katerega vpliva dodana točka. Ko dodamo novo točko, poiščemo vse obstoječim trikotnikom očrtane kroge, ki vsebujejo dodano točko. Take trikotnike pobrišemo in ta del grafa ponovno trianguliramo.

Množico točk v ravnini uredimo po naraščajoči x-koordinati, in jih nato dodajamo v tem vrstnem redu. Zaradi uporabe zgoraj omenjene krivulje nam ni potrebno pregledati očrtanih krogov za vse trikotnike v že trianguliranem delu grafa, pač pa samo tistih, ki še niso v tem delu. Vzporednice, ki jih bomo uporabili v primeru, nam kažejo, v katero smer se bo krivulja premaknila. Preden dodamo novo točko, preverimo, če ta točka leži znotraj katerega trikotnikom očrtanega kroga. To storimo z izračunom zgoraj omenjene determinante.


Primer

Primer Delaunayeve triangulacije:

Slika:DT0.JPG

Postopek

Imamo množico točk na ravnini, ki jih uredimo po naraščajočih x-koordinatah:

Slika:DT1a.JPG

Postopoma po vrsti dodajamo točke. Ko smo dodali tri, dobimo prvi trikotnik, ki nam sedaj predstavlja že trianguliran del grafa :

Slika:DT7a.JPG

Nato nadaljujemo z naslednjo, četrto točko. Preverimo (z izračunom determinante), če točka leži znotraj katerega (obstoječim trikotnikom) očrtanega kroga. V tem primeru točka ni v nobenem krogu, zato vsi (en) obstoječi trikotniki ostanejo nespremenjeni. To nam pokaže krivulja. S četrto točko lahko tvorimo tri nove trikotnike: 1-2-4, 1-3-4 in 2-3-4. Če za vsakega z determinanto izračunamo vsebovanost preostalih točk v tem trikotniku očratnega kroga, vidimo, da trikotnika 1-2-4 (očrtan krog vsebuje točko 3) in 1-3-4 (očrtan krog vsebuje točko 2) ne moreta biti del Delaunayeve triangulacije. Medtem, ko trikotnik 2-3-4 je del triangulacije (očrtan krog ne vsebuje točke 1), zato povežemo točko 4 s točkama 2 in 3.

Slika:DT8a.JPG

Nadaljujemo z naslednjo, peto točko. Tudi v tem primeru (nova) točka ne leži znotraj nobenega obstoječim trikotnikom očrtanega kroga. To nam kaže krivulja. S peto točko lahko tvorimo naslednje trikotnike: 1-2-5, 1-3-5, 1-4-5, 2-3-5, 2-4-5 in 3-4-5. Za trikotnika 1-3-5 in 3-4-5 ugotovimo, da sta del Delaunayeve triangulacije, medtem ko ostali niso. Povežemo točko 5 s točkami 1, 3 in 4.

Slika:DT12a.JPG

Nadaljujemo s šesto točko. Ker nam krivulja kaže, da ni vsebovana v nobenim obstoječim trikotnikom očrtanega kroga, ne odstranimo nobenega od obstoječih trikotnikov. Ugotovimo, da od možnih novih trikotnikov samo trikotnik 4-5-6 izpolnjuje kriterij za Delaunayevo triangulacijo, zato točko 6 povežemo s točkama 4 in 5.

Slika:DT14a.JPG

Ker smo uporabili vse točke, smo končali s postopkom triangulacije.

Glej tudi

Demonstracija je tukaj.
Izberemo Delaunayevo triangulacijo ter določimo točke.

Viri

angleška wikipedia

Osebna orodja