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

基于一般曲线多边形Voronoi图的面向对象数据结构,提出了一种改进的Voronoi图生成算法——基链分治算法.该算法与经典的分治法相比更容易被实现.同时，在欧氏米制中,由于Voronoi区的边界包含抛物线或双曲线,因而Voronoi区的面积很难被计算.为此提出了Voronoi区的面积计算定理,并给出了定理证明和算例,从而为某些工程应用中的面积计算提供了一种方法.

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

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.