GIS算法原理知识点总结(共33页).docx

《GIS算法原理知识点总结(共33页).docx》由会员分享，可在线阅读，更多相关《GIS算法原理知识点总结(共33页).docx（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上GIS算法原理知识点总结算法设计和分析：1、算法设计的原则：正确性：若一个算法本身有缺陷，那么它将不会解决问题；确定性：指每个步骤必须含义明确，对每种可能性都有确定的操作。清晰性：一个良好的算法，必须思路清晰，结构合理。2、算法的复杂性包括：时间复杂性和空间复杂性。3、时间复杂性：用一个与问题相关的整数量来衡量问题的大小，该整数量表示输入数据量的尺度，称为问题的规模。利用某算法处理一个问题规模为n的输入所需要的时间，称为该算法的时间复杂性。4、算法的概念：算法是完成特定任务的有限指令集。所有的算法必须满足下面的标准：u 输入u 输出u 明确性u 有限性u 有效性GIS

2、算法的计算几何基础O1、理解矢量的概念：如果一条线段的端点是有次序之分的,我们把这种线段称为有向线段(directed segment)。如果有向线段p1p2的起点P1在坐标原点，我们可以把它称为矢量P2。p2p15.矢量叉积：计算矢量叉积是直线和线段相关算法的核心部分。设矢量P = （x1,y1），Q = （x2,y2）,则矢量叉积定义为（0,0）、p1、p2和p1p2 所组成的平行四边形的带符号的面积，即PQ = x1y2-x2y1，其结果是个标量。显然有性质PQ= -（QP）和P-Q= -（PQ）。P X Q0,则P在Q的顺时针方向；P X Q0,则P Q共线，但可能同向也可能反向。6、

3、判断线段的拐向：折线段的拐向判断方法，可以直接由矢量叉积的性质推出，对于有公共端点的线段p0p1和P1P2，通过计算（p2-p0）(P1-p0)的符号便可以给出折线段的拐向。p2p2p2p1p1p1p0p0p0基（p2-p0）(P1-p0)0，则P0P1在P1点拐向右侧后得到P1P2基（p2-p0）(P1-p0)=0，则P0P1P2三点共线基（p2-p0）(P1-p0)0，则P0P1在P1点拐向左侧后得到P1P2理解矢量的概念通过矢量差积的方法就可以判断的拐向了。7.判断点是否在线段上：设点为Q，线段为P1 P2：(Q-P1)X(P2-P1)=0且Q在以P1，P2为对角顶点的矩形内。前者抱走点

4、在直线上，后者保证点不在线段延长线或反向延长线上。8、判断两线段是否相交（算法一）：快速排斥实验：设以线段P1P2为对角线的矩形为R，设以线段Q1Q2为对角的矩形为T，如果R和T不相交，显然两线段不会相交跨立实验： 如果两线段相交，则两线段必然相互跨立对方。若p1p2跨立Q1Q2，则矢量（P1-Q1）和（P2-Q2）位于矢量（Q2-Q1）的两侧，则（P1-Q1）（Q2-Q1） （P2-Q1） （Q2-Q1）0。当（P1-Q1）（Q2-Q1）=0时，说明 （P1-Q1）（Q2-Q1）共线，但是因为已经通过快速排斥实验，所以P1一定在线段Q1Q2上；同理 （Q2-Q1） （P2-Q1） =0说明P

5、2一定在线段Q1Q2上。所以判断P1P2跨立Q1Q2的依据是：（P1-Q1）（Q2-Q1） （Q2-Q1） （P2-Q1 0。同理判断Q1Q2跨立P1P2的依据是（Q1-P1）（P2-P1） （P2-P1） （Q2-P1）0。注意在进行“跨立判断”的时候是进行两次跨立判断9.判断矩形内是否包含点：只要判断该店的横坐标和纵坐标是否都夹在矩形的左右边和上下边之间。10.判断线段、折线、多边形是否在矩形中：因为矩形是个凸集，所以只要判断所有端点都在矩形就行了。11.判断矩形是否在矩形中：只要比较左右边界和上下边界就行了。12.判断圆是否在矩形中：圆心在矩形中且圆的半径小于或等于圆心到矩形四边的距离的

