2025年GIS算法原理知识点总结

GIS 算法原理知识点总结算法设计和分析：1、算法设计的原则：对的性：若一个算法自身有缺陷，那么它将不会解决问题；拟定性：指每个环节必须含义明确，对每种也许性都有拟定的操作。清楚性：一个良好的算法，必须思绪清楚，结构合理。2、算法的复杂性涉及：时间复杂性和空间复杂性。3、时间复杂性：用一个与问题相关的整数量来衡量问题的大小，该整数量表达输入数据量的尺度，称为问题的规模。运用某算法解决一个问题规模为 n 的输入所需要的时间，称为该算法的时间复杂性。4、算法的概念：算法是完毕特定任务的有限指令集。所有的算法必须满足下面的标准：输入输出明确性有限性有效性GIS 算法的计算几何基础1、理解矢量的概念：假如一条线段的端点是有顺序之分的,我们把这种线段称为有向线段(directed segment)。假如有向线段 p1p2 的起点 P1O在坐标原点，我们可以把它称为矢量 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）。P X Q>0,则 P 在 Q 的顺时针方向；P X Q<0,则 P 在 Q 的顺逆针方向；P X Q>0,则 P Q 共线，但也许同向也也许反向。6、推断线段的拐向：折线段的拐向推断方法，可以直接由矢量叉积的性质推出，对于有公共端点的线段 p0p1 和 P1P2，通过计算（p2-p0）×(P1-p0)的符号便可以给出折线段的拐向。p1p2p1p2p1p2p1p2理解矢量的概念通过矢量差积的方法就可以推断的拐向了。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）共线，但是由于已经通过快速排斥...