2022年GIS算法原理知识点总结2.docx

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

1、GIS 算法原理学问点总结算法设计与分析：1、算法设计得原就：正确性：如一个算法本身有缺陷,那么它将不会解决问题；确定性：指每个步骤必需含义明确,对每种可能性都有确定得操作；清楚性：一个良好得算法,必需思路清楚,结构合理；2、算法得复杂性包括 ：时间复杂性与空间复杂性；3、时间复杂性： 用一个与问题相关得整数量来衡量问题得大小,该整数量表示输入数据量得尺度,称为问题得规模；利用某算法处理一个问题规模为n得输入所需要得时间,称为该算法得时间复杂性；4、算法得概念 ：算法就是完成特定任务得有限指令集；全部得算法必需满意下面得标准：输入 输出 明确性有限性有效性GIS 算法得运算几何基础1、懂得矢量

2、得概念： 假如一条线段得端点就是有次序之分得 , 我们把这种线段称为有向线段 directed segment；假如有向线段 p1p2 得起点 P1 在坐标原点,我们可以把它称为矢量P2；p2p15、矢量叉积： 运算矢量叉积就是直线与线段相关算法得核心部分；设矢量 P = （x1,y1）,Q = （x2,y2）,就矢量叉积定义为（ 0,0）、p1、p2与 p1p2 所组成得平行四边形得带符号得面积,即PQ = x1 y2-x2 y1,O其结果就是个标量；明显有性质PQ= -（QP）与 P-Q= -（PQ）； P X Q0,就 P 在 Q 得顺时针方向；P X Q0,就 P Q共线,但可能同向也

3、可能反向；6、判定线段得拐向 ：折线段得拐向判定方法,可以直接由矢量叉积得性质推出,对于有公共端点得线段 p0p1 与 P1P2,通过运算（ p2-p0）P1-p0得符号便可以给出折线段得拐向；p2p2p2p1p1p0p0基（ p2-p0 ） P1-p0=0 ,p1基（ p2-p0 ）p0P1-p00 ,就 P0P1基（ p2-p0 ） P1-p00 ,就懂得矢P0量P1得概念通过矢量差积得就方P法0P就1P可2 三以点判共断线得拐向了在；P1 点拐向右侧后得到在 P1 点拐向左侧后得到 P1P2P1P27、判定点就是否在线段上 ：设点为 Q,线段为 P1 P2：Q-P1XP2-P1=0 且Q

4、 在以 P1,P2 为对角顶点得矩形内；前者抱走点在直线上,后者保证点不在线段延长线或反向延长线上；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）共线,但就是由

5、于已经通过快速排斥试验,所以 P1 肯定在线段 Q1Q2 上；同理 （ Q2-Q1） （P2-Q1） =0 说明 P2 肯定在线段 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、判定线段、折线、多边形就是否在矩形中：由于矩形就是个凸集,所以只要判

6、定全部端点都在矩形就行了；11、判定矩形就是否在矩形中： 只要比较左右边界与上下边界就行了；12、判定圆就是否在矩形中 ：圆心在矩形中且圆得半径小于或等于圆心到矩形四边得距离得最小值；13、判定点就是否在多边形内：1) 射线法：一条射线从点 P 开头,穿过多边形得边界得次数称为交点数目；当交点数目就是偶数时,点 P 在多边形外部；否就,为奇数时,在多边形内部；射线法要考虑几种特别得情形,并且射线法适用于凸多边形2) 转角法：多边形环绕点 P 得次数称为环绕数,环绕数为 0 时,点 P 在多边形外部,否就在多边形内部；14、判定线段就是否在多边形内： （折线就是判定它得每条线段） 条件一：线段得

7、两个端点都在多边形内条件二：线段与多边形得全部边都不内交；15、判定多边形否在多边形内：只要判定多边形得每条边就是否都在多边形内即可；判定有m 个顶点得多边形就是否在一个有 n 个顶点得多边形内得复杂度为 OmXn16、判定矩形就是否在多边形内：将矩形转化为多边形,然后再判定就是否在多边形内；17、判定圆就是否在多边形内： 运算圆心到多边形每条变边得最短距离,如该距离大于或等于圆半径,就该圆在多边形内；18、判定点就是否在圆内： 运算圆心到该点得距离,如小于或等于半径,就该点在圆内；19、判定线段、折线、矩形、多边形就是否在圆内：由于圆就是凸集, 所以只要判定就是否每个顶点都在圆内即可；20、

