Delaunayeva triangulacija

Iz Wikipedije, proste enciklopedije
Jump to navigation Jump to search

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 se dobi 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 Steven Fortune (1987). V bistvu je Fortune razvil algoritem, ki skonstruira dualni graf Delaunayeve triangulacije - Voronojevih diagramov. Časovna zahtevnost je O(n log n).