空间数据的研讨.ppt

例子(思路) 第二步，我们把与v2直接连通的点v3考虑进来。 dis[0][5]=100; dis[0][4]=30; dis[0][2]=10; dis[0][3]=60; 除10以外，30是最小的。 我们可以证明30是v0到其它顶点除10以外最小的。 V5 V0 V4 V3 V2 100 30 10 50 例子(思路) 不可能存在这样一个点Vn，使得 10mindistance[0][n]30. 原因如前所述。 V5 V0 V4 V3 V2 100 30 10 50 Vn Bi 例子(思路) 这样我们得到我们的第二个最小距离： Mindistance[v0][v4]=mindist[1]=30 ,(v0-v4) 接下来，我们把v4与之直接连通的点考虑进来。。。 V5 V0 V4 V3 V2 100 30 10 50 Bi 例子 以v0为起点，计算它到其它各顶点的最短路径，计算过程中最短路径长度向量D的变化见D0-D4，计算出的各条最短路径见表4-4。 例子 终点 从v0到其它各结点的最短路径 v1 ∞ ∞ ∞ ∞ ∞ v2 10 (v0, v2) v3 ∞ 60 (v0, v2,v3) 50 (v0, v4,v3) v4 30 (v0, v4) 30 (v0, v4) v5 100 (v0, v5) 100 (v0, v5) 90 (v0, v4,v5) 60 (v0, v4,v3,v5) vj v2 v4 v3 v5 例子 起点 终点 最短路径 路径长度 v0 v1 无 ? ? v2 (v0,v2) 10 ? v3 (v0,v4,v3) 50 ? v4 (v0,v4) 30 ? v5 (v0,v4,v3,v5) 60 7.9 空间分析模型与空间决策支持 * * 空间分析与应用模型的关系 空间分析 应用模型 空间分析是基本的、解决一般问题的理论和方法，而一般应用模型是不可枚举的，是复合、复杂的，解决专门问题的理论和方法，它的解决应以空间分析的基本方法和算法模型为基础。（局部与整体的关系） * 空间分析模型是指用于GIS空间分析的数学模型，是在GIS空间数据基础上建立起来的模型，是通过作用于原始数据和派生数据的一组顺序的、交互的空间分析操作命令，对一个空间决策过程进行的模拟。 * 一、网络图论基础 1.网络图：由一些点及点之间的线段所组成的图形。这些图形与地图，与各种函数图形有较大的区别。 * * 2.路与回路 图中的一条路，就是由图中的一个定点、一条边，再一个定点、一条边……排列而成，而且要求排在它前面的定点和排在它后面的定点都是它的端点。对于有向路来说，要求排在每一条边之前和之后的顶点分别是这条边的起点和终点。 * * v1 v2 v3 v4 v5 v6 v7 v8 v9 e1 e2 e3 e4 e5 e6 e7 e8 e9 3.连通性： * 连通 无向图 不连通 连通 有向图 不连通 强连 通性 * v1 v2 v3 v4 v5 e1 e2 e3 e4 v1 v2 v3 e1 e2 v4 v5 e3 v1 v2 v3 v4 v5 e1 e2 e3 v1 v2 v3 v4 v5 (1) (2) 二、网络分析的应用 1.服务点的最优区位问题 2.最小生成树 3.最短路径分析 * 1.服务点的最优区位问题： 在城市管理中，利用GIS技术确定服务点的最优区位问题十分重要，如确定幼儿园、商场、消防队、医院等的最优位置，以达到服务、资源的最优配置。 * 算法A 设G是一个有 n个顶点，即V={v1,v2,…vn}, m条边,即E={e1,e2,…en},的无向连通图， 那么对于每一个顶点vi，它与各顶点间的最短路径的长度为 di1,di2,…din， 上式中，最大数称为顶点vi的最大服务距离，用e(vi)表示。 为了得到服务点的最优区位，需要解决如下问题，即求出一个点vio，使得e (vio)具有最小的值。 * 0 3 6 3 6 4 3 0 3 4 5 7 6 3 0 3 2 4 3 4 3 0 5 7 6 5 2 5 0 2 4 7 4 7 2 0 * v1 v2 v3 v4 v5 v6 3 3 4 4 3 3 2 2 1）计算G的距离表 2）计算每一行的最大值，得 e(v1)=6, e(v2)=7, e(v3)=6, e(v4)=7, e(v5)=6, e(v6)=7; 3）求得min[e(vi)]=6, 从而，定出v1,v3,v5均是G的中心。 * 算法B 设G是一个有 n个顶点，即V={v1,v2,…vn}