An improved algorithm of constrained Delaunay triangulation based on the diagonal exchange

The constrained Delaunay triangulation algorithm is not very stable or even failure when the influence domain is concave polygon. In this paper, we introduce some related conceptions and algorithms and focus on the Constrained Delaunay Triangulation Algorithm and Influence domain that is concave polygon issues related. An improved algorithm based on the diagonal exchange is presented. Experiments show that the algorithm can solve the influence domain for concave polygon and other special circumstances, and can be implemented by programs easily, and be stable.