泰森多边形及其特征课件

1第六章空间关系（一）——空间距离§6－7缓冲区分析§6－1空间物体的距离§6－3基于栅格的欧氏距离变换主要内容：§6－4空间曲面上的距离计算§6－5基于距离的分析§6－2最短路径问题§6－6泰森多边形分析§6－7缓冲区分析1第六章空间关系（一）——空间距离§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空间物体的距离距离：两个实体或事物之间的远近或亲疏程度。距离的定义由应用决定。第六章空间关系（一）——空间距离2一、点－点距离量算§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

1sin2+cos1cos2cos(2-1)S=arccos[sin1

2+cos1cos2cos(2-1)]L=RS/1803空间直线距离4二、点－线距离量算

点/线段最短距离获取点所在地位置区域，然后计算点与直线距离。点/线段垂直距离给定直线方程L：ax+by+c=0,则点p(x,y)与直线距离为:D＝|ax+by+c|/sqrt(a*a+b*b)点/线段的平均距离点到线段两个端点距离的平均值。点/线段最大距离点到线段两个端点中距离最大者。4二、点－线距离量算

5三点—面距离量算点/面最短距离指点与所有构成面中的边的最短距离。点/面最大距离指点与所有构成面中的边的最大距离。点/面的中心距离定义A中一特定点P0（例如形心或重心），以P,P0间的距离表示P与A间的距离。PPP中心距离最小距离最大距离如森林防火中，任何火源（点）距森林（面）的距离必须大于一个安全临界值（最小距离）。在无线电覆盖范围分析中，为了保证信号被给定区域内的任意点所接受，则必须使用最大距离。5三点—面距离量算PPP中心距离最小距离最大距离如森林防火6四、线与线的距离两个线状物体L1，L2间的距离可以定义为L1中点P1与L2中点P2之间的距离的极小值。L1，L2之间距离的计算如图所示。线/线最短、最大距离相交线段之间距离为0，否则计算两条线段中所有节点到对应边上的最短（最大）距离，即为两线段之间最短（最大）距离。6四、线与线的距离两个线状物体L1，L2间的距离可以定义为L7计算两条曲线之间的距离所需的计算量大，需通过适当的数据组织减少数据量。如:1）避免重复点对连线间距离的计算。2）采用计算简单的预探测。7计算两条曲线之间的距离所需的计算量大，需通过适当的数据组织8类似于点面间距离，可以定义中心距离、极小距离和极大距离。五、线与面的距离

仿照线状物体间距离的定义和计算方法，因为面状物体也是以折线序列表示的。中心距离极小距离极大距离面状物体间的极大距离归结为折线段对间距离的计算，但：d12=max(ac,ad,bc,bd)L1L2acbd8类似于点面间距离，可以定义中心距离、极小距离和极大距离。五9§6－2最短路径问题一、推销员问题定义对于给定一个平面初始集，给定一个起始点和终止点，寻找一条路径，该路径通过所有数据点且每个数据点只通过一次，同时位于这两个起始点和终止点间的路径的长度最短。推销员要不重复地经过所有的推销点，且又要使所走的路程最短。例子：对不规则的空间分布，建立基于点集的Y坐标的一个路径。建立初始集根据Y序，将排列其后的点插入到初始集中，原则：插入后路径增加的长度为最小迭代，遵循同样的插入原则。9§6－2最短路径问题一、推销员问题10§6－2最短路径问题第一步：{P11,P4}第二步：{P9,P11,P4},插入原则：插入后路径增加的长度为最小以此类推10§6－2最短路径问题11§6－2最短路径问题二、基于网络的距离图论的基本概念网络上最短路径问题的基础是图论11§6－2最短路径问题二、基于网络的距离12§6－2最短路径问题最短路径问题的提法找出两个给定顶点X,Y之间的最短路径找出从顶点X0到G中其他全部顶点的最短路径找出所有顶点对之间的最短路径12§6－2最短路径问题最短路径问题的提法13§6－2最短路径问题算法一——第二种提法的解开始，X＝{x0},然后每一步向X中加入一个顶点，加入x的条件是已知从x0到x的最短路径的路程，以及在这个路程中位于x之前的顶点。当所有从x0可达的顶点都加入到X中时，运算结束。13§6－2最短路径问题算法一——第二种提法的解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}14§6－2最短路径问题算法一——第二种提法的解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;15§6－2最短路径问题第三步：在M中，V1到V5的路程最16§6－2最短路径问题算法二——第三种提法的解Floyd算法：弗洛伊德（R.WFloyd）提出了另一种算法，这种算法仍用邻接矩阵A表示带权有向图。如果从Vi到Vj有弧，则从Vi到Vj存在一条长度为A[i，j]的路径，该路径不一定是最短路径，需要进行n次试探。

