Voronoi图的构建和应用

1、Voronoi图的构建和应用侯玉昭（南京航空航天大学机电学院，南京市，210016）摘要：Voronoi图是计算几何中常用而又重要的几何结构，它有很强的实用价值。本文介绍了平面点集上的Voronoi图的一些生成方法，主要是矢量法和栅格法的原理与生成过程。其次就是V图在各个领域中的应用和分析了 V图的一些优势特点。以此希望我国科研人员关注V图的研发工作。关键词：Voronoi图；矢量法；栅格法；V图应用Construction and application of V oronoi diagramHou Yuzhao(College of Aerospace Engineering, Nanji

2、ng University of Aeronautics & Astronautics, Nanjing, 210016, China;)Abstract: Voronoi graph is a common and important computational geometry in diagram geometry,it has a strong practical value.This paper introduces some generation method for planar point set on the Voronoi graph,it is mainly th

3、e principle and formation process of the vector method and the grid method.The second is the application of V graphs in various fields and analyzes some advantages of V graphs. We hope our researchers focus on R&D of V graph.Key words : Voronoi graph;Vector method;Grid method;Application of V or

4、onoi graph引言Voronoi图的历史是相当古老的。许多不同的自然结构都与Voronoi图十分接近，并且这些结构曾经被很多早期的科学家甚至普通人注意过。早在1908年，俄国数学家G.Voronoi在对二次型的研究中首先使用了这种图，后被计算机研究者称之为Voronoi图。1944年，笛卡尔使用了一种图来显示太阳系内部和外部物质的性质。尽管没有特殊的注解来解释那些图的结构，但实际上这些图已经十分接近今天我们所说的加权Voronoi图。Voronoi图在许多领域都在尝试它的应用，并取得了成功。如天文学家用来研究宇宙结构；考古学家用来识别新石器时代不同部落影响下的地区；气象学家在仪器分布不足

5、时估算降雨（雪）量；城市规划者在城市中用来进行设施定位；生物学家用来研究毛细血管供应肌肉组织情况。这些研究表面上涉及完全不同的现象，但实际上都可以用Voronoi图的概念来解释。近年来，Voronoi图已被纳入计算几何的范畴，成为计算几何的一个重要分支。随着计 算机科学与技术的飞速发展，尤其是计算机在图像处理方面的广泛应用，使得计算几何的研究，越来越受重视并日益蓬勃发展起来。计算几何在计算机辅助设计、计算机图形学、数字图像处理、地理信息处理、机器人等许多领域都有重要应用。它已成功解决了找最近点，求最大空圆，求 n个点的凸包，求最小树等问题。另外，Voronoi图在模式识别、生态研究、城市规划、

6、最优化配置、物理学等许多领域也有广泛的应用1。Voronoi图构建V图有着按距离划分邻近区域的普遍特性，应用范围广。生成V图的方法很多，一般分为两种：矢量方法；栅格方法。1.1矢量方法（基于GIS软件）矢量方法生成 V图大多是对点实体。 方法分为：对偶生成法；增添法；部件合成法等。1.1.1对偶生成法对偶生成法：主要是指生成V图时先生成其对偶元 Delaunay三角网，再通过做三角网每一三角形三条边的中垂线，形成以每一三角形顶点为生成元的多边形网。如图1所示。图2增添法图2增添法图1对偶生成法生成V图对偶生成法的关键是 Delaunay三角网的生成。Delaunay三角网的特性：任一三角形外

7、接圆内部包含其他点；三角形均衡或三边均衡，其最小角最大；使三角网总边长最小；在确定的n个点上，构造的 Delaunay三角网网形唯一。1.1.2增添法增添法生成 V图的基本思想是：假设平面上原有n个点（生成元），已生成了 Vn图,现在增加一个生成元 Pn+1，这时生成新的 Vn+i图。由于V图的特性，加入一个新生成元只 与该新生成元所在 Voronoi多边形及与之相邻其它 Voronoi多边形"迎向半边”有关，与这 些多边形的“另半边”无关，也与除它们之外的其它生成元的Voronoi多边形无关。增添法的基本步骤： 搜索最邻近单元和相邻单元。最邻近单元为Pn+i所在原V图中某点的Vor

8、onoi多边形Vk以及原来与它相邻的若干个多边形及相应生成元，如图2（a）。 局部更新。对于各邻近单元，首先与最邻近单元Vk中Pk作中垂线，并找其余Vk的交点，由于Vk是凸多边形，因而只产生两个交点1、2, 1与2连线把与Vk相关的单元分为“两半”：与Pn+1相关的一半”及“不相关的一半”，使Pn+1与相关一半的各生成元Pk+1 , Pk+2Pn+1生成元后的新的Vn+1图。类此，可不断加入新作中垂线围成各封闭多边形，即是加入 的生成元，直至所需。如图 2 （b ）。(a)(b)图2增添法1.1.3部件合成法部件合成法：是指把生成元点集分为若干个子集，并且这些子集的并集必须为生成元点集，为避免

