20.500.12556/RUL-181267 Uporaba Douglas-Peuckerjevega algoritma za redukcijo podatkovnih točk v odsekoma linearnih krivuljah pri opisovanju ravninskih poti Application of the Douglas-Peucker algorithm for data point reduction in piecewise linear functions for describing planar paths Douglas-Peuckerjev algoritem je metoda za poenostavljanje odsekoma linearnih krivulj, ki učinkovito zmanjša število točk ob omejeni geometrijski napaki. V diplomskem delu obravnavamo delovanje algoritma in njegov vpliv na kakovost poenostavljenih krivulj pri opisovanju ravninskih poti, zlasti pri obdelavi GPS poti. Najprej predstavimo matematično ozadje algoritma in časovno zahtevnost algoritma. Nato izpostavimo ključne pomanjkljivosti klasičnega postopka, kot sta možnost nastanka samopresečišč pri večjih tolerancah ter neustrezno ravnanje pri zaprtih krivuljah. Na podlagi sorodnih pristopov implementiramo razširitve, ki izboljšajo topološko konsistentnost poenostavitve in omogočajo stabilnejšo obravnavo zaprtih krivulj. Predlagane rešitve eksperimentalno ovrednotimo na realnih podatkih ter primerjamo rezultate glede na stopnjo redukcije, geometrijsko napako in pojavljanje topoloških nepravilnosti. Dodatno razvijemo interaktivno orodje za vizualizacijo poteka algoritma, ki omogoča sprotno opazovanje vpliva tolerance na izbiro točk in končni potek krivulje. The Douglas-Peucker algorithm is a method for simplifying piecewise linear curves, efficiently reducing the number of points while keeping the geometric error bounded. In this thesis, we examine how the algorithm works and how it affects the quality of simplified curves when representing planar paths, in particular in the processing of GPS tracks. First, we present the mathematical background of the algorithm and analyze its time complexity. We then highlight key limitations of the classical procedure, such as the possibility of self-intersections when using larger tolerances and inadequate handling of closed curves. Based on related approaches, we implement extensions that improve the topological consistency of the simplification and enable a more stable treatment of closed curves. We evaluate the proposed solutions experimentally on real-world data and compare the results in terms of reduction rate, geometric error, and the occurrence of topological inconsistencies. In addition, we develop an interactive tool for visualizing the algorithm's execution, which allows real-time observation of how the tolerance influences point selection and the final shape of the curve. Redukcija podatkovnih točk Douglas-Peuckerjev algoritem odsekoma linearne krivulje opisovanje ravninskih poti. Data point reduction Douglas-Peucker algorithm piecewise linear functions describing planar paths. true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2026-03-30 08:25:12 2026-03-30 08:25:21 2026-05-04 11:09:36 0000-00-00 00:00:00 2026 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 38076 276896003 Jakomin_Veno_-_Uporaba_Douglas-Peuckerjevega_algoritma_za_redukcijo_podatkovnih_tock_v_odsekoma_.pdf Jakomin_Veno_-_Uporaba_Douglas-Peuckerjevega_algoritma_za_redukcijo_podatkovnih_tock_v_odsekoma_.pdf 1 18E683E5332CC685136F46FD0F0F7667 d68ffde73536ee621029ec6aa188de640ed7aa37259f2eda1a945f4ffe4821f5 1a9a75eb-2c01-11f1-b0ab-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=231548 Fakulteta za računalništvo in informatiko 0 0 0