GIS算法复习

算法概念：指的是完成一个任务所需要的具体步骤和方法 GIS算法特点：

①GIS算法用来解决地学领域中的问题，但是算法不是孤立的，GIS的算法借鉴和发展了其他学科的研究成果；

②GIS算法是用来处理海量地理信息数据的，涉及许多复杂的空间运算，不同于简单的数据查询、编辑等操作；

③地理信息系统与实际应用、工程开发有着密切的关系，与一般算法的重要区别在于所要处理问题的不确定性，无法被定性、定量成一个纯算法问题 GIS算法是整个地理信息科学的核心

基本的GIS空间数据结构、各种各样的空间拓扑关系

必需的GIS空间关系的表达与描述到各种各样的空间拓扑关系 从高级的时态多维GIS到GIS空间数据挖掘与知识发现

算法设计的任务是对各类具体问题设计良好的算法以及研究设计算法的规律和方法。 常用的算法有穷举搜索法、递归法、回溯法、贪心法、分治法等

算法分析:算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论各种复杂度，以探讨某种具体算法适用于哪类问题，或某类问题宜采用哪些解法 算法设计原则:正确性 确定性 清晰性

算法复杂性度量:问题的规模 时间复杂性 空间复杂性

元运算:对于任何计算步骤，不管输入数据或执行的算法，它的代价总是以一个时间常量为上界，则称该计算步骤为元运算

空间：为了解求问题的实例而执行的计算步骤所需要额内存空间（或字）数目，不包括用来存储输入的空间。算法空间复杂性不可能超过运行时间的复杂性

算法的评价估计:算法运行时间 最坏情况与平均情况分析 平摊分析 输入大小和问题实例 基本运算：如果算法中一个元运算具有最高频度，所有其他元运算频度均在其频度的常数倍内，则称这个运算为基本运算

算法性能的测度通常是输入大小、顺序和分布的函数

关系运算：指的是用于检验两个几何对象的特定的拓扑空间关系的逻辑方法 4交集模型：最大维数在一维和二维空间中两个几何体的空间关系研究一般只考虑对比内部和边界的交集，并定义为4交集模型。

9交集模型：4交集模型考虑输入几何体的外部时就扩展为9交集模型 优点：基于模式矩阵的空间关系的确定可以检测大部分的空间关系，并且能对特殊的空间关系进行检测。缺点：语言抽象化，不人性化

人性化的语言定义的五种用于DE-9IM的空间关系命名 ：相离、相接、相交、真包含和叠置

判断点是否在多边形内常用算法：射线法（奇偶法）；转角法：环绕数（多边形环绕点的次数）为0，则点在多边形外，否则，点在多边形内

实践中常使用的有地理坐标系，球面极坐标系和球面直角坐标系，地理坐标系在GIS应用最为广泛

仿射变换是使用最多的一种几何纠正方式。在保留线条平行条件下，仿射转换允许对长方形目标做旋转、平移、倾斜和不均匀缩放

地图投影变换的实质是建立两平面场之间点的一一对应关系，其方法通常分为解析变换法、数值变换法和数值解析变换法三类 曲率的倒数就是曲率半径

子午圈：包含旋转轴的平面与椭球面相截所得的椭圆

法截面：过椭球表面上任一点作法线，通过法线的平面所截成的截面

主法截面：通过一点的法线可以做出无穷多个法截面，为说明椭球体在某点上的曲率起见，通常研究两个相互垂直的截面曲率，这种相互垂直的法截面称为主法截面 垂直于子午圈的截面称为卯酉圈截面

矢量线的栅格化方法：八方向栅格化 全路径栅格化 恒密度栅格化

矢量面格式向栅格面格式转换又称为多边形填充，就是在矢量表示的多边形边界内部的所有栅格点上赋以相应的多边形编码，从而形成栅格数据阵列，方法:内部点扩散算法 射线算法和扫描算法 边界代数算法

内部点扩散算法特点：扩散算法程序设计比较复杂，并且在一定的栅格精度上，如果复杂图形的同一多边形的两条边界落在同一个或相邻的两个栅格内，会造成多边形不连通，这样一个种子点不能完成整个多边形的填充

扫描线算法可以分为4个步骤：求交；排序；交点配对；区域填色

边界代数多边形填充算法是一种基于积分思想的矢量格式向栅格格式转换算法，它适合于记录拓扑关系的多边形矢量数据转换为栅格结构。优点：因此算法简单、可靠性好，各边界弧段只被搜索一次，避免了重复计算。边界代数法不可以完全替代其他算法，在某些场合下，还是要采用种子填充算法和射线算法，前者应用于在栅格图像上提取特定的区域；后者则可以进行点和多边形关系的判断

栅格格式向矢量格式转换通常包括以下4个基本步骤：边界提取；边界线追踪；拓扑关系生成；去除多余点及曲线圆滑

线状栅格数据需要细化，以提取其中轴线，这是因为：中轴线是栅格数据曲线的标准化存储形式；实现细化是将栅格曲线矢量化的前提；在有些算法中可以提高计算精度

线状栅格数据的细化算法：第一类是基于距离变换，首先得到骨架像元，然后跟踪距离变换图中的“山脊线”，并将其作为中轴线；第二类是基于在不破坏栅格拓扑连通性的前提下，按对称的原则删除影像边缘的栅格点