6、最小值。13.判断点是否在多边形内： 1)射线法：一条射线从点P开始，穿过多边形的边界的次数称为交点数目。当交点数目是偶数时，点P在多边形外部；否则，为奇数时，在多边形内部。射线法要考虑几种特殊的情况，并且射线法适用于凸多边形2)转角法：多边形环绕点P的次数称为环绕数，环绕数为0时，点P在多边形外部，否则在多边形内部。14.判断线段是否在多边形内：（折线是判断它的每条线段）条件一：线段的两个端点都在多边形内条件二：线段和多边形的所有边都不内交。15.判断多边形否在多边形内：只要判断多边形的每条边是否都在多边形内即可。判断有m个顶点的多边形是否在一个有n个顶点的多边形内的复杂度为O(mXn)16

7、.判断矩形是否在多边形内：将矩形转化为多边形，然后再判断是否在多边形内。17.判断圆是否在多边形内：计算圆心到多边形每条变边的最短距离，若该距离大于或等于圆半径，则该圆在多边形内。18.判断点是否在圆内：计算圆心到该点的距离，若小于或等于半径，则该点在圆内。19.判断线段、折线、矩形、多边形是否在圆内：因为圆是凸集，所以只要判断是否每个顶点都在圆内即可。20.判断圆是否在圆内：设两圆为O1,O2,半径为r1,r2。先比较r1,r2的大小，若r1矢转换为拓扑转换，即保持实体原有的连通性、邻接性等；2） 转换实体保持正确的外形。（二）方法方法一，实际应用中大多数采用人工矢量化法，如扫描矢量化，该法

8、工作量大，成为GIS数据输入、更新的瓶颈问题之一。方法二，程序转化转换（全自动或半自动）过程为：1、边界提取2、二值化 3、二值图像的预处理4、细化:1）剥皮法 2)骨架法5、跟踪 6、拓扑化 6.”矢量点”转栅格实例：6.矢量数据的压缩：矢量数据的压缩包括两个方面的内容，一是在不扰乱拓扑关系的前提下，对采样点数据进行合理的抽稀。二是对矢量坐标数据重新进行编码，以减少所需要的存储空间。1）间隔取点法：每隔K个点取一点，或舍去那些比规定距离更近的点，首末点一定要保留。临界值 隔点法临界值法2）垂距法：原始曲线对点2测试距离大于规定的限差点2保留对点3测试距离小于规定的限差234234234234

9、141113点舍去，化简结果14限差23）光栅法：d/2c1c2b2b1p1P4P3P2a1a2d/2Pn光栏法的基本思想是(上图)：定义一个扇形区域，通过判断曲线上的点在扇形外还是在扇形内，确定保留还是舍去。设曲线上的点列为pi，i1，2，n，光栏口经为d，可根据压缩量的大小自己定义，则光栏法的实施步骤可描述为：1、连接p1和p2点，过p2点作一条垂直于p1p2的直线，在该垂线上取两点a1和a2，使a1p2a2p2d2，此时a1和a2为“光栏”边界点，p1与a1、p1与a2的连线为以p1为顶点的扇形的两条边，这就定义了一个扇形(这个扇形的口朝向曲线的前进方向，边长是任意的)。通过p1并在扇形

10、内的所有直线都具有这种性质，即p1p2上各点到这些直线的垂距都不大于d/2。2、若p3点在扇形内，则舍去p2点。然后连接p1和p3，过p3作p1p1的垂线，该垂线与前面定义的扇形边交于c1和c2。在垂线上找到b1和b2点，使p3b1p3b2d2，若b1或b2点(图4-4-3中为b2点)落在原扇形外面，则用c1或c2取代(图4-4-3中由c2取代b2)。此时用p1b1和p1c2定义一个新的扇形，这当然是口径(b1c2)缩小了的“光栏”。3、检查下一节点，若该点在新扇形内，则重复第(2)步；直到发现有一个节点在最新定义的扇形外为止。4、当发现在扇形外的节点，如图4-4-3中的p4，此时保留p3点，

