《泰森多边形及其特征ppt课件.ppt》由会员分享，可在线阅读，更多相关《泰森多边形及其特征ppt课件.ppt（27页珍藏版）》请在三一办公上搜索。
1、1,第六章 空间关系（一）空间距离,67 缓冲区分析,61 空间物体的距离,63 基于栅格的欧氏距离变换,主要内容：,64 空间曲面上的距离计算,65 基于距离的分析,62 最短路径问题,66 泰森多边形分析,67 缓冲区分析,2,一、点点距离量算平面距离与角度| p1p2 | = Sqrt( (x1-x2)*(x1-x2) +(y1-y2)*(y1-y2) )二者夹角为：Sin(a) = (x2 - x1) / |P1P2 |Cos(a) = (y2 - y1) / |P1P2 |,61 空间物体的距离,距离：两个实体或事物之间的远近或亲疏程度。距离的定义由应用决定。,第六章 空间关系（一）
2、空间距离,3,空间直线距离空间两点P1(x1,y1,z1), P2(x2,y2,z2)距离为：|P1P2| = Sqrt(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1- z2)*(z1-z2)球面距离在航海与航空中，其作业范围较大，因此常常用到球面上的最短距离。给定球面上两点，A(1, 1),B(2, 2), 距离为：Cos(S) = sin1sin2 + cos1cos2cos(2 - 1)S = arccossin12 + cos1cos2cos(2 - 1) L = RS / 180,4,二、点线距离量算,点/线段最短距离获取点所在地位置区域，然后计算点与直线距离
3、。点/线段垂直距离给定直线方程L：ax + by + c = 0, 则点p(x,y)与直线距离为:D |ax + by + c | / sqrt(a*a+b*b)点/线段的平均距离点到线段两个端点距离的平均值。点/线段最大距离点到线段两个端点中距离最大者。,5,三 点面距离量算点/面最短距离指点与所有构成面中的边的最短距离。点/面最大距离指点与所有构成面中的边的最大距离。点/面的中心距离定义A中一特定点P0（例如形心或重心），以P,P0间的距离表示P与A间的距离。,P,P,P,中心距离,最小距离,最大距离,如森林防火中，任何火源（点）距森林（面）的距离必须大于一个安全临界值（最小距离）。在无线
4、电覆盖范围分析中，为了保证信号被给定区域内的任意点所接受，则必须使用最大距离。,6,四、线与线的距离,两个线状物体L1，L2间的距离可以定义为L1中点P1与L2中点P2之间的距离的极小值。L1，L2之间距离的计算如图所示。,线/线最短、最大距离相交线段之间距离为0，否则计算两条线段中所有节点到对应边上的最短（最大）距离，即为两线段之间最短（最大）距离。,7,计算两条曲线之间的距离所需的计算量大，需通过适当的数据组织减少数据量。如:1）避免重复点对连线间距离的计算。2）采用计算简单的预探测。,8,类似于点面间距离，可以定义中心距离、极小距离和极大距离。,五、线与面的距离,仿照线状物体间距离的定义
5、和计算方法，因为面状物体也是以折线序列表示的。,中心距离,极小距离,极大距离,面状物体间的极大距离归结为折线段对间距离的计算，但：d12=max(ac,ad,bc,bd),9,62 最短路径问题,一、推销员问题定义对于给定一个平面初始集，给定一个起始点和终止点，寻找一条路径，该路径通过所有数据点且每个数据点只通过一次，同时位于这两个起始点和终止点间的路径的长度最短。推销员要不重复地经过所有的推销点，且又要使所走的路程最短。例子：对不规则的空间分布，建立基于点集的Y坐标的一个路径。建立初始集根据Y序，将排列其后的点插入到初始集中，原则：插入后路径增加的长度为最小迭代，遵循同样的插入原则。,10,
6、62 最短路径问题,第一步：P11,P4第二步：P9,P11,P4,插入原则：插入后路径增加的长度为最小以此类推,11,62 最短路径问题,二、基于网络的距离图论的基本概念网络上最短路径问题的基础是图论,12,62 最短路径问题,最短路径问题的提法找出两个给定顶点X,Y之间的最短路径找出从顶点X0到G中其他全部顶点的最短路径找出所有顶点对之间的最短路径,13,62 最短路径问题,算法一第二种提法的解开始，Xx0,然后每一步向X中加入一个顶点，加入x的条件是已知从x0到x的最短路径的路程，以及在这个路程中位于x之前的顶点。当所有从x0可达的顶点都加入到X中时，运算结束。,14,62 最短路径问题
7、,算法一第二种提法的解第一步：初始化X=X0=V1M=V2,V3,V4,V5,V6DIS=0,10,3,0,6, ,PRED=1,1,1,1,1,1第二步：在M中，V1到V3的路程最近，故X=X+V3=V1,V3M=M-V3=V2,V4,V5,V6DIS=0,7,3,0,5, ,PRED=1,3,1,1,3,1,15,62 最短路径问题,第三步：在M中，V1到V5的路程最近X=X+V5=V1,V3,V5M=M-V5=V2,V4,V6DIS=0,5,3,0,5, 6,PRED=1,3,1,1,3,1第四步：在M中，V1到V2的路程最近X=X+V2=V1,V3,V5,V2M=M-V6=V4,V6D
8、IS=0,5,3,5, 6,PRED=1,5,1,1,3,5第五步：在M中，V1到V6的路程比V1到V4的路程近X=X+V6=V1,V3,V5,V2,V6M=M-V6=V4DIS=0,5,3,5, 6,PRED=1,5,1,1,3,5第六步：仅剩V4,计算结束PREDi=j:从x0到Vi的最短路径经过Vj，且Vj是此路径上Vi的前一个顶点。PRED6=5; PRED5=3; PRED3=1;,16,62 最短路径问题,算法二第三种提法的解Floyd算法：弗洛伊德（R. W Floyd）提出了另一种算法，这种算法仍用邻接矩阵A表示带权有向图。如果从Vi到Vj有弧，则从Vi到Vj存在一条长度为Ai
9、，j的路径，该路径不一定是最短路径，需要进行n次试探。,17,63 基于栅格数据的欧氏距离变换,栅格数据的表示表示为一个01矩阵，经过距离变换，对每一个“0”元素，我们获得其与最近的“1”元素之间的距离值，即背景元素与空间物体的最小距离。两个相异元素间的距离距离变换算法初始化计算aij，bij的值对P（i，j）中任一“0”元素，其距离为dij（aij2bij2）1/2,18,64 空间曲面上的距离计算,基本思想将曲面体上的距离计算转换为网络距离的计算。转换方法将高程点与相邻的8个邻点用边相连，并给每条边赋予相应的曲面距离值。中心点导到某给定点的距离值与其相邻点的距离值以及相应的边值有关。x0
10、xieimin（x1e1,x2+e2,x8+e8）,19,64 空间曲面上的距离计算,距离计算方法对规则格网点矩阵，根据格网大小和高程计算格网点与8个相邻点的曲面距离。对所有格网点，赋予距离初值，作为距离起算点的格网点赋予0，其余点赋予一个足够大的距离值。对所有格网点，按下式计算。X0min（x1+e1,x2+e2,x8+e8） X0=min(x0,x0)重复上步直至所有格网点距离值在上步的计算中保持不变。,20,64 空间曲面上的距离计算,确定相应的路径xi=xj+eij,则格网点j必位于格网点i的最短路径上，且位于i点之前，如此循环直至起算点，就确定了相应的路径。,21,65 基于距离的分
11、析,【问题1】对于平面上的n个点，确定这样一个点位，使该点到所有点的距离之和为极小。【问题2】对于平面上的n个点，确定这样一个点位，使该点到所有点的距离的最大值尽可能小。【问题3】对于有n个顶点的连通图，其任意两顶点之间均是可达的，设定一点，其到所有顶点的最短路程之和达极小。【问题4】对于有n个顶点的连通图，其任意两顶点之间均是可达的，设定一点，其到所有顶点的最短路程的最大值达极小，亦即该点到所有顶点的路程都不致过远。【问题5】已知平面上相异的n个点的集合P，根据距离大小确定各点Pi的邻域，保证Pi邻域中的点距Pi的距离小于任何其他已知点【问题6】给定任一空间物体，计算空间物体的邻域，保证邻域
12、中任意一点到该物体得的距离小于等于给定值。,22,65 基于距离的分析,一、最小支撑树生成树是图的极小连通子图。一个连通的赋权图G可能有很多的生成树。设T为图G的一个生成树，若把T中各边的权数相加，则这个和数称为生成树T的权数。在G的所有生成树中，权数最小的生成树称为G的最小生成树。在实际应用中，常有类似在n个城市间建立通信线路这样的问题。这可用图来表示，图的顶点表示城市，边表示两城市间的线路，边上所赋的权值表示代价。对n个顶点的图可以建立许多生成树，每一棵树可以是一个通信网。若要使通信网的造价最低，就需要构造图的最小生成树,23,65 基于距离的分析,算法先把图G中的各边按权数从小到大重新排
13、列，并取权数最小的一条边为T中的边。在剩下的边中，按顺序取下一条边。若该边与T中已有的边构成回路，则舍去该边，否则选进T 中重复（2），直到有m-1条边被选进T中，这m-1条边就是G的最小生成树。例子,24,65 基于距离的分析,赋权图,最小支撑树,25,一、 泰森多边形及其特征荷兰气候学家A.H.Thiessen提出的一种根据离散分布的气象站的降雨量来计算平均降雨量的方法。将所有气象站，连接成三角形，作各个三角形的中垂线，围成一个多边形，用这个多边形内的唯一气象站来表示这个区域的降雨量，称该多边形为泰森多边形。特征：泰森多边形内的点到相应的离散点的距离最近；每个泰森多边形内仅有一个离散点数据
14、；泰森多边形边上的点到其他两边的离散点的距离相等。构造泰森多边形，首先要构造Delaunay三角网。,66 泰森多边形分析,26,二、Delaunay三角网的构建,Delaunay三角网的准则：任何一个Delaunay三角网的外接圆不能包含任何其他离散点；相邻两个Delaunay三角形构成凸四边形，在交换凸四边形的对角线之后，六个内角的最小角不再增大，该性质即为最小角最大准则。,Delaunay三角网的构建也称为不规则三角网的构建，就是由离散数据点构建三角网，如下图，即确定哪三个数据点构成一个三角形，也称为自动联接三角网。即对于平面上n个离散点，其平面坐标为(xi，yi)，i1，2，n，将其中相近的三点构成最佳三角形，使每个离散点都成为三角形的顶点。,27,三、泰森多边形的生成,基本步骤：离散点构造三角网，即构建Delaunay三角网；找出每个离散点相邻的所有三角形的编号；对与离散点相邻的三角形按顺时针或逆时针排列，以便连接成泰森多边形；计算每个三角形的外接圆圆心，并记录下来；根据三角形的顺序，连接所有外接圆圆心。,原始点位,Delaunay三角网,生成泰森多边形,
