多边形的Voronoi图及其研究应用
Voronoi图是计算几何的重要几何结构之一，也是计算几何的重要研究内容之一。

它按照对象集合中元素的最近属性将空间划分成许多单元区域。

由于Voronoi图具有最近性、邻接性等众多性质和较完善的理论体系，如今已经在图形学、机械工程、虚拟现实、地理信息系统、机器人、图像处理、CAD等领域得到广泛应用，也是解决距离计算、碰撞检测、路径规划、Delaunay三角化、骨架计算、凸包计算以及可见性计算等计算几何其它问题的有效工具，因而受到人们的广泛关注。

目前，对Voronoi图的研究工作，从所在空间上来说，更多的集中在2维上；从生成对象上来说，更多的集中在离散点集上；在研究内容上来说，主要集中在其构造算法和相关应用研究上。

对于多边形的Voronoi 图来说，则主要集中在多边形的内部Voronoi图的构造和相关应用上。

本论文对多边形的内部和外部Voronoi图的相关性质进行了较为深入的研究，并以此为基础研究解决在图形图像、虚拟现实等方面的研究工作中遇到的可见性计算、距离计算以及骨架计算等问题。

本论文的贡献主要有：
1、分析了M.Held给出的关于多边形内部Voronoi图顶点和边数的上界所存在的局限性：只适用于单边界多边形，对多边界多边形则不适用；给出了新的可适用于单边界和多边界多边形的内部Voronoi图顶点和边数上界估计；同时给出了多边形的外部Voronoi图顶点和边数上界估计；并对多边形的内部和外部Voronoi图的每一个Voronoi区域所包含的顶点和边数的平均值进行了估计。

2、提出了一种基于Voronoi图的计算多边形可见性的算法。

我们用多边形的Voronoi图建立多边形的骨架，利用Voronoi图的邻近属性和最近特性等性质，沿着骨架在局部范围内确定可能产生遮挡的对象，从而确定多边形内任意一点的可见边。

在预先建立一个多边形的骨架后，可在时间内确定多边形内任一观察点的可见边，其中为搜索过程中涉及到的Voronoi图中的骨架元素的数目。

大部分情况和可见边数接近。

本算法时间复杂度低，适用于任意多边形，且易于理解和编程实现。

3、给出了基于Voronoi图快速计算两个分离凸多边形距离的算法。

算法利用两个分离凸多边形P和Q的外部Voronoi图的性质及其相互间的位置关系，采用二分法逐渐缩小搜索范围来快速查找最短距离对象对。

算法首先根据多边形外部Voronoi图的性质确定最短距离对象对所在的初始搜索范围P(和Q(；然后取P(和Q(的中间顶点对象pm1和qm2，它们分别将P(，Q(平分成和，和四个子搜索范围，并根据pm1和qm2及其所在Voronoi 区域的位置关系，确定可删除的一个或两个子搜索范围；然后在剩余的子搜索范围继续用二分法查找最短距离
对象对，从而在时间内快速计算两个分离凸多边形的距离，其中、分别为两个多边形的边的数目。

本算法简单且易于编程实现，不需要任何预处理和特殊的数据结构。

4、提出了基于多边形划分的带状图像及其骨架表示模型，并分别以一般的多边形划分和多边形的约束Delaunay三角化为基础，设计并实现了两种骨架化算法。

对于一个带状图像，我们可以将其分割成许多色带，每条色带又可以分为若干区域，每个区域都用一个三角形、梯形、平行四边形或扇形来近似，因而带状图像的骨架可以通过计算这些三角形、梯形、平行四边形或扇形等区域的骨架求得。

对于不同类型的区域，根据其形状及相应邻接关系，采用不同的方法计算其骨架。

基于本论文的工作，可以把Voronoi图理论扩展到场景的表示、光线跟踪、阴影生成等方面，为系统化地解决三维虚拟场景快速绘制问题提供了一定的理论基础。

这些工作的成果，可用在我们研发的“数字博物馆应用支撑平台”、“集成化计算机辅助图案设计制版系统”等系统中，有非常重要的理论意义和实际应用价值。

关键词：计算几何、多边形、Voronoi图、可见性计算、距离计算、骨架、Delaunay三角化。

【关闭窗口】。