20.500.12556/RUL-98576 Voronoijevi diagrami Voronoi diagrams V diplomski nalogi najprej opišemo definicijo Voronoijevega diagrama in bolj podrobno lastnosti ravninskih Voronoijevih diagramov. Opišemo tudi triangulacijo ravnine, pojem Delaunayeve triangulacije in predstavimo povezavo med njima. Nato predstavimo tri različne algoritme za konstrukcijo ravninskih Voronoijevih diagramov in bolj podrobno pogledamo Fortunov algoritem, ki spada med algoritme s prebirno premico. Algoritmi s prebirno premico so posebej razširjeni v računski geometriji in z njimi rešujemo različne probleme v evklidskem prostoru. Za konstrukcijo Voronoijevega diagrama smo si izbrali Fortunov algoritem, ki smo ga implementirali v programskem jeziku Java. Pravilnost delovanja algoritma smo preverili na točkah, ki predstavljajo lokacije letališč v ZDA, lokacije javnih polnilnih mest za električne avtomobile v Sloveniji in na več naborih naključno generiranih točk. In the thesis we first describe the definition of a Voronoi diagram and several properties of Voronoi diagrams in the plane. We also define triangulations of the plane and the concept of a Delaunay triangulation, and present the connection between Voronoi diagrams and Delaunay triangulations. We then present three different algorithms for constructing a Voronoi diagram in the plane, and provide a more detailed description of Fortune’s algorithm which is an example of a sweep line algorithm. Sweep line algorithms are especially widespread in computational geometry and are used for solving various problems in Euclidean space. We selected Fortune’s algorithm for constructing Voronoi diagrams, and implemented it in the Java programming language. The performance of our implementation of the algorithm was checked on several randomly generated datasets and on a dataset of geographic coordinates of public charging stations for electric cars in Slovenia. Voronoijev diagram dvodimenzionalen Voronoijev diagram prebirna premica računska geometrija Fortunov algoritem evklidski prostor Voronoi diagram two-dimensional Voronoi diagram sweep line computational geometry Fortune’s algorithm Euclidean space true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2017-12-07 11:00:03 2017-12-07 11:00:04 2022-08-12 15:02:27 0000-00-00 00:00:00 2017 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 20024 Kristan_Matej_-_Voronoijevi_diagrami.pdf Kristan_Matej_-_Voronoijevi_diagrami.pdf 1 09462F11EBBB257A3084222FC9DD287F aa7b3447f8eb7feacdbf02dc9e8a6419b1d91b7cf6048fe33eafcf3b51844783 704e2223-a1b4-11eb-a523-00155dcfd717 20.500.12556/rul/02b26b71-9044-4323-be10-c14cc7f8cc90 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=107912 Fakulteta za računalništvo in informatiko 0 0 0