11、以p3作为新起点，重复13。如此继续下去，直到整个点列检测完为止。所有被保留的节点(含首、末点)，顺序地构成了简化后的新点列。首先将一条曲线首、末点连一直线，求出各点到该直线的距离，选其最大者与规定的临界值相比较若大于临界值，则离该直线距离最大的点保留，否则，将直线两端间各点全部舍去，并将原线条分成两部分，对每部分线条再实施该抽稀过程，直到结束。抽稀结果点数随选取限差临界值的增大而减少，应用时应根据精度要求来确定抽稀限差临界值，以获得最好的结果。即道格拉斯普克（Douglas-peuker）算法。4）道格拉斯普克法：P1PN splitpointP1PN Result 第一轮垂距第二轮垂距弦阈

12、值7栅格数据的压缩：1）链式编码：2）游程编码：所谓游程是指按行的顺序连续且属性值相同的若干栅格。 游程长度的记录方式有两种 记录每个游程起（迄）列号 记录每个游程像元数3）块式编码：块式编码是将游程扩大到两维情况，把多边形范围划分成若干具有同一属性的正方形，然后对各个正方形进行编码。块式编码的数据结构由初始位置（行列号）、半径和属性代码组成。3）四叉树编码：四叉树又称四元树或四分树，是最有效的栅格数据压缩编码方法之一。 四分树将整个图像区域逐步分解为一系列方形区域，且每一个方形区域具有单一的属性。最小区域为一个象元。8.隔点取样法实例：空间数据内插算法1.空间数据内插的定义：根据已知的空间数

13、据估计(预测)未知空间的数据值。2. 空间数据内插目标：缺值估计：估计某一点缺失的观测数据，以提高数据密度。内插等值线：以等值线的形式直观地显示数据的空间分布。数据网格化。把无规则分布的空间数据内插为规则分布的空间数据集，如规则矩形格网、三角网等。3.空间内插法的种类：几何方法、统计方法、空间统计方法、函数方法、随机模拟方法、物理模型模拟方法和综合方法。 4.优缺点比较：每一种方法均有其适用范围、算法和优缺点，因此，没有绝对最优的空间内插方法。5.如何选择：对数据进行空间探索分析，根据数据的特点，选择最优方法；同时，应对内插结果进行严格的检验。6空间数据内插的分类依据：确定或随机；点与面；全局

14、或局部等标准分类；内插方法的基本假设和数学本质。3.反距离权重插值算法：是一种局部插值算法，它假设未知值的点受较近控制点的影响比较远控制点的影响更大。反距离权重方法的通用方程是：式中，z0为点0的估计值；zi为控制点i的z值；dj为控制点i与点0间的趾离；s为在估算中用到的控制点的数目；K为指定的幂。4.双线性插值算法：是一种数字图像处理、DEM数据处理等方面使用较多的局部插值算法。原理：如图8.5所示，设f(0，0) = Z1，f (1，0)= Z2，f (0，1) = Z3，f (1，1) = Z4，求f (x,y)点的值，其中x,y 0，1。将f (0，0)、f (1，0)、f (0，1

15、)、f (1，1)代入双线性内插方程：f(x,y) = ax + by + cxy + d求出各参数a、b、c、d的值，再将x, y代入，解得f(x,y)。5反距离权重插值实例：TIN、DEM、DAT1.数字高程模型概念与理解：高程常常用来描述地形表面的起伏形态，传统的高程模型是等高线，其数学意义是定义在二维地理空间上的连续曲面函数，当此高程模型用计算机来表达时，称为数字高程模型。2.数字高程模型：是通过有限的地形高程数据实现对地形曲面的数字化模拟或者说是地形表面形态的数字化表示，英文为Digital Elevation Model，简称DEM。3.理解DEM和DTM：由于高程数据常常采用绝对

