Triangulirajmo mnogokotnik

Abstract

This paper considers different approaches how to divide polygons intotriangles what is known as a polygon triangulation. Polygons can be very complex in geodesic applications (they could have a lot of 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.

Keywords

• polygon
• polygon triangulation
• computational geometry
• algorithms
• mnogokotnik
• triangulacija mnogokotnikov
• računalniška geometrija
• algoritmi