GIS算法基础重点解读_.docx

《GIS算法基础重点解读_.docx》由会员分享，可在线阅读，更多相关《GIS算法基础重点解读_.docx（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、GIS算法基础重点解读_GIS算法基础重点解读GIS算法基础重点解读一、算法的时间复杂性T(n):利用某算法处理一个问题规模为n的输入所需要的时间。空间：为了解求问题的实例而执行的计算步骤所需要额内存空间(或字)数目，不包括用来存储输入的空间。算法空间复杂性不可能超过运行时间的复杂性。元运算：对于任何计算步骤，不管输入数据或执行的算法，它的代价总是以一个时间常量为上界，则称该计算步骤为元运算。基于比拟的排序问题的最优算法：我们通常把在0(nlgn)时间内用元素比拟法排序的任何算法，称为基于比拟的排序问题的最优算法。一般来讲，假如能够证实任何一个求解问题A的算法必定是Q(f(n),那么我们把在0

2、(f(n)时间内求解任何问题A的任何算法都称为问题A的最优算法。算法设计原则：正确性确定性明晰性。算法的要素：1.待解问题的描绘2?算法设计的任务3.算法分析。二、关系运算：指的是用于检验两个几何对象的特定的拓扑空间关系的逻辑方法。两步确定两条线段能否相交：1.快速排挤实验(矩形不相交)2.跨立实验(判定线段P1P2能否和Q1Q2跨立根据是：(P1-Q1)*(Q2-Q1)*(Q2-Q1)*(P2-Q1)=0.)判定点能否在多边形内常用算法：1.射线法(又叫奇偶测试法)2.转角法。线段在多边形内的一个重要条件是线段的两个端点都在多边形内，第二个必要条件是线段和多边形的所有边都不内交。线段在多边形

3、内判定步骤：1.先求出所有和线段相交的多边形的顶点2.然后根据X-Y坐标排序(X坐标小GIS算法基础重点解读GIS算法基础重点解读的排在前面，对于X坐标一样的点，丫坐标小的排在前面，这种排序准则也是为了保证水安然平静垂直情况的判定正确，这样相邻的两个点就是在线段上相邻的两交点，假如任意相邻两点的中点也在多边形内，则该线段一定在多边形内。计算线段或直线与线段的交点：设一条线段为L0二P1P2另一条线段或直线为L仁Q1Q2要计算的就是L0和L1的交点：第一步：首先判定L0和L1能否相交2.若L1不平行与丫轴，则交点横坐标为P1的横坐标，代入到L1的直线方程中能够计算出交点纵坐标。第三步：若L1平行

4、于y轴，贝卩第四步：若L0平行于x轴，有2种情况，第五步：若L1平行于x轴，贝打第六步：若L1和L0斜率均存在，贝聽中心点的计算：多边形的中心点又叫质心或重心能够通过将多边形分割成为三角形，求取三角形的中心点，然后将三角形的中心点加权求和获得。三点画圆：算法关键是求取圆心和园半径：第一步：求取圆心，第二步：求取半径R,Rxa-xpA2+ya-ypA2八1/2。p是圆心。四、矢量线栅格化三种方法：八方向栅格化、全途径栅格化、恒密度栅格化。矢量面格式向栅格面格式转换又称为多边形填充，就是在矢量表示的多边形边界内部的所有栅格点上赋以相应的多边形编码，进而构成栅格数据阵列。方法有：内部点扩散算法种子，

5、八方向扩散、射线算法和扫描算法、边界代数算法积分、拓扑。栅格数据矢量化有4个基本步骤：1.边界提取2.边界限追踪3.拓扑关系生成4.去除多余点及曲线圆滑。细化算法:栅格数据需要细化，以提取其中轴线，由于：1.中轴线是栅格数据曲线的标准化存储形式2.实现细化是将栅格曲线矢量化的前提3.GIS算法基础重点解读GIS算法基础重点解读在有些算法中能够提高计算精度。细化算法可分两大类：第一大类是基于距离变换，首先得到骨架像元，然后跟踪距离变换图中的“山脊线并将其作为中轴线；第二类是基于在不毁坏栅格拓扑连通性的前提下，按对称的原则删除影像边缘的栅格点。四例：1?用距离变换法搜索中轴线减细2.最大数值计算法

6、V值4、13.经典的细化算法4.边缘跟踪剥皮法.多边形栅格转矢量的双边界搜索算法：基本思想：通过边界提取，将左右多边形信息保存在边界点上，每条边界弧段由两个并行的边界链组成，分别记录该边界弧段的左右多边形编号。详细步骤：1.边界点和结点提取2.边界限搜索与左右多边形信息记录3.多余点去除。多边形栅格转矢量的单边界搜索算法：单边界搜索算法时通过对传统的区域跟踪算法进行改良而构成的，传统区域跟踪算法中，对区域的描绘由两部分组成：区域外轮廓和内部孔洞。单边界搜索算法流程：1.跟踪、搜索第一层所有的区域并记录外轮廓和内部孔洞信息2.根据跟踪到的孔洞信息找出下一层中未跟踪过的区域的外轮廓跟踪起始点即找出

7、一个新区域3.跟踪找到的新区域并记录其外轮廓和内部孔洞信息4.重复23步，直到该层所有区域都已被跟踪完毕5重复2到3步，直到整幅图像内所有区域都已被跟踪完毕。五、道格拉斯-普克法优点是具有最小的线性位移，压缩效果占优，缺点是需对整条曲线完成数字化后方能进行压缩，且计算工作量较大。光栏法原理：它根据预先定义的一个扇形“喇叭口，根据曲线上各节点是在扇形外还是在扇形内，决定节点是保留还是舍去。其优点是光栏法不仅算法严密，能按给定阈值保留曲线特征点，GIS算法基础重点解读GIS算法基础重点解读并按时处理，运算量小，占用内存少。链式编码：多边形边界可定义为：由某一原点开场并按某些基本方向确定的单位矢量链

8、。东0东南1东北7游程长度编码：游程指相邻同值网格的数量，游程长度编码构造是逐行将相邻同值的网格合并，并记录合并后网格的值及合并网格的长度，其目的是压缩栅格数据量，消除数据间的冗余。块式编码：块式编码是将游程长度编码扩大到二维的情况，把多边形范围划分成由像元组成的正方形，然后对各个正方形进行编码。差分映射法：就是选择某一参照值对有关栅格的属性值进行求差运算，根据差值得到一个新的栅格数据层。分行选取和全区选取拓扑关系左转算法描绘如下：1.顺序取一个结点作为起始结点，取完为止；取过该结点的方位角最小的未使用过的或仅使用一次，且使用过的方向与本次相反的弧段作为起始弧段。2.取这条弧段的另一个结点，找

9、这个结点关联的弧段集合中的本条弧段的下一条弧段，假如本条弧段是最后一条弧段，则取弧段集合的第一条弧段，作为下一条弧段。3.判定能否回到起点，假如是，贝S构成了一个多边形，记录下它，并且根据弧段的方向，设置组成该多边形的左右多边形信息；否则转2。4.取起始点上开场的，刚刚所构成多边形的最后一条边作为新的起始弧段，转2;若这条弧段已经使用过两次，即构成了两个多边形，转1。岛的判定问题算法如下：1.计算所有多边形的面积2.分别对面积为正的多边形和面积为负的多边形排序，分别构成正多边形和负多边形集合。3.假如负多边形集合的个数为1,结束程序；否则，从面积为正的多边形集合中，顺序取出一个多边形，假如正多

10、边形已经都被访问GIS算法基础重点解读GIS算法基础重点解读过，则程序结束。4.依次从负多边形集合中取出负多边形，判定当前取出的正多边形能否包含该多边形，假如包含，就将该负多边形参加当前取出的正多边形中，构成复杂多边形，设置负多边形的组成弧段的拓扑信息，并从负多边形集合中删除该负多边形。当所有负多边形都被访问一遍后转3.六、直线方程的所有形式：P(t)=P0+tVl二PO+t(Pl-Po)=(1-t)P0+tPl(yO-y1)x+(x1-xO)y+(xOy1-x1yO)=O。P(t)=(xO+tcosO,y0+tsinO)点到直线距离计算公式：d(P,L)=(y0-y1)x+(x1-x0)y+

11、(x0y1-x1y0)/(x1-x0)A2+(y1-y0)A2)A1/2.三角形面积计算公式：A=1/2*bh,A=1/2*absinO,A=(s(s-a)(s-b)(s-c)1/2,s=1/2*(a+b+c),A=1/4*(4a2b2-(a2+b2-c2)2)1/2,A=t)/2(cotO+cotB)。A=1/2|v*w|=1/2|(v1-v0)(v2-v0)|,2A=(x1-x0)(y2-y0)-(x2-x0)(y1-y0)o四边形面积计算公式：A=(s-a)(s-b)(s-c)(s-d),A(v0v1v2v3)=|(v1-v0)*(v3-v0)|,A=(x1-x0)(y3-y0)-(x3

12、-x0)(y1-y0),A=1/2|(v2-v0)*(v3-v1)|,2A=(x2-x0)(y3-y1)-(x3-x1)(y2-y0)。任意二维平面多边形面积计算方法与公式：A多边形二艺A(i),i=APVV+1，注意：对于一个逆时针多边形，当点P在边VV+1的左边，则i的面积是正的；相反，当点P在边VV+1的右边，并且位于多边形外部，则i的面积是负的。假如是一个顺时针多边形，贝S符号相反，并且内部的三角形面积为负的。GIS算法基础重点解读GIS算法基础重点解读七、空间索引：就是指根据空间对象的位置和形状或空间对象之间的某种空间关系，按一定的顺序排列的一种数据构造，其中包括空间对象的概要信息。

13、B树的定义：一个m阶的B树，或为空树，或是为知足下列特征的m叉树。1树中每个结点至多有m棵子树；2若根结点不是叶子结点，则至少有两颗子树；3除根之外的所有非终端结点至少有m/2棵子树；4所有的非叶结点中包含下列信息数据：AO,VK,AI,DI,VK2,A2,D2,Kn,An,Dn式中Ki=1,2n为关键字，且K称为结点的一个元素。5所有的叶子结点都出如今同一层次上，并且不带信息能够看作是外部结点查询失败的结点，实际上这些结点不存在，指向这些结点的指针为空。插入算法：设将元素插入B树中。1首先在树中查找K,若查找到，算法结束假定B树中不容许有一样的关键字存在。若没有查到，设最后查到的结点为N。将

14、关键字K插入结点N中，若结点N的元素的个数小于等于m-1，将A指向叶结点，插入结束，若结点N的元素关键字的个数为m则需分裂结点N。2设插入关键字K后的结点情况如下：A,VK2,A2,D2?.VKEAEDA创立一新结点L,将N中的第m/2+1以及其后的所有元素，共m-m/2个元素移入新结点L中。再将元素移出N,插入结点N的父结点。N的父结点还可能需要分裂，最坏的情况是分裂一直延续到根结点，最后产生新的根结点，树高增加1。当插入操作引起了s个结点的分裂时，磁盘访问的次数为h读取搜索途径上的结点+2s回写两个分裂出的新结点+1回写新的根结点或插入后没GIS算法基础重点解读GIS算法基础重点解读有导致

15、分裂的结点。因而，所需要的磁盘访问次数是h+2s+1,最多可达3h+1。R树的定义：设M为结点中单元的最大数目，m1GIS算法基础重点解读GIS算法基础重点解读树中各个结点及其互相间关系，而是通过编码四叉树的叶结点来表示数据块的层次和空间关系。叶结点都具有一个反映位置的关键字，亦称位置码，表示它所处位置。本质是把原来大小相等的栅格集合转变成大小不等的正方形集合，并对不同尺寸和位置的正方形集合赋予一个位置码。缺点：位置码的位数决定分割的层数，图形越复杂，分割的层数越多，相应的位置码得位数亦越多，这种自上而下的分割方法需要大量重复运算，效率比拟低。线性四又树的编码方法：基于深度和层次码的线性四叉树

16、编码；基于四进制的线性四叉树编码；四叉树的十进制编码。的概念：指的是完成一个任务所需要的详细步骤和方法。常用的算法有穷举搜索法，递归法，回溯法，贪心法，分治法。算法设计的原则：正确性，确定性，明晰性。时间复杂性：去除了表示算法运行时间的函数中的低阶项和首项系数，就称度量算法的渐进运行时间。空间复杂性：为了求解问题实例而执行的计算步骤所需要的内存空间数目，它不包括分配用来存储输入的空间.元运算：对于任何计算步骤，他的代价是以一个时间常量为上界，而不管输入数据或执行的算法，这个计算步骤叫做元运算。(算术，比拟，逻辑，赋值)最优算法：假如能够证实任何一个求解的问题A的算法必定是Q(f(n),那么我们

17、把在ofn时间内求解问题A的任何算法都称为问题A的最优算法。关系运算是指用于检验两个几何对象的特定的拓扑空间关系的逻GIS算法基础重点解读GIS算法基础重点解读辑方法。判定两直线相交：1快速排挤实验，设以线段p1p2,Q1Q2为对角线的矩形不想交，则两线段不相交。2跨立实验假如两个线段相交，则一定跨立对方运用矢量乘法乘积小于零则位于两边。判定点是不是在多边形内1射线法，一条射线从点P开场，穿太多边形的边界的次数成为交点数目，当交点数目为偶数时，点在多边形外部，不然在内部。2转角发，多边形环绕点P的次数成为环绕数，环绕数为零，在多边形外部，不然在内部。判定线段是不是在多边形内：线段在多边形内的必

18、要条件是两个端点都在多边形内，线段和多边形的所有边都不内交。假如多边形的一个顶点和线段相交，还必须判定两个相邻交点之间的线段是不是包含与多边形内部。计算线段或直线与线段的交点：第一步判定两条线是不是相交，假如不像交，没有交点。第二到第五步分别判定平行与X,Y轴的情况。第六步两条线斜率都存在并且不为零。中心点的计算：重心分割三角形，加权求的，权重为三角形面积站的多边形面积比例三点画圆：求圆心P,求取圆的半径。栅格数据向矢量格式的转换步骤：1边界提取，采用高通滤波将栅格图像二值化或者以特殊值标识边界点。2边界限追踪，对每个边界弧段由一个结点向另一个结点搜索，通常对每个已知边界点需沿除了进入方向的其

19、他七个方向搜索下一个边界，直到连成边界弧段。3拓扑关系生成，对于矢量表示得边界弧段数据，判定其与原图上各多边形的空间关系，以构成完好的拓扑构造并建立与属性数据的联络。4去GIS算法基础重点解读GIS算法基础重点解读除多余点及曲线圆滑，由于搜索是逐个栅格进行的，必须去除由此造成的多余点记录，以减少数据冗杂，搜索结果，曲线由于栅格精度的限制可能不够圆滑，需要采用一定的插补算法进行光滑处理，常用的算法有线性迭代法，分段三次多项式插值法，正轴抛物线平均加权法。斜轴抛物线平均加权法，样条函数插值法。多边形栅格转矢量的双边界搜索算法：思想是通过边界提取，将左右多边形信息保存在边界点上，每条边界弧段甴两个并

20、行的边界链组成，分别记录该边界弧段的左右多边形编号。边界限搜索采用2*2的栅格窗口，在每个窗口内4个栅格数据的形式，能够唯一地确定下一个窗口的搜索方向和该弧段的拓扑关系，极大的加快了搜索速度，拓扑关系也很容易建立，步骤1边界点和结点提取2边界限搜索与左右多边形信息记录3多余点去除。单边界搜索算法：对区域的描绘由两部分组成，区域外轮廓和内部孔洞，确定外轮廓跟踪起始点，对区域的外轮廓进行跟踪和记录，对区域内部的所有孔洞进行扫描跟踪和记录。将图像中的所有区域按包含关系分为若干层，每一层至少包含一个区域对象，流程：1搜索跟踪第一层所有的区域并记录外轮廓和内部孔洞信息；2根据跟踪到的空孔洞信息找出下一层中未跟踪过的区域的外轮廓跟踪起始点；3跟踪找到的新区域并记录其外轮廓和内部孔洞信息4重复2,3步直到该层所有区域都已被跟踪完毕5重复2-4步知道整幅图像内所有区域都已被跟踪完毕。拓扑关系生成经过：1弧段处理，使整幅图形中的所有弧段，除在端点处相交外没有其他交点，即没有相交或自相交的弧段2结点匹配，建立结点弧段关系3建立多边形，以左转算法或