GIS算法原理知识点总结
算法设计与分析:
1、算法设计得原则:
正确性:若一个算法本身有缺陷,那么它将不会解决问题;
确定性:指每个步骤必须含义明确,对每种可能性都有确定得操作。 清晰性:一个良好得算法,必须思路清晰,结构合理。
2、算法得复杂性包括:时间复杂性与空间复杂性。
3、时间复杂性:用一个与问题相关得整数量来衡量问题得大小,该整数量表
示输入数据量得尺度,称为问题得规模。利用某算法处理一个问题规模为n得输入所需要得时间,称为该算法得时间复杂性。
4、算法得概念:算法就是完成特定任务得有限指令集。所有得算法必须满足
下面得标准:
? 输入 ? 输出 ? 明确性 ? 有限性 ? 有效性 GIS算法得计算几何基础
1、理解矢量得概念:如果一条线段得端点就是有次序之分得,我们把这种线
段称为有向线段(directed segment)。如果有向线段p1p2得起点P1在坐标原点,我们可以把它称为矢量P2。
p1 p2
5、矢量叉积:计算矢量叉积就是直线与线段相关算法得核心部分。
设矢量P = (x1,y1),Q = (x2,y2),则矢量叉积定义为(0,0)、p1、p2与p1p2 所组成得平行四边形得带符号得面积,即P×Q = x1·y2-x2·y1,
。 O 其结果就是个标量。显然有性质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)得符号便可以给出折线段得拐向。
p2 p2
p2
p1
p1
p1
p0 p0 基(p2-p0)×(P1-p0)>0,
p0 则P0P1 基(p2-p0)×(P1-p0)=0, 基(p2-p0)×(P1-p0)<0,则
在P1点拐向右侧后得到则P0P1P2三点共线 理解矢量得概念通过矢量差积得方法就可以判断得拐向了。 P0P1
P1P2
在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、判断圆就是否在多边形内:计算圆心到多边形每条变边得最短距离,
若该距离大于或等于圆半径,则该圆在多边形内。
18、判断点就是否在圆内:计算圆心到该点得距离,若小于或等于半径,则
该点在圆内。
19、判断线段、折线、矩形、多边形就是否在圆内:因为圆就是凸集,
所以只要判断就是否每个顶点都在圆内即可。