增删点后的Voronoi图生成算法

张 娟， 杜全叶

（1. 兰州交通大学，甘肃 兰州 730070；2. 中国测绘科学研究院，北京 100380）

1 Voronoi图的基础

1.1 Voronoi 图的概念[1]

如图1，L是P1P2的垂直平分线，并将平面分成L左和L右两部分，位于L左内的点P左 具有特性：

d(P左,P1)

图 1 V(P1)，V(P2)图示

图2 n= 6时的一种Voronoi图

给定平面上n个点的点集S={P1，P2，…，Pn}，定义V(Pi)=H(Pi，Pj)，即V(Pi)表示比其他点更接近Pi的点的轨迹是n-1个半平面的交，它是一个不多于n-1条边的凸多边形域，称为关联于Pi的Voronoi多边形或关联于Pi的Voronoi域。

S中的每个点都可做一个 Voronoi多边形，这样的n个多边形组成的图称为Voronoi图，记作Vor(S)，其顶点和边分别称为Voronoi顶点和Voronoi边，如图2为n= 6时的一种Voronoi图。Voronoi图的定义可以推广到三维或多维，也可以推广到二阶或高阶（以2个站点或多个站点为一组来划分临近区域）[2]。1.2 Voronoi 图的特性

1） 每个Voronoi多边形内仅含有一个离散点数据；

2） Voronoi多边形内的点到相应离散点的距离最近；

3） 每个Voronoi 点恰好是3条Voronoi 边的交点（Voronoi 点是S中3点形成的三角形的外接圆的圆心）。

1.3 Voronoi 图的应用

简单来说，Voronoi图是一个关于空间划分的基础数据结构[2]，已知平面上有任意n个点，按照这些点的分布将平面划分成n部分，从而得到一种对平面的划分图。Voronoi图理论成功地解决了找最近点、求最大空圆、求n个点的凸包、求最小树等问题，与其对偶图Delaunay三角剖分已被广泛地应用到几何形体重构、计算机图形学、图像处理、模式识别、机器人运动规划、分子生物学等众多领域。

随着计算机的发展和工程设计自动化的要求以及建立地理信息系统的需要，出现了用数字形式表示地面的方式，即“数字地面模型（DTM）”。……