# Delaunayeva triangulacija

### Iz Wikipedije, proste enciklopedije

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.

### [uredi] Potek triangulacije

Slika 1. Naključne točke | Slika 2. Triangulacija | Slika. 3. Pregled ali izpolnjuje Delaunayev pogoj

## [uredi] Algoritmi

### [uredi] Naključni inkrementalni algoritem

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.

### [uredi] Algoritem deli in vladaj

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.

### [uredi] Algoritem s prebirno premico

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).

Poiščemo središča očrtanih krogov | Dobljene točke povežemo in tako nastane Voronojev diagram

  Ta članek, ki se nanaša na računalništvo, je škrbina. Slovenski Wikipediji lahko pomagate tako, da ga dopolnite z vsebino.

Vzpostavljeno iz »http://sl.wikipedia.org../../../d/e/l/Delaunayeva_triangulacija.html«

Kategorije: Računalniške škrbine | Geometrija | Algoritmi | Boris Nikolajevič Delaunay | 1934 v znanosti

##### Views

- Članek
- Pogovor
- Trenutna redakcija

##### občestvo

- Portal občestva
- Pod lipo
- Stik z nami

##### podpora

- Pomoč
- Denarni prispevki

##### Iskanje

##### V drugih jezikih

- Deutsch
- English
- Español
- Français
- עברית
- Polski