Voronoi图.ppt

1、第五章Voronoi图，讲师：邱春霞测绘学院，重点内容：Voronoi图的定义Voronoi图的制作方法Voronoi图的应用，Voronoi结构的概念是俄罗斯数学家M.G.Voronoi在1908年发现的，以他的名字命名。 它本质上是自然界宏观和微观实体在距离上相互作用的普遍结构，具有广泛的应用范围。 5.1 Voronoi图从Voronoi结构产生的计算几何来看，v图就平面n个离散点把平面分成几个区域，每个区域包含了离该点最近的点的集合。1、v图的基本定义、(1)定义、p为离散点集合P1、P2、PnP，定义Pi的Voronoi区域V(Pi )全部为到Pi为止的距离最小的点的集合： V(Pi

2、)=P/d(P，Pi)d(P，Pj )、ji、j=1、2、np (2)性质假定在平面上有n个离散点，与此对应的Voronoi多边形分别在V1、V2Vn、Voronoi多边形之间除了边界之外，其交叉是空集合，所有的Voronoi多边形的和是二维平面R2，即，(Pi变为0的点在Vi内两个多边形边界上的点相对应的两个多边形生成元素之间的距离相等。 在一个多边形内，生成源和各边的距离一般不同，可以从小到大排序，其中有最小的，次小的表示其周围的生成源和其生成源的距离不同。 二、地理空间(二维)是v图的扩展定义，二维地理空间g由n个点、线、面实体集合g1、g2、gn构成，据说该地理空间是定义了尺度d的测量

3、空间。 设g是由n个实体构成的集合，定义g1，g2，gn G，gi的Voronoi区域V(gi )是到gi的距离最小点(网格)的集合V(gi)=p/d(p，gi)d(p，gj )，ij，j=1，2，n是g，则n个定义gn G g的Voronoi图V(G )在V(G)=V(g1)、V(g2)、V(gn )、(1)v图中定义，其中v图与距离密切相关，并且距离值基本上由尺度定义。 距离的概念根据比例而不同，数值也经常不同，所以v映射根据比例空间而不同。 上述定义也适用于三维。 (2)扩大广义的Voronoi图、广义的Voronoi图具有广泛的意义。 设g为n个实体的集合，g1、g2、gn G，各实体

4、具有权重ki，定义gi的Voronoi区域V(gi )是到gi的加权距离最小点(网格)的集合V(gi)=p/kid(p，gi)kj d(p，gj n是由n个实体组成的集合，定义设为g1、g2、gn G的g的Voronoi图V(G )与V(G)=V(g1 )、V(g2 )、V(gn )的一般v图特性类似于广义的v图。 5.2 V图的生成方法，v图具有以距离划分邻接区域的普遍特性，应用范围很广。 产生v图的方法有很多，大致分为向量方法的网格方法、产生v图的向量方法、产生向量方法的v图的点实体多这两种。 方法是，对偶生成法附加加法零件合成法，(1)对偶生成法，对偶生成法：主要在生成v图时老师成为对偶

5、元darane三角网，通过作成三角网三角形的每三条边的垂线，在每个三角形顶点形成作为生成源的多边形网。 对偶生成法生成v图，对偶生成法的关键是德洛尼三角网的生成。 delaunaytin的特性：三角形外接圆的内部包含其他点。三角形的均衡或三边均衡是其最小角最大的三角网的总边长最小的确定的n点，构建的Delaunay三角形网格是唯一的。 (2)通过加法、加法产生v图的基本思想是，假设在平面上存在n个点(产生源)，并且生成了Vn图，则现在增加了一个产生源Pn 1的情况下，产生新的Vn 1图。由于v映射的特性，添加新的生成元素仅涉及该新的生成元素所在的Voronoi多边形及其相邻的其他Voronoi

6、多边形的“半向”，而与这些多边形的“半向”无关，也不涉及其他生成元素的Voronoi多边形。 加法的基本步骤：最接近小区和相邻小区的最接近小区搜索具有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，只

7、改变与其相关的生成源的Voronoi多边形，其馀不动。 (3)部件合成法、部件合成法：将生成的元点集分割成几个子集，这些子集的和集合必须生成元点集，为了避免不必要的故障，这些子集相互的和集合尽可能小或空集合。 为这些子集产生子v图，合并这些子v图，修改其相互影响的Voronoi多边形，以获得完整生成的元点集的v图。 零件合成，以上三种方法常用于向量法，随着并行处理技术的发展，也出现了v图生成页面、并行算法，用使各生成源同时进行各点的v图计算的向量法生成v图的算法和数据结构很复杂，其生成源基于离散点集在实际的地理信息不够，应该扩展到点、线、面、体及其组合的复杂的体上的现在，向量法用离散点集代替线

8、性面来破坏空间实体的完整性，同时生成的v图必须经过复杂的识别和修复作业， 这还是要克服的困难，在光滑不光滑的组合曲线和对应的闭合区域中，可以用折线近似，但是，折线不是曲线，而是在曲线光滑的地方，所有的点都是拐点，变成折线，折线的交点成为唯一的拐点(4)基于向量法的v图的分析、二、产生v图的网格方法、以及产生v图的网格方法一般基于距离变换而产生。 关于v图生成网格方法，数学形态学距离变换法生成v图代数距离变换法生成v图，(1)数学形态学距离变换法在1998年武汉映射科学技术大学学报李有名的论文基于Voronoi图的空间关系判定和模型中有详细描述。 数学形态学的扩展算法。 (二)地图代数的v图生成

9、方法、地图代数的v图生成方法能够在一定的尺度空间内处理所有的点、线、面实体，该方法在理论上是严密的，算法简洁、高效、精密、实用化的技术。 该方法在三维和多维中也很容易普及。 自学。 5.3 V图的意思和应用，Voronoi多边形图从点集的生成扩展到点、线、面集的生成后，v图具有以下特性： (1)每个v多边形有一个生成要素(2)从各v多边形内点到该生成源的距离比其他生成源的距离短(3)。 从多边形边界上的点到生成该边界的生成源的距离相等(4)邻接图形的Voronoi多边形边界线将原来的邻接边界线作为子集。 另一方面，v图的特性，v图是空间邻近关系的客观、全面、正确的表现，v图显示了邻近的正确尺度。 相邻取决于空间比例，是几何关系，“相邻”是拓扑关系，两者不同。 复杂的连续函数插值在邻近点之间进行，v图显示了主影响元、邻近影响元，为优秀