多边形栅格转矢量的双边界搜索算法基本思想是通过边界提取，将左右多边形信息保存在边界点上，每条边界弧段由两个并行的边界链组成，分别记录该边界弧段的左右多边形编号。边界线搜索采用2×2栅格窗口，在每个窗口内的4个栅格数据的模式，可以唯一地确定下一个窗口的搜索方向和该弧段的拓扑关系，极大地加快了搜索速度，拓扑关系 也很容易建立。步骤：边界点和结点提取；边界线搜索与左右多边形信息记录；多余点去除

区域跟踪算法中，对区域的描述由两部分组成：区域外轮廓和内部孔洞。因此运用传统的区域跟踪算法完整地跟踪一个区域有如下3个步骤：确定区域外轮廓跟踪的起始点；对区域的外轮廓进行跟踪和记录；对区域内部的所有孔洞进行扫描跟踪和记录 单边界搜索算法是通过对传统的区域跟踪算法进行改进而形成的。可以搜索并跟踪出一幅图像中的所有区域并生成区域间的主要空间拓扑关系

单边界搜索算法的流程可描述如下： ①搜索、跟踪第一层所有的区域并记录外轮廓和内部孔洞信息；②根据跟踪到的孔洞信息找出下一层中未跟踪过的区域的外轮廓跟踪起始点（即找出一个新区域）； ③跟踪找到的新区域并记录其外轮廓和内部孔洞信息；④重复②?③步，直到该层所有区域都已被跟踪完毕；⑤重复②?④步，直到整幅图像内所有区域都已被跟踪完毕。

节点：两个以上相邻目标对象的交汇处。 空间索引：指依据空间对象的位置和形状或空间对象之间的某种空间关系，按一定的顺序排列的一种数据结构，其中包括空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针目的：对存储在介质上的数据位置信息的描述，用来提高系统对数据获取的效率。提出原因：计算机内外存访问的时间差；GIS数据的复杂性

空间数据索引的研究关键是设计索引域

B+树是B树的改进，在B树中，数据指针可以出现在树的任一级。在B+树中，数据指针仅出现在叶结点。B+树的叶结点的结构与内结点的结构不同。在内结点中出现的每一个关键字，在叶结点中都存在

常规四叉树缺点：所占的内外存空间比较大，原因在于它不仅要记录每个结点值，还需记录结点的一个前趋结点及四个后继结点，以反映结点之间的联系。对栅格数据进行运算时，还要作遍历树结点的运算。这样就增加了操作的复杂性。所以实际上，在地理信息系统或图像分割中不采用常规四叉树，而用线性四叉树

线性四叉树不像常规四叉树那样存储树中各个结点及其相互间关系，而是通过编码四叉树的叶结点来表示数据块的层次和空间关系。叶结点都具有一个反映位置的关键字，亦称位置码，表示它所处位置。实质是把原来大小相等的栅格集合转变成大小不等的正方形集合，并对不同尺寸和位置的正方形集合赋予一个位置码 线性四又树的编码方法：基于深度和层次码的线性四叉树编码；基于四进制的线性四叉树编码；四叉树的十进制编码

空间数据内插方法：几何方法、统计方法、空间统计方法、函数方法、随机模拟方法、物理模型模拟方法和综合方法（看看各自的原理与优缺点）

空间数据内插：根据已知的空间数据估计(预测)未知空间的数据值

空间数据内插目标：缺值估计：估计某一点缺失的观测数据，以提高数据密度。内插等值线：以等值线的形式直观地显示数据的空间分布。数据网格化：把无规则分布的空间数据内插为规则分布的空间数据集，如规则矩形格网、三角网等

空间数据内插的分类依据：确定或随机；点与面；全局或局部等标准分类；内插方法的基本假设和数学本质。

多项式回归分析是描述长距离渐变特征的最简单方法。基本思想是用多项式表示的线或面按最小二乘法原理对数据点进行拟合，线或面多项式的选择取决于数据是一维还是二维 反距离权重插值算法原理：是一种局部插值方法，它假设未知值的点受较近控制点的影响比较远控制点的影响更大。这种方法通常用在计算机辅助制图方面。影响的程度(或权重)用点之间距离乘方的倒数表示。乘方为1.0意味着点之间数值变化率为恒定，该方法称为线性插值法

双线性插值算法是一种数字图像处理、DEM数据处理等方面使用比较多的局部插值方法 Delaunay三角网与Voronoi图是两个被普遍接受和采用的分析研究区域离散数据的有利工具

TIN的用途与优点：是表达表面的一种有效方法，具有高效率的存储，数据结构简单，与不规则的地面特征和谐一致，可以表示线性特征和叠加任意形状的区域边界，易于更新，可适应各种分布密度的数据等优点

TIN与栅格的比较：栅格也被用来表面建模，但TIN在表面发生显著变化处体现数据密度改变方面更有优势

DTM(数字地形模型)模型主要由规则网格(栅格)与不规则网格(栅格)两种数据格式来表示 TIN的特点：TIN是由点生成的，每个点具有一个反映高程值的连续型实数值。当然，也可以使用TIN来表示其他类型的表面值，如化学物质的浓度、地下水位或降水量。 TIN是根据采样数据点的值计算出来的，表现为一个连续的三维的表面。TIN是一系列非重叠的三角形或面，这些三角形或面完全充填一个区域。TIN表现的是具有矢量要素（点、线、面）的表面，可以精确地模拟具有断线(beeak-line)的表面中的不连续区域。

Delaunay三角网是一系列相连的但不重叠的三角形的集合，而且这些三角形的外接圆不包含这个面域的其他任何点，两个特有性质：保证最邻近的点构成三角形；最大最小角性质