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

Fast Constrained Delaunay Triangulation for Planar Polygonal Domains

作　　者：曾薇[1] 孟祥旭[1] 杨承磊[1] 杨义军[2] 

机构地区：[1]山东大学计算机科学与技术学院,济南250061 [2]清华大学计算机科学与技术系,北京100084

出　　处：《计算机辅助设计与图形学学报》2005年第9期1933-1940,共8页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(60473103)

摘　　要：针对任意平面多边形域,采用增量思想和均匀网格,在局部范围内快速生成约束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.

关 键 词：平面多边形域 约束DELAUNAY三角化 均匀网格 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]