Aproksimacija srednje osi enostavnih mnogokotnikov

diplomsko delo univerzitetnega študijskega programa

Gregor Smogavec (Avtor), Borut Žalik (Mentor), David Podgorelec (Komentor)

Povzetek

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.

Ključne besede

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

Podatki

Jezik:	Slovenski jezik
Leto izida:	2009
Izvor:	Maribor
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Založnik:	[G. Smogavec]
UDK:	004.94(043.2)
COBISS:	13786390
Št. ogledov:	1591
Št. prenosov:	114
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Medial axis aproximation of simple polygons
Sekundarni povzetek:	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.
Sekundarne ključne besede:	algorithm;computer geometry;medial axis;triangulation;centres of maximal disks;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Diplomsko delo
Komentar na gradivo:	Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko
Strani:	VIII, 44 f.
Ključne besede (UDK):	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