8、判定圆就是否在圆内：设两圆为 O1,O2,半径为 r1,r2；先比较 r1,r2 得大小,如 r1矢转换为拓扑转换,即保持实体原有得连通性、邻接性等；2） 转换实体保持正确得外形；（二）方法方法一,实际应用中大多数采纳人工矢量化法,如扫描矢量化,该法工作量大,成为 GIS 数据输入、更新得瓶颈问题之一；方法二,程序转化转换（全自动或半自动）过程为： 1、边界提取 2、二值化 3、二值图像得预处理 4、细化:1）剥皮法 2骨架法 5 、跟踪6、拓扑化6、”矢量点 ”转栅格实例：6、矢量数据得压缩 ： 矢量数据得压缩包括两个方面得内容,一就是在不扰乱拓扑关系得前提下, 对采样点数据进行合理得抽稀；

9、二就是对矢量坐标数据重新进行编码,以削减所需要得储备空间；1） 间隔取点法 ：每隔 K 个点取一点,或舍去那些比规定距离更近得点,首末点肯定要保留；2） 垂距隔点法法：临界值法原始曲线4131123 点舍去,化简结果33） 光栅法：2对点 2 测试距离大于规定得限差4限差4临界值2点 2 保留光栏法得基本思想就是 c上1图：定义一个4扇形区域,通过判定曲线上得点在扇形外仍就是在2扇、形如内p3,点确在定扇保形留内仍,就3就是舍去；p设2 曲点线；上然得后点连列接为p1 与 pp3i,过ip13,作2P,pn1p1,得n垂,线光,栏该口垂经线为与d,4） 可前道面根格定据拉义压斯得缩扇量形得普大

10、克小交法自：己定c1义与,c就2；光在栏垂法线得上实找施到步骤b可1 描与述b为2 点：,使 p3b1 p3b2 d 2,如 b1首或1先、b2将连点一接条图p曲1 4与线-4首-p32、中点末为,点过b连2一p点2直点落线作在,一原求条扇出P垂形各4直外点于面到,该p就直1p用线2 得得c1距直或离线c,2选在取其该代最垂图大线者4上-4与取-3规两中定点由得临ca21 取与代a2b,2使；界a此1值时p2相用比ap21pb如21 大与2d于p临1c2界2 值,就a离1 该与直a线2 距离最对大点得点3 保测留试,距否离p1就小b与,1于c将a2规1直定缩、线得p小1两限了与端差得间a“2各

11、光得点栏连全”线；为以 p1 为,定此义时一个新得扇为形“,光这栏当”然边就界是点口,径3splitpoint顶部点舍得去a,1形并得将两原条线d条/2,分这成就两定部义分b1了,一对个每扇部形分线条这再个实扇施形该得抽口稀朝过向程曲,线直得到前结进束方；向抽,稀边结长就是任 意果3得点、数检；随查通选下过取一p限节1差点并临,在界如扇值该形得点内增在得大新所而扇有减形直少内线,都应就具用重有时复这4应第种根性据质2精,步度即；要直求到来p1发确p2现定上有抽各一稀点个限到节差这点临些在界直最线新得定垂义距得都 不扇值,形以外为获d得/2 ；最好得P结2果；即道格拉斯 普克（ Douglas-

12、peuker ）算法；d/2弦7栅格数据得压缩：Result第一轮垂距1） 链式编码 ：其次轮垂距PNP1阈值2） 游程编码 ：所谓游程就是指按行得次序连续且属性值相同得如干栅格；游程长度得记录方式有两种 记录每个游程起（迄）列号 记录每个游程像元数3）块式编码 ：块式编码就是将游程扩大到两维情形,把多边形范畴划分成如干具有同一属性得正方形,然后对各个正方形进行编码；块式编码得数据结构由初始位置（行列号） 、半径与属性代码组成；3） 四叉树编码 ：四叉树又称四元树或四分树,就是最有效得栅格数据压缩编码方法之一；四分树将整个图像区域逐步分解为一系列方形区域,且每一个方形区域具有单一得属性；最小区

13、域为一个象元；8、隔点取样法实例：空间数据内插算法1、空间数据内插得定义 ： 依据已知得空间数据估量 猜测未知空间得数据值；2、 空间数据内插目标：缺值估量：估量某一点缺失得观测数据,以提高数据密度；内插等值线：以等值线得形式直观地显示数据得空间分布；数据网格化；把无规章分布得空间数据内插为规章分布得空间数据集, 如规章矩形格网、三角网等；3、空间内插法得种类： 几何方法、 统计方法、 空间统计方法、 函数方法、 随机模拟方法、物理模型模拟方法与综合方法；4、优缺点比较： 每一种方法均有其适用范畴、算法与优缺点,因此,没有肯定最优得空间内插方法；5、如何挑选： 对数据进行空间探究分析,依据数据

