| 摘要: |
| 基于一般曲线多边形Voronoi图的面向对象数据结构,提出了一种改进的Voronoi图生成算法——基链分治算法.该算法与经典的分治法相比更容易被实现.同时，在欧氏米制中,由于Voronoi区的边界包含抛物线或双曲线,因而Voronoi区的面积很难被计算.为此提出了Voronoi区的面积计算定理,并给出了定理证明和算例,从而为某些工程应用中的面积计算提供了一种方法. |
| 关键词: Voronoi区 面向对象的数据结构 候选轮廓平分线 基链分治法 |
| DOI： |
| 分类号: |
| 基金项目:国家自然科学基金资助项目(69685006) |
|
| The Main-Chain Divide-and-Conquer Algorithm and the Area Computation Lemma for Voronoi Cell |
|
FU Zhuang,WANG Shu-guo,WANG Jian-ying,CAI He-gao
|
| Abstract: |
| 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. |
| Key words: Voronoi cell object-oriented data structure candidate contour bisector main-chain divide-and-conquer algorithm |
