Construction Of The Constrained Delaunay Triangulation Of A Polygonal Domain

A fast and easy to implement divide-and-conquer algorithm is presented for the construction of the Constrained Delaunay triangulation of a polygonal domain. The algorithm simplifies the complicated merging step inherent to divide-and-conquer algorithms for the computation of triangulations. Furthermore, no triangles are computed outside the valid region of the domain. A grid structure accelerates the computation of the visibility among vertices with respect to the boundary polygons as well as the computation of Constrained Delaunay triangles. Introduction and previous work This algorithm was motivated by the development of an adaptive triangulation algorithm for trimmed parametric surface patches [Kle94], [Ke95]. In the first step of this algorithm an initial Constrained Delaunay triangulation of the polygonal domain of the trimmed parametric surface ha