Delaunayeva triangulacija s prebirnim krogom

diplomsko delo

Gal Meznarič (Avtor), Borut Žalik (Mentor)

Povzetek

V diplomski nalogi predstavimo problem Delaunayeve triangulacije na ravninski množici točk in njene pomembnejše lastnosti. Naredimo splošen pregled obstoječih metod izgradnje Delaunayeve triangulacije, več pozornosti pa namenimo metodi Delaunayeve triangulacije s prebirno premico, ki služi kot osnova algoritmu s prebirnim krogom. Glavni del diplomske naloge obsega podrobnejšo predstavitev vseh faz algoritma Delaunayeve triangulacije s prebirnim krogom, implementacijo tega algoritma in primerjavo hitrosti izvajanja z Žalikovim algoritmom s prebirno premico. Ugotovimo, da se poenostavljena verzija algoritma s prebirnim krogom obnese bolje od izvirne, a ne prehiti Žalikovega algoritma s prebirno premico.

Ključne besede

Delaunayeva triangulacija;algoritmi;računalniška geometrija;diplomske naloge;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2017
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Založnik:	G. Meznarič
UDK:	004.925.8(043.2)
COBISS:	20682262
Št. ogledov:	1412
Št. prenosov:	196
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Delaunay triangulation with circle sweep
Sekundarni povzetek:	A problem of computing the Delaunay triangulation of a set of 2D points and its related properties is considered in this thesis. An overview of existing computational methods is done at first. Focus is given to the sweep-line algorithm, which served as a basis for the circle-sweep algorithm. The central part of the thesis covers the presentation of the circle-sweep algorithm in detail, its implementation and comparison of spent CPU time in regard to the Žalik’s sweep-line algorithm. It was determined that the simplified version of the circle-sweep algorithm offers better performance in comparison to the original version, yet fails to surpass the Žalik’s sweep-line algorithm.
Sekundarne ključne besede:	Delaunay triangulation;algorithms;computer geometry;
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:	IX, 33 str.
ID:	10843506