平面多边形域的快速约束Delaunay三角化

Fast Constrained Delaunay Triangulation for Planar Polygonal Domains

针对任意平面多边形域,采用增量思想和均匀网格,在局部范围内快速生成约束Delaunay三角形.该方法不会生成区域外的三角形;对存在折线、离散点以及含“洞”的情况不需要特殊处理.实验结果表明,该方法对于随机生成的简单多边形域三角化速度快,平均计算时间呈近似线性.另外,针对文字、工业图案等带状图像的边界多边形,充分利用其近似等宽性优化算法,将其应用于带状图像骨架的快速提取.

Based on the incremental idea and the uniform grid, constrained Delaunay triangles can be computed in local ranges for arbitrary planar polygonal domains. No triangles outside the valid region of the domain are computed and for domains with polylines, scattered points and holes, no extra operations are specially required. The tested analysis shows that for simple polygonal domains randomly generated, the algorithm is efficient in computation and has an almost linear run time. Furthermore, the algorithm is optimized on a special kind of polygons formed by the boundary of such band-images as texts, industrial patterns etc. , with their characteristic of approximately equal width fully utilized. The feature has been applied for efficient skeleton extraction of band-like images.