基链分治算法与Voronoi区的面积计算定理研究  

The Main-Chain Divide-and-Conquer Algorithm and the Area Computation Lemma for Voronoi Cell

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

机构地区：[1]哈尔滨工业大学机器人研究所,黑龙江哈尔滨150001 [2]中国科技大学计算机科学与技术系,安徽合肥230027

出　　处：《软件学报》2001年第3期440-447,共8页Journal of Software

基　　金：国家自然科学基金资助项目!(6 96 85 0 0 6 )&&

摘　　要：基于一般曲线多边形 Voronoi图的面向对象数据结构 ,提出了一种改进的 Voronoi图生成算法——基链分治算法 .该算法与经典的分治法相比更容易被实现 .同时 ,在欧氏米制中 ,由于 Voronoi区的边界包含抛物线或双曲线 ,因而 Voronoi区的面积很难被计算 .为此提出了 Voronoi区的面积计算定理 ,并给出了定理证明和算例 ,从而为某些工程应用中的面积计算提供了一种方法 .Based on the object oriented data structure of Voronoi diagram for normal curvilinear polygon, an improved Divide and Conquer algorithm is presented in this paper for Voronoi diagram generation called Main Chain Divide and Conquer algorithm. It is easier to implement compared with the classical one. Meanwhile, because the boundary of a Voronoi cell contains parabolic or hyperbolic curves in the Euclidean metric, it is difficult to compute the Voronoi cell area in practice. For this reason, an area computation lemma of the Voronoi cell is presented. The lemma proof and an example are also given. Thus, a way is provided for the area calculation in some engineering applications.

关 键 词：VORONOI 面向对象 数据结构 VORONOI图 基链分治算法 计算机图形学 

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