Voronoi图的构建和应用

侯玉昭

(南京航空航天大学机电学院，南京市，210016)

摘要：Voronoi图是计算几何中常用而又重要的几何结构，它有很强的实用价值。本文介绍了平面点集上的Voronoi图的一些生成方法，主要是矢量法和栅格法的原理与生成过程。其次就是V图在各个领域中的应用和分析了V图的一些优势特点。以此希望我国科研人员关注V图的研发工作。

关键词：Voronoi图；矢量法；栅格法；V图应用

Construction and application of Voronoi diagram

Hou Yuzhao

(College of Aerospace Engineering, Nanjing 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

the 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 Voronoi graph

引言

Voronoi图的历史是相当古老的。许多不同的自然结构都与Voronoi图十分接近，并且这些结构曾经被很多早期的科学家甚至普通人注意过。早在1908年，俄国数学家G.Voronoi

在对二次型的研究中首先使用了这种图，后被计算机研究者称之为Voronoi图。1944年，笛卡尔使用了一种图来显示太阳系内部和外部物质的性质。尽管没有特殊的注解来解释那些图的结构，但实际上这些图已经十分接近今天我们所说的加权Voronoi图。Voronoi图在许多领域都在尝试它的应用，并取得了成功。如天文学家用来研究宇宙结构；考古学家用来识别新石器时代不同部落影响下的地区；气象学家在仪器分布不足时估算降雨（雪）量；城市规划者在城市中用来进行设施定位；生物学家用来研究毛细血管供应肌肉组织情况。这些研究表面上涉及完全不同的现象，但实际上都可以用Voronoi图的概念来解释。

近年来，Voronoi图已被纳入计算几何的范畴，成为计算几何的一个重要分支。随着计算机科学与技术的飞速发展，尤其是计算机在图像处理方面的广泛应用，使得计算几何的研究，越来越受重视并日益蓬勃发展起来。计算几何在计算机辅助设计、计算机图形学、数字图像处理、地理信息处理、机器人等许多领域都有重要应用。它已成功解决了找最近点，求最大空圆，求n个点的凸包，求最小树等问题。另外，Voronoi图在模式识别、生态研究、城市规划、最优化配置、物理学等许多领域也有广泛的应用[1]。

Voronoi图构建

V图有着按距离划分邻近区域的普遍特性，应用范围广。生成V图的方法很多，一般分为两种：矢量方法；栅格方法。

1.1矢量方法（基于GIS软件）

矢量方法生成V图大多是对点实体。方法分为：对偶生成法；增添法；部件合成法等。 1.1.1对偶生成法

对偶生成法：主要是指生成V图时先生成其对偶元Delaunay三角网，再通过做三角网每一三角形三条边的中垂线，形成以每一三角形顶点为生成元的多边形网。如图1所示。

图1 对偶生成法生成V图

对偶生成法的关键是Delaunay三角网的生成。Delaunay三角网的特性：任一三角形外接圆内部包含其他点；三角形均衡或三边均衡，其最小角最大；使三角网总边长最小；在确定的n个点上，构造的Delaunay三角网网形唯一。

1.1.2增添法

增添法生成V图的基本思想是：假设平面上原有n个点（生成元），已生成了Vn图，现在增加一个生成元Pn+1，这时生成新的Vn+1图。由于V图的特性，加入一个新生成元只与该新生成元所在Voronoi多边形及与之相邻其它Voronoi多边形“迎向半边”有关，与这些多边形的“另半边”无关，也与除它们之外的其它生成元的Voronoi多边形无关。

增添法的基本步骤：

①搜索最邻近单元和相邻单元。最邻近单元为Pn+1所在原V图中某点的Voronoi多边形Vk以及原来与它相邻的若干个多边形及相应生成元，如图2（a）。

②局部更新。对于各邻近单元，首先与最邻近单元Vk中Pk作中垂线，并找其余Vk的交点，由于Vk是凸多边形，因而只产生两个交点1、2，1与2连线把与Vk相关的单元分为“两半”：与Pn+1“相关的一半”及“不相关的一半”，使Pn+1与相关一半的各生成元Pk+1， Pk+2…作中垂线围成各封闭多边形，即是加入Pn+1生成元后的新的Vn+1图。类此，可不断加入新的生成元，直至所需。如图2（b）。

（a） （b）

图2 增添法 1.1.3部件合成法

部件合成法：是指把生成元点集分为若干个子集，并且这些子集的并集必须为生成元点集，为避免不必要的麻烦，这些子集相互的交集尽可能小或为空集φ。先对这些子集生成子V图，然后把这些子V图合并，修正其相互影响部分的Voronoi多边形，从而得到全生成元点集的V图。如下图3所示。

图3 部件合成法

矢量方法生成V图的分析：

➢ 以上三种方法是矢量方法中常用的，随着并行处理技术的发展，V图生成页、也出现了并行算法，它使各生成元同时进行各点的V图计算；

➢ 矢量方法生成V图的算法和数据结构都较为复杂，其生成元是基于离散点集的，对于实际的地理信息，这远远不够，应该拓展成点、线、面、体及其组合的复杂形体；

➢ 目前矢量方法用离散点集代替线面，使空间实体的完整性遭到破坏，同时生成的V图，要经过复杂的识别和修补工作，这是一个尚待克服的困难；

➢ 对于光滑、不光滑组合曲线及相应组合成的封闭面域，尽管可用折线逼近，但折线毕竟不是曲线，在曲线光滑处，每一点都是转折点，而化为折线，折线交接处的点就成为唯一转折点，性质突变处。

1.2栅格方法（基于GIS软件和编程）

目前利用矢量法生成的Voronoi图的算法和数据结构复杂,其生成元基于离散点集,对于线、面和其他更复杂的空间目标需分解为点集进行处理。这种分解使空间实体的完整性遭到破坏,同时生成的Voronoi图需经过复杂的识别和修补。由于基于矢量方法生成的矢量Voronoi图存在的问题和不足,进而提出基于栅格方法生成栅格Voronoi图。距离变换是基于栅格方法的核心,下面给出了利用基于栅格方法生成Voronoi图的原理和步骤。

任意形状发生元Voronoi图构建的栅格方法：

wi1>0、wi2是加权Voronoi图的权重。

 当wi2=0时产生倍增的加权Voronoi图（multiplicatively weighted

Voronoi diagram），是在发生点集的扩散速度与权重成比例情况下形成的；

 当wi1=1时产生相加的加权Voronoi图（additively weighted Voronoi

diagram）；

 当wi1≠1, wi2 ≠ 0时产生复合的加权Voronoi图（compoundly weighted

Voronoi diagram）。

下面介绍加权Voronoi图的栅格构建方法： ,),(1),(21iiiiwwppdwppd 用gridpoint命令将包含有空间点位坐标的矢量图层数据转换为栅格数据，并把栅格数据放置在一个文本文件中。

 利用方程计算每一个栅格单元与各发生点的加权距离，以距离最短的发生点栅格的代码作为该栅格单元的隶属代码，如此下去，直至所有栅格单元的归属都被确定为止。

 把新的栅格单元代码数据写入到一个新的文本文件中，再用gridpoly命令将该代码数据转变为一个点的加权Voronoi图图层（在该方法的实现中，注意数据转换中所需要的文件头的内容），完毕。

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

V图的意义和应用

2.1 V图的特点

Voronoi多边形图由点集生成扩展为由点、线、面集生成后，V图就具有了以下特性：

（1）每个V多边形内有一个生成元；

（2）每个V多边形内点到该生成元距离短于到其它生成元距离；

（3）多边形边界上的点到生成此边界的生成元距离相等；

（4）邻接图形的Voronoi多边形界线以原邻接界线作为子集。

V图是空间邻近关系客观、全面、准确的体现，V图给出了邻近的准确量度。邻近决定于空间尺度, 是一种几何关系,而“邻”是一种拓扑关系, 两者不一样。复杂的连续函数内插要在邻近点间进行，V图给出了主影响元、邻近影响元，提供了优良内插方法的优秀环境。

V图、障碍V图、广义V图的多边形边界提供了点、线、面全形态，障碍、非障碍完备空间，广义加权距离的等距线、等比线、等势线等，是具有严密数学意义且极广泛使用价值的轨迹线。

2.2 V图的应用

Voronoi图的在计算几何学科中的重要地位，是由于Voronoi图在求解点集或其它几何对象与距离有关的问题时起的重要作用而决定的。这种根据Voronoi图的性质对区域的合理划分，广泛应用在地理学、气象学、结晶学、航天、核物理学、机器人等领域。例如，它可以应用于运动规划问题，即在充满障碍物的环境中为机器人寻找一条无碰撞的路径．解决的方法，可以利用障碍物的Voronoi图，因为它描述出了距离障碍物最远，也就是最安全的路径。随着Voronoi图的定义和算法被广泛传播，Voronoi图的应用领域也在不断扩展。这些应用实例尽管从专业角度千差万别，但从Voronoi图所发挥的作用角度，可以归结为如下3个方面：

（1）把Voronoi图作为表示各种元素之间关系的一个结构，通过这个结构可以提取出重要信息。这样的实例多见于用Voronoi图研究自然界物质结构的性质。

例如Nullans等将Voronoi图用在了地质结构的几何模型重构中，目标是将不同岩性的