自由边界平面连通域的Voronoi图生成方法研究  

Approach to build Voronoi diagram for multiply-connected domains with free-form contour

作　　者：胡俊[1] 王宇晗[1] 蔡建国[1] 

机构地区：[1]上海交通大学机械与动力工程学院,上海200030

出　　处：《工程设计学报》2004年第1期6-10,15,共6页Chinese Journal of Engineering Design

基　　金：国家"8 6 3"专项资金资助项目 (2 0 0 2 AA 4 2 4 0 4 2 ) ;上海市科技发展基金重点资助项目 (0 2 111112 0 )

摘　　要：平面连通域的 Voronoi图被广泛应用于许多领域 ,常用的分治法等算法实现较为复杂 ,影响了其应用范围 .在凸多边形中轴算法的基础上 ,提出一种建立自由边界平面连通域的 Voronoi图的新方法 .通过求解相邻边界元素的平分线 ,计算出相邻平分线的交点 ,由距离最小的平分线交点实现 Voronoi图边的增长 ,最终建立完整的平面单连通域的 Voronoi图 .同时 ,还介绍了平面多连通域的内外边界的 Voronoi图的合并算法 .The Voronoi diagram of connected domain is widely used. The generally adopted algorithms, such as divide-and-conquer method, are difficult to realize. A new method to establish free boundary connected domain Voronoi diagram is introduced based on the algorithm for determining the medial axis of an convex polygon. Through finding the bisectors of neighboring boundary elements, points of intersection of neighboring bisectors are obtained.Point of intersection with the minimum distance is used to realize the growing of Voronoi diagram. The entire simply-connected domain Voronoi diagram is established in this way. The Voronoi diagram merging algorithm for inner and outer boundary of multi-connected domain is also introduced.

关 键 词：平面连通域 平分线 VORONOI图 凸多边形中轴算法 计算几何 CAD 

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