16、高程或海拔（即从大地水准面起算的高度），DEM也常常称为DTM。要说明的是由于“Terrain”一词的含义比较广泛，不同专业背景对“Terrain”的理解也不一样，DTM趋向于表达比DEM更为广泛的内容，详见后文的分析。4. TIN和规则DEM的区别：不规则三角网数字高程模型由连续的三角面组成，三角形的形状、大小取决于不规则分布的点的位置和密度。地形变化越简单，采样点就越少，则单元格就越大；反之地形变化比较复杂，数据点分布比较密集，格网单元就越小。因此TIN与规则格网DEM显著不同之处在于TIN模型不需要维护模型的结构规则性，不但能灵活地随地形的复杂程度而改变格网单元大小，避免平坦地形的数据冗

17、余，而且又能按地形特征点线如山脊点、山谷线、地形变化线等表示地形特征。5.DEM数据结构：规则格网DEM数据结构不规则三角形DEM数据结构6.规则格网数据：由于DEM的边界范围一般是规则矩形，而实际地形范围却是不规则的，还应考虑不在研究区域内的DEM高程值的表示方法（无效区域数据），一般是给出一个特殊的常数值，如-9999等。规则格网DEM的数据文件一般包含用对DEM数据进行说明的数据头和DEM数据体两部分。 1）数据头：一般包括定义DEM西南角起点坐标、坐标类型、格网间距、行列数、最低高程以及高程放大系数等内容；2）数据体：按行或列分布记录的高程数字阵列。 7.TIN：在TIN模型中，基本的

18、结构元素有三角形顶点、边和面。它们之间存在着点与线、点与面、线与面、面与面等拓扑关系。理论上，通过组成三角形的三顶点可完整地表达三角形的构成以及三角形顶点、三角形边、三角形之间的拓扑关系(下图)，这种结构只需要两个文件，即三角形顶点坐标文件和组成三角形三顶点（通常用点在坐标文件中的序号表示）文件。这种结构虽然简单，三角形结构元素的拓扑关系却是隐含的，不利于TIN模型的检索与应用。因此，围绕三角形的拓扑关系描述而产生了多种TIN的数据结构。 8.TIN模型的面结构最大特点是：由于存储了三角形之间的邻接关系，TIN内插、检索、等高线提取、显示以及局部结构分析都比较方便，不足之处是：存储量较大，而且

19、在TIN的编辑中要随时维护这种关系。9.DEM数据获取：建立DEM的第一步是获取地形数据。DEM的数据源和数据获取方式对于DEM的最终质量至关重要。DEM原始数据主要是高程和平面位置数据，在可能条件下还应包括各种地形结构线如山脊线、山谷线、断裂线等。另外，DEM应用目的、数据采集效率和成本、技术熟练程度也影响着DEM数据采集的方法和策略。/*目前DEM的数据主要来源于地形图、摄影测量与遥感影像数据、地面测量、既有DEM数据等。*/ 10.坡度：（1）坡度是地表形态最为重要的因子，通过坡度可以完整地形成地形曲面（Evans,1972；Strahler,1956）；（2）坡度是地形曲面函数一阶微分

20、的函数，表达了高程随距离变化的比率（坡度定义为地面一点的切平面与水平面之间的夹角），而坡度的变率是地形曲面的二阶微分，进一步刻画了坡度的变化，从而反映地形的复杂程度；（3）大量的研究表明，区域DEM高程精度与平均坡度值之间存在强相关，通过模型的平均坡度可预测DEM的精度（Ackermann,1979; Ley, 1986）；（4）坡度通过相互垂直的两个坐标轴方向的高程变化表达地形曲面局部单元的倾斜程度，也就是通过地形表面的凸面和凹面来描述地形表面特性，即地表的陡峭方向和大小。11.TIN数据的建立：基于不规则三角网的数字高程模型（Based on Triangulated Irregular

