32 KB105 KB29 KB197320252000Lamot, MarkoRadovan, DaliborŠumrada, RadošŽalik, Borutštevilka:1/2letnik:44str. 42-52ISSN:0351-0271COBISSID:5875222URN:URN:NBN:SI:doc-GYTEF2XOslZveza geodetov SlovenijeGeodetski vestnikalgoritmigeometrijamnogokotnikiračunalniška geometrijatraingulacijaTriangulirajmo mnogokotnik|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 pointsV č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čkeTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaZveza geodetov Slovenije