Triangulirajmo mnogokotnik

Marko Lamot (Author), Borut Žalik (Author), Radoš Šumrada (Reviewer), Dalibor Radovan (Reviewer)

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2000
Typology:	1.04 - Professional Article
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
Publisher:	Zveza geodetov Slovenije
UDC:	681.3.019:514.116
COBISS:	5875222
ISSN:	0351-0271
Parent publication:	Geodetski vestnik
Views:	1239
Downloads:	37
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary abstract:	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.
Secondary keywords:	polygon;polygon triangulation;computational geometry;algorithms;
URN:	URN:NBN:SI
Type (COBISS):	Not categorized
Pages:	str. 42-52
Volume:	ǂLetn. ǂ44
Issue:	ǂšt. ǂ1-2
Chronology:	2000
ID:	1749153