GIS算法原理知识点总结_.docx

GIS算法原理知识点总结_GIS算法原理知识点总结GIS算法原理知识点总结GIS算法原理知识点总结算法设计和分析：1、算法设计的原则：正确性：若一个算法本身有缺陷，那么它将不会解决问题；确定性：指每个步骤必须含义明确，对每种可能性都有确定的操作。明晰性：一个良好的算法，必须思路明晰，构造合理。2、算法的复杂性包括：时间复杂性和空间复杂性。3、时间复杂性：用一个与问题相关的整数量来衡量问题的大小，该整数量表示输入数据量的尺度，称为问题的规模。利用某算法处理一个问题规模为n的输入所需要的时间，称为该算法的时间复杂性。4、算法的概念：算法是完成特定任务的有限指令集。所有的算法必须知足下面的标准：输入输出明确性有限性有效性GIS算法的计算几何基础1、理解矢量的概念：假如一条线段的端点是有次序之分的,我们把这种线段称为有向线段(directedsegment)。假如有向线段p1p2的起点P1在坐标原点，我们能够把它称为矢量P2。p2p1O5.矢量叉积：计算矢量叉积是直线和线段相关算法的核心部分。设矢量P=x1,y1，Q=x2,y2,则矢量叉积定义为0,0、p1、p2和p1p2所组成的平行四边形的带符号的面积，即P×Q=x1·y2-x2·y1，其结果是个标量。显然有性质P×Q=-Q×P和P×-Q=-P×Q。PXQ>0,则P在Q的顺时针方向；GIS算法原理知识点总结GIS算法原理知识点总结PXQ0,则PQ共线，但可能同向可以能反向。6、判定线段的拐向：折线段的拐向判定方法，能够直接由矢量叉积的性质推出，对于有公共端点的线段p0p1和P1P2，通过计算p2-p0×(P1-p0)的符号便能够给出折线段的拐向。理解矢量的概念通过矢量差积的方法就能够判定的拐向了。7.判定点能否在线段上：设点为Q，线段为P1P2：(Q-P1)X(P2-P1)=0且Q在以P1，P2为对角顶点的矩形内。前者抱走点在直线上，后者保证点不在线段延长线或反向延长线上。8、判定两线段能否相交算法一：快速排挤实验：设以线段P1P2为对角线的矩形为R，设以线段Q1Q2为对角的矩形为T，假如R和T不相交，显然两线段不会相交p0p1p1p0p1p2基p2-p0×(P1-p0)0，则P0P1在P1点拐向右侧后得到P1P2GIS算法原理知识点总结GIS算法原理知识点总结跨立实验：假如两线段相交，则两线段必然互相跨立对方。若p1p2跨立Q1Q2，则矢量P1-Q1和P2-Q2位于矢量Q2-Q1的两侧，则P1-Q1×Q2-Q1×P2-Q1×Q2-Q10。当P1-Q1×Q2-Q1=0时，讲明P1-Q1×Q2-Q1共线，但是由于已经通过快速排斥实验，所以P1一定在线段Q1Q2上；同理Q2-Q1×P2-Q1=0讲明P2一定在线段Q1Q2上。所以判定P1P2跨立Q1Q2的根据是：P1-Q1×Q2-Q1×Q2-Q1×P2-Q10。同理判定Q1Q2跨立P1P2的根据是Q1-P1×P2-P1×P2-P1×Q2-P10。注意在进行“跨立判定的时候是进行两次跨立判定9.判定矩形内能否包含点：只要判定该店的横坐标和纵坐标能否都夹在矩形的左右边和上下边之间。10.判定线段、折线、多边形能否在矩形中：由于矩形是个凸集，所以只要判定所有端点都在矩形就行了。11.判定矩形能否在矩形中：只要比拟左右边界和上下边界就行了。12.判定圆能否在矩形中：圆心在矩形中且圆的半径小于或等于圆心到矩形四边的距离的最小值。13.判定点能否在多边形内：1)射线法：一条射线从点P开场，穿太多边形的边界的次数称为交点数目。当交点数目是偶数时，点P在多边形外部；否则，为奇数时，在多边形内部。GIS算法原理知识点总结GIS算法原理知识点总结射线法要考虑几种特殊的情况，并且射线法适用于凸多边形2)转角法：多边形环绕点P的次数称为环绕数，环绕数为0时，点P在多边形外部，否则在多边形内部。14.判定线段能否在多边形内：折线是判定它的每条线段条件一：线段的两个端点都在多边形内条件二：线段和多边形的所有边都不内交。15.判定多边形否在多边形内：只要判定多边形的每条边能否都在多边形内即可。判定有m个顶点的多边形能否在一个有n个顶点的多边形内的复杂度为O(mXn)16.判定矩形能否在多边形内：将矩形转化为多边形，然后再判定能否在多边形内。17.判定圆能否在多边形内：计算圆心到多边形每条变边的最短距离，若该距离大于或等于圆半径，则该圆在多边形内。18.判定点能否在圆内：计算圆心到该点的距离，若小于或等于半径，则该点在圆内。19.判定线段、折线、矩形、多边形能否在圆内：由于圆是凸集，所以只要判定能否每个顶点都在圆内即可。20.判定圆能否在圆内：设两圆为O1,O2,半径为r1,r2。先比拟r1,r2的大小，若r1GIS算法原理知识点总结GIS算法原理知识点总结空间数据的变换算法1.了解平面坐标变换的几种形式:2.仿射变换：它是使用最多的一种几何纠正方式。在保留线条平行条件下，仿射变换允许对长方形目的做旋转、平移、倾斜和不均匀缩放。旋转指在原点旋转x和y轴；平移是指把源点移动到新的位置；倾斜是指以一个倾向将形状改变为平行四边形；不均匀缩放是指在x或y方向同时或单独增大和缩小GIS算法原理知识点总结GIS算法原理知识点总结比例尺。yBxBBYyAxAAXmBmBmAmABymxmYAymxmXyyxxyyxx21021020cos2,sin1sin,cos1)cos()sin()sin()cos(0+=-+=+=+-=平移变换实例代码：比例变换实当代码：此页面能否是列表页或首页？未找到适宜正文内容。GIS算法原理知识点总结GIS算法原理知识点总结3.类似变换：图形的类似变换是指由一个图形到另一个图形，在改变的经过中保持形状不变大小方向和位置可变的图形。图形类似变换的性质：图形的类似变换不改变图形中每一个角的大小；图形类似变换后对应线段都扩大或缩小一样的倍数，这个数叫类似比。类似变换面积：经类似变换的像与原图的面积等于类似比的平方。类似变换的分解：任何类似变换能够分解为放缩，平移，旋转和翻转变换的复合。类似变换是仿射变换的一种特殊情况，也就是在仿射变换中去除错位变换这个因子后的结果。yAxBBYyBxAAXmBmAByxmYAyxmX1101100sin1cos1)cossin()sincos(0+=-+=+=+-=4.矢量转栅格：点：简单的坐标变换线：线的栅格化面：线的栅格化+面填充面(多边形)的填充方法1、内部点扩散法种子扩散法2、扫描法3、射线法4、复数积分法5、边界代数算法栅格表示法的精度与分辨率有关。在图(a)、(b)、(c)中，栅格的分辨率分别为7*5，15*11，24*13。分辨率的大小与下面两个问题有关：GIS算法原理知识点总结GIS算法原理知识点总结5.栅格矢量化：从栅格单元转换为几何图形的经过为矢量化；一要求矢量化经过应保持：1栅->矢转换为拓扑转换，即保持实体原有的连通性、邻接性等；2转换实体保持正确的外形。二方法方法一，实际应用中大多数采用人工矢量化法，如扫描矢量化，该法工作量大，成为GIS数据输入、更新的瓶颈问题之一。方法二，程序转化转换全自动或半自动经过为：1、边界提取2、二值化3、二值图像的预处理4、细化:1剥皮法2)骨架法5、跟踪6、拓扑化6.矢量点转栅格实例：此页面能否是列表页或首页？未找到适宜正文内容。此页面能否是列表页或首页？未找到适宜正文内容。此页面能否是列表页或首页？未找到适宜正文内容。GIS算法原理知识点总结GIS算法原理知识点总结光栏法的基本思想是(上图)：定义一个扇形区域，通过判定曲线上的点在扇形外还是在扇形内，确定保留还是舍去。设曲线上的点列为pi，i1，2，n，光栏口经为d，可根据压缩量的大小本人定义，则光栏法的施行步骤可描绘为：1°、连接p1和p2点，过p2点作一条垂直于p1p2的直线，在该垂线上取两点a1和a2，使a1p2a2p2d2，此时a1和a2为“光栏边界点，p1与a1、p1与a2的连线为以p1为顶点的扇形的两条边，这就定义了一个扇形(这个扇形的口朝向曲线的前进方向，边长是任意的)。通过p1并在扇形内的所有直线都具有这种性质，即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点，以p3作为新起点，重复1°3°。如此继续下去，直到整个点列检测完为止。所有被保留的节点(含首、末点)，顺序地构成了简化后的新点列。4道格拉斯普克法：首先将一条曲线首、末点连一直线，求出各点到该直线的距离，选其最大者与规定的临界值相比拟若大于临界值，则离该直线距离最大的点保留，否则，将直线两端间各点全部舍去，并将原线条分成两部分，对每部分线条再施行该抽稀经过，直到结束。抽稀结果点数随选取限差临界值的增大而减少，应用时应根据精度要求来确定抽稀限差临界值，以获得最好的结果。即道格拉斯普克Douglas-peuker算法。P1此页面能否是列表页或首页？未找到适宜正文内容。此页面能否是列表页或首页？未找到适宜正文内容。此页面能否是列表页或首页？未找到适宜正文内容。此页面能否是列表页或首页？未找到适宜正文内容。此页面能否是列表页或首页？未找到适宜正文内容。GIS算法原理知识点总结GIS算法原理知识点总结空间数据内插算法1.空间数据内插的定义：根据已知的空间数据估计(预测)未知空间的数据值。2.空间数据内插目的：缺值估计：估计某一点缺失的观测数据，以提高数据密度。内插等值线：以等值线的形式直观地显示数据的空间分布。数据网格化。把无规则分布的空间数据内插为规则分布的空间数据集，如规则矩形格网、三角网等。3.空间内插法的种类：几何方法、统计方法、空间统计方法、函数方法、随机模拟方法、物理模型模拟方法和综合方法。4.优缺点比拟：每一种方法均有其适用范围、算法和优缺点，因而，没有绝对最优的空间内插方法。5.怎样选择：对数据进行空间探索分析，根据数据的特点，选择最优方法；同时，应对内插结果进行严格的检验。6空间数据内插的分类根据：确定或随机；点与面；全局或局部等标准分类；内插方法的基本假设和数学本质。3.反距离权重插值算法：是一种局部插值算法，它假设未知值的点受较近控制点的影响比拟远控制点的影响更大。反距离权重方法的通用方程是：式中，z0为点0的估计值；zi为控制点i的z值；dj为控制点i与点0间的趾离；s为在估算中用到的控制点的数目；K为指定的幂。4.双线性插值算法：是一种数字图像处理、DEM数据处理等方面使用较多的局部插值算法。，f(1，0)=Z2，原理：如图8.5所示，设f(0，0)=Zf(0，1)=Z3，f(1，1)=Z4，求f(x,y)点的值，其中x,y0，1。将f(0，0)、f(1，0)、f(0，1)、f(1，1)代入双线性内插方程：f(x,y)=ax+by+cxy+d求出各参数a、b、c、d的值，再将x,y代入，解得f(x,y)。5反距离权重插值实例：此页面能否是列表页或首页？未找到适宜正文内容。GIS算法原理知识点总结GIS算法原理知识点总结1.数字高程模型概念与理解：高程经常用来描绘地形外表的起伏形态，传统的高程模型是等高线，其数学意义是定义在二维地理空间上的连续曲面函数，当此高程模型用计算机来表达时，称为数字高程模型。2.数字高程模型：是通过有限的地形高程数据实现对地形曲面的数字化模拟或者讲是地形外表形态的数字化表示，英文为DigitalElevationModel，简称DEM。3.理解DEM和DTM：由于高程数据经常采用绝对高程或海拔即从大地水准面起算的高度，DEM也经常称为DTM。要讲明的是由于“Terrain一词的含义比拟广泛，不同专业背景对“Terrain的理解也不一样，DTM趋向于表达比DEM更为广泛的内容，详见后文的分析。4.TIN和规则DEM的区别：不规则三角网数字高程模型由连续的三角面组成，三角形的形状、大小取决于不规则分布的点的位置和密度。地形变化越简单，采样点就越少，则单元格就越大；反之地形变化比拟复杂，数据点分布比拟密集，格网单元就越小。因而TIN与规则格网DEM显著不同之处在于TIN模型不需要维护模型的构造规则性，不但能灵敏地随地形的复杂程度而改变格网单元大小，避免平坦地形的数据冗余，而且又能按地形特征点线如山脊点、山谷线、地形变化线等表示地形特征。GIS算法原理知识点总结GIS算法原理知识点总结5.DEM数据构造：规则格网DEM数据构造不规则三角形DEM数据构造6.规则格网数据：由于DEM的边界范围一般是规则矩形，而实际地形范围却是不规则的，还应考虑不在研究区域内的DEM高程值的表示方法无效区域数据，一般是给出一个特殊的常数值，如-9999等。规则格网DEM的数据文件一般包含用对DEM数据进行讲明的数据头和DEM数据体两部分。1数据头：一般包括定义DEM西南角起点坐标、坐标类型、格网间距、行列数、最低高程以及高程放大系数等内容；2数据体：按行或列分布记录的高程数字阵列。7.TIN：在TIN模型中，基本的构造元素有三角形顶点、边和面。它们之间存在着点与线、点与面、线与面、面与面等拓扑关系。理论上，通过组成三角形的三顶点可完好地表达三角形的构成以及三角形顶点、三角形边、三角形之间的拓扑关系(下列图)，这种构造只需要两个文件，即三角形顶点坐标文件和组成三角形三顶点通常用点在坐标文件中的序号表示文件。这种构造固然简单，三角形构造元素的拓扑关系却是隐含的，不利于TIN模型的检索与应用。因而，围绕三角形的拓扑关系描绘而产生了多种TIN的数据构造。GIS算法原理知识点总结GIS算法原理知识点总结8.TIN模型的面构造最大特点是：由于存储了三角形之间的邻接关系，TIN内插、检索、等高线提取、显示以及局部构造分析都比拟方便，缺乏之处是：存储量较大，而且在TIN的编辑中要随时维护这种关系。9.DEM数据获取：建立DEM的第一步是获取地形数据。DEM的数据源和数据获取方式对于DEM的最终质量至关重要。DEM原始数据主要是高程和平面位置数据，在可能条件下还应包括各种地形构造线如山脊线、山谷线、断裂线等。另外，DEM应用目的、数据收集效率和成本、技术熟练程度也影响着DEM数据收集的方法和策略。/*目前DEM的数据主要;于地形图、摄影测量与遥感影像数据、地面测量、既有DEM数据等。*/10.坡度：1坡度是地表形态最为重要的因子，通过坡度能够完好地构成地形曲面Evans,1972；Strahler,1956；2坡度是地形曲面函数一阶微分的函数，表达了高程随距离变化的比率坡度定义为地面一点的切平面与水平面之间的夹角，而坡度的变率是地形曲面的二阶微分，进一步刻画了坡度的变化，进而反映地形的复杂程度；3大量的研究表明，区域DEM高程精度与平均坡度值之间存在强相关，通过模型的平均坡度可预测DEM的精度Ackermann,1979;Ley,1986；4坡度通过互相垂直的两个坐标轴方向的高程变化表达地形曲面局部单元的倾斜程度，也就是通过地形外表的凸面和凹面来描绘地形外表特性，即地表的陡峭方向和大小。11.TIN数据的建立：基于不规则三角网的数字高程模型BasedonTriangulatedIrregularNetworkDEM，简写为BasedonTINDEM，俗称TIN就是用一系列互不穿插、互不重叠的连接在一起的三角形来表示地形外表。TIN是DEM的又一个主要数据模型，TIN的特点在其字面意思中表露无遗。GIS算法原理知识点总结GIS算法原理知识点总结11.TIN的三角剖分准则：TIN的三角剖分准则是指TIN中三角形的构成法则，它决定着三角形的几何形状和TIN的质量。目前在GIS、计算几何和计算机图形学邻域常用的三角剖分准则有下面几种1空外接圆准则：在TIN中，过每个三角形的外接圆均不包含点集的其余任何点，如图A所示；2最大最小角准则：在两相邻三角形构成的凸四边形中，这两三角形中的最小内角一定大于交换凸四边形对角线后所构成的两三角形的最小内角,如图B所示；3最短距离和准则：图C，最短距离和就是指一点到基边两端的距离和为最小；4张角最大准则：图D，一点到基边的张角为最大；5面积比准则：图E，三角形内切圆面积与三角形面积或三角形面积与周长平方之比最小；6对角线准则：图F，两三角形组成的凸四边形的两条对角线之比。超过给定限定值时对三角形进行优化。理论上能够证实：张角最大准则、空外接圆准则及最大最小角准则是等价的，其余的则不然。三角形剖分准则是建立三角形网络的基本原则，应用不同的准则将会得到不同的三角形网络。一般而言，应尽量保持三角网的唯一性，即在同一准则下由不同的位置开场建立三角形网络，其最终的形状和构造应是一样的，在这一点上，张角最大准则、空外接圆准则及最大最小角准则能够做到。对角线准则含有主观因素，现今使用已不多。GIS算法原理知识点总结GIS算法原理知识点总结通常将在空外接圆准则、最大最小角准则下进行三角剖分称为Delaunay三角剖分，简称为DT，同时空外接圆和最大最小角也是Delaunay三角网的两个基本性质。DT三角剖分是目前应用最为广泛的三角剖分方法，其特性是可最大限度避免狭长三角形的出现以及不管从何处开场构网都能保持三角形网络的唯一性，这一点在实际应用中相当重要。实际上，在任何三角剖分准则下得到的TIN，只要用LOP法则局部优化经过，localoptimalprocedure，LOP对其进行优化处理，就能得到唯一的DT三角网络。LOP法则是Lawson在1977年提出的，其基本思想是运用DT三角网的空外接圆性质对由两个有公共边的三角形组成的四边形进行判定。假如其中一个三角形的外接圆中含有第四个顶点，则交换四边形的对角线。LOP局部优化经过12.无约束散点域的三角剖分算法与实现：*分割合并算法*三角法生长算法*逐点插入算法GIS算法原理知识点总结GIS算法原理知识点总结1*分割合并算法：分割合并算法divideandconquerdelaunaytriangulationalgorithm的思想最早是由Shamos和Hoey在1975年提出的，并将其应用于V-图的构成V-图是Vorinoi图的简称，是DT三角网的对偶图，为DT三角网中相邻三角形边垂直平分线交点的连线所构成的多边形，有关V-图的定义、性质和分割算法参见计算几何方面的书籍。Lewis和Robinson于1978年将该方法用来进行DT三角网的剖分，随后Lee和Schachter、Dwyer等相继对Lewis和Robinson的算法进行了优化和改良，其中Lee和Schachter于1980年的算法合适于无约束数据域的三角剖分，而Dwyer于1987年的算法则考虑了带约束条件的LOP优化策略，因此能处理带约束条件的数据。分割合并算法的思想很简单，就是将复杂问题简单化，首先将数据点分割成易于进行三角剖分的子集，如一个子集中包括三个、四个点，然后对每个子集进行三角剖分，并用LOP算法保证三角剖分为DT三角网。当每个子集剖分完成后，对每个子集的三角剖分进行合并，构成最终的整体三角网。不同的实现方法可有不同的点集划分方法、子三角网生成方法及合并方法等。分割合并算法的基本步骤为：GIS算法原理知识点总结GIS算法原理知识点总结第一步，把数据集以横坐标为主、纵坐标为辅按升序进行排序；第二步，假如数据集中的数据个数大于给定的阈值，则把数据域划分为个数近似相等的左右两个子集，并对每一子集做如下的工作，计算每一子集的凸壳；以凸壳为数据边界，对每一数据子集进行三角剖分，并用LOP进行优化，使之成为DT三角剖分；找出连接左右子集两个凸壳的底线和顶线；由底线到顶线，合并两个子三角网；第三步：假如数据集中的数据个数小于给定的阈值，则直接输出三角剖分结果；此页面能否是列表页或首页？未找到适宜正文内容。GIS算法原理知识点总结GIS算法原理知识点总结2*三角网生长算法：顾名思义，三角网生长算法就是从一个“源开场，逐步构成覆盖整个数据区域的三角网。从生长经过角度，三角网生长算法分为收缩生长算法和扩张生长算法两种。收缩生长算法是先构成整个数据域的数据边界凸壳，并以此作为源头，逐步缩小以构成整个三角网。收缩生长算法与数据点的分布密度有关，实际情况往往比拟复杂，例如当边界收缩后一个完好的区域可能会分解成若干个互相独立的子区域，这就增加了三角剖分的复杂性扩张生长算法与收缩算法经过恰好相反，该算法是从一个三角形开场向外层层扩展，最终构成覆盖整个区域的三角网，其主要步骤为：第一步，生成初始三角形。在数据点中任取一点A该点一般是位于数据点的几何中心附近，并寻找距离此点近期的点B，两者相连构成初始基线AB，如图。利用三角剖分准则空外接圆准则或张角最大准则，在数据域中寻找第三点C，进而构成第一个Delaunay三角形ABC。第二步，扩展构成三角网。以初始三角形的三条边为初始基线，利用空外接圆准则或张角最大准则，寻找能与该三条初始基线构成Delaunay三角形的D、E、F点。注意：1初始边界将整个数据域分成两个部分，搜索第三点一般是在初始三角形另一顶点的异侧范围进行。例如若初始三角形为ABC，初始边界为AB，第三个顶点为C，能与三角形ABC共用AB边的另一三角形ABD，D点要位于AB边的另一侧，而不能与C同侧，判定方法为：BCADEFBADGIS算法原理知识点总结GIS算法原理知识点总结2为避免三角形的穿插和重复，通过上述异侧点判别所选的第三点还要进行进一步的认定。其方法是根据三角形任一条边最多只能与两个三角形所共用这个条件，进行三角形的全等比拟，即判定新三角形的三条边能否被前面所构成的三角形共用过两次，假如是，则新三角形无效，否则为有效三角形。逐点插入算法逐点插入算法的经过非常简单，基本步骤为：第一步，定义包含所有数据点的初始包涵盒，并对该包涵盒进行初始三角剖分；第二步，对所有数据点进行循环，做如下工作设当前处理的数据点为P，在已存在的三角网中，查找包含p的三角形t；p与t的三个顶点相连，构成t的三个初始三角剖分；用LOP算法对初始三角剖分进行优化处理。第三步，处理外围三角形。12.规则格网DEM读取实例：GIS算法原理知识点总结GIS算法原理知识点总结13缓冲区分析算法：56.缓冲区(buffer)概念：是根据空间数据库中的点、线、面地理实体或规划目的，自动建立其周围一定宽度范围的多边形。分类：点缓冲区、线缓冲区、面缓冲区和复杂实体缓冲区。57.步进拟合的思想，即圆弧弥合的方法：双侧平行线法将圆心角等分，用等长的弦代替圆弧，即用均匀步长的直线段逼近圆弧段。等分的圆心角越小，步长越小，误差越小；等分的圆心角越大，步长越大，误差越大。58.凸角圆弧法，基本思想：在轴线的两端用半径为缓冲距的圆弧弥合；在轴线的各转折点，判定该点的凸凹性，在凸侧用半径为缓冲距的圆弧弥合，在凹侧用与该点关联的前后两相邻线段的偏移量为缓冲距的两平行线的交点作为对应顶点。59.关于缓冲区自相交处理：P194自相交多边形的两种情况：岛屿，多边形当存在岛屿和重叠自相交多边形时，最终计算的边线被分为外部边线和若干岛屿。缓冲区边线只绘制外围边线和岛屿轮廓。缓冲区检索时，在外边线所构成的多边形检索后，再扣除所有岛屿多边形。网络分析1网络中基本组成部分：1结点(Node)：网络中任意两条线段的交点，属性如资源数量等?链(Link)：连接两个结点的弧段。供物体运营的通道，链间的连接关系由弧段-结点拓扑数据构造来表达。属性如资源流动的时间、速度等?中心(Center)：网络中位于结点处，具有沿着链采集和发放资源能力的设施，如邮局、电站、水库等?站点(Stop)：资源沿着网络途径流动时被分配或采集的位置，如邮件投放点、公共汽车站，属性如资源需求量?转向点(拐点，Turn)：链路相交处，资源流向发生改变的点2边/边集3图：是一个非空的有限结点和有限边的集合。4网络5流：指网络中任意一条弧的物流量。2.给定单源点的最短途径的求解三步:1选一顶点v为源点，并视从源点v出发的所有边为到各顶点的最短途径确定数据构造：由于求的是最短途径，所以就要用一个记录从源点v到其它各顶点的途径长度数组dist,开场时，dist是源点v到顶点i的直接边长度，即dist中记录的是邻接阵的第v行。设一个用来记录从源点到其它顶点的途径数组path,path中存放途径上第i个顶点的前驱顶点。2在上述的最短途径dist中选一条最短的，并将其终点即k参加到集合s中。3调整T中各顶点到源点v的最短途径。由于当顶点k参加到集合s中后，源GIS算法原理知识点总结GIS算法原理知识点总结点v到T中剩余的其它顶点j就又增加了经过顶点k到达j的途径,这条途径可能要比源点v到j原来的最短的还要短。调整方法是比拟distk+gk,j与distj，取其中的较小者。4再选出一个到源点v途径长度最小的顶点k,从T中删去后参加S中，再回去到第三步，如此重复，直到集合S中的包含图G的所有顶点。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)