20.500.12556/RUL-84109 Ravninska Delaunayeva triangulacija Plane Delaunay triangulation Delaunayeva 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. Delaunay triangulation is one of the fundamental data structures in computational geometry. In the thesis we present the planar Delaunay triangulation and describe its construction. Several types of algorithms for building a two-dimensional Delaunay triangulation exist, the most popular are randomized incremental algorithms. We implemented the Bowyer-Watson algorithm in the programming language Java and tested it on a number of samples of randomly generated point sets. The expected degree of a vertex in a triangulation is an important parameter in many algorithms for constructing triangulations. Theoretical expectations for average and maximal vertex degrees are compared with the obtained values. računska geometrija ravninska triangulacija ravninska Delaunayeva triangulacija naključni inkrementalni algoritem algoritem Bowyer-Watson stopnja točke pričakovana najvišja stopnja točke computational geometry planar triangulation planar Delaunay triangulation randomized incremental algorithm Bowyer-Watson algorithm vertex degree expected maximum vertex degree true false false Slovenski jezik Angleški jezik Diplomsko delo 2016-07-08 11:20:02 2016-07-08 11:20:05 2022-08-02 00:55:35 0000-00-00 00:00:00 2016 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 17726 Stevancec_Tadej_-_Ravninska_Delaunayeva_triangulacija.pdf Stevancec_Tadej_-_Ravninska_Delaunayeva_triangulacija.pdf 1 FF0F8AA83F2B7B05A661B4E872477649 44d6c03bd4c8d39df0d1aabcdd9da55cea493760320ee2ef3ce8e84bc61c9632 db8f791d-a1b0-11eb-a523-00155dcfd717 20.500.12556/rul/09696ea5-e213-4713-81c0-d4c6dfd7c7be https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=87146 Fakulteta za računalništvo in informatiko 0 0 0