14、得特点,挑选最优方法；同时,应对内插结果进行严格得检验；6 空间数据内插得分类依据：确定或随机；点与面；全局或局部等标准分类；内插方法得基本假设与数学本质；3、反距离权重插值算法： 就是一种局部插值算法,它假设未知值得点受较近控制点得影响比较远掌握点得影响更大；反距离权重方法得通用方程就是：式中, z0 为点 0 得估量值； zi 为掌握点 i 得 z 值； dj 为掌握点 i 与点 0 间得趾离； s为在估算中用到得掌握点得数目； K 为指定得幂；4、双线性插值算法： 就是一种数字图像处理、 DEM数据处理等方面使用较多得局部插值算法；原理：如图 8、5 所示,设 f 0,0 = Z1 ,f

15、 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、f 1,1代入双线性内插方程：fx,y = ax + by + cxy + d求出各参数 a、b、c、d 得值,再将 x, y 代入,解得fx,y；5 反距离权重插值实例：TIN 、DEM 、DAT1、数字高程模型概念与懂得：高程经常用来描述地势表面得起伏外形,传统得高程模型就是等高线,其数学意义就是定义在二维地理空间上得连续曲面函数, 当此高程模型用运算机来表达时,称为数字高程模型；2、数字高程模型： 就是通过有限得地势高程数据实现对地势曲面得数

16、字化模拟或者说就是地势表面外形得数字化表示,英文为Digital Elevation Model ,简称DEM；3、懂得 DEM 与 DTM：由于高程数据经常采纳肯定高程或海拔（即从大地水准面起算得高度）, DEM 也经常称为 DTM ；要说明得就是由于“ Terrain 一”词得含义比较广泛,不同专业背景对“ Terrain 得”懂得也不一样, DTM 趋向于表达比 DEM 更为广泛得内容,详见后文得分析；4、 TIN 与规章 DEM 得区分 ：不规章三角网数字高程模型由连续得三角面组成,三角形得外形、大小取决于不规章分布得点得位置与密度；地势变化越简洁,采样点就越少, 就单元格就越大；反之

17、地势变化比较复杂,数据点分布比较密集,格网单元就越小；因此 TIN 与规章格网 DEM 显著不同之处在于TIN 模型不需要保护模型得结构规章性,不但能敏捷地随地势得复杂程度而转变格网单元大小,防止平整地势得数据冗余,而且又能按地势特点点线如山脊点、山谷线、地势变化线等表示地势特点；5、DEM 数据结构：规章格网 DEM 数据结构6、规章格网数据： 由于 DEM 得边界范畴一般就是规章矩形,而实际地势范畴却就是不规不就得规,仍就应三考虑角不在形讨论区D域E内M得 数D据EM 结高程构值得表示方法（无效区域数据）,一般就是给出一个特别得常数值,如 -9999 等；规章格网 DEM 得数据文件一般包

18、含用对 DEM 数据进行说明得数据头与 DEM 数据体两部分；1）数据头：一般包括定义 DEM 西南角起点坐标、坐标类型、格网间距、行列数、最低高程以及高程放大系数等内容； 2）数据体：按行或列分布记录得高程数字阵列；7、TIN ：在 TIN 模型中,基本得结构元素有三角形顶点、边与面；它们之间存在着点与线、点与面、线与面、面与面等拓扑关系；理论上,通过组成三角形得 三顶点可完整地表达三角形得构成以及三角形顶点、三角形边、三角形之间得拓扑关系下图,这种结构只需要两个文件,即三角形顶点坐标文件与组成三角形 三顶点（通常用点在坐标文件中得序号表示）文件；这种结构虽然简洁,三角形 结构元素得拓扑关系

19、却就是隐含得,不利于TIN 模型得检索与应用；因此,环绕三角形得拓扑关系描述而产生了多种TIN 得数据结构；8、TIN 模型得面结构最大特点就是： 由于储备了三角形之间得邻接关系, TIN内插、检索、等高线提取、显示以及局部结构分析都比较便利,不足之处就是：储备量较大,而且在 TIN 得编辑中要随时保护这种关系；9、DEM 数据猎取： 建立 DEM 得第一步就是猎取地势数据； DEM 得数据源与数据猎取方式对于 DEM 得最终质量至关重要； DEM 原始数据主要就是高程与平面位置数据,在可能条件下仍应包括各种地势结构线如山脊线、山谷线、断裂线等；另外, DEM 应用目得、数据采集效率与成本、技

