Delaunayeva triangulacija s prebirnim krogom

diplomsko delo

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

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2017
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
Publisher:	G. Meznarič
UDC:	004.925.8(043.2)
COBISS:	20682262
Views:	1412
Downloads:	196
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Delaunay triangulation with circle sweep
Secondary abstract:	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.
Secondary keywords:	Delaunay triangulation;algorithms;computer geometry;
URN:	URN:SI:UM:
Type (COBISS):	Bachelor thesis/paper
Thesis comment:	Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Računalništvo in informacijske tehnologije
Pages:	IX, 33 str.
ID:	10843506