Voronoi图.ppt

《Voronoi图.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章Voronoi图主讲教师：邱春霞测绘学院重点内容：Voronoi图的定义Voronoi图的生成方法Voronoi图的应用Voronoi结构的概念是由俄国数学家M.G.Voronoi于1908年发现并以他的名字命名的。它实质是一种在自然界中宏观和微观实体以距离相互作用的普遍结构，具有广泛的应用范围。5.1Voronoi图定义从Voronoi结构所脱胎的计算几何来看，V图是对平面n个离散点而言的，它把平面分为几个区，每一个区包括一个点，该点所在的区是到该点距离最近点的集合。一、V图基本定义（一）定义设P是一离散点集合P1，P2，…Pn∈P，定义Pi的Voronoi区

2、域V（Pi）为所有到Pi距离最小点的集合：V（Pi）={P/d（P，Pi）≤d（P，Pj），j≠i，j=1，2，…n}假设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，即（假定到Pi为0的点不算在Vi内）（假定到Pi为0的点算在Vi内）多边形内点到该多边形生成元距离最小。两多边形边界上的点到两对应

3、多边形生成元距离相等。在一多边形内，生成元到各个边的距离一般不同，可由小到大排序，其中有最小，次小……表明其周围生成元到该生成元的不同距离。二、地理空间（二维）对V图的扩展定义二维地理空间G是由n个点、线、面实体集合g1，g2，……gn组成的，则称该地理空间是定义了一种尺度d的量度空间。设G是由n个实体组成的集合，g1，g2，…，gn∈G，定义gi的Voronoi区域V（gi）为所有到gi距离最小点（栅格）的集合V（gi）={p/d（p,gi）≤d（p,gj）,i≠j,j=1,2,…，n}设G是由n个实体组成的集合，g1，g2，…gn∈G，定义G的Voronoi图V（

4、G）为V（G）={V（g1），V（g2），…，V（gn）}（一）V图定义V图是与距离紧密相关的，而距离值是由尺度所基本定义的。不同尺度，距离的概念不一样，数值往往也不一样，因此不同的尺度空间，有不同的V图。上述定义同样可推广到3维。（二）广义Voronoi图拓展Voronoi图为广义Voronoi图具有广泛意义。设G是由n个实体组成的集合，g1，g2，…，gn∈G，且各实体具有权ki，定义gi的Voronoi区域V（gi）为所有到gi加权距离最小点（栅格）的集合V(gi)={p/kid(p，gi)≤kjd(p，gj)，i≠j,j=1,2,…，n}设G是由n个实体组成的

5、集合，g1，g2，…gn∈G，定义G的Voronoi图V（G）为V（G）={V(g1)，V(g2)，…，V(gn)}一般V图特性在广义V图中类似存在。5.2V图生成方法V图有着按距离划分邻近区域的普遍特性，应用范围广。生成V图的方法很多，一般分为两种：矢量方法栅格方法一、生成V图的矢量方法矢量方法生成V图大多是对点实体。方法分为：对偶生成法增添法部件合成法（一）对偶生成法对偶生成法：主要是指生成V图时先生成其对偶元Delaunay三角网，再通过做三角网每一三角形三条边的中垂线，形成以每一三角形顶点为生成元的多边形网。对偶生成法生成V图对偶生成法的关键是Delaunay

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

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