Triangulirajmo mnogokotnik

Marko Lamot (Avtor), Borut Žalik (Avtor), Radoš Šumrada (Recenzent), Dalibor Radovan (Recenzent)

Povzetek

V članku predstavljamo tehnike delitve mnogokotnikov v trikotnike oz. triangulacijo mnogokotnikov. Namen delitve mnogokotnikov je v poenostavitvi obdelovanja mnogokotnikov, saj so lahko le-ti v geodetskih aplikacijah zelo kompleksni (vsebujejo veliko število konkavnih oglišč, imajo ugnezdene luknje). Vsak mnogokotnik je mogoče triangulirati z vstavljanjem diagonal, karje razvidno iz dokaza o triangulaciji mnogokotnika. Obstaja veliko postopkov, ki uporabljajo to dejstvo, vendar pa je mogoče triangulirati mnogokotnike tudi s popolnoma drugimi pristopi. Algoritme delitve mnogokotnikov lahko delimo na tri skupine: algoritme, ki temeljijo na vstavljanju diagonale, algoritme, ki temeljijo na Delaunayevi triangulaciji inalgoritme, ki uporabljajo za delitev Steinerjeve točke.

Ključne besede

mnogokotnik;traingulacija mnogokotnikov;računalniška geometrija;algoritmi;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2000
Tipologija:	1.04 - Strokovni članek
Organizacija:	UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Založnik:	Zveza geodetov Slovenije
UDK:	681.3.019:514.116
COBISS:	5875222
ISSN:	0351-0271
Matična publikacija:	Geodetski vestnik
Št. ogledov:	1239
Št. prenosov:	37
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni povzetek:	This paper considers different approaches how to divide polygons into triangles what is known as a polygon triangulation. Polygons can be very complex in geodesic applications (they could have a lot concave vertices, they could contain holes) therefore there is often a need to decompose them into simpler components. Every polygon can be triangulated by inserting diagonals what is shown in the proof of existence of polygon triangulation. There are a lot of polygon triangulation techniques which use that fact. However, polygons can be triangulated by some other approaches, too. The algorithms performing polygon triangulation can be classified into three major groups: algorithms, which are based on diagonal insertion, algorithms, which are based on Delaunay triangulation, and algorithms using Steiner's points.
Sekundarne ključne besede:	polygon;polygon triangulation;computational geometry;algorithms;
URN:	URN:NBN:SI
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 42-52
Letnik:	ǂLetn. ǂ44
Zvezek:	ǂšt. ǂ1-2
Čas izdaje:	2000
ID:	1749153