21、Network DEM，简写为 Based on TIN DEM，俗称TIN）就是用一系列互不交叉、互不重叠的连接在一起的三角形来表示地形表面。TIN是DEM的又一个主要数据模型，TIN的特点在其字面意思中表露无遗。 11. TIN的三角剖分准则：TIN的三角剖分准则是指TIN中三角形的形成法则，它决定着三角形的几何形状和TIN的质量。目前在GIS、计算几何和计算机图形学邻域常用的三角剖分准则有以下几种（1）空外接圆准则：在TIN中，过每个三角形的外接圆均不包含点集的其余任何点，如图A所示；（2）最大最小角准则：在两相邻三角形形成的凸四边形中，这两三角形中的最小内角一定大于交换凸四边形对角线后

22、所形成的两三角形的最小内角,如图B所示；（3）最短距离和准则： 图C，最短距离和就是指一点到基边两端的距离和为最小；（4）张角最大准则：图D，一点到基边的张角为最大；（5）面积比准则：图E，三角形内切圆面积与三角形面积或三角形面积与周长平方之比最小；（6）对角线准则：图F，两三角形组成的凸四边形的两条对角线之比。超过给定限定值时对三角形进行优化。理论上可以证明：张角最大准则、空外接圆准则及最大最小角准则是等价的，其余的则不然。三角形剖分准则是建立三角形网络的基本原则，应用不同的准则将会得到不同的三角形网络。一般而言，应尽量保持三角网的唯一性，即在同一准则下由不同的位置开始建立三角形网络，其最终

23、的形状和结构应是相同的，在这一点上，张角最大准则、空外接圆准则及最大最小角准则可以做到。对角线准则含有主观因素，现今使用已不多。 通常将在空外接圆准则、最大最小角准则下进行三角剖分称为Delaunay三角剖分，简称为DT，同时空外接圆和最大最小角也是Delaunay三角网的两个基本性质。DT三角剖分是目前应用最为广泛的三角剖分方法，其特性是可最大限度避免狭长三角形的出现以及不管从何处开始构网都能保持三角形网络的唯一性，这一点在实际应用中相当重要。实际上，在任何三角剖分准则下得到的TIN，只要用LOP法则（局部优化过程，local optimal procedure ，LOP）对其进行优化处理，

24、就能得到唯一的DT三角网络。LOP法则是Lawson在1977年提出的，其基本思想是运用DT三角网的空外接圆性质对由两个有公共边的三角形组成的四边形进行判断。如果其中一个三角形的外接圆中含有第四个顶点，则交换四边形的对角线。 LOP局部优化过程12.无约束散点域的三角剖分算法与实现 ：*分割合并算法 *三角法生长算法*逐点插入算法 1*分割合并算法：分割合并算法（divide and conquer delaunay triangulation algorithm）的思想最早是由Shamos和Hoey在1975年提出的，并将其应用于V-图的构成（V-图是Vorinoi图的简称，是DT三角网的对

25、偶图，为DT三角网中相邻三角形边垂直平分线交点的连线所形成的多边形，有关V-图的定义、性质和分割算法参见计算几何方面的书籍）。Lewis和Robinson于1978年将该方法用来进行DT三角网的剖分，随后Lee和Schachter、Dwyer等相继对Lewis和Robinson的算法进行了优化和改进，其中Lee和Schachter于1980年的算法适合于无约束数据域的三角剖分，而Dwyer于1987年的算法则考虑了带约束条件的LOP优化策略，因而能处理带约束条件的数据。分割合并算法的思想很简单，就是将复杂问题简单化，首先将数据点分割成易于进行三角剖分的子集，如一个子集中包括三个、四个点，然后对

