Constrained Delaunay Triangulation using Plane Subdivision
Vid Domiter · 2004
This paper presents an algorithm for obtaining a constrained Delaunay triangulation from a given planar graph. The main advantage towards other algorithms is that I use an efficient ˇZalik’s algorithm, using a plane subdivison for obtaining a Delaunay triangulation. It is used for insertion of points into existing triangulation. The other part of algorithm presents a method for inserting edges, already proposed by Anglada. The algorithm is fast and efficient and therefore appropriate for GIS applications.