目前矢量方法用离散点集代替线面，使空间实体的完整性 遭到破坏，同时生成的V图，要经过复杂的识别和修补工 作，这是一个尚待克服的困难；
增添法的基本步骤：
①搜索最邻近单元和相邻单元
最邻近单元为Pn+1所在原V图中某点 的Voronoi多边形Vk以及原来与它 相邻的若干个多边形及相应生成 元；
②局部更新
对于各邻近单元，首先与最邻近单
元Vk中Pk作中垂线，并找其余Vk 的交点，由于Vk是凸多边形，因 而只产生两个交点1、2，1与2连 线把与Vk相关的单元分为“两 半”：与Pn+1“相关的一半”及 “不相关的一半”，使Pn+1与相 关一半的各生成元Pk+1， Pk+2…作 中垂线围成各封闭多边形，即是
增添法 部件合成法
（一）对偶生成法
对偶生成法：主要是指生成V图时先生成其对偶元 Delaunay三角网，再通过做三角网每一三角形三条 边的中垂线，形成以每一三角形顶点为生成元的多 边形网 。
对偶生成法生成V图
对偶生成法的关键是Delaunay三角网的生成。
Delaunay三角网的特性： 任一三角形外接圆内部包含其他点； 三角形均衡或三边均衡，其最小角最大； 使三角网总边长最小； 在确定的n个点上，构造的Delaunay三角网网形唯一。
部件合成
（四）矢量方法生成V图的分析
以上三种方法是矢量方法中常用的，随着并行处理技术的 发展，V图生成页、也出现了并行算法，它使各生成元同 时进行各点的V图计算；
矢量方法生成V图的算法和数据结构都较为复杂，其生成 元是基于离散点集的，对于实际的地理信息，这远远不够， 应该拓展成点、线、面、体及其组合的复杂形体；
Vi Vj
PV1 V2 ...Vn R2 （假定到Pi为0的点不算在Vi内）
V1 V2 ...Vn R2
（假定到Pi为0的点算在Vi内）
多边形内点到该多边形生成元距离最小。 两多边形边界上的点到两对应多边形生成元距
离相等。 在一多边形内，生成元到各个边的距离一般不
同，可由小到大排序，其中有最小，次小…… 表明其周围生成元到该生成元的不同距离。
（二）增添法
增添法生成V图的基本思想是：假设平面上原有n 个点（生成元），已生成了Vn图，现在增加一个 生成元Pn+1，这时生成新的Vn+1图。由于V图的特 性，加入一个新生成元只与该新生成元所在 Voronoi多边形及与之相邻其它Voronoi多边形“迎 向半边”有关，与这些多边形的“另半边”无关， 也与除它们之外的其它生成元的Voronoi多边形无 关。
（二）广义Voronoi图
拓展Voronoi图为广义Voronoi图具有广泛意义。
设G是由n个实体组成的集合，g1，g2，…，gn ∈ G， 且各实体具有权ki，定义gi的Voronoi区域V（gi）为所 有到gi加权距离最小点（栅格）的集合
V(gi)={p/kid(p，gi)≤kj d(p，gj)， i≠j, j=1, 2, …，n} 设G是由n个实体组成的集合，g1，g2，…gn ∈ G，定
V（gi）={p/d（p,gi）≤d（p,gj）, i≠j, j=1, 2, …，n} 设G是由n个实体组成的集合，g1，g2，…gn ∈ G，定
义G的Voronoi图V（G）为
V（G）={V（g1），V（g2），…，V（gn）}
V图是与距离紧密相关的，而距离值是由尺度所 基本定义的。不同尺度，距离的概念不一样， 数值往往也不一样，因此不同的尺度空间，有 不同的V图。上述定义同样可推广到3维。
加入Pn+1生成元后的新的Vn+1图。 类此，可不断加入新的生成元，
直至所需。
新加入Pn+1只改变与 之相关的生成元的
Voronoi多边形，其余 不动。
（三）部件合成法
部件合成法：是指把生成元点集分为若干个子集， 并且这些子集的并集必须为生成元点集，为避免 不必要的麻烦，这些子集相互的交集尽可能小或 为空集φ。先对这些子集生成子V图，然后把这些 子V图合并，修正其相互影响部分的Voronoi多边 形，从而得到全生成元点集的V图。
假设P是一离散点集合，P1，P2，…Pn ∈ P，定义P 的V图V（P）为：
V（P）={V（P1）,V（P2）,…,V（Pn）} 其中Pi称为V图生成元。
（二）性质
假设平面上有n个离散点，其对应的Voronoi多边
形分别为V1，V2…Vn， Voronoi多边形之间除边
界外，其交集为空集，所有Voronoi多边形的并集 为二维平面R2，即
第五章 Voronoi图
主讲教师：邱春霞 测绘学院
重点内容：
Voronoi图的定义 Voronoi图的生成方法 Voronoi图的应用
Voronoi结构的概念是由俄国数学家 M.G.Voronoi于1908年发现并以他的名字命名 的。它实质是一种在自然界中宏观和微观实 体以距离相互作用的普遍结构，具有广泛的 应用范围。
二、地理空间（二维）对V图的扩展定义
（一）V图定义
二维地理空间G是由n个点、线、面实体集合g1， g2，……gn组成的，则称该地理空间是定义了一种尺 度d的量度空间。
设G是由n个实体组成的集合，g1，g2，…，gn ∈ G， 定义gi的Voronoi区域V（gi）为所有到gi距离最小点 （栅格）的集合
义G的Voronoi图V（G）为
V（G）={V(g1)，V(g2)，…，V(gn)} 一般V图特性在广义V图中类似存在。
5.2 V图生成方法
V图有着按距离划分邻近区域的普遍特性，应 用范围广。
生成V图的方法很多，一般分为两种： 矢量方法 栅格方法
一、生成V图的矢量方法
矢量方法生成V图大多是对点实体。 方法分为：对偶生成法
5.1 Voronoi图定义
一、V图基本定义
从Voronoi结构所脱胎的计算几何来看，V图是 对平面n个离散点而言的，它把平面分为几个 区，每一个区包括一个点，该点所在定义
设P是一离散点集合P1，P2，…Pn∈P，定义Pi的 Voronoi区域V（Pi）为所有到Pi距离最小点的集合： V（Pi）={P/d（P，Pi）≤d（P，Pj）， j≠i，j=1，2，…n}