26、每个子集进行三角剖分，并用LOP算法保证三角剖分为DT三角网。当每个子集剖分完成后，对每个子集的三角剖分进行合并，形成最终的整体三角网。不同的实现方法可有不同的点集划分方法、 子三角网生成方法及合并方法等。分割合并算法的基本步骤为： 第一步，把数据集以横坐标为主、 纵坐标为辅按升序进行排序；第二步，如果数据集中的数据个数大于给定的阈值，则把数据域划分为个数近似相等的左右两个子集，并对每一子集做如下的工作，计算每一子集的凸壳；以凸壳为数据边界，对每一数据子集进行三角剖分，并用LOP进行优化，使之成为DT三角剖分；找出连接左右子集两个凸壳的底线和顶线；由底线到顶线，合并两个子三角网；第三步：如果数

27、据集中的数据个数小于给定的阈值，则直接输出三角剖分结果；2*三角网生长算法：顾名思义，三角网生长算法就是从一个“源”开始，逐步形成覆盖整个数据区域的三角网。从生长过程角度，三角网生长算法分为收缩生长算法和扩张生长算法两种。收缩生长算法是先形成整个数据域的数据边界（凸壳），并以此作为源头，逐步缩小以形成整个三角网。收缩生长算法与数据点的分布密度有关，实际情况往往比较复杂，例如当边界收缩后一个完整的区域可能会分解成若干个相互独立的子区域，这就增加了三角剖分的复杂性扩张生长算法与收缩算法过程刚好相反，该算法是从一个三角形开始向外层层扩展，最终形成覆盖整个区域的三角网，其主要步骤为：第一步，生成初始三

28、角形。在数据点中任取一点A（该点一般是位于数据点的几何中心附近），并寻找距离此点最近的点B，两者相连形成初始基线AB，如图。利用三角剖分准则（空外接圆准则或张角最大准则），在数据域中寻找第三点C，从而形成第一个Delaunay三角形ABC。第二步，扩展形成三角网。以初始三角形的三条边为初始基线，利用空外接圆准则或张角最大准则，寻找能与该三条初始基线形成Delaunay三角形的D、E、F点。 BCADEFBCAD注意：（1）初始边界将整个数据域分成两个部分，搜寻第三点一般是在初始三角形另一顶点的异侧范围进行。例如若初始三角形为ABC，初始边界为AB，第三个顶点为C，能与三角形ABC共用AB边的另

29、一三角形ABD，D点要位于AB边的另一侧，而不能与C同侧，判断方法为： 2）为避免三角形的交叉和重复，通过上述异侧点判别所选的第三点还要进行进一步的认定。其方法是根据三角形任一条边最多只能与两个三角形所共用这个条件，进行三角形的全等比较，即判断新三角形的三条边是否被前面所形成的三角形共用过两次，如果是，则新三角形无效，否则为有效三角形。逐点插入算法 逐点插入算法的过程非常简单，基本步骤为：第一步，定义包含所有数据点的初始包容盒，并对该包容盒进行初始三角剖分；第二步，对所有数据点进行循环，做如下工作（设当前处理的数据点为P），在已存在的三角网中，查找包含p的三角形t；p与t的三个顶点相连，形成t

30、的三个初始三角剖分；用LOP算法对初始三角剖分进行优化处理。第三步，处理外围三角形。12.规则格网DEM读取实例： 13缓冲区分析算法：56. 缓冲区(buffer)概念：是根据空间数据库中的点、线、面地理实体或规划目标，自动建立其周围一定宽度范围的多边形。分类：点缓冲区、线缓冲区、面缓冲区和复杂实体缓冲区。57. 步进拟合的思想，即圆弧弥合的方法：（双侧平行线法）将圆心角等分，用等长的弦代替圆弧，即用均匀步长的直线段逼近圆弧段。等分的圆心角越小，步长越小，误差越小；等分的圆心角越大，步长越大，误差越大。58. 凸角圆弧法，基本思想：在轴线的两端用半径为缓冲距的圆弧弥合；在轴线的各转折点，判断

