20.500.12556/DKUM-57627 ISKANJE NAJBLIŽJE TOČKE V 3D PROSTORU THE CLOSEST POINT SEARCH IN 3D SPACE Iskanje najbližje točke je temeljni problem v računalniški geometriji. Diplomsko delo obravnava Bentleyev algoritem z delitvijo prostora na celice v različici za 3D prostor ter razširitev z rekurzivno delitvijo celic na podcelice. Algoritem je preizkušen na različnih množicah točk, tako sintetičnih kot praktičnih. Za primerjavo so testirani tudi naivna metoda iskanja ter metoda z osmiškim drevesom. Ugotovljeno je, da je Bentleyev algoritem učinkovit na različnih vhodnih podatkih in ima v večini primerov linearno časovno zahtevnost tako pri predobdelavi podatkov kot pri iskanju vseh najbližjih sosedov. Metoda z rekurzivno delitvijo celic izboljša hitrost iskanja na množicah z močno neenakomerno porazdelitvijo točk v prostoru, kjer prejšnja dosega slabše rezultate. A closest point search is a basic problem in the computational geometry. This diploma thesis deals with the Bentley cell-based space partitioning algorithm and an extension of it with recursive subdivision of the cells. The algorithm is tested on different point distributions in the 3D space, both synthetic and from the real world. For comparison the naive method and an octree-based method were also tested. It was found that the Bentley algorithm performs well on different datasets and in most cases has a linear time complexity both for preprocessing and searching all nearest neighbors. The recursive method improves searching speed on inputs with strongly non-uniform distributions, where the former algorithm performs worse. algoritmi računalniška geometrija najbližja točka delitev prostora algorithm computational geometry closest point spatial subdivision true true false D. Balažic Slovenski jezik Angleški jezik Diplomsko delo 2016-03-03 17:21:21 2016-03-18 14:40:38 2022-06-14 03:06:53 2021-05-16 03:25:18 2016 0 [Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.921.021(043.2) 19466006 URN:SI:UM:DK:8B3XVZWI UN_Balazic_David_2016.pdf UN_Balazic_David_2016.pdf 1 DDF3BAB154CD3F7448463E0D360E109C 3cc01dd27384bc29e6c3a59e17e562b65a5843f688a217856f31f46e1d6920cf f21ed601-7c0b-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=86836 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0