20.500.12556/DKUM-54018 SPREMEMBA DELAUNAYEVE TRIANGULACIJE V REALNEM ČASU MODIFICATIONS OF DELAUNAY TRIANGULATION IN REAL-TIME Delaunayeva triangulacija je eden izmed najbolj uporabnih elementarnih algoritmov v računalniški geometriji. V tem diplomskem delu se ukvarjamo s spremembo Delaunayeve triangulacije pri premikanju že vstavljenih točk v realnem oziroma v doslednem času. V diplomskem delu predstavimo inkrementalni algoritem Delaunayeve triangulacije ter predlagano rešitev za pospešitev dinamičnega spreminjanja triangulacije s pomočjo štiriškega drevesa. Predlagano rešitev smo testirali na različnih množicah točk, štiriško drevo primerjali z naivno metodo in prikazali rezultate. Iz njih je razvidno, pri koliko točkah je še možno posodabljanje v realnem času ter učinkovitost štiriškega drevesa v primerjavi z naivno metodo. Delaunay triangulation is one of the most useful algorithms in computational geometry. In this thesis, we are dealing with the change of Delaunay triangulation when we modify already inserted points in real-time or in reasonable time. In this thesis we present the incremental algorithm for Delaunay triangulation and our solution for supporting dynamic modification by using quad-tree data structure. We tested the proposed method on different point sets, compared quad tree to naive approach, and presented results. They show us how many points can be updated to achieve the real-time response and suitability of the quadtree data structure against the naive approach. računalniška geometrija realni čas Delaunayeva triangulacija štiriško drevo sprememba Delaunayeve triangulacije computational geometry real-time triangulation Delaunay triangulation quadtree modification of Delaunay triangulation true true false D. Mori Slovenski jezik Angleški jezik Diplomsko delo/naloga 2015-08-18 10:46:39 2015-08-27 13:59:49 2022-06-04 03:10:10 2023-12-31 03:28:54 2015 0 [Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.925(043.2) 19078934 URN:SI:UM:DK:NJE2YAPX UN_Mori_Domen_2015.pdf UN_Mori_Domen_2015.pdf 1 2AB8E650E712FDAB5E54E866EC21B2E2 05d941f36a445b3824337e03f60f3efa1c94f24ced0c3222ea49d440e1de9ca2 ab12d1c2-7c06-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=78981 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0