9、不必要的麻烦，这些子集相互的交集尽可能小或为空集心先对这些子集生成子V图，然后把这些子 V图合并，修正其相互影响部分的Voronoi多边形，从而得到全生成元点集的V图。如下图3所示。矢量方法生成 V图的分析：以上三种方法是矢量方法中常用的，随着并行处理技术的发展，V图生成页、也出现了并行算法，它使各生成元同时进行各点的V图计算；矢量方法生成V图的算法和数据结构都较为复杂，其生成元是基于离散点集的，对 于实际的地理信息，这远远不够，应该拓展成点、线、面、体及其组合的复杂形体； 目前矢量方法用离散点集代替线面，使空间实体的完整性遭到破坏，同时生成的V图，要经过复杂的识别和修补工作，这是一个尚待克服

10、的困难；对于光滑、不光滑组合曲线及相应组合成的封闭面域，尽管可用折线逼近，但折线 毕竟不是曲线，在曲线光滑处，每一点都是转折点，而化为折线，折线交接处的点 就成为唯一转折点，性质突变处。1.2栅格方法(基于GIS软件和编程)目前利用矢量法生成的Voronoi图的算法和数据结构复杂，其生成元基于离散点集，对于线、面和其他更复杂的空间目标需分解为点集进行处理。这种分解使空间实体的完整性遭到破坏，同时生成的Voronoi图需经过复杂的识别和修补。由于基于矢量方法生成的矢量Voronoi图存在的问题和不足，进而提出基于栅格方法生成栅格Voronoi图。距离变换是基于栅格方法的核心，下面给出了利用基于栅