16§6－2最短路径问题算法二——第三种提法的解17§6－3基于栅格数据的欧氏距离变换栅格数据的表示表示为一个0－1矩阵，经过距离变换，对每一个“0”元素，我们获得其与最近的“1”元素之间的距离值，即背景元素与空间物体的最小距离。两个相异元素间的距离距离变换算法初始化计算aij，bij的值对P（i，j）中任一“0”元素，其距离为dij＝（aij2＋bij2）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)17§6－3基于栅格数据的欧氏距离变换栅格数据的表示(i18§6－4空间曲面上的距离计算基本思想将曲面体上的距离计算转换为网络距离的计算。转换方法将高程点与相邻的8个邻点用边相连，并给每条边赋予相应的曲面距离值。中心点导到某给定点的距离值与其相邻点的距离值以及相应的边值有关。x0＝xi＋ei＝min（x1＋e1,x2+e2,…x8+e8）18§6－4空间曲面上的距离计算基本思想19§6－4空间曲面上的距离计算距离计算方法对规则格网点矩阵，根据格网大小和高程计算格网点与8个相邻点的曲面距离。对所有格网点，赋予距离初值，作为距离起算点的格网点赋予0，其余点赋予一个足够大的距离值。对所有格网点，按下式计算。X0’＝min（x1+e1,x2+e2,…,x8+e8）

X0=min(x0,x0’)重复上步直至所有格网点距离值在上步的计算中保持不变。19§6－4空间曲面上的距离计算距离计算方法20§6－4空间曲面上的距离计算确定相应的路径xi=xj+eij,则格网点j必位于格网点i的最短路径上，且位于i点之前，如此循环直至起算点，就确定了相应的路径。20§6－4空间曲面上的距离计算确定相应的路径21§6－5基于距离的分析【问题1】对于平面上的n个点，确定这样一个点位，使该点到所有点的距离之和为极小。【问题2】对于平面上的n个点，确定这样一个点位，使该点到所有点的距离的最大值尽可能小。【问题3】对于有n个顶点的连通图，其任意两顶点之间均是可达的，设定一点，其到所有顶点的最短路程之和达极小。【问题4】对于有n个顶点的连通图，其任意两顶点之间均是可达的，设定一点，其到所有顶点的最短路程的最大值达极小，亦即该点到所有顶点的路程都不致过远。【问题5】已知平面上相异的n个点的集合P，根据距离大小确定各点Pi的邻域，保证Pi邻域中的点距Pi的距离小于任何其他已知点【问题6】给定任一空间物体，计算空间物体的邻域，保证邻域中任意一点到该物体得的距离小于等于给定值。21§6－5基于距离的分析【问题1】对于平面上的n个点，22§6－5基于距离的分析一、最小支撑树

生成树是图的极小连通子图。一个连通的赋权图G可能有很多的生成树。设T为图G的一个生成树，若把T中各边的权数相加，则这个和数称为生成树T的权数。在G的所有生成树中，权数最小的生成树称为G的最小生成树。

在实际应用中，常有类似在n个城市间建立通信线路这样的问题。这可用图来表示，图的顶点表示城市，边表示两城市间的线路，边上所赋的权值表示代价。对n个顶点的图可以建立许多生成树，每一棵树可以是一个通信网。若要使通信网的造价最低，就需要构造图的最小生成树22§6－5基于距离的分析一、最小支撑树23§6－5基于距离的分析算法先把图G中的各边按权数从小到大重新排列，并取权数最小的一条边为T中的边。在剩下的边中，按顺序取下一条边。若该边与T中已有的边构成回路，则舍去该边，否则选进T中重复（2），直到有m-1条边被选进T中，这m-1条边就是G的最小生成树。例子23§6－5基于距离的分析算法24§6－5基于距离的分析赋权图最小支撑树24§6－5基于距离的分析赋权图最小支撑树25一、泰森多边形及其特征荷兰气候学家A.H.Thiessen提出的一种根据离散分布的气象站的降雨量来计算平均降雨量的方法。将所有气象站，连接成三角形，作各个三角形的中垂线，围成一个多边形，用这个多边形内的唯一气象站来表示这个区域的降雨量，称该多边形为泰森多边形。特征：泰森多边形内的点到相应的离散点的距离最近；每个泰森多边形内仅有一个离散点数据；泰森多边形边上的点到其他两边的离散点的距离相等。构造泰森多