空间关系(一)——空间距离

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,武汉大学,资源与环境科学学院,空间分析,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,第六章 空间关系（一）,空间距离,6,7,缓冲区分析,6,1,空间物体的距离,6,3,基于栅格的欧氏距离变换,主要内容：,6,4,空间曲面上的距离计算,6,5,基于距离的分析,6,2,最短路径问题,6,6,泰森多边形分析,6,7,缓冲区分析,2,一、点点距离量算,平面距离与角度,|,p,1,p,2,|=Sqrt(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2),二者夹角为：,Sin(,a,)=(x,2,-x,1,)/|,P,1,P,2,|,Cos(a)=(y,2,-y,1,)/|,P,1,P,2,|,6,1,空间物体的距离,距离：两个实体或事物之间的远近或亲疏程度。距离的定义由应用决定。,第六章 空间关系（一）,空间距离,3,空间直线距离,空间两点,P,1,(,x,1,y,1,z,1,),P,2,(,x,2,y,2,z,2,),距离为：,|,P,1,P,2,|=Sqrt(,x,1,-,x,2,)*(,x,1,-x,2,)+(,y,1,-y,2,)*(,y,1,-y,2,)+(,z1,-,z,2,)*(,z,1,-z,2,),球面距离,在航海与航空中，其作业范围较大，因此常常用到球面上的最短距离。,给定球面上两点，,A(,1,1,),B(,2,2,),距离为：,Cos(S)=sin,1,sin,2,+cos,1,cos,2,cos(,2,-,1,),S=arccossin,1,2,+cos,1,cos,2,cos(,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,间的距离。,P,P,P,中心距离,最小距离,最大距离,如森林防火中，任何火源（点）距森林（面）的距离必须大于一个安全临界值（,最小距离,）。,在无线电覆盖范围分析中，为了保证信号被给定区域内的任意点所接受，则必须使用最大距离。,6,四、线与线的距离,两个线状物体,L1,，,L2,间的距离可以定义为,L1,中点,P1,与,L2,中点,P2,之间的距离的极小值。,L1,，,L2,之间距离的计算如图所示。,线,/,线最短、最大距离,相交线段之间距离为,0,，否则计算两条线段中所有节点到对应边上的最短（最大）距离，即为两线段之间最短（最大）距离。,7,计算两条曲线之间的距离所需的计算量大，需通过适当的数据组织减少数据量。如,:,1,）避免重复点对连线间距离的计算。,2,）采用计算简单的预探测。,8,类似于点面间距离，可以定义,中心,距离、,极小,距离和,极大,距离。,五、线与面的距离,仿照线状物体间距离的定义和计算方法，因为面状物体也是以折线序列表示的。,中心,距离,极小,距离,极大,距离,面状物体间的极大距离归结为折线段对间距离的计算，但：,d12=max(ac,ad,bc,bd),L1,L2,a,c,b,d,9,6,2,最短路径问题,一、推销员问题,定义,对于给定一个平面初始集，给定一个起始点和终止点，寻找一条路径，该路径通过所有数据点且每个数据点只通过一次，同时位于这两个起始点和终止点间的路径的长度最短。推销员要不重复地经过所有的推销点，且又要使所走的路程最短。,例子：,对不规则的空间分布，建立基于点集的,Y,坐标的一个路径。,建立初始集,根据,Y,序，将排列其后的点插入到初始集中，原则：插入后路径增加的长度为最小,迭代，遵循同样的插入原则。,10,6,2,最短路径问题,第一步：,P,11,P,4,第二步：,P,9,P,11,P,4,插入原则：插入后路径增加的长度为最小,以此类推,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,计算结束,PREDi=j:,从,x0,到,Vi,的最短路径经过,Vj,，且,Vj,是此路径上,Vi,的前一个顶点。,PRED6=5;PRED5=3;PRED3=1;,16,6,2,最短路径问题,算法二,第三种提法的解,Floyd,算法：,弗洛伊德（,R.W Floyd,）提出了另一种算法，这种算法仍用,邻接矩阵,A,表示带权有向图,。如果从,Vi,到,Vj,有弧，则从,Vi,到,Vj,存在一条长度为,Ai,，,j,的路径，该路径不一定是最短路径，需要进行,n,次试探。,17,6,3,基于栅格数据的欧氏距离变换,栅格数据的表示,表示为一个,0,1,矩阵，经过距离变换，对每一个“,0”,元素，我们获得其与最近的“,1”,元素之间的距离值，即背景元素与空间物体的最小距离。,两个相异元素间的距离,距离变换算法,初始化,计算,aij,，,bij,的值,对,P,（,i,，,j,）中任一“,0”,元素，其距离为,d,ij,（,aij,2,bij,2,）,1/2,(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,个邻点用边相连，并给每条边赋予相应的曲面距离值。中心点导到某给定点的距离值与其相邻点的距离值以及相应的边值有关。,x,0,x,i,e,i,min,（,x,1,e,1,x,2,+e,2,x,8,+e,8,）,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,个离散点，其平面坐标为,(x,i,，,y,i,),，,i,1,，,2,，,，,n,，将其中相近的三点构成最佳三角形，使每个离散点都成为三角形的顶点。,27,三、泰森多边形的生成,基本步骤：,离散点构造三角网，即构建,Delaunay,三角网；,找出每个离散点相邻的所有三角形的编号；,对与离散点相邻的三角形