GIS算法原理知识点总结

GIS算法原理学问点总结算法设计和分析：1、算法设计的原则：正确性：假设一个算法本身有缺陷，那么它将不会解决问题；清楚性：一个良好的算法，必需思路清楚，构造合理。2、算法的简单性包括：时间简单性和空间简单性。3、时间简单性：用一个与问题相关的整数量来衡量问题的大小，该整数量n的输入所需要的时间，称为该算法的时间简单性。4、算法的概念：算法是完成特定任务的有限指令集。全部的算法必需满足下面的标准：输入输出明确性有限性有效性GIS算法的计算几何根底1、理解矢量的概念：假设一条线段的端点是有次序之分的,我们把这种线段称为有向线段(directedsegmentp1p2P1P2。p2p1p2p15.矢量叉积：计算矢量叉积是直线和线段相关算法的核心局部。P=〔x1,y1Q〔x2,y2,则矢量叉积定义为0,0p1P×〔×P〕〔Q。6：折线段的拐向推断方法，可以直接由矢量叉积的性质推号便可以给出折线段的拐向。p2 p2 p2p1 p1p1p0基〔p2p0〕×(P1p0)<0，P0P1P1点拐向左侧后得到P1P2

p0基〔p2p0〕×(P1p0)=0，P0P1P2三点共线

p0基〔p2p0〕×(P1P1点拐向右侧后得到P1P2理解矢量的概念通过矢量差积的方法就可以推断的拐向了。7.推断点是否在线段上QP1P2：(Q-P1)X(P2-P1)=0Q保证点不在线段延长线或反向延长线上。8、推断两线段是否相交〔算法一：快速排斥试验：P1P2为对角线的矩形为RQ1Q2为对角TRT不相交，明显两线段不会相交跨立试验：p1p2Q1Q2，和〔P2-Q2〕位于矢量〔Q2-Q1〕的两侧，则〔P1-〕×〕〕〔〈0。当〕×P1Q1Q2上；同理〔Q2-Q1〕P2Q1Q2上。Q1Q2的依据是：〔P1-Q1〕×〔Q2-Q1〕〔Q2-Q1〕〔P2-Q1≥0。P1P2的依据是〔Q1-P1〕×〔P2-P1〕〔P2-P1〕×〔Q2-P1〕≥0。留意在进展“跨立推断”的时候是进展两次跨立推断推断矩形内是否包含点：只要推断该店的横坐标和纵坐标是否都夹在矩形的左右边和上下边之间。推断线段、折线、多边形是否在矩形中：由于矩形是个凸集，所以只了。推断矩形是否在矩形中：只要比较左右边界和上下边界就行了。：圆心在矩形中且圆的半径小于或等于圆心到矩形四边的距离的最小值。推断点是否在多边形内：P开头，穿过多边形的边界的次数称为交点数目。边形内部。射线法要考虑几种特别的状况，并且射线法适用于凸多边形0P在多边形外部，否则在多边形内部。〔折线是推断它的每条线段〕条件一：线段的两个端点都在多边形内条件二：线段和多边形的全部边都不内交。推断多边形否在多边形内：m个顶点的多边形是O(mXn)推断矩形是否在多边形内：将矩形转化为多边形，然后再推断是否在多边形内。推断圆是否在多边形内：计算圆心到多边形每条变边的最短距离，假设该距离大于或等于圆半径，则该圆在多边形内。推断点是否在圆内：计算圆心到该点的距离，假设小于或等于半径，则该点在圆内。由于圆是凸集，所以只要推断是否每个顶点都在圆内即可。推断圆是否在圆内：r1,r2r1<r2,O2不行能r1-r2O2O1内；反之，O2O1内。距离交会:是以两个掌握点为中心，分别以目标点与两掌握点的距离为半径划圆，交会点即为要求目标点〔留意方向二选其中一个。距离量算算法的实现：空间数据的变换算法了解平面坐标变换的几种形式:仿射变换：它是使用最多的一种几何订正方式。在保存线条平行条件下，原点旋转x和y轴；平移是指把源点移动到的位置；倾斜是指以一个倾xy方向同时或单独增XYXY大和缩小比例尺。xx 0(myyA1mxcos,AmB1mysin,B2m2xsiny0XYAAxAy0 1 2BBxBy0 1 2平移变换实例代码：比例变换实现代码：旋转变换实现代码：相像变换：图形的相像变换是指由一个图形到另一个图形，在转变的过程中保持形状不变〔大小方向和位置可变〕的图形。图形相像变换的性质：图形的相像变换不转变图形中每一个角的大小；图形相像变换后对应线段都扩〔或缩小相像比。相像变换面积：经相像变换的像与原图的面积等于相像比的平方。XYm(xcosXYm(xcosysin)A0m(xsinycos)BB1msin0XYAAxBy0 1 1BBxAy0 1 1点：简洁的坐标变换线：线的栅格化点：简洁的坐标变换线：线的栅格化面：线的栅格化+的填充方法1、内部点集中法〔种子集中法〕2、扫描法3、射线法4、复数积分法5、边界代数算法栅格表示法的精度与区分率有关。在图(a)、(b)、(c)中，栅格的区分率分别为7*5，15*11，24*13。区分率的大小与下面两个问题有关：栅格矢量化：从栅格单元转换为几何图形的过程为矢量化；〔一〕要求〔矢量化过程应保持：栅->矢转换为拓扑转换，即保持实体原有的连通性、邻接性等；转换实体保持正确的外形。〔二〕方法GIS数据输入、更的瓶颈问题之一。方法二，程序转化转换〔全自动或半自动〕12、二值化34、细化:[1〕剥皮法2)骨架法]5跟踪 扑化”矢量点”转栅格实例：矢量数据的压缩：矢量数据的压缩包括两个方面的内容，一是在不扰乱拓扑关系的编码，以削减所需要的存储空间。1〕间隔取点法：每隔K个点取一点，或舍去那些比规定距离更近的点，首末点肯定要保存。临界值隔点法临界值法2〕垂距法：临界值隔点法临界值法2〕垂距法：原始曲线 4312 对点2测试距离大于规定的限差4312保存24312 3测试距离小于规定的限差432限差41 432限差412光栅法：c1a1 d/2P2p1a2

P4Pnb1d/2P3c2b2(上图)：定义一个扇形区域，通过推断曲线上的点在扇形外还是在扇形内，确定保存还是舍去。设曲线上的点列为｛i，＝1，2，…，d，可依据压缩量的大小自己定义，则光栏法的实施步骤可描述为：p2p2p1p2a1a2，使a1a2为“光栏”边界点，p1a1、p1a2的连线为以p1为顶点的扇形的两条边，这就定义了一个扇形(这个扇形的口朝向曲线的前进方向，边长是任p1p2上各点到这些直线的垂距都d/2。点在扇形内，则舍去p2点。然后连接p1和p3，过p3作p1p1的垂线，该垂线扇形边交于c1和c2。在垂线上找到b1和b2点，使p3b1＝p3b2＝d／2，假设图443 外面，则用c1或c2取代(图443 中由c2取p1b1和p1c2定义一个的扇形，这固然是口径(b1c2)缩小了的“光栏。、检查下一节点，假设该点在扇形内，则重复第(2)步；直到觉察有一个节点在最定义的扇形外为止。、当觉察在扇形外的节点，如图443 中的p4，此时保存p3点，以p3作为起点，重个点列检测完为止。全部被保存的节点(含首、末点)，挨次地构成了简化后的点列。道格拉斯—普克法：差临界值，以获得最好的结果。即道格拉斯—普克〔Douglaspeuker〕算法。splitpointPsplitpointPNP1ResultP1

PN弦第一轮垂距其次轮垂距阈值栅格数据的压缩：链式编码：游程编码：所谓游程是指按行的挨次连续且属性值一样的假设干栅格。游程长度的记录方式有两种①记录每个游程起〔迄〕列号②记录每个游程像元数块式编码的数据构造由初始位置〔行列号、半径和属性代码组成。3〕四叉树编码四叉树又称四元树或四分树，是最有效的栅格数据压缩编码方法之一。四分树将整个图像区域逐步分解为一系列方形区域，且每一个方形区域具有单一的属性。最小区域为一个象元。隔点取样法实例：4.双线性插值算法：4.双线性插值算法：是一种数字图像处理、DEM数据处理等方面使用较多的局部插值算法。8.5所示，设f(0，0)=Z1，f(1，0)=Z3，f(1，1)Z4f(x,y)点的值，其中f(0，0)、f(1，0)、f(0，1)、f(1，1)代入双线性内插方程：f(x,y)=ax+by+cxy+da、b、c、dx,y代入，解得f(x,y)。1.空间数据内插的定义：依据的空间数据估量(推测)未知空间的数据值。空间数据内插目标：空间数据内插目标：①缺值估量：估量某一点缺失的观测数据，以提高数据密度。②内插等值线：以等值线的形式直观地显示数据的空间分布。如规章矩形格网、三角网等。空间内插法的种类：几何方法、统计方法、空间统计方法、函数方法、随机模拟方法、物理模型模拟方法和综合方法。优缺点比较：每一种方法均有其适用范围、算法和优缺点，因此，没有确定最优的空间内插方法。5.如何选择：对数据进展空间探究分析，依据数据的特点，选择最优方法；同时，应对内插结果进展严格的检验。6空间数据内插的分类依据：①确定或随机；②点与面；③全局或局部等标准分类；式中，z式中，z00的估量值；zii的zs为在估算中用到的掌握点的数目；K为指定的幂。3.3.反距离权重插值算法：是一种局部插值算法，它假设未知值的点受较近掌握反距离权重方法的通用方程是：55反距离权重插值实例：TIN、DEM、DAT数字高程模型概念与理解：高程常常用来描述地形外表的起伏形态，传统的高程模型用计算机来表达时，称为数字高程模型。是通过有限的地形高程数据实现对地形曲面的数字化模拟或者ElevationModelDEM。3.DEMDTM：〔即从大地水准面起算的高度M也常常称为对“Terrain”的理解也不一样，DTMDEM更为广泛的内容，详见后文的分析。TINDEM的区分：不规章三角网数字高程模型由连续的三角面组成，三角形的格就越大；反之地形变化比较简单，数据点分布比较密集，格网单元就越小。TINDEMTIN模型不需要维护模型的构造规章性，不但形特征点线如山脊点、山谷线、地形变化线等表示地形特征。DEM数据构造：规章格网DEM数据构造不规章三角形DEM数据构造6.6.规章格网数据：由于DEM的边界范围一般是规章矩形，而实际地形范围却是不规章的还应考虑不在争论区域内的M高程值的表示方〔无效区域数据一般是给出一个特别的常数值，如9999 规章格网DEM的数据文件一般包数据进展说明的数据头和DEM数据体两局部。数据头：一般包括定义DEM西南角起点坐标、坐标类型、格网间距、行列数、最低高程以及高程放大系数等内容；2〕数据体：按行或列分布记录的高程数字阵列。TIN：TIN模型中，根本的构造元素有三角形顶点、边和面。它们之间存在系(以下图)通常用点在坐标文件中的序号表示〕文件。这种构造虽然简洁，三角形构造元素的拓扑关系却是隐含的，不利于TINTIN的数据构造。TIN模型的面构造最大特点是：由于存储了三角形之间的邻接关系，TIN内插、检TIN的编辑中要随时维护这种关系。DEM数据猎取：建立DEM的第一步是猎取地形数据。DEM的数据源和数据猎取DEM数据采集的方法和策略。DEM数据等。*/坡度：坡度是地表形态最为重要的因子，通过坡度可以完整地形成地形曲面〔Evans,1972；；坡度是地形曲面函数一阶微分的函数，表达了高程随距离变化的比率〔坡面的二阶微分，进一步刻画了坡度的变化，从而反映地形的简单程度；大量的争论说明，区域DEM高程精度与平均坡度值之间存在强相关，通过M的精度〔；坡度通过相互垂直的两个坐标轴方向的高程变化表达地形曲面局部单元的的陡峭方向和大小。TIN基于不规章三角网的数字高程模型〔BasedonTriangulatedTINDEM的又一个主要数据模型，TIN的特点在其字面意思中表露无遗。TIN的三角剖分准则：TINTIN中三角形的形成法则，它打算TINGIS、计算几何和计算机图形学邻域常用的三角剖分准则有以下几种空外接圆准则：在TIN中，过每个三角形的外接圆均不包含点集的其余任A所示；最大最小角准则：在两相邻三角形形成的凸四边形中，这两三角形中的最小内角肯定大于交换凸四边形对角线后所形成的两三角形的最小内角,如图B所示；最短距离和准则：图C，最短距离和就是指一点到基边两端的距离和为最小；张角最大准则：图D，一点到基边的张角为最大；图E，三角形内切圆面积与三角形面积或三角形面积与周长平方之比最小；对角线准则：图F定限定值时对三角形进展优化。理论上可以证明：张角最大准则、空外接圆准则及最大最小角准则是等价的，其余的则不然。三角形剖分准则是建立三角形网络的根本原则因素，现今使用已不多。LOP局部优化过程DelaunayDelaunay三角网的两个根本性质。DT三角剖分是目前应用最为广泛的三角剖分方法，其特性是可最大限度避开狭长三角形的消灭以及不管从何处开头构网都能保持三角形网络的唯TIN，LOP法则〔局部优化过程，localoptimalprocedure，LOP〕对其进展优化LOPLawson1977年提出的，其DT三角网的空外接圆性质对由两个有公共边的三角形组成的四LOP局部优化过程无约束散点域的三角剖分算法与实现：*分割合并算法*三角法生长算法*逐点插入算法@1*分割合并算法：分割合并算法〔divideandconquerdelaunaytriangulationDTDT三角网中相邻三角形边垂直平分线交点的连线所形成的多边形，有关V-图的定义、性质〕。LewisRobinson1978年将该方法DTLeeSchachter、DwyerLewis和LeeSchachter1980年的算法适合于无约束数据域的三角剖分，而Dwyer1987年的算法则考虑了带约束条件LOP优化策略，因而能处理带约束条件的数据。DT三角网。当每个子集剖分完成可有不同的点集划分方法、子三角网生成方法及合并方法等。分割合并算法的根本步骤为：第一步，把数据集以横坐标为主、纵坐标为辅按升序进展排序；以凸壳为数据边界，对每一数据子集进展三角剖分，并用LOP进展优化，使之成为DT三角剖分；③找出连接左右子集两个凸壳的底线和顶线；④由底线到顶线，合并两个子三角网；第三步：假设数据集中的数据个数小于给定的阈值，则直接输出三角剖分结果；〔凸壳，并以此作为源头，逐步缩小以形成整个三角网。收缩生长算法与数据点的会分解成假设干个相互独立的子区域，这就增加了三角剖分的简单性扩张生长算法与收缩算法过程刚好相反展，最终形成掩盖整个区域的三角网，其主要步骤为：第一步，生成初始三角形。在数据点中任取一点A〔该点一般是位于数据点的几何中心四周〔空外接圆准则或张角最大准则C，ABC。DBACDelaunayD、E、F点。DBAC D BFACEFACE〔1ABCAB，第三边的C同侧，推断方法为：2〕为避开三角形的穿插和重复，通过上述异侧点判别所选的第三点还要进展进形共用过两次，假设是，则三角形无效，否则为有效三角形。@逐点插入算法逐点插入算法的过程格外简洁，根本步骤为：〔PLOP算法对初始三角剖分进展优化处理。第三步，处理外围三角形。12.DEM读取实例：13缓冲区分析算法：(buffer)概念：是依据空间数据库中的点、线、面地理实体或规划目标，自动建立其四周肯定宽度范围的多边形。分类：点缓冲区、线缓冲区、面缓冲区和简单实体缓冲区。步进拟合的思想圆弧弥合〔双侧平行线法〕大，误差越大。凸角圆弧法，根本思想：在轴线的两端用半径为缓冲距的圆弧弥合；为对应顶点。〔4〕自相交多边形的两种状况：岛屿，多边形干岛屿。缓冲区边线只绘制外围边线和岛屿轮廓。形。网络分析11网络中根本组成局部：接关系由弧段-结点拓扑数据构造来表达。属性如资源流淌的时间、速度等中心(Center)：网络中位于结点处，具有沿着链收集和发放资源力量的设施，如邮局、电站、水库等邮件投放点、公共汽车站，属性如资源需求量边/边集图：是一个非空的有限结点和有限边的集合。网络流：指网络中任意一条弧的物流量。2.给定单源点的最短路径的求解〔三步〕:1〕选一顶点v为源点，并视从源点v动身的全部边为到各顶点的最短路径dist[],开头时，distvi的distv行。②设一个用来记