Sprememba Delaunayeve triangulacije v realnem času

diplomsko delo

Domen Mori (Avtor), Borut Žalik (Mentor), Niko Lukač (Komentor)

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