GIS算法原理知识点总结Word格式.docx
- 文档编号:4642822
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:33
- 大小:2.75MB
GIS算法原理知识点总结Word格式.docx
《GIS算法原理知识点总结Word格式.docx》由会员分享,可在线阅读,更多相关《GIS算法原理知识点总结Word格式.docx(33页珍藏版)》请在冰点文库上搜索。
PXQ>
0,则P在Q的顺时针方向;
PXQ<
0,则P在Q的顺逆针方向;
0,则PQ共线,但可能同向也可能反向。
6、判断线段的拐向:
折线段的拐向判断方法,可以直接由矢量叉积的性质推出,对于有公共端点的线段p0p1和P1P2,通过计算(p2-p0)×
(P1-p0)的符号便可以给出折线段的拐向。
p0
基(p2-p0)×
(P1-p0)>
0,则P0P1
在P1点拐向右侧后得到P1P2
(P1-p0)=0,
则P0P1P2三点共线
(P1-p0)<
在P1点拐向左侧后得到P1P2
理解矢量的概念通过矢量差积的方法就可以判断的拐向了。
7.判断点是否在线段上:
设点为Q,线段为P1P2:
(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)×
(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.判断线段、折线、矩形、多边形是否在圆内:
因为圆是凸集,所以只要判断是否每个顶点都在圆内即可。
20.判断圆是否在圆内:
设两圆为O1,O2,半径为r1,r2。
先比较r1,r2的大小,若r1<
r2,则O2不可能在O1内;
若两圆心距离大鱼r1-r2,则O2不在O1内;
反之,O2在O1内。
21.距离交会:
是以两个已知控制点为中心,分别以目标点与两已知控制点的距离为半径划圆,交会点即为要求目标点(注意方向二选其中一个)。
22.距离量算算法的实现:
空间数据的变换算法
1.了解平面坐标变换的几种形式:
2.仿射变换:
它是使用最多的一种几何纠正方式。
在保留线条平行条件下,仿射变换允许对长方形目标做旋转、平移、倾斜和不均匀缩放。
旋转指在原点旋转x和y轴;
平移是指把源点移动到新的位置;
倾斜是指以一个倾向将形状改变为平行四边形;
不均匀缩放是指在x或y方向同时或单独增大和缩小比例尺。
平移变换实例代码:
比例变换实现代码:
旋转变换实现代码:
3.相似变换:
图形的相似变换是指由一个图形到另一个图形,在改变的过程中保持形状不变(大小方向和位置可变)的图形。
图形相似变换的性质:
图形的相似变换不改变图形中每一个角的大小;
图形相似变换后对应线段都扩大(或缩小)相同的倍数,这个数叫相似比。
相似变换面积:
经相似变换的像与原图的面积等于相似比的平方。
相似变换的分解:
任何相似变换可以分解为放缩,平移,旋转和翻转变换的复合。
相似变换是仿射变换的一种特殊情况,也就是在仿射变换中去除错位变换这个因子后的结果。
4.矢量转栅格:
点:
简单的坐标变换
线:
线的栅格化
面:
线的栅格化+面填充
面(多边形)的填充方法
1、内部点扩散法(种子扩散法)
2、扫描法
3、射线法
4、复数积分法
5、边界代数算法
栅格表示法的精度与分辨率有关。
在图(a)、(b)、(c)中,栅格的分辨率分别为7*5,15*11,24*13。
分辨率的大小与下面两个问题有关:
5.栅格矢量化:
从栅格单元转换为几何图形的过程为矢量化;
(一)要求(矢量化过程应保持):
1)
栅->
矢转换为拓扑转换,即保持实体原有的连通性、邻接性等;
2)
转换实体保持正确的外形。
(二)方法
方法一,实际应用中大多数采用人工矢量化法,如扫描矢量化,该法工作量大,成为GIS数据输入、更新的瓶颈问题之一。
方法二,程序转化转换(全自动或半自动)
过程为:
1、边界提取2、二值化3、二值图像的预处理4、细化:
[1)剥皮法2)骨架法]5、跟踪6、拓扑化
6.”矢量点”转栅格实例:
6.矢量数据的压缩:
矢量数据的压缩包括两个方面的内容,一是在不扰乱拓扑关系的前提下,对采样点数据进行合理的抽稀。
二是对矢量坐标数据重新进行编码,以减少所需要的存储空间。
1)间隔取点法:
每隔K个点取一点,或舍去那些比规定距离更近的点,首末点一定要保留。
临界值
隔点法
临界值法
2)垂距法:
原始曲线
对点2测试距离大于规定的限差
点2保留
对点3测试距离小于规定的限差
2
3
4
1
3点舍去,化简结果
限差
3)光栅法:
d/2
c1
c2
b2
b1
P4
P3
P2
a1
a2
Pn
光栏法的基本思想是(上图):
定义一个扇形区域,通过判断曲线上的点在扇形外还是在扇形内,确定保留还是舍去。
设曲线上的点列为{pi},i=1,2,…,n,光栏口经为d,可根据压缩量的大小自己定义,则光栏法的实施步骤可描述为:
1°
、连接p1和p2点,过p2点作一条垂直于p1p2的直线,在该垂线上取两点a1和a2,使a1p2=a2p2=d/2,此时a1和a2为“光栏”边界点,p1与a1、p1与a2的连线为以p1为顶点的扇形的两条边,这就定义了一个扇形(这个扇形的口朝向曲线的前进方向,边长是任意的)。
通过p1并在扇形内的所有直线都具有这种性质,即p1p2上各点到这些直线的垂距都不大于d/2。
2°
、若p3点在扇形内,则舍去p2点。
然后连接p1和p3,过p3作p1p1的垂线,该垂线与前面定义的扇形边交于c1和c2。
在垂线上找到b1和b2点,使p3b1=p3b2=d/2,若b1或b2点((图4-4-3中为b2点)落在原扇形外面,则用c1或c2取代(图4-4-3中由c2取代b2)。
此时用p1b1和p1c2定义一个新的扇形,这当然是口径(b1c2)缩小了的“光栏”。
3°
、检查下一节点,若该点在新扇形内,则重复第
(2)步;
直到发现有一个节点在最新定义的扇形外为止。
4°
、当发现在扇形外的节点,如图4-4-3中的p4,此时保留p3点,以p3作为新起点,重复1°
~3°
。
如此继续下去,直到整个点列检测完为止。
所有被保留的节点(含首、末点),顺序地构成了简化后的新点列。
首先将一条曲线首、末点连一直线,求出各点到该直线的距离,选其最大者与规定的临界值相比较若大于临界值,则离该直线距离最大的点保留,否则,将直线两端间各点全部舍去,并将原线条分成两部分,对每部分线条再实施该抽稀过程,直到结束。
抽稀结果点数随选取限差临界值的增大而减少,应用时应根据精度要求来确定抽稀限差临界值,以获得最好的结果。
即道格拉斯—普克(Douglas--peuker)算法。
4)道格拉斯—普克法:
P1
PN
splitpoint
Result
第一轮垂距
第二轮垂距
弦
阈值
7.栅格数据的压缩:
1)链式编码:
2)游程编码:
所谓游程是指按行的顺序连续且属性值相同的若干栅格。
游程长度的记录方式有两种
①记录每个游程起(迄)列号
②记录每个游程像元数
3)块式编码:
块式编码是将游程扩大到两维情况,把多边形范围划分成若干具有同一属性的正方形,然后对各个正方形进行编码。
块式编码的数据结构由初始位置(行列号)、半径和属性代码组成。
3)四叉树编码:
四叉树又称四元树或四分树,是最有效的栅格数据压缩编码方法之一。
四分树将整个图像区域逐步分解为一系列方形区域,且每一个方形区域具有单一的属性。
最小区域为一个象元。
8.隔点取样法实例:
空间数据内插算法
1.空间数据内插的定义:
根据已知的空间数据估计(预测)未知空间的数据值。
2.空间数据内插目标:
①缺值估计:
估计某一点缺失的观测数据,以提高数据密度。
②内插等值线:
以等值线的形式直观地显示数据的空间分布。
③数据网格化。
把无规则分布的空间数据内插为规则分布的空间数据集,如规则矩形格网、三角网等。
3.空间内插法的种类:
几何方法、统计方法、空间统计方法、函数方法、随机模拟方法、物理模型模拟方法和综合方法。
4.优缺点比较:
每一种方法均有其适用范围、算法和优缺点,因此,没有绝对最优的空间内插方法。
5.如何选择:
对数据进行空间探索分析,根据数据的特点,选择最优方法;
同时,应对内插结果进行严格的检验。
6空间数据内插的分类依据:
①确定或随机;
②点与面;
③全局或局部等标准分类;
④内插方法的基本假设和数学本质。
3.反距离权重插值算法:
是一种局部插值算法,它假设未知值的点受较近控制点的影响比较远控制点的影响更大。
反距离权重方法的通用方程是:
式中,z0为点0的估计值;
zi为控制点i的z值;
dj为控制点i与点0间的趾离;
s为在估算中用到的控制点的数目;
K为指定的幂。
4.双线性插值算法:
是一种数字图像处理、DEM数据处理等方面使用较多的局部插值算法。
原理:
如图8.5所示,设f(0,0)=Z1,f(1,0)=Z2,f(0,1)=Z3,f(1,1)=Z4,求f(x,y)点的值,其中x,y∈[0,1]。
将f(0,0)、f(1,0)、f(0,1)、f(1,1)代入双线性内插方程:
f(x,y)=ax+by+cxy+d
求出各参数a、b、c、d的值,再将x,y代入,解得f(x,y)。
5反距离权重插值实例:
TIN、DEM、DAT
1.数字高程模型概念与理解:
高程常常用来描述地形表面的起伏形态,传统的高程模型是等高线,其数学意义是定义在二维地理空间上的连续曲面函数,当此高程模型用计算机来表达时,称为数字高程模型。
2.数字高程模型:
是通过有限的地形高程数据实现对地形曲面的数字化模拟或者说是地形表面形态的数字化表示,英文为DigitalElevationModel,简称DEM。
3.理解DEM和DTM:
由于高程数据常常采用绝对高程或海拔(即从大地水准面起算的高度),DEM也常常称为DTM。
要说明的是由于“Terrain”一词的含义比较广泛,不同专业背景对“Terrain”的理解也不一样,DTM趋向于表达比DEM更为广泛的内容,详见后文的分析。
4.TIN和规则DEM的区别:
不规则三角网数字高程模型由连续的三角面组成,三角形的形状、大小取决于不规则分布的点的位置和密度。
地形变化越简单,采样点就越少,则单元格就越大;
反之地形变化比较复杂,数据点分布比较密集,格网单元就越小。
因此TIN与规则格网DEM显著不同之处在于TIN模型不需要维护模型的结构规则性,不但能灵活地随地形的复杂程度而改变格网单元大小,避免平坦地形的数据冗余,而且又能按地形特征点线如山脊点、山谷线、地形变化线等表示地形特征。
5.DEM数据结构:
规则格网DEM数据结构
不规则三角形DEM数据结构
6.规则格网数据:
由于DEM的边界范围一般是规则矩形,而实际地形范围却是不规则的,还应考虑不在研究区域内的DEM高程值的表示方法(无效区域数据),一般是给出一个特殊的常数值,如-9999等。
规则格网DEM的数据文件一般包含用对DEM数据进行说明的数据头和DEM数据体两部分。
1)数据头:
一般包括定义DEM西南角起点坐标、坐标类型、格网间距、行列数、最低高程以及高程放大系数等内容;
2)数据体:
按行或列分布记录的高程数字阵列。
7.TIN:
在TIN模型中,基本的结构元素有三角形顶点、边和面。
它们之间存在着点与线、点与面、线与面、面与面等拓扑关系。
理论上,通过组成三角形的三顶点可完整地表达三角形的构成以及三角形顶点、三角形边、三角形之间的拓扑关系(下图),这种结构只需要两个文件,即三角形顶点坐标文件和组成三角形三顶点(通常用点在坐标文件中的序号表示)文件。
这种结构虽然简单,三角形结构元素的拓扑关系却是隐含的,不利于TIN模型的检索与应用。
因此,围绕三角形的拓扑关系描述而产生了多种TIN的数据结构。
8.TIN模型的面结构最大特点是:
由于存储了三角形之间的邻接关系,TIN内插、检索、等高线提取、显示以及局部结构分析都比较方便,不足之处是:
存储量较大,而且在TIN的编辑中要随时维护这种关系。
9.DEM数据获取:
建立DEM的第一步是获取地形数据。
DEM的数据源和数据获取方式对于DEM的最终质量至关重要。
DEM原始数据主要是高程和平面位置数据,在可能条件下还应包括各种地形结构线如山脊线、山谷线、断裂线等。
另外,DEM应用目的、数据采集效率和成本、技术熟练程度也影响着DEM数据采集的方法和策略。
/*目前DEM的数据主要来源于地形图、摄影测量与遥感影像数据、地面测量、既有DEM数据等。
*/
10.坡度:
(1)坡度是地表形态最为重要的因子,通过坡度可以完整地形成地形曲面(Evans,1972;
Strahler,1956);
(2)坡度是地形曲面函数一阶微分的函数,表达了高程随距离变化的比率(坡度定义为地面一点的切平面与水平面之间的夹角),而坡度的变率是地形曲面的二阶微分,进一步刻画了坡度的变化,从而反映地形的复杂程度;
(3)大量的研究表明,区域DEM高程精度与平均坡度值之间存在强相关,通过模型的平均坡度可预测DEM的精度(Ackermann,1979;
Ley,1986);
(4)坡度通过相互垂直的两个坐标轴方向的高程变化表达地形曲面局部单元的倾斜程度,也就是通过地形表面的凸面和凹面来描述地形表面特性,即地表的陡峭方向和大小。
11.TIN数据的建立:
基于不规则三角网的数字高程模型(BasedonTriangulatedIrregularNetworkDEM,简写为BasedonTINDEM,俗称TIN)就是用一系列互不交叉、互不重叠的连接在一起的三角形来表示地形表面。
TIN是DEM的又一个主要数据模型,TIN的特点在其字面意思中表露无遗。
11.TIN的三角剖分准则:
TIN的三角剖分准则是指TIN中三角形的形成法则,它决定着三角形的几何形状和TIN的质量。
目前在GIS、计算几何和计算机图形学邻域常用的三角剖分准则有以下几种
(1)空外接圆准则:
在TIN中,过每个三角形的外接圆均不包含点集的其余任何点,如图A所示;
(2)最大最小角准则:
在两相邻三角形形成的凸四边形中,这两三角形中的最小内角一定大于交换凸四边形对角线后所形成的两三角形的最小内角,如图B所示;
(3)最短距离和准则:
图C,最短距离和就是指一点到基边两端的距离和为最小;
(4)张角最大准则:
图D,一点到基边的张角为最大;
(5)面积比准则:
图E,三角形内切圆面积与三角形面积或三角形面积与周长平方之比最小;
(6)对角线准则:
图F,两三角形组成的凸四边形的两条对角线之比。
超过给定限定值时对三角形进行优化。
理论上可以证明:
张角最大准则、空外接圆准则及最大最小角准则是等价的,其余的则不然。
三角形剖分准则是建立三角形网络的基本原则,应用不同的准则将会得到不同的三角形网络。
一般而言,应尽量保持三角网的唯一性,即在同一准则下由不同的位置开始建立三角形网络,其最终的形状和结构应是相同的,在这一点上,张角最大准则、空外接圆准则及最大最小角准则可以做到。
对角线准则含有主观因素,现今使用已不多。
通常将在空外接圆准则、最大最小角准则下进行三角剖分称为Delaunay三角剖分,简称为DT,同时空外接圆和最大最小角也是Delaunay三角网的两个基本性质。
DT三角剖分是目前应用最为广泛的三角剖分方法,其特性是可最大限度避免狭长三角形的出现以及不管从何处开始构网都能保持三角形网络的唯一性,这一点在实际应用中相当重要。
实际上,在任何三角剖分准则下得到的TIN,只要用LOP法则(局部优化过程,localoptimalprocedure,LOP)对其进行优化处理,就能得到唯一的DT三角网络。
LOP法则是Lawson在1977年提出的,其基本思想是运用DT三角网的空外接圆性质对由两个有公共边的三角形组成的四边形进行判断。
如果其中一个三角形的外接圆中含有第四个顶点,则交换四边形的对角线。
LOP局部优化过程
12.无约束散点域的三角剖分算法与实现:
*分割合并算法
*三角法生长算法
*逐点插入算法
@1*分割合并算法:
分割合并算法(divideandconquerdelaunaytriangulationalgorithm)的思想最早是由Shamos和Hoey在1975年提出的,并将其应用于V-图的构成(V-图是Vorinoi图的简称,是DT三角网的对偶图,为DT三角网中相邻三角形边垂直平分线交点的连线所形成的多边形,有关V-图的定义、性质和分割算法参见计算几何方面的书籍)。
Lewis和Robinson于1978年将该方法用来进行DT三角网的剖分,随后Lee和Schachter、Dwyer等相继对Lewis和Robinson的算法进行了优化和改进,其中Lee和Schachter于1980年的算法适合于无约束数据域的三角剖分,而Dwyer于1987年的算法则考虑了带约束条件的LOP优化策略,因而能处理带约束条件的数据。
分割合并算法的思想很简单,就是将复杂问题简单化,首先将数据点分割成易于进行三角剖分的子集,如一个子集中包括三个、四个点,然后对每个子集进行三角剖分,并用LOP算法保证三角剖分为DT三角网。
当每个子集剖分完成后,对每个子集的三角剖分进行合并,形成最终的整体三角网。
不同的实现方法可有不同的点集划分方法、子三角网生成方法及合并方法等。
分割合并算法的基本步骤为:
第一步,把数据集以横坐标为主、纵坐标为辅按升序进行排序;
第二步,如果数据集中的数据个数大于给定的阈值,则把数据域划分为个数近似相等的左右两个子集,并对每一子集做如下的工作,①计算每一子集的凸壳;
②以凸壳为数据边界,对每一数据子集进行三角剖分,并用LOP进行优化,使之成为DT三角剖分;
③找出连接左右子集两个凸壳的底线和顶线;
④由底线到顶线,合并两个子三角网;
第三步:
如果数据集中的数据个数小于给定的阈值,则直接输出三角剖分结果;
@2*三角网生长算法:
顾名思义,三角网生长算法就是从一个“源”开始,逐步形成覆盖整个数据区域的三角网。
从生长过程角度,三角网生长算法分为收缩生长算法和扩张生长算法两种。
收缩生长算法是先形成整个数据域的数据边界(凸壳),并以此作为源头,逐步缩小以形成整个三角网。
收缩生长算法与数据点的分布密度有关,实际情况往往比较复杂,例如当边界收缩后一个完整的区域可能会分解成若干个相互独立的子区域,这就增加了三角剖分的复杂性
扩张生长算法与收缩算法过程刚好相反,该算法是从一个三角形开始向外层层扩展,最终形成覆盖整个区域的三角网,其主要步骤为:
第一步,生成初始三角形。
在数据点中任取一点A(该点一般是位于数据点的几何中心附近),并寻找距离此点最近的点B,两者相连形成初始基线AB,如图。
利用三角剖分
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- GIS 算法 原理 知识点 总结