- 1、本文档共42页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
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.判断圆与否在多边形内:计算圆心到
文档评论(0)