泰森多边形及其特征课件.ppt

《泰森多边形及其特征课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章空间关系（一）——空间距离§6－7缓冲区分析§6－1空间物体的距离§6－3基于栅格的欧氏距离变换主要内容：§6－4空间曲面上的距离计算§6－5基于距离的分析§6－2最短路径问题§6－6泰森多边形分析§6－7缓冲区分析1一、点－点距离量算平面距离与角度

2、p1p2

3、=Sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))二者夹角为：Sin(a)=(x2-x1)/

4、P1P2

5、Cos(a)=(y2-y1)/

6、P1P2

7、§6－1空间物体的距离距离：两个实体或事物之间的远近或亲疏程度。距离的定义由应用决定。第六章空间关系（一

8、）——空间距离2空间直线距离空间两点P1(x1,y1,z1),P2(x2,y2,z2)距离为：

9、P1P2

10、=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/1803二、点－线距离量算点/线段最

11、短距离获取点所在地位置区域，然后计算点与直线距离。点/线段垂直距离给定直线方程L：ax+by+c=0,则点p(x,y)与直线距离为:D＝

12、ax+by+c

13、/sqrt(a*a+b*b)点/线段的平均距离点到线段两个端点距离的平均值。点/线段最大距离点到线段两个端点中距离最大者。4三点—面距离量算点/面最短距离指点与所有构成面中的边的最短距离。点/面最大距离指点与所有构成面中的边的最大距离。点/面的中心距离定义A中一特定点P0（例如形心或重心），以P,P0间的距离表示P与A间的距离。PPP中心距离最小距离最大距离如森林防火中，任何火源（点）距

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

15、似于点面间距离，可以定义中心距离、极小距离和极大距离。五、线与面的距离仿照线状物体间距离的定义和计算方法，因为面状物体也是以折线序列表示的。中心距离极小距离极大距离面状物体间的极大距离归结为折线段对间距离的计算，但：d12=max(ac,ad,bc,bd)L1L2acbd8§6－2最短路径问题一、推销员问题定义对于给定一个平面初始集，给定一个起始点和终止点，寻找一条路径，该路径通过所有数据点且每个数据点只通过一次，同时位于这两个起始点和终止点间的路径的长度最短。推销员要不重复地经过所有的推销点，且又要使所走的路程最短。例子：对不规则的空间

16、分布，建立基于点集的Y坐标的一个路径。建立初始集根据Y序，将排列其后的点插入到初始集中，原则：插入后路径增加的长度为最小迭代，遵循同样的插入原则。9§6－2最短路径问题第一步：{P11,P4}第二步：{P9,P11,P4},插入原则：插入后路径增加的长度为最小以此类推10§6－2最短路径问题二、基于网络的距离图论的基本概念网络上最短路径问题的基础是图论11§6－2最短路径问题最短路径问题的提法找出两个给定顶点X,Y之间的最短路径找出从顶点X0到G中其他全部顶点的最短路径找出所有顶点对之间的最短路径12§6－2最短路径问题算法一——第二种提

17、法的解开始，X＝{x0},然后每一步向X中加入一个顶点，加入x的条件是已知从x0到x的最短路径的路程，以及在这个路程中位于x之前的顶点。当所有从x0可达的顶点都加入到X中时，运算结束。13§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

18、,3,1,1,3,1}14§6－2最短路径问题第三步：在M中，V1到V5的路程最近X=X+V5={V1,V3,V5}M=M-V5={V2,V4,V6}DIS={0,5,3,0,,5,6,}P