Ravninska Delaunayeva triangulacijaŠTEVANČEC, TADEJ (Avtor) Mramor Kosta, Nežka (Mentor) računska geometrijaravninska triangulacijaravninska Delaunayeva triangulacijanaključni inkrementalni algoritemalgoritem Bowyer-Watsonstopnja točkepričakovana najvišja stopnja točkeDelaunayeva triangulacija predstavlja eno izmed fundamentalnih podatkovnih struktur v računski geometriji. V diplomskem delu predstavimo ravninsko Delaunayevo triangulacijo in opišemo njeno konstrukcijo. Za izgradnjo Delaunayeve triangulacije v ravnini obstaja več vrst algoritmov, najbolj so razširjeni naključni inkrementalni. Naredili smo implementacijo algoritma Bowyer-Watson v programskem jeziku Java in preverili njegovo delovanje na več naborih naključno zgeneriranih točk. Mnogo algoritmov za izgradnjo Delaunayeve triangulacije je na tak ali drugačen način odvisnih od števila povezav, ki jim pripada posamezna točka. Primerjali smo teoretična pričakovanja za najvišjo in povprečno stopnjo točke v triangulaciji z rezultati, ki jih je vrnil naš algoritem.20162016-07-08 11:20:02Diplomsko delo84109VisID: 17726sl