多连通域Voronoi图生成算法的研究  

An Algorithm of Voronoi Diagram Generation for Multiply Connected Polygonal Domains

作　　者：付庄[1] 王树国[1] 王剑英[2] 蔡鹤皋[1] 

机构地区：[1]哈尔滨工业大学机器人研究所，150001 [2]中国科技大学计算机系，合肥 230027

出　　处：《系统工程与电子技术》2000年第11期88-90,共3页Systems Engineering and Electronics

基　　金：国家自然科学基金资助课题;"863"高技术计划资助课题

摘　　要：Voronoi图作为一种重要的计算机图形学技术 ,在数控加工、机器人的运动规划和曲面生成等许多领域都有广阔的应用前景。研究了由直线和圆弧组成的平面多连通域Voronoi图的生成算法 ,提出了平面闭包的搜索算法与闭包的归一化方法 ,根据单连通域Voronoi图的生成算法实现了多连通域Voronoi图的构造。As one of the important computer graphics techniques, the Voronoi diagram has potential prospect of application in many fields, such as the NC machining, robot motion planning, mesh generation and so on. This paper studies the Voronoi diagram generation algorithm for planar multiply connected polygonal domain (MCPD), which consists of the straight lines and the circular arcs, and presents a searching algorithm and the merging method for planar closures. According to the Voronoi diagram generation for simply connected polygonal domain (SCPD), the Voronoi diagram construction for MCPD is implemented. We have verified the efficiency and the feasibility of the algorithms by practics.

关 键 词：计算机图形学 图像分析 Voronoi图生成算法 

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