Delaunayeva triangulacija

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Delaunayeva triangulacija se imenuje po ruskem matematiku Borisu Nikolajeviču Delaunayu, ki jo je izumil leta 1934. Triangulacija je Delaunayeva, če izpolnjuje Delaunayev pogoj, ki pravi, da v nobenem krogu, ki bi bil očrtan nekemu trikotniku triangulacije, ne sme biti nobena točka. S tem dobimo triangulacijo, ki ima najmanjše število tankih trikotnikov (trikotnikov z majhnimi notranjimi koti), kar je nezaželeno in povzroča nevšečnosti v praksi.

Potek triangulacije[uredi | uredi kodo]

Algoritmi[uredi | uredi kodo]

Naključni inkrementalni algoritem[uredi | uredi kodo]

Algoritmi iz te skupine so najpogosteje uporabljeni. V najslabšem primeru lahko imajo časovno zahtevnost O(N2), vendar je pričakovana časovna zahtevnost O(n log n). Obstaja več rešitev kot je na primer iskalni algoritem, ki v vsakem koraku dodaja po en pravilni trikotnik k trenutni triangulaciji in algoritem z vstavljanjem, ki zaporedoma vstavlja točke v narejeno triangulacijo, nato pa jo popravi, da zadošča Delaunayevemu pogoju.

Algoritem deli in vladaj[uredi | uredi kodo]

Algoritem na začetku množico vhodnih točk razdeli na manjše množice točk, nad katerimi naredi triangulacijo, nato pa te manjše množice združi in naredi celotno triangulacijo.

Algoritem s prebirno premico[uredi | uredi kodo]

Priljubljeni algoritem s prebirno premico je predlagal Fortune (1987). V bistvu je Fortune razvil algoritem, ki skonstruira dualni graf Delaunayeve triangulacije - Voronojevih diagramov. Časovna zahtevnost je O(n log n).