20、术娴熟程度也影响着DEM 数据采集得方法与策略；/* 目前 DEM 得数据主要来源于地势图、摄影测量与遥感影像数据、地面测量、既有 DEM 数据等； */10、坡度：（1） 坡度就是地表外形最为重要得因子,通过坡度可以完整地势成地势曲面（Evans,1972； Strahler,1956）；（2） ）坡度就是地势曲面函数一阶微分得函数,表达了高程随距离变化得比率 （坡度定义为地面一点得切平面与水平面之间得夹角）,而坡度得变率就是地势曲面得二阶微分,进一步刻画了坡度得变化,从而反映地势得复杂程度；（3） ）大量得讨论说明,区域 DEM 高程精度与平均坡度值之间存在强相关,通过模型得平均坡度可猜测

21、DEM 得精度（ Ackermann,1979; Ley, 1986）；（4） ）坡度通过相互垂直得两个坐标轴方向得高程变化表达地势曲面局部单元得倾斜程度,也就就是通过地势表面得凸面与凹面来描述地势表面特性,即地表得陡峭方向与大小；11、TIN 数据得建立： 基于不规章三角网得数字高程模型（ Based on Triangulated Irregular Network DEM,简写为 Based on TIN DEM,俗称 TIN）就就是用一系列互不交叉、互不重叠得连接在一起得三角形来表示地势表面； TIN 就是 DEM 得又一个主要数据模型, TIN 得特点在其字面意思中表露无遗；11、T

22、IN 得三角剖分准就： TIN 得三角剖分准就就是指TIN 中三角形得形成法就, 它打算着三角形得几何外形与TIN 得质量；目前在 GIS、运算几何与运算机图形学邻域常用得三角剖分准就有以下几种（1） ）空外接圆准就： 在 TIN 中,过每个三角形得外接圆均不包含点集得其余任何点,如图 A 所示；（2） ）最大最小角准就： 在两相邻三角形形成得凸四边形中,这两三角形中得最小内角肯定大于交换凸四边形对角线后所形成得两三角形得最小内角,如图B 所示；（3） ）最短距离与准就： 图 C,最短距离与就就是指一点到基边两端得距离与为最小；（4） ）张角最大准就： 图 D,一点到基边得张角为最大；（5）

23、）面积比准就： 图 E,三角形内切圆面积与三角形面积或三角形面积与周长平方之比最小；（6） ）对角线准就： 图 F,两三角形组成得凸四边形得两条对角线之比；超过给定限定值时对三角形进行优化；理论上可以证明 ：张角最大准就、空外接圆准就及最大最小角准就就是等价得, 其余得就不然；三角形剖分准就就是建立三角形网络得基本原就 ,应用不同得准就将会得到不同得三角形网络； 一般而言, 应尽量保持三角网得唯独性, 即在同一准就下由不同得位置开头建立三角形网络, 其最终得外形与结构应就是相同得, 在这一点上,张角最大准就、 空外接圆准就及最大最小角准就可以做到； 对角线准就含有主观因素,现今使用已不多；通常

24、将在空外接圆准就、 最大最小角准就下进行三角剖分称为Delaunay 三角剖分,简称为 DT,同时空外接圆与最大最小角也就是Delaunay三角网得两个基本性质； DT 三角剖分就是目前应用最为广泛得三角剖分方法,其特性就是可最大限度防止狭长三角形得显现以及不管从何处开头构网都能保持三角形网络得唯独性, 这一点在实际应用中相当重要； 实际上, 在任何三角剖分准就下得到得 TIN,只要用 LOP法就（ 局部优化过程, local optimal procedure,LOP）对其进行优化处理,就能得到唯独得DT 三角网络； LOP法就就是 Lawson 在 1977 年提出得,其基本思想就是运用D

25、T 三角网得空外接圆性质对由两个有公共边得三角形组成得四边形进行判定；假如其中一个三角形得外接圆中含有第四个顶点,就交换四边形得对角线；LOP 局部优化过程12、无约束散点域得三角剖分算法与实现：* 分割合并算法*三角法生长算法*逐点插入算法1* 分割合并算法： 分割合并算法（ divide and conquer delaunay triangulation algorithm）得思想最早就是由 Shamos与 Hoey 在 1975 年提出得,并将其应用于 V- 图得构成（ V- 图就是 Vorinoi 图得简称,就是 DT 三角网得对偶图,为DT 三角网中相邻三角形边垂直平分线交点得连线

