Delaunay三角化是计算几何的重要研究内容之一,由其生成的Delarnay三角网格,具有空外接圆、最小角最大等众多特性,是计算几何的重要几何结构之一。此外,Delaunay三角化拥有较完善的理论体系,如今已经在图形学、机械工程、虚拟现实、地理信息系统、机器人、图像处理、CAD等领域得到广泛应用,也是解决骨架计算、可见性计算等计算几何其它问题的有效工具。近年来,也被成功地应用于模式识别过程中的模式匹配,比如指纹细节点匹配,受到人们的密切关注。 本论文对多边形域的Delaunay三角化进行了较为深入的研究,并以此为基础研究解决在图形图像、虚拟现实等研究工作中的骨架计算问题,以及在线手写体识别中的特征提取问题。这些问题来源于教研室的“集成化计算机辅助图案设计制版系统”的研发工作以及在微软亚洲研究院实习期间关于“基于离散隐Markov模型的在线手写体识别系统”的研究实现中,有着非常重要的理论意义和实际应用价值。 本论文的贡献主要有: 1、针对任意平面多边形域,采用增量思想和均匀网格,在局部范围内快速生成约束Delaunay三角形。算法不会生成区域外的三角形;对存在折线、离散点以及含“洞”的情况不需要特殊处理。实验结果表明,对于随机生成的简单多边形域三角化速度快,平均计算时间呈近似线性,明显快于其它三角化算法。 2、针对文字、工业图案等带状图像的带状边界多边形,充分利用其近似等宽性优化约束Delaunay三角化(CDT)算法,并以此为基础设计实现了一种有效的带