31、该点的凸凹性，在凸侧用半径为缓冲距的圆弧弥合，在凹侧用与该点关联的前后两相邻线段的偏移量为缓冲距的两平行线的交点作为对应顶点。59.关于缓冲区自相交处理：（P194）自相交多边形的两种情况：岛屿，多边形当存在岛屿和重叠自相交多边形时，最终计算的边线被分为外部边线和若干岛屿。缓冲区边线只绘制外围边线和岛屿轮廓。缓冲区检索时，在外边线所形成的多边形检索后，再扣除所有岛屿多边形。网络分析1网络中基本组成部分：1）结点(Node)：网络中任意两条线段的交点，属性如资源数量等n 链(Link)：连接两个结点的弧段。供物体运营的通道，链间的连接关系由弧段-结点拓扑数据结构来表达。属性如资源流动的时间、速度

32、等n 中心(Center)：网络中位于结点处，具有沿着链收集和发放资源能力的设施，如邮局、电站、水库等 n 站点(Stop)：资源沿着网络路径流动时被分配或收集的位置，如邮件投放点、公共汽车站，属性如资源需求量n 转向点(拐点，Turn)：链路相交处，资源流向发生改变的点 2）边/边集 3）图：是一个非空的有限结点和有限边的集合。 4）网络 5）流：指网络中任意一条弧的物流量。2.给定单源点的最短路径的求解（三步）: 1）选一顶点v为源点，并视从源点v出发的所有边为到各顶点的最短路径（确定数据结构：因为求的是最短路径，所以就要用一个记录从源点v到其它各顶点的路径长度数组dist,开始时，dis

33、t是源点v到顶点i的直接边长度，即dist中记录的是邻接阵的第v行。设一个用来记录从源点到其它顶点的路径数组path,path中存放路径上第i个顶点的前驱顶点）。2）在上述的最短路径dist中选一条最短的，并将其终点（即）k加入到集合s中。3）调整T中各顶点到源点v的最短路径。 因为当顶点k加入到集合s中后，源点v到T中剩余的其它顶点j就又增加了经过顶点k到达j的路径,这条路径可能要比源点v到j原来的最短的还要短。调整方法是比较distk+gk,j与distj，取其中的较小者。4）再选出一个到源点v路径长度最小的顶点k,从T中删去后加入S中，再回去到第三步，如此重复，直到集合S中的包含图G的所

34、有顶点。3（要求掌握基本概念和步骤，他们的区别）带权图分为有向和无向，无向图的最短路径又叫做最小生成树，有prime算法和kruskal算法；有向图的最短路径算法有dijkstra算法和floyd算法。（一）Floyd算法(P209)：Floyd又称为，插点法，是一种用于寻找给定的中多源点之间的算法。基本思想如下：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点X到B。所以，我们假设Dis(AB)为节点A到节点B的最短路径的距离，对于每一个节点X，我们检查Dis(AX) + Dis(XB) Dis(AB)是否成立，如果成立，证明从A到X再到B的路径比A

35、直接到B的路径短，我们便设置Dis(AB) = Dis(AX) + Dis(XB)，这样一来，当我们遍历完所有节点X，Dis(AB)中记录的便是A到B的最短路径的距离。步骤：1）从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。2）对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则Gi,j=d，d表示该路的长度；否则Gi,j=无穷大。定义一个矩阵D用来记录所插入点的信息，Di,j表示从Vi到Vj需要经过的点，初始化Di,j=j。把各个顶

36、点插入图中，比较插点后的距离与原来的距离，Gi,j = min( Gi,j, Gi,k+Gk,j )，如果Gi,j的值变小，则Di,j=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通的信息。比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为V5,V3,V1，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。实验作业作业1：实验1 空间数据(矢量)的采集作业2：实验2 空间数据的保存作业3：实验三 计算几何基础（1） 折线拐向判断作业4：实验三 计算几何基础（2） 地图量算作业5：实验三 计算几何基础（3） 三角形面积量算作业6：实验四（一）坐标变换作业7： 实验四（二） 格式转换作业8：实验四（三）矢量数据压缩作业9：实验四（四）栅格数据压缩作业10：实验五 空间数据的内插专心-专注-专业