26、所形成得多边形,有关 V- 图得定义、性质与分割算法参见运算几何方面得书籍）；Lewis 与 Robinson 于 1978 年将该方法用来进行 DT 三角网得剖分,随后 Lee 与 Schachter、Dwyer 等相继对 Lewis 与 Robinson 得算法进行了优化与改进,其中Lee 与 Schachter于 1980 年得算法适合于无约束数据域得三角剖分,而Dwyer 于 1987 年得算法就考虑了带约束条件得 LOP 优化策略,因而能处理带约束条件得数据；分割合并算法得思想很简洁, 就就是将复杂问题简洁化, 第一将数据点分割成易于进行三角剖分得子集, 如一个子集中包括三个、 四个

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

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

29、盖整个区域得三角网,其主要步骤为：第一步,生成初始三角形；在数据点中任取一点A（该点一般就是位于数据点得 几何中心邻近）,并查找距离此点最近得点 B,两者相连形成初始基线 AB,如图；利用三角剖分准就（空外接圆准就或张角最大准就） ,在数据域中查找第三点 C, 从而形成第一个 Delaunay 三角形 ABC；其次步, 扩展形成三角网； 以初始三角形得三条边为初始基线, 利用空外接圆准就或张角最大准就,查找能与该三条初始基线形成Delaunay 三角形得 D、E、F 点；DBDBFAACCE留意：（ 1）初始边界将整个数据域分成两个部分,角形另一顶点得异侧范畴进行；例如如初始三角形为搜寻第三点

30、一般就是在初始三ABC,初始边界为AB,第三个顶点为 C,能与三角形 ABC共用 AB 边得另一三角形 ABD,D 点要位于 AB边得另一侧,而不能与C同侧,判定方法为：2）为防止三角形得交叉与重复,通过上述异侧点判别所选得第三点仍要进行进 一步得认定；其方法就是依据三角形任一条边最多只能与两个三角形所共用这个条件,进行三角形得全等比较, 即判定新三角形得三条边就是否被前面所形成得三角形共用过两次,假如就是,就新三角形无效,否就为有效三角形；逐点插入算法逐点插入算法得过程特别简洁,基本步骤为：第一步,定义包含全部数据点得初始包涵盒,并对该包涵盒进行初始三角剖分；其次步,对全部数据点进行循环,做

31、如下工作（设当前处理得数据点为 P）,在已存在得三角网中,查找包含 p 得三角形 t；p 与 t 得三个顶点相连,形成 t 得三个初始三角剖分；用 LOP算法对初始三角剖分进行优化处理；第三步,处理外围三角形；12、规章格网 DEM 读取实例：13 缓冲区分析算法：56、 缓冲区 buffer 概念：就是依据空间数据库中得点、线、面地理实体或规划目标,自动建立其四周肯定宽度范畴得多边形；分类：点缓冲区、线缓冲区、面缓冲区与复杂实体缓冲区；57、 步进拟合得思想 ,即圆弧弥合 得方法：（双侧平行线法）将圆心角等分,用等长得弦代替圆弧,即用匀称步长得直线段靠近圆弧段；等分得圆心角越小,步长越小,误

32、差越小；等分得圆心角越大,步长越大,误差越大；58、 凸角圆弧法 ,基本思想：在轴线得两端用半径为缓冲距得圆弧弥合； 在轴线得各转折点, 判定该点得凸凹性, 在凸侧用半径为缓冲距得圆弧弥合,在凹侧用与该点关联得前后两相邻线段得偏移量为缓冲距得两平行线得交点作为对应顶点；59、关于缓冲区自相交处理： （ P194） 自相交多边形得两种情形：岛屿,多边形当存在岛屿与重叠自相交多边形时, 最终运算得边线被分为外部边线与如干岛屿；缓冲区边线只绘制外围边线与岛屿轮廓；缓冲区检索时,在外边线所形成得多边形检索后,再扣除全部岛屿多边形；网络分析1 网络中基本组成部分：1） 结点 Node：网络中任意两条线段

