diplomsko delo
Povzetek
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.
Ključne besede
računalniška geometrija;realni čas;Delaunayeva triangulacija;štiriško drevo;sprememba Delaunayeve triangulacije;
Podatki
Jezik: |
Slovenski jezik |
Leto izida: |
2015 |
Tipologija: |
2.11 - Diplomsko delo |
Organizacija: |
UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko |
Založnik: |
D. Mori |
UDK: |
004.925(043.2) |
COBISS: |
19078934
|
Št. ogledov: |
1166 |
Št. prenosov: |
150 |
Ocena: |
0 (0 glasov) |
Metapodatki: |
|
Ostali podatki
Sekundarni jezik: |
Angleški jezik |
Sekundarni naslov: |
MODIFICATIONS OF DELAUNAY TRIANGULATION IN REAL-TIME |
Sekundarni povzetek: |
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. |
Sekundarne ključne besede: |
computational geometry;real-time triangulation;Delaunay triangulation;quadtree;modification of Delaunay triangulation; |
URN: |
URN:SI:UM: |
Vrsta dela (COBISS): |
Diplomsko delo/naloga |
Komentar na gradivo: |
Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Računalništvo in informacijske tehnologije |
Strani: |
VII, 32 str. |
ID: |
8887383 |