11、格方法生成Voronoi图的原理和步骤。任意形状发生元Voronoi图构建的栅格方法：1dw(p，Pi)d(p, pj - Wi2，WiiWi >0、W2是加权Voronoi图的权重。当 W2=0 时产生倍增的加权 Voronoi 图(multiplicatively weightedVoronoi diagram ),是在发生点集的扩散速度与权重成比例情况下形成的；当 W1 =1 时产生相加的加权 Voronoi 图(additively weighted Voronoi diagram )；当w丰1, W2工0时产生复合的加权 Voronoi图(compoundly weighted

12、 Voronoi diagram )。下面介绍加权 Voronoi图的栅格构建方法：用 gridpoint 命令将包含有空间点位坐标的矢量图层数据转换为栅格数据，并把栅格 数据放置在一个文本文件中。利用方程计算每一个栅格单元与各发生点的加权距离，以距离最短的发生点栅格的 代码作为该栅格单元的隶属代码，如此下去，直至所有栅格单元的归属都被确定为 止。把新的栅格单元代码数据写入到一个新的文本文件中，再用 gridpoly 命令将该代码 数据转变为一个点的加权 Voronoi 图图层（在该方法的实现中，注意数据转换中所 需要的文件头的内容） ，完毕 。下面是对栅格方法的一些改进性研究。 如李成名等提

13、出一个基于邻域扩张的 Voronoi 图 生成算法 ,分析了利用传统的距离变换生成栅格Voronoi 图的误差情况 ,对各种栅格算法的精度进行了分析 ,并引入动态距离变换的栅格邻域扩张模式。王新生等提出了一种新的基于栅 格的 Voronoi 生成方法 ,通过确定每个栅格的归属来定义Voronoi 区域 ,为了减少计算时间 ,设计了一种搜索某个栅格所属最近发生元栅格的方法。 栅格法的核心问题是栅格空间中两点的 距离定义 ,关于栅格的距离典型定义有 :街区距离、棋盘距离、八角形距离、斜面3-4 距离、斜面 2-3 距离 ,无论是普通 Voronoi 图还是加权 Voronoi 图 ,这些距离计算的

14、前提是每个栅格是 等距的基元。故马林兵提出一个非均质栅格 Voronoi 图的生成方法 24 。V 图的意义和应用2.1 V 图的特点Voronoi 多边形图由点集生成扩展为由点、线、面集生成后， V 图就具有了以下特性：（ 1）每个 V 多边形内有一个生成元；（ 2）每个 V 多边形内点到该生成元距离短于到其它生成元距离；（3）多边形边界上的点到生成此边界的生成元距离相等；（ 4）邻接图形的 Voronoi 多边形界线以原邻接界线作为子集。V 图是空间邻近关系客观、全面、准确的体现， V 图给出了邻近的准确量度。邻近决定 于空间尺度 , 是一种几何关系 ,而“邻”是一种拓扑关系 , 两者不一

15、样。复杂的连续函数内插 要在邻近点间进行， V 图给出了主影响元、邻近影响元，提供了优良内插方法的优秀环境。V 图、障碍 V 图、广义 V 图的多边形边界提供了点、线、面全形态，障碍、非障碍完 备空间，广义加权距离的等距线、等比线、等势线等，是具有严密数学意义且极广泛使用价 值的轨迹线。2.2 V 图的应用Voronoi 图的在计算几何学科中的重要地位，是由于 Voronoi 图在求解点集或其它几何 对象与距离有关的问题时起的重要作用而决定的。 这种根据 Voronoi 图的性质对区域的合理 划分，广泛应用在地理学、气象学、结晶学、航天、核物理学、机器人等领域。例如，它可 以应用于运动规划问题

16、， 即在充满障碍物的环境中为机器人寻找一条无碰撞的路径 解决的 方法，可以利用障碍物的 Voronoi 图，因为它描述出了距离障碍物最远，也就是最安全的路 径。随着 Voronoi 图的定义和算法被广泛传播， Voronoi 图的应用领域也在不断扩展。这些 应用实例尽管从专业角度千差万别，但从 Voronoi 图所发挥的作用角度，可以归结为如下 3 个方面：（ 1）把 Voronoi 图作为表示各种元素之间关系的一个结构，通过这个结构可以提取出 重要信息。这样的实例多见于用 Voronoi 图研究自然界物质结构的性质。例如 Nullans 等将 Voronoi 图用在了地质结构的几何模型重构中

17、，目标是将不同岩性的地质结构表示为不同的实体， 以便工程设计与分析之用。 他们首先对各种工程地质勘探数据 进行预处理，得到一个带颜色的点集(岩性相同的点具有相同的颜色)；然后以这些带颜色点为站点作出 Voronoi 图；最后再合并颜色相同的 Voronoi 区域，将相邻的且岩性相同的地质 结构表示为同一实体。 如果不考虑地质结构的方向异性因素， 这种方法所确定的地质结构分 布范围应是非常合理的。 这种方法也适合于根据 CT 数据重构人体组织器官的几何模型，比 连接等高轮廓线的方法更具有通用性( 2)把 Voronoi 图作为一个辅助数据结构，通过这个数据结构可以完成许多物体形态 或邻近关系的计

18、算任务。例如，近年来， Voronoi 图被广泛地用在分析蛋白质等生物大分子的结构。在此领域， 人们一般首先用 X 射线衍射测量的方法或分子动力计算的方法得到蛋白质表面上原子的位 置和溶剂分子的位置。然后以蛋白质原子和溶剂分子为站点生成三维 Voronoi 图，把蛋白质 原子的 Voronoi 多面体加在一起就可以得到蛋白质分子的体积， 进一步还可以得到可接触表 面积和包装密度等参数。在这里之所以采用 Voronoi 图进行计算，而不是把原子看成球体来 计算，是因为人们不必关心蛋白质内部的原子类型和位置。 在此领域， 在一个分子中原子之 间的距离比较近，如果不区分原子的大小而一概以原子的中心为

19、站点划分 Voronoi 图，小原 子计算出的体积比实际要大， 大原子计算出的体积比实际要小。 为解决此问题， 人们也提出 了各种方法。 Gerstein 等的方法是先计算出普通的 Voronoi 图，然后在根据原子的大小对 Voronoi 多面体加以调整。 Will 引入了考虑原子半径的加权 Voronoi 图，即每个 Voronoi 区域 是距离原子表面最近的区域，并且给出了这种 Voronoi 图的生成算法。( 3)把 Voronoi 图作为提高某些几何算法运算速度的重要手段。一般来说，二维的Voronoi图可以在 0(nlogn)时间内获得，三维的 Voronoi图可以在 0(n2)时

20、间内获得。Voronoi 图的性质决定了它与许多其它几何结构具有内在关系，通过Voronoi 图，许多几何算法可以得到快速运算。Fujita 等应用 Voronoi 图求解约束非线性规划问题。 Voronoi 图在这里的作用是获得目标 函数和约束函数的逼近函数， 然后用逼近函数去求最优解， 这样可以使求梯度的解析过程得 到简化。 求解过程是一个迭代过程， 首先在参数空间随机地选取一些采样点， 如果由这些点 确定的最优解可信度足够大，则停止；否则，在可能产生最优解的Voronoi 区域内插入新的采样点，继续迭代，直到得到一个可信的最优解或迭代到指定次数为止3。总结Voronoi 图是一种很基本的几何数据结构， 在解决很多的实际问题中有许多应用。Voronoi图是一个内容丰富庞杂的研究课题，对于这个问题，有着广泛的应用背景。国外在Voronoi图方面的研究开展的很广泛、 很深入， 而国内专门从事这方面研究的人很少。 因此国内人士 应加强对 Voronoi 图理论和应用的研究，充分认识 Voronoi 图的重要性与实用性，吸引更多 的研究人员关注这个领域。参考文献：1. 宗大伟 .Voronoi 图及其应用研究 D ：南京：南京航空航天大学， 2006.Zong Dawei.Study on Voronoi diagram and