泰森多边形及其特征

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