GIS算法原理知识点总结

1GIS算法原理知识点总结算法设计和分析：1、算法设计的原则：正确性：若一个算法本身有缺陷，那么它将不会解决问题；确定性：指每个步骤必须含义明确，对每种可能性都有确定的操作。清晰性：一个良好的算法，必须思路清晰，结构合理。2、算法的复杂性包括：时间复杂性和空间复杂性。3、时间复杂性：用一个与问题相关的整数量来衡量问题的大小，该整数量表示输入数据量的尺度，称为问题的规模。利用某算法处理一个问题规模为n的输入所需要的时间，称为该算法的时间复杂性。4、算法的概念：算法是完成特定任务的有限指令集。所有的算法必须满足下面的标准：输入输出明确性有限性有效性GIS算法的计算几何基础1、理解矢量的概念：如果一条线段的端点是有次序之分的,我们把这种线段称为有向线段(directedsegment)。如果有向线段p1p2的起点P1在坐标原点，我们可以把它称为矢量P2。5.矢量叉积：计算矢量叉积是直线和线段相关算法的核心部分。设矢量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）。PXQ0,则P在Q的顺时针方向；Op1p22PXQ0,则P在Q的顺逆针方向；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不相交，显然两线段不会相交p0p1p2p0p1p2p0p1p2基（p2-p0）×(P1-p0)0，则P0P1在P1点拐向左侧后得到P1P2基（p2-p0）×(P1-p0)=0，则P0P1P2三点共线基（p2-p0）×(P1-p0)0，则P0P1在P1点拐向右侧后得到P1P23跨立实验：如果两线段相交，则两线段必然相互跨立对方。若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说明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.判断线段、折线、多边形是否在矩形中：因为矩形是个凸集，所以只要判断所有端点都在矩形就行了。11.判断矩形是否在矩形中：只要比较左右边界和上下边界就行了。12.判断圆是否在矩形中：圆心在矩形中且圆的半径小于或等于圆心到矩形四边的距离的最小值。13.判断点是否在多边形内：1)射线法：一条射线从点P开始，穿过多边形的边界的次数称为交点数目。当交点数目是偶数时，点P在多边形外部；否则，为奇数时，在多边形内部。4射线法要考虑几种特殊的情况，并且射线法适用于凸多边形2)转角法：多边形环绕点P的次数称为环绕数，环绕数为0时，点P在多边形外部，否则在多边形内部。14.判断线段是否在多边形内：（折线是判断它的每条线段）条件一：线段的两个端点都在多边形内条件二：线段和多边形的所有边都不内交。15.判断多边形否在多边形内：只要判断多边形的每条边是否都在多边形内即可。判断有m个顶点的多边形是否在一个有n个顶点的多边形内的复杂度为O(mXn)16.判断矩形是否在多边形内：将矩形转化为多边形，然后再判断是否在多边形内。17.判断圆是否在多边形内：计算圆心到多边形每条变边的最短距离，若该距离大于或等于圆半径，则该圆在多边形内。18.判断点是否在圆内：计算圆心到该点的距离，若小于或等于半径，则该点在圆内。19.判断线段、折线、矩形、多边形是否在圆内：因为圆是凸集，所以只要判断是否每个顶点都在圆内即可。20.判断圆是否在圆内：设两圆为O1,O2,半径为r1,r2。先比较r1,r2的大小，若r1r2,则O2不可能在O1内；若两圆心距离大鱼r1-r2，则O2不在O1内；反之，O2在O1内。21.距离交会:是以两个已知控制点为中心，分别以目标点与两已知控制点的距离为半径划圆，交会点即为要求目标点（注意方向二选其中一个）。22.距离量算算法的实现：5空间数据的变换算法1.了解平面坐标变换的几种形式:2.仿射变换：它是使用最多的一种几何纠正方式。在保留线条平行条件下，仿射变换允许对长方形目标做旋转、平移、倾斜和不均匀缩放。旋转指在原点旋转x和y轴；平移是指把源点移动到新的位置；倾斜是指以一个倾向将形状改变为平行四边形；不均匀缩放是指在x或y方向同时或单独增大和缩小6比例尺。yBxBBYyAxAAXmBmBmAmABymxmYAymxmXyyxxyyxx21021020cos2,sin1sin,cos1)cos()sin()sin()cos(0平移变换实例代码：比例变换实现代码：7旋转变换实现代码：83.相似变换：图形的相似变换是指由一个图形到另一个图形，在改变的过程中保持形状不变（大小方向和位置可变）的图形。图形相似变换的性质：图形的相似变换不改变图形中每一个角的大小；图形相似变换后对应线段都扩大（或缩小）相同的倍数，这个数叫相似比。相似变换面积：经相似变换的像与原图的面积等于相似比的平方。相似变换的分解：任何相似变换可以分解为放缩，平移，旋转和翻转变换的复合。相似变换是仿射变换的一种特殊情况，也就是在仿射变换中去除错位变换这个因子后的结果。yAxBBYyBxAAXmBmAByxmYAyxmX1101100sin1cos1)cossin()sincos(04.矢量转栅格：点：简单的坐标变换线：线的栅格化面：线的栅格化+面填充面(多边形)的填充方法12、扫描法3、射线法45、边界代数算法栅格表示法的精度与分辨率有关。在图(a)、(b)、(c)中，栅格的分辨率分别为7*5，15*11，24*13。分辨率的大小与下面两个问题有关：95.栅格矢量化：从栅格单元转换为几何图形的过程为矢量化；（一）要求（矢量化过程应保持）：1）栅-矢转换为拓扑转换，即保持实体原有的连通性、邻接性等；2）转换实体保持正确的外形。（二）方法方法一，实际应用中大多数采用人工矢量化法，如扫描矢量化，该法工作量大，成为GIS数据输入、更新的瓶颈问题之一。方法二，程序转化转换（全自动或半自动）过程为：1、边界提取2、二值化3、二值图像的预处理4、细化:[1）剥皮法2)骨架法]5、跟踪6、拓扑化6.”矢量点”转栅格实例：10116.矢量数据的压缩：矢量数据的压缩包括两个方面的内容，一是在不扰乱拓扑关系的前提下，对采样点数据进行合理的抽稀。二是对矢量坐标数据重新进行编码，以减少所需要的存储空间。1）间隔取点法：每隔K个点取一点，或舍去那些比规定距离更近的点，首末点一定要保留。2）垂距法：临界值隔点法临界值法123）光栅法：限差原始曲线对点2测试距离大于规定的限差点2保留对点3测试距离小于规定的限差3点舍去，化简结果23423423423414111124p1PnP4P3P2aad/2d/2c1c2bb134）道格拉斯—普克法：2°、若p3点在扇形内，则舍去p2点。然后连接p1和p3，过p3作p1p1的垂线，该垂线与前面定义的扇形边交于c1和c2。在垂线上找到b1和b2点，使p3b1＝p3b2＝d／2，若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°。如此继续下去，直到整个点列检测完为止。所有被保留的节点(含首、末点)，顺序地构成了简化后的新点列。光栏法的基本思想是(上图)：定义一个扇形区域，通过判断曲线上的点在扇形外还是在扇形内，确定保留还是舍去。设曲线上的点列为｛pi｝，i＝1，2，…，n，光栏口经为d，可根据压缩量的大小自己定义，则光栏法的实施步骤可描述为：1°、连接p1和p2点，过p2点作一条垂直于p1p2的直线，在该垂线上取两点a1和a2，使a1p2＝a2p2＝d／2，此时a1和a2为“光栏”边界点，p1与a1、p1与a2的连线为以p1为顶点的扇形的两条边，这就定义了一个扇形(这个扇形的口朝向曲线的前进方向，边长是任意的)。通过p1并在扇形内的所有直线都具有这种性质，即p1p2上各点到这些直线的垂距都不大于d/2。首先将一条曲线首、末点连一直线，求出各点到该直线的距离，选其最大者与规定的临界值相比较若大于临界值，则离该直线距离最大的点保留，否则，将直线两端间各点全部舍去，并将原线条分成两部分，对每部分线条再实施该抽稀过程，直到结束。抽稀结果点数随选取限差临界值的增大而减少，应用时应根据精度要求来确定抽稀限差临界值，以获得最好的结果。即道格拉斯—普克（Douglas--peuker）算法。P1PNsplitpoint147．栅格数据的压缩：1）链式编码：P1PNResult第一轮垂距第二轮垂距弦阈值152）游程编码：所谓游程是指按行的顺序连续且属性值相同的若干栅格。游程长度的记录方式有两种①记录每个游程起（迄）列号②记录每个游程像元数163）块式编码：块式编码是将游程扩大到两维情况，把多边形范围划分成若干具有同一属性的正方形，然后对各个正方形进行编码。块式编码的数据结构由初始位置（行列号）、半径和属性代码组成。173）四叉树编码：四叉树又称四元树或四分树，是最有效的栅格数据压缩编码方法之一。四分树将整个图像区域逐步分解为一系列方形区域，且每一个方形区域具有单一的属性。最小区域为一个象元。188.隔点取样法实例：19空间数据内插算法1.空间数据内插的定义：根据已知的空间数据估计(预测)未知空间的数据值。2.空间数据内插目标：①缺值估计：估计某一点缺失的观测数据，以提高数据密度。②内插等值线：以等值线的形式直观地显示数据的空间分布。③数据网格化。把无规则分布的空间数据内插为规则分布的空间数据集，如规则矩形格网、三角网等。3.空间内插法的种类：几何方法、统计方法、空间统计方法、函数方法、随机模拟方法、物理模型模拟方法和综合方法。4.优缺点比较：每一种方法均有其适用范围、算法和优缺点，因此，没有绝对最优的空间内插方法。5.如何选择：对数据进行空间探索分析，根据数据的特点，选择最优方法；同时，应对内插结果进行严格的检验。6空间数据内插的分类依据：①确定或随机；②点与面；③全局或局部等标准分类；④内插方法的基本假设和数学本质。3.反距离权重插值算法：是一种局部插值算法，它假设未知值的点受较近控制点的影响比较远控制点的影响更大。反距离权重方法的通用方程是：式中，z0为点0的估计值；zi为控制点i的z值；dj为控制点i与点0间的趾离；s为在估算中用到的控制