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

2021年GIS算法原理知识点总结 2021年GIS算法原理知识点总结 PAGE / NUMPAGES 2021年GIS算法原理知识点总结 GIS算法原理知识点总结 算法设计和分析： 1、算法设计原则： 对的性：若一种算法自身有缺陷，那么它将不会解决问题； 拟定性：指每个环节必要含义明确，对每种也许性均有拟定操作。 清晰性：一种良好算法，必要思路清晰，构造合理。 2、算法复杂性涉及：时间复杂性和空间复杂性。 3、时间复杂性：用一种与问题有关整数量来衡量问题大小，该整数量表达输入数据量尺度，称为问题规模。运用某算法解决一种问题规模为n输入所需要时间，称为该算法时间复杂性。 4、算法概念：算法是完毕特定任务有限指令集。所有算法必要满足下面原则： 输入 输出 明确性 有限性 有效性 GIS算法计算几何基本 O1、理解矢量概念：如果一条线段端点是有顺序之分,咱们把这种线段称为有向线段(directed segment)。如果有向线段p1p2起点P1在坐标原点，咱们可以把它称为矢量P2。 O p2 p2 p1 p1 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）。 P X Q0,则P在Q顺时针方向； P X Q0,则P在Q顺逆针方向； P X Q0,则P Q共线，但也许同向也也许反向。 6、判断线段拐向：折线段拐向判断办法，可以直接由矢量叉积性质推出，对于有公共端点线段p0p1和P1P2，通过计算（p2-p0）×(P1-p0)符号便可以给出折线段拐向。 p2p2p2 p2 p2 p2 p1p1 p1 p1 p1 p1 p0p0 p0 p0 p0 p0 基（ 基（p2-p0）×(P1-p0)0，则P0P1 在P1点拐向右侧后得到P1P2 基（p2-p0 基（p2-p0）×(P1-p0)=0， 则P0P1P2三点共线 基（p2-p0）×(P1-p0)0，则P0P1 在P1点拐向左侧后得到P1P2 理解矢量概念通过矢量差积办法就可以判断拐向了。 7.判断点与否在线段上：设点为Q，线段为P1 P2：(Q-P1)X(P2-P1)=0且Q在以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）共线，但是由于已经通过迅速排斥实验，因此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在多边形外部；否则，为奇数时，在多边形内部。 射线法要考虑几种特殊状况，并且射线法合用于凸多边形 2)转角法：多边形环绕点P次数称为环绕数，环绕数为0时，点P在多边形外部，否则在多边形内部。 14.判断线段与否在多边形内：（折线是判断它每条线段） 条件一：线段两个端点都在多边形内 条件二：线段和多边形所有边都不内交。 15.判断多边形否在多边形内： 只要判断多边形每条边与否都在多边形内即可。判断有m个顶点多边形与否在一种有n个顶点多边形内复杂度为O(mXn) 16.判断矩形与否在多边形内： 将矩形转化为多边形，然后再判断与否在多边形内。 17.判断圆与否在多边形内：计算圆心到