A Fast Algorithm for Constructing Constrained Delaunay Triangulation

This paper presents a fast incremental insertion algorithm for constructing constrained Delaunay triangulation. Constraints are considered any kind of polygonal lines. The bottleneck of incremental Delaunay triangulation algorithm is the search for a triangle containing current integrating point. The advantage of our algorithm over the others is that we used an efficient Skvortsov´s algorithm, dynamic uniform grid. It is used to insert point into an existing triangulation. A topology model is used to represent a triangle network so that we can easily and fast locate a point in a triangulation. The rest of algorithm presents a method for constrained edges, already proposed by Anglada. The algorithm is fast and easy to implement.