Delaunayeva triangulacija
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 triangulacijeUredi
Slika 1. Naključne točke
Slika 2. Triangulacija
Slika. 3. Pregled ali izpolnjuje Delaunayev pogoj
AlgoritmiUredi
Naključni inkrementalni algoritemUredi
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 vladajUredi
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 premicoUredi
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).
Poišče se središča očrtanih krogov
Dobljene točke se poveže in tako nastane Voronojev diagram
