Aproksimacija srednje osi enostavnih mnogokotnikov

diplomsko delo univerzitetnega študijskega programa

Gregor Smogavec (Author), Borut Žalik (Mentor), David Podgorelec (Co-mentor)

Abstract

Srednja os mnogokotnika je množica središč maksimalnih notranjih krožnic v mnogokotniku. Uporablja se kot nepogrešljiv del pri reševanju različnih problemov, kot so razpoznavanje znakov, GIS, zaznavanje trkov, obdelava in analiza slik. Po definiciji dobimo eksaktno rešitev srednje osi, če v mnogokotnik vstavljamo krožnice, ki se stikajo z mejami mnogokotnika na vsaj dveh mestih, in povežemo sosednja središča le teh. Omenjeni pristop pa za posledico, razen eksaktne rešitve, potegne za sabo veliko časovno zahtevnost. To je glavni razlog, zakaj ima ta pristop omejeno uporabnost pri zgoraj omenjenih nalogah, če potrebujemo rešitev v realnem času. V diplomski nalogi predlagamo nov algoritem, ki se bo uspešno kosal s tem problemom. Algoritem deluje v štirih korakih. Najprej se zgradi omejena Delaunayeva triangulacija nad mnogokotnikom. Nato iz triangulacije izločimo odvečne trikotnike. Preostalo triangulacijo popravimo z dodajanjem Steinerjevih točk in nazadnje povežemo središča sosednjih si trikotnikov, da dobimo aproksimacijo srednje osi mnogokotnika. Meritve kažejo, da dobimo z našim algoritmom aproksimacijo srednje osi zelo hitro, kar nam daje možnost, da uporabimo algoritem v realno časovnih aplikacijah, kot na primer v robotizaciji.

Keywords

algoritem;računalniška geometrija;srednja os;triangulacija;skladišča maksimalnih krožnic;

Data

Language:	Slovenian
Year of publishing:	2009
Source:	Maribor
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
Publisher:	[G. Smogavec]
UDC:	004.94(043.2)
COBISS:	13786390
Views:	1591
Downloads:	114
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Medial axis aproximation of simple polygons
Secondary abstract:	Medial axis of a simple polygon is a set of centres of maximal inscribed discs. It is used as an essential part in a variety of applications like character recognition, GIS, collision detection, image processing and analysis. By definition, exact medial axis is obtained, if we put maximal circles in the polygon and connect the neighboring circles. Since exact computation of the medial axis is difficult and time consuming, it limits the above applications in a sense of real-time execution. Because of this, we propose an algorithm which finds an approximation of a medial axis. The algorithm works in four steps. Firstly, a constrained Delaunay triangulation is constructed. Then superfluous triangles are removed. The polygon is after that further triangulated with Steiner points to meet the criteria of introduced heuristics. The centres of gravity of neighboring triangles are connected and an approximation of the medial axis of a polygon is obtained. Experiments show that approximation of the medial axis is obtained very rapidly, what gives the possibility to use the algorithm in real-time applications; for example in robotics.
Secondary keywords:	algorithm;computer geometry;medial axis;triangulation;centres of maximal disks;
URN:	URN:SI:UM:
Type (COBISS):	Undergraduate thesis
Thesis comment:	Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko
Pages:	VIII, 44 f.
Keywords (UDC):	science and knowledge;organization;computer science;information;documentation;librarianship;institutions;publications;znanost in znanje;organizacije;informacije;dokumentacija;bibliotekarstvo;institucije;publikacije;prolegomena;fundamentals of knowledge and culture;propaedeutics;prolegomena;splošne osnove znanosti in kulture;computer science and technology;computing;data processing;računalniška znanost in tehnologija;računalništvo;obdelava podatkov;application-oriented computer-based techniques;računalniške tehnike za namensko rabo;aplikativno usmerjene računalniško podprte tehnike;simulation;simulacija;
ID:	988539