Construction Of the Constrained Delaunay Triangulation Of A Polygonal Domain
Construction Of the Constrained Delaunay Triangulation Of A Polygonal Domain
复制标题
DOI：
10.1007/978-3-642-60718-9_22
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
R. Klein
中科院分区：
文献类型：
--
作者：
R. Klein
针对多边形区域的约束Delaunay三角剖分问题，提出了一种快速、易于实现的分治算法。该算法简化了复杂的合并步骤固有的分而治之算法的三角剖分计算。此外，在域的有效区域之外不计算三角形。网格结构加速了顶点相对于边界多边形的可见性的计算以及约束Delaunay三角形的计算。
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.