Iskanje najbližje točke v 3D prostoru
diplomsko delo
Povzetek
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.
Ključne besede
algoritmi;računalniška geometrija;najbližja točka;delitev prostora;diplomske naloge;
Podatki
| Jezik: | Slovenski jezik |
|---|---|
| Leto izida: | 2016 |
| Tipologija: | 2.11 - Diplomsko delo |
| Organizacija: | UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko |
| Založnik: | D. Balažic |
| UDK: | 004.921.021(043.2) |
| COBISS: |
19466006
|
| Št. ogledov: | 1010 |
| Št. prenosov: | 72 |
| Ocena: | 0 (0 glasov) |
| Metapodatki: |
|
Ostali podatki
| Sekundarni jezik: | Angleški jezik |
|---|---|
| Sekundarni naslov: | THE CLOSEST POINT SEARCH IN 3D SPACE |
| Sekundarni povzetek: | 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. |
| Sekundarne ključne besede: | algorithm;computational geometry;closest point;spatial subdivision; |
| URN: | URN:SI:UM: |
| Vrsta dela (COBISS): | Diplomsko delo |
| Komentar na gradivo: | Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Računalništvo in informatika |
| Strani: | X, 34 str., [32] pril. |
| ID: | 9128108 |
Priporočena dela:
Iskanje najbližje točke v 3D prostoru
2016,
diplomsko delo
Računalniška simulacija poplavnega področja pri zajezitvah
2007,
diplomska naloga univerzitetnega študijskega programa
Inkrementalno iskanje najbližje točke z uporabo k-d drevesa
2015,
diplomsko delo
Dinamično zaznavanje trkov geometrijskih objektov v 3D prostoru
2002,
diplomska naloga univerzitetnega študijskega programa
Triangulirajmo mnogokotnik
2000,
ni podatka o podnaslovu