33、得交点,属性如资源数量等链Link ：连接两个结点得弧段；供物体运营得通道,链间得连接关系由弧段 -结点拓扑数据结构来表达；属性如资源流淌得时间、速度等中心Center：网络中位于结点处,具有沿着链收集与发放资源才能得设施,如邮局、电站、水库等站点Stop：资源沿着网络路径流淌时被安排或收集得位置,如邮件投放点、公共汽车站,属性如资源需求量转向点拐点, Turn：链路相交处,资源流向发生转变得点2）边/边集3） 图：就是一个非空得有限结点与有限边得集合；4） 网络5） 流：指网络中任意一条弧得物流量；2、给定单源点得最短路径得求解（三步）:1）选一顶点 v 为源点,并视从源点 v 动身得全部边

34、为到各顶点得最短路径（确定数据结构： 由于求得就是最短路径, 所以就要用一个记录从源点v 到其它各顶点得路径长度数组dist, 开头时,dist 就是源点 v 到顶点 i 得直接边长度, 即 dist 中记录得就是邻接阵得第v 行；设一个用来记录从源点到其它顶点得路径数组 path,path 中存放路径上第 i 个顶点得前驱顶点）；2） 在上述得最短路径 dist 中选一条最短得,并将其终点（即 ）k 加入到集合 s 中；3） 调整 T 中各顶点到源点 v 得最短路径； 由于当顶点 k 加入到集合 s 中后, 源点 v 到 T 中剩余得其它顶点 j 就又增加了经过顶点 k 到达 j 得路径 ,

35、这条路径可能要比源点 v 到 j 原先得最短得仍要短；调整方法就是比较distk+gk,j 与 distj ,取其中得较小者；4） 再选出一个到源点 v 路径长度最小得顶点 k,从 T 中删去后加入 S 中,再回去到第三步,如此重复,直到集合S 中得包含图 G 得全部顶点；3（要求把握基本概念与步骤,她们得区分）带权图分为有向与无向, 无向图得最短路径又叫做最小生成树, 有 prime算法与 kruskal 算法；有向图得最短路径算法有dijkstra 算法与 floyd 算法；（一） Floyd 算法P209：Floyd 算法又称为弗洛伊德算法,插点法,就是一种用于查找给定得加权图中多源点之

36、间最短路径得算法；基本思想如下：从任意节点 A 到任意节点 B 得最短路径不外乎 2 种可能,1 就是直接从 A 到 B,2 就是从 A 经过如干个节点 X 到 B；所以,我们假设 DisAB 为节点 A 到节点 B 得最短路径得距离,对于每一个节点X,我们检查 DisAX + DisXB DisAB就是否成立,假如成立,证明从 A 到 X 再到 B 得路径比 A 直接到 B 得路径短,我们便设置 DisAB = DisAX + DisXB ,这样一来,当我们遍历完全部节点X, DisAB 中记录得便就是 A 到 B 得最短路径得距离；步骤： 1）从任意一条单边路径开头；全部两点之间得距离就是

37、边得权, 假如两点之间没有边相连,就权为无穷大；2）对于每一对顶点 u 与 v,瞧瞧就是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知得路径更短；假如就是更新它；把图用邻接矩阵 G 表示出来,假如从 Vi 到 Vj 有路可达,就Gi,j=d ,d 表示该路得长度； 否就 Gi,j= 无穷大；定义一个矩阵 D 用来记录所插入点得信息, Di,j 表示从 Vi 到 Vj 需要经过得点,初始化Di,j=j ；把各个顶点插入图中,比较插点后得距离与原先得距离,Gi,j = min Gi,j, Gi,k+Gk,j ,假如 Gi,j 得值变小,就 Di,j=k ；在 G 中包含有两点之间最短道路

38、得信息,而在 D 中就包含了最短通路径得信息；比如,要查找从 V5 到 V1得路径；依据 D,假如 D5,1=3就说明从 V5到 V1 经过 V3 ,路径为 V5,V3,V1 ,假如 D5,3=3,说明 V5 与 V3 直接相连,假如D3,1=1,说明 V3 与 V1直接相连；试验作业作业 1：试验 1空间数据 矢量 得采集作业 2：试验 2 空间数据得储存作业 3：试验三 运算几何基础（ 1） 折线拐向判定作业 4：试验三 运算几何基础（ 2） 地图量算作业 5：试验三 运算几何基础（ 3） 三角形面积量算作业 6：试验四（一）坐标变换作业 7： 试验四（二）格式转换作业 8：试验四（三）矢量数据压缩作业 9：试验四（四）栅格数据压缩作业 10：试验五 空间数据得内插