GIS算法原理知识点总结

1、GIS算法原理知识点总结算法设计和分析:1、算法设计的原则：正确性：若一个算法本身有缺陷，那么它将不会解决问题；确定性：指每个步骤必须含义明确，对每种可能性都有确定的操作。 清晰性：一个良好的算法，必须思路清晰，结构合理。2、算法的复杂性包括：时间复杂性和空间复杂性。3、时间复杂性：用一个与问题相关的整数量来衡量问题的大小，该整数量表示输入数据量的尺度，称为问题的规模。利用某算法处理一个问题规模为n的输入所需要的时间，称为该算法的时间复杂性。4、算法的概念：算法是完成特定任务的有限指令集。所有的算法必须满足下 面的标准：输入输出明确性有限性有效性GISGIS 算法的计算几何基础1、 理解矢量的

2、概念：如果一条线段的端点是有次序之分的，我们把这种线段 称为有向线段(directedsegment)。如果有向线段p1p2的起点P1在坐 标原点，我们可以把它称为矢量P2。5.矢量叉积：计算矢量叉积是直线和线段相关算法的核心部分。设矢量P =(x1,y1)，Q =(x2,y2),则矢量叉积定义为(0,0)、p1、p2和p1p2所组成的平行四边形的带符号的面积，即PXQ = x1 y2-x2 y1， 其结果是个标量。显然有性质PXQ= -(QXP)和PX-Q= -(PXQ)0P X Q0,则P在Q的顺时针方向；P X Qvo,贝U P在Q的顺逆针方向；P X Q0,则P Q共线，但可能同向也可

3、能反向6、判断线段的拐向：折线段的拐向判断方法，可以直接由矢量叉积的性质推 出，对于有公共端点的线段p0p1和P1P2,通过计算(p2-p0)X(P1-p0)的符 号便可以给出折线段的拐向。理解矢量的概念通过矢量差积的方法就可以判断的拐向了。7.判断点是否在线段上：设点为Q，线段为P1 P2: (Q-P1)X(P2-P1)=0且Q在以P1,P2为对角顶点的矩形内。前者抱走点在直线上，后者保 证点不在线段延长线或反向延长线上。8判断两线段是否相交(算法一)：快速排斥实验：设以线段P1P2为对角线的矩形为R,设以线段Q1Q2为对角 的矩形为T,如果R和T不相交，显然两线段不会相交基(p2-p0)X

4、(P1-p0)0，则P0P1在P1点拐向右侧后得到P1P2跨立实验：如果两线段相交，则两线段必然相互跨立对方。若p1p2跨立Q1Q2,则矢量(P1-Q1) 和 (P2-Q2)位于矢量(Q2-Q1)的两侧，则(P1-Q1)X(Q2-Q1)X(P2-Q1)X(Q2-Q1)0。当(P1-Q1)X(Q2-Q1)=0时，说明 (P1-Q1)X(Q2-Q1)共线，但是因为已经通过快速 排斥实验，所以P1一定在线段Q1Q2上；同理(Q2-Q1)X(P2-Q1)=0说明P2一定在线段Q1Q2上。所以判断P1P2跨立Q1Q2的依据是：(P1-Q1)X(Q2-Q1) X (Q2-Q1) X(P2-Q10。同理判断

5、Q1Q2跨立P1P2的依据是(Q1-P1)X(P2-P1) X (P2-P1) X(Q2-P1)0。注意在进行“跨立判断”的时候是进行两次跨立判断9.判断矩形内是否包含点：只要判断该店的横坐标和纵坐标是否都夹在矩形的左右边和上下边之间。10.判断线段、折线、多边形是否在矩形中：因为矩形是个凸集，所以只要判断所有端点都在矩形就行 了。11.判断矩形是否在矩形中：只要比较左右边界和上下边界就行了。12.判断圆是否在矩形中：圆心在矩形中且圆的半径小于或等于圆心到矩形四边的距离的最小值。13.判断点是否在多边形内:1)射线法：一条射线从点P开始，穿过多边形的边界的次数称为交点数目。当 交点数目是偶数时

6、，点P在多边形外部；否则，为奇数时，在多边 形内部。射线法要考虑几种特殊的情况，并且射线法适用于凸多边形2）转角法：多边形环绕点P的次数称为环绕数，环绕数为0时，点P在多边形外 部，否则在多边形内部。14.判断线段是否在多边形内：（折线是判断它的每条线段）条件一：线段的两个端点都在多边形内 条件二：线段和多边形的所有边都不内交。15.判断多边形否在多边形内：只要判断多边形的每条边是否都在多边形内即可。判断有m个顶点的多边形是否在一个有n个顶点的多边形内的复杂度为O（mXn）16.判断矩形是否在多边形内：将矩形转化为多边形，然后再判断是否在多边形内。17.判断圆是否在多边形内：计算圆心到多边形每

7、条变边的最短距离，若该距离大于或等于圆半径，则该圆在多边形内。18.判断点是否在圆内：计算圆心到该点的距离，若小于或等于半径，则该点在圆内。19.判断线段、折线、矩形、多边形是否在圆内：因为圆是凸集，所以只要判断是否每个顶点都在圆内即可。20.判断圆是否在圆内：设两圆为01,02,半径为r1,r2。先比较r1,r2的大小，若r1Rectangle (point, x-2, point., y 2, point, x+2, point, y+2):num+;arr num. . x=poiit. x;arrInum * ypoint y;if(numl)pDC-MoveTo (an num. x

8、xarr jium. y)； pDC-LineTo(arrnuin-l. x,arrnum-lty);Di5=Di5+tiQrtf (arrtiiuml, x-air rnuui-l_. x) *(arr num. xaii .LIUHI-1. , x)+ (arrnum y-arr Lnum-1* y)(arr Lnum y-arrnum-* y);str. Format|Dis);MessageBox(str);CView：:0nLButtonDown(nFlags point);|空间数据的变换算法1了解平面坐标变换的几种形式：2.仿射变换：它是使用最多的一种几何纠正方式。在保留线条平行

9、条件下，仿 射变换允许对长方形目标做旋转、平移、倾斜和不均匀缩放。旋转指在原点 旋转x和y轴；平移是指把源点移动到新的位置；倾斜是指以一个倾向将形 状改变为平行四边形；不均匀缩放是指在x或y方向同时或单独增大和缩小比例尺。Xcos：)x_(mxsin：)yAY=(mysin：)x(m)cos:)yBA1 = mxcos: , A =n sin :B1 = mysin : ,B2 = mycos :X二A Ax - AyY= BoB-jXBy平移变换实例代码：甘define MaxNum 100 tvpedef struct int x;int y;Pnt;PntarrPntMaxNum;int

10、 numPnt;void CmoveDlg:OnLButtonDown(UINT nFlags, CPoint point)/ TODO:在此添加消息处理程序代码和/或调用默认值CDC切DC二G巳tDC()：pDC-Rectangle(point.x-5?point* y-5#point, x+5, point* y+5): numPnt+;arrPnt InuniPnt x二point, x; arrPntnumPnt. y=point y：|CDialogEx:OnLBu11onDown(nFlags, point);bvoid CpatiDlg:OnBnClickedButtonLP0C

11、DC *pX-GetDC();Invalidate()； LpdateWindoO ; for(mt i=l ； iVnumPrYt; i) arrPnt i- y-=10;|pDC-Rectangle(arrPnti, x-5, arrPntil.y-5arrPnti,x+5, arrPnti. y+5):/fTODO：在此添加控件通知处理程序代码比例变换实现代码：int xl-150, yl=150, x2=300, y2-250;/比例因子fl oat s ;|-void CscaleChangeDlg:OnBnC1ickedBu11onSca1e()/ TODO:在此添加控件通知处理程

12、序代码CDC軽DC =GetDC()；Inval idate ();Updateffindow();/更新巳dit值LpdateData(TRUE):Ixl=xls；yl=yl*s;x2=x2*s;y2=y2s；pDC-MoveTo(xl1yl);pDC-LineTo(x21y2):bI旋转变换实现代码：float x=200, y=200?x2二400 y2=200, x3二200, y3-300?x4=400, y4=300;float PI=3* 1415926;void CspinDlg:OnBnC1ickedButtonSpLn 0/ TODO:在此添加控件通知处理程序代码CDC *

13、pDC-GetDCO :Inval i dat殆();Updateffindow0:Updat eData (TRUE)；x=x*cos (PI/180)*10) -y*sin (PI/180)*10);y=y*cos(PI/180)*10) +x*sln(PI/180)*10): x2=x2*cos(PI/180)*10)-y2*sin(PI/180)*10);y2=y2*cos(PI/180)*10)+x2*si n(PI/180)*10);x3=x3cos (PI/180)举10)-y3*sw(PI/180)*10):y3=y3*cos(PI/180)*10)+x3*sin(PI/180

14、) *10):x4=x4*cos(PI/180)*10)y4*si n(PI/180)*10);y4-y4*cos(PI/180)*10)+x4*sin(PI/180)*10): pDC-MoveTo(x, y);prc-LineTo(x2fy2):pDC-LineTo(x4, y4);pDCfdneTo(x3Jy3);pDC-LineTo(x, y);3.相似变换：图形的相似变换是指由一个图形到另一个图形，在改变的过程中保持形状不变（大小方向和位置可变）的图形。图形相似变换的性质：图形的相似变换不改变图形中每一个角的大小；图形相似变换后对应线段都扩大（或缩小）相同的倍数，这个数叫相似比。相似

15、变换面积：经相似变换的像与原图的面积等于相似比的平方。相似变换的分解：任何相似变换可以分解为放缩，平移，旋转和翻转变换的复合。相似变换是仿射变换的一种特殊情况,也就是在仿射变换中去除错位变换这个因子后的结果。X = n（x cos二-y sin : ）AY= m（x sin二心y cos : ） B0I= mcos := msin :X= AA,x - BiyY= B0B1xA4.矢量转栅格:点：简单的坐标变换线：线的栅格化面：线的栅格化+面填充 面（多边形）的填充方法1厂2、扫描法3、射线法4厂5、边界代数算法栅格表示法的精度与分辨率有关。在图、 （b b）、 （c c）中，栅格的分辨率分别

16、为 7*57*5，15*1115*11，24*1324*13。分辨率的大小与下面两个问题有关：(b)5.栅格矢量化：从栅格单元转换为几何图形的过程为矢量化；（一） 要求（矢量化过程应保持）：1）栅-矢转换为拓扑转换，即保持实体原有的连通性、邻接性等；2）转换实体保持正确的外形。（二） 方法方法一，实际应用中大多数采用人工矢量化法，如扫描矢量化，该法工 作量大，成为GIS数据输入、更新的瓶颈问题之一。方法二，程序转化转换（全自动或半自动）过程为：1、边界提取2、二值化3、二值图像的预处理4、细化:1皮法2）骨架法5、跟踪 拓扑化6”矢量点”转栅格实例：ir* MAX 100 struct PNT

17、i ntJC;ir.t y：struct PNT jrrMAX;int ent-;string str:IILLXICLLIL,yinlti, ycudx;剥6、void CpntToDemDlg:RcToDem()/ TODO:在此添加控件通知处理程序代码在此添加控件通知处理程序代码CDC *p!X：-GetDC();FILE *out;out=fopen (Mi: 3 JInvalidate ();UpdateWindowO;UpdateData(true);returnRecO;int dy(ymax-ymin)/(row );int dx (xniax-xrcin) / (col-);

18、Dool judqe=alse;fprintf(out,%d - ：nM/rowrcol);for (int i ；Krow*for(int j= ;jcol- ;j-M-)for(int n ;ncnt4 ；)(xwin* (j-) dx)(nJ . y(zmin-(ymin*(i- ) *dy) &arr(n yRectangle(xmin*(j丨)*dxrymin*(i ) dy xmin j dx,yniin i*dy); CRoctrt(xmin+(j- )dx/ymin+(i-i) dy.xmin j dy.ymin+i dy);pDC-FillSolidRect(4rtz

19、RGB(255rLrC);fprintf (out/%d r1); judgefalse;else(pDC-Rectangle(xmin*(j-I)*dxrymin* (i )*dytxmin*j*dx,ymin+i*dy); fprintf(out/w%dR#0);judg=false;fprintf (out/*nw);void CpntToDemDlg:returnRec(void)xmax=arr1 xzymax=arr1 y;xmin=arr1.x,ymin=arr1.y;for(inti=l;iarri x)if(yminarri.y)if(xmaxarri x) if(ymaxa

20、rri .y)xmin=arri.x;ymin=arri.y;磊pntTQDemXRow: |106.矢量数据的压缩:矢量数据的压缩包括两个方面的内容，一是在不扰乱拓扑关系的前提下，对采样点数据进行合理的抽稀。二是对矢量坐标数据重新进 行编码，以减少所需要的存储空间。1）间隔取点法：每隔K个点取一点，或舍去那些比规定距离更近的点，首末点 一定要保留o临界值法2 2）垂距法:磊pntTQDemX1原始曲线3对点2测试距离大于规定的限差4点2保留4对点3测试距离小于规定的限差限差ab光栏法的基本思想是（上图）：定义一个扇形区域，通过判断曲线上的点在扇形外还是在扇 形内，确定保留还是舍去。设曲线上的

21、点列为pi,i二1,2,，n,光栏口经为d,可根据 压缩量的大小自己定义，则光栏法的实施步骤可描述为：1连接pl和p2点，过p2点作一条垂直于p1p2的直线，在该垂线上取两点al和a2，使a1p2=a2p2=d/2,此时al和a2为“光栏”边界点，pl与al、pl与a2的连线为以pl为 顶点的扇形的两条边，这就定义了一个扇形（这个扇形的口朝向曲线的前进方向，边长是任意 的）。通过pl并在扇形内的所有直线都具有这种性质，即p1p2上各点到这些直线的垂距都不大于d/2。2若p3点在扇形内，则舍去p2点。然后连接pl和p3，过p3作plpl的垂线，该垂线与 前面定义的扇形边交于cl和c2。在垂线上找

22、到bl和b2点，使p3b1=p3b2=d/2,若bl或b2点（图4-4-3中为b2点）落在原扇形外面，则用cl或c2取代（图4-4-3中由c2取代b2）。此时用plbl和p1c2定义一个新的扇形，这当然是口径（b1c2）缩小了的“光栏”。3检查下一节点，若该点在新扇形内，则重复第（2）步；直到发现有一个节点在最新定义的 扇形外为止。4当发现在扇形外的节点，如图4-4-3中的p4，此时保留p3点，以p3作为新起点，重复13如此继续下去，直到整个点列检测完为止。所有被保留的节点（含首、末点），顺序地 构成了简化后的新点列。4 4）道格拉斯一普克法：首先将一条曲线首、末点连一直线，求出各点到该直线的

23、距离，选其最大者与规定的临 界值相比较若大于临界值，则离该直线距离最大的点保留，否则，将直线两端间各点全 部舍去，并将原线条分成两部分，对每部分线条再实施该抽稀过程，直到结束。抽稀结 果点数随选取限差临界值的增大而减少，应用时应根据精度要求来确定抽稀限差临界 值，以获得最好的结果。即道格拉斯 一普克（Douglas-peuker）算法。1ResultPi- 弦_ 第一轮垂距- 第二轮垂距阈值7.栅格数据的压缩:1）链式编码：3,1,7,0,1，23佔64,1血7,0,123,4,5费里曼链码（Frgem貯）2）游程编码：所谓游程是指按行的顺序连续且属性值相同的若干栅格。1rj记录每个游程像元数

24、111l5, 5A, 2, B, 3A, 1, C, 3, A, 1D, 1, C, 2, A, 2D, 2, C, 1, A, 2D, 2, A, 3-记录每个游程像元数1”J Z/Jj 工劭丿 J1U5, 5A, 2, B, 3A, L C, 3, A, 1D, b C, 2, A, 2D, 2, C, 1, A, 2D, 2, A, 3游程长度的记录方式有两种1记录每个游程起（迄）列号2记录每个游程像元数记录每个游程像元数5, 52, A3, B3, CL AL D2, C2, A3）块式编码：块式编码是将游程扩大到两维情况，把多边形范围划分成若干具有同一属性的正方形，然后对各个正方形进

25、行编码。块式编码的数据结构由初始位置（行列号）、半径和属性代码组成。MMMM22M M RM33M RRRM RRR R RR MM RR RR RR MR RRRR6MRRR R MMMMM M1 2 34 5 6 7 8L b2,M；b 3, bR：4, LMi1,5TLM：h 6 J1, M；1,7,2fM2, 3,2, R；2,5,h M；2,6, 1?R3, 1,U M；3,2, hR;3,5, 3,R：3,8, 1,M4, bL, M；4, 2, 3fR;4, &1, M5, 1,hM：5, 8, hM3）四叉树编码：四叉树又称四元树或四分树，是最有效的栅格数据压缩编码方法

26、之一四分树将整个图像区域逐步分解为一系列方形区域，且每一个方形区域具 有单一的属性。最小区域为一个象元。2334PMRM:M M MMMRRMKM MMRRRR 1 MMRRR RR 1 MMRRlRR R MMRRRRR R MMMRRRRR MMM MRR M M M74 5 6 7 82 388四叉树编码方法记录每个叶子结点的地址和属性2020OJz1层2层3层SW (2)NW (0)NE (1)2321 22 /200 201 202 203 230 231 232 2338 8隔点取样法实例：define Max 100日typedef structHint x;int y:Put;

27、Prit arr Max ;Pnt arr2 Max:int num=0;int num2=0;/定义俩数组int n;void Ccompre5s2Dlg:OnBnClickedCompress()(|/ IODO:在此添加控件通知处理程序代码CDC *pDC=GetDCO ./7Inva1 idateO;/UpdateWindow ();Updat eData (TRUE);for (ijit i=l: i-jmni； iH)if(i%n=l)fnum2+ + ：arr2 niim2 x=arr I i Lx；arr2 Enum2.尸arr订.v；if(num%n!=l) num2+;ar

28、r2| num2 l x=arr mim * x;arr2num2j. y-arrnujii. y：forhnt j=2;jMoveTo(ar:2 jl .xtarr2j-i. y);pDC-Lin?To (arr2 j,昭arr2jZ4y) ;void CcompressSDlg: :OnLButtonDown(l IXT nFlags CPoint point) / TODO:在此添加消息处理程序代码和/或调用默认值CDC W=GetDC0;pDC-Rectangle(points x-2 point, y-2, point, x+2, point* y+2): num+:arr丨num

29、I x=point x;aiLtnuun y二 y;i f (niml):pDC- MoveTo(airnum-1 x, airnum-l y):pDCLi neTo (.arr num.l. x, arr _nLin |. y),CDialogEx: : OnLBut ton Down (nF lags, point);空间数据内插算法1 1空间数据内插的定义：根据已知的空间数据估计(预测)未知空间的数据值。2.2.空间数据内插目标：1缺值估计：估计某一点缺失的观测数据，以提高数据密度。2内插等值线：以等值线的形式直观地显示数据的空间分布。3数据网格化。把无规则分布的空间数据内插为规则分布的

30、空间数据集，如规则矩形格网、三角网等。3 3空间内插法的种类：几何方法、统计方法、空间统计方法、函数方法、随机模拟方法、 物理模型模拟方法和综合方法。4 4优缺点比较：每一种方法均有其适用范围、算法和优缺点，因此，没有绝对最优的空间 内插方法。5.5.如何选择：对数据进行空间探索分析，根据数据的特点，选择最优方法；同时，应对内插 结果进行严格的检验。6 6空间数据内插的分类依据：1确定或随机；2点与面；3全局或局部等标准分类；4内插方法的基本假设和数学本质。3 3反距离权重插值算法：是一种局部插值算法，它假设未知值的点受较近控制点 的影响比较远控制点的影响更大。反距离权重方法的通用方程是：式中

31、，zo为点0的估计值；zi为控制点i的z值；dj为控制点i与点0间的趾离；s为在估算中 用到的控制点的数目；K为指定的幕。4 4双线性插值算法：是一种数字图像处理、DEM数据处理等方面使用较多的局原理：如图8.5所示，设f(0,0) = Zi,f (1，0)= Z2,f (0，1) = Z3，f (1，1)=乙，求f (x,y)点的值，其中x,y0，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 5 反距离权重插值实例:4inclu

32、dedefine MAX 100wtypedef struct-int x?y, zjFnt;部插值算法阳jRffinaiKPrrt arr MAX;int num=0;-vold CinterpolationDlg: lOnLButtonDown(1 IM nFJags, CPoint point) / TODO:在此添加消息处理程序代码和/或调用默认值CDC *pDCTextOutA(arrnurai . x-30, arr.num. y30tstr);CDialogEx: :OnLButtonDownliiFlags, point);-void Ciriterpolat ionDlg:

33、:OnBnClickedButtonlD (J/. TODO:在此添加控件通知处理程序代码double nAtor=OtdAtor=0;double disO,Z；CString str:for(int i=l；iT ex t Out A (XsY, str):TIN、DEM、DAT1 1数字高程模型概念与理解：高程常常用来描述地形表面的起伏形态，传统的高 程模型是等高线，其数学意义是定义在二维地理空间上的连续曲面函数，当此高程模型用计算机来表达时，称为数字高程模型。2 2数字高程模型：是通过有限的地形高程数据实现对地形曲面的数字化模拟或者 说是地形表面形态的数字化表示，英文为Digital

34、Elevation Model，简称DEM。3 3理解 DEMDEM 和 DTMDTM:由于高程数据常常采用绝对高程或海拔 （即从大地水准面起算的高 度），DEDEM M也常常称为 DTMDTM。要说明的是由于“ TerrainTerrain 一词的含义比较广泛，不同专业背 景对“TerrainTerrain 的理解也不一样，DTMDTM 趋向于表达比 DEMDEM 更为广泛的内容，详见后文的分析。表2数宇地面摸型有关术语术语全称全称持点与含义持点与含义DEMDigital ElevationUodel以绝对鬲程或梅拔表不的地形模堰以绝对鬲程或梅拔表不的地形模堰DlfMDigital Heig

35、ht Model以仃以仃: :意筒程茨示的地形模型，包期绝对為意筒程茨示的地形模型，包期绝对為 程和程和相对高程相对高程, ,为德国所使川为德国所使川DGHDigital Ground Model具冇连续变化特征的地表实体楔型，为英具冇连续变化特征的地表实体楔型，为英 国所国所使用使用Digital GeomorphologyUxiel除禹程外的除禹程外的K他地貌形态模型他地貌形态模型. .如坡度、如坡度、 坡向坡向等等DTMDigital Terrain Model泛指地形表面泛指地形表面H燃、人文燃、人文 社会景观模型社会景观模型, ,DTEDDigital Terrain Elevati

36、onModel为美国国防制图局所侵用的地形模型为美国国防制图局所侵用的地形模型. .强强 调模型调模型的格网结构特征的格网结构特征豪豪4.4. TINTIN 和规则 DEMDEM 的区别：不规则三角网数字高程模型由连续的三角面组成，三角形的 形状、大小取决于不规则分布的点的位置和密度。地形变化越简单，采样点就越少，则单元格就越大；反之地形变化比较复杂，数据点分布比较密集，格网单元就越小。因此 TINTIN 与规则格网 DEMDEM 显著不同之处在于 TINTIN 模型不需要维护模型的结构规则性，不但 能灵活地随地形的复杂程度而改变格网单元大小，避免平坦地形的数据冗余，而且又能按地形特征点线如山

37、脊点、山谷线、地形变化线等表示地形特征。规则格网DEM不规则三角网 TIN优点r优点简单的数据存储结构；与遥感影像数振的复合性:好的表面分析功能较少的点可获取较高的 精度；可辨分辨率；良妤的拓扑结构缺点 O 效率较低；数据冗余；格网结构规则缺点袤面分析能力较差；构建比较费时；算法设计比较复杂5.DEM5.DEM 数据结构:规则格网DEM数据结构不规则三角形DEM数据结构6 6规则格网数据： 由于DEM的边界范围一般是规则矩形， 而实际地形范围却是 不规则的，还应考虑不在研究区域内的DEM高程值的表示方法（无效区域数据）， 一般是给出一个特殊的常数值，如-9999等。规则格网DEM的数据文件一般

38、包 含用对DEM数据进行说明的数据头和DEM数据体两部分。1）数据头：一般包括定义DEM西南角起点坐标、坐标类型、格网间距、行列 数、最低高程以及高程放大系数等内容；2）数据体：按行或列分布记录的高程数字阵列。7.TIN7.TIN :在TIN模型中，基本的结构元素有三角形顶点、边和面。它们之间存在 着点与线、点与面、线与面、面与面等拓扑关系。理论上，通过组成三角形的三 顶点可完整地表达三角形的构成以及三角形顶点、三角形边、三角形之间的拓扑 关系（下图），这种结构只需要两个文件，即三角形顶点坐标文件和组成三角形三 顶点（通常用点在坐标文件中的序号表示）文件。这种结构虽然简单，三角形结 构元素的拓

39、扑关系却是隐含的，不利于TIN模型的检索与应用。因此，围绕三角 形的拓扑关系描述而产生了多种TIN的数据结构。miSrfiia1525西砸朋帧臥歸网西砸朋帧臥歸网西娥朋臥刪掾血西娥朋臥刪掾血LQ榕Kff # W PEM ft埠以咻& &TINTIN 模型的面结构最大特点是：由于存储了三角形之间的邻接关系，TIN内插、检 索、等高线提取、显示以及局部结构分析都比较方便，不足之处是：存储量较大， 而且在TIN的编辑中要随时维护这种关系。9.9. DEMDEM 数据获取：建立DEM的第一步是获取地形数据。DEM的数据源和数据获取方式对于DEM的最终质量至关重要。DEM原始数据主要是高

40、程和平面位置数 据，在可能条件下还应包括各种地形结构线如山脊线、山谷线、断裂线等。另外，DEM应用目的、数据采集效率和成本、技术熟练程度也影响着DEM数据采集的方法和策略。/*目前DEM的数据主要来源于地形图、摄影测量与遥感影像数据、地面测量、既有DEM数据等。*/10.10. 坡度：（1 1） 坡度是地表形态最为重要的因子，通过坡度可以完整地形成地形曲面（EvaEva ns,1972ns,1972;Strahler,1956Strahler,1956）；（2）坡度是地形曲面函数一阶微分的函数，表达了高程随距离变化的比率（坡度定义为地面一点的切平面与水平面之间的夹角），而坡度的变率是地形曲 面

41、的二阶微分，进一步刻画了坡度的变化，从而反映地形的复杂程度；（3）大量的研究表明，区域DEM高程精度与平均坡度值之间存在强相关，通过模型的平均坡度可预测DEM的精度（Ackermann,1979; Ley, 1986;（4）坡度通过相互垂直的两个坐标轴方向的高程变化表达地形曲面局部单元的 倾斜程度，也就是通过地形表面的凸面和凹面来描述地形表面特性，即地表 的陡峭方向和大小。11.11. TINTIN 数据的建立：基于不规则三角网的数字高程模型（Based on TriangulatedIrregular Network DEM，简写为Based on TIN DEM俗称TIN）就是用一系列 互

42、不交叉、互不重叠的连接在一起的三角形来表示地形表面。TIN是DEM的 又一个主要数据模型，TIN的特点在其字面意思中表露无遗。图图口惶蛰的基口惶蛰的基丰琏炭结仪丰琏炭结仪不规则分布数第岂网游11.TINTIN 的三角咅【J J 分准则：TINTIN 的三角剖分准则是指 TINTIN 中三角形的形成法则，它决定着三角形的几何形状和 TINTIN 的质量。目前在 GISGIS 计算几何和计算机图形学邻域常用的 三角剖分准则有以下几种(1)(1) 空外接圆准则：在TIN中，过每个三角形的外接圆均不包含点集的其余任 何点，如图A所示；(2)(2) 最大最小角准则：在两相邻三角形形成的凸四边形中，这两三

43、角形中的最小内角一定大于交换凸四边形对角线后所形成的两三角形的最小内角，如图B所示；(3)(3)最短距离和准则： 图C,最短距离和就是指一点到基边两端的距离和为最 小;(4)(4) 张角最大准则：图D, 点到基边的张角为最大；(5)(5) 面积比准则：图E,三角形内切圆面积与三角形面积或三角形面积与周长 平方之比最小；(6)(6) 对角线准则：图F,两三角形组成的凸四边形的两条对角线之比。超过给 定限定值时对三角形进行优化。理论上可以证明：张角最大准则、空外接圆准则及最大最小角准则是等价的，其 余的则不然。三角形剖分准则是建立三角形网络的基本原则，应用不同的准则将会得到不 同的三角形网络。一般

44、而言，应尽量保持三角网的唯一性，即在同一准则下由不 同的位置开始建立三角形网络，其最终的形状和结构应是相同的，在这一点上， 张角最大准则、空外接圆准则及最大最小角准则可以做到。对角线准则含有主观 因素，现今使用已不多。通常将在空外接圆准则、最大最小角准则下进行三角剖分称为Delaunay三角剖(P)(E)面积比准则F对角线准则(B)最大最小角椎则( (C)最短距离和准则分，简称为DT,同时空外接圆和最大最小角也是Delaunay三角网的两个 基本性质。DT三角剖分是目前应用最为广泛的三角剖分方法，其特性是可最大 限度避免狭长三角形的出现以及不管从何处开始构网都能保持三角形网络的唯 一性，这一点

45、在实际应用中相当重要。实际上，在任何三角剖分准则下得到的TIN,只要用LOP法则（局部优化过程,locallocal optimaloptimal procedureprocedure， LOPLOP 对其进 行优化处理，就能得到唯一的DT三角网络。LOP法则是Lawson在1977年提出 的，其基本思想是运用DT三角网的空外接圆性质对由两个有公共边的三角形组 成的四边形进行判断。如果其中一个三角形的外接圆中含有第四个顶点，则交换四边形的对角线。1212无约束散点域的三角剖分算法与实现：*分割合并算法三角法生长算法*逐点插入算法1*分害U合并算法：分 害U合 并 算 法 （divide and

46、 conquer delaunaytriangulationalgorithm）的思想最早是由Shamos和Hoey在1975年提出的，并将其应用于V-图的构成（V-图是Vorinoi图的简称，是DT三角网的对偶图，为DT三角网 中相邻三角形边垂直平分线交点的连线所形成的多边形，有关V-图的定义、性质和分割算法参见计算几何方面的书籍）。Lewis和Rob in son于1978年将该方法用来进行DT三角网的剖分， 随后Lee和Schachte、Dwyer等相继对Lewis和Robinson的算法进行了优化和改进，其中Lee和Schachter于1980年的算法适合于无约束数据域的三角剖分，而D

47、wyer于1987年的算法则考虑了带约束条 件的LOP优化策略，因而能处理带约束条件的数据。分割合并算法的思想很简单，就是将复杂问题简单化，首先将数据点分割成 易于进行三角剖分的子集，如一个子集中包括三个、四个点，然后对每个子集进 行三角剖分，并用LOP算法保证三角剖分为DT三角网。当每个子集剖分完成 后，对每个子集的三角剖分进行合并，形成最终的整体三角网。不同的实现方法 可有不同的点集划分方法、 子三角网生成方法及合并方法等。分割合并算法的基本步骤为：递归的对原始数据进 行分割.将原始数据 域分成大致相等的左 右两个部分对每一个子集进行三 角剖分.并用LOP算 法进行优化寻找了集凸壳的底线

48、和顶线（粗实线），并从底线开始自下而 上进行合并利用凸壳算法上成每子块的边界合并三角网*形成最 终的三角形网络第一步，把数据集以横坐标为主、纵坐标为辅按升序进行排序;第二步，如果数据集中的数据个数大于给定的阈值，则把数据域划分为个数近似相等的左右两个子集，并对每一子集做如下的工作，计算每一子集的凸壳； 以凸壳为数据边界，对每一数据子集进行三角剖分，并用LOP进行优化，使之成为DT三角剖分；找出连接左右子集两个凸壳的底线和顶线；由底线到顶 线，合并两个子三角网； 第三步：如果数据集中的数据个数小于给定的阈值，则直接输出三角剖分结果;设左右凸壳分别为Z和瓦/和B分 别是Z和R上的点，A.丧满足如下

49、 条件：A JVAk=maxXLB: Y=ra.inX底线査找；从48有向线段开始， 对于人中点#如果沿逆时针且与B相邻的V点位于曲的右侧，则B=Y；在新的力君方向上，如果顺吋针且 与/相邻的玉点位于4S的冇侧，则 直到E和中没有位于 川8线段右侧的点为止，才&为连接兀 和的底线。顶线査找：从有向线段开始， 对于盘中点*如果顺时针且与鸟相 邻的F点位于上心的左侧，则召=二 在新的&召方向上*如果逆吋针且 与/相邻的乂点位于49的左侧，则 北三葛，直到和卫中没有位于 儿8线段左侧的点为止* /!丘为连接 和R的上线口子三角网合并： 合并的方式是同 层优先，从下至上的递归方式进.

50、行这是分割合并算法中“合并 一词的由来）。合并时先找出两 个相邻子三角网凸壳在上下（或 左右）的公共切线，这些公共切 线将足最终三角网的一部分。上 卜公切线查找完后，即可从连接两子三角网的底线开始，在两子 三角网中寻找与底线组成Delaunay三角形的第三点，选 其屮外接圆半径小的一个插入到 最终的三角网中。新生成的连接 左右两个子三角网的边成为新的 底线，逐步上推到顶线结束，如 图所示。在第一步中，主要工作是对数据点进行排序，目的是使 了三角网不相互重叠和交叉。一般是以横坐标为主、纵 坐标为辅按升序进行排序，即数据点之间满足如下的条 件：（兀J） （兀X+J不等式成立的条件是Xz. 兀+1且

51、必必+1排序的方法采用以递归方式进行的分割快速排序方法, 详见数据结构书籍的介绍。第二步是该算法 的主体，包括数 据集的连续分割、凸壳生成、凸壳 三角剖分、子网合并等内容，集 中体现了该算法 的基本思想，即 分割（数据点的 分割），合并（子三角网的合并）。80/2* *三角网生长算法：顾名思义，三角网生长算法就是从一个“源”开始，逐步 形成覆盖整个数据区域的三角网。 从生长过程角度，三角网生长算法分为收缩生 长算法和扩张生长算法两种。收缩生长算法是先形成整个数据域的数据边界（凸 壳），并以此作为源头，逐步缩小以形成整个三角网。收缩生长算法与数据点的 分布密度有关，实际情况往往比较复杂，例如当边

52、界收缩后一个完整的区域可能 会分解成若干个相互独立的子区域，这就增加了三角剖分的复杂性扩张生长算法与收缩算法过程刚好相反，该算法是从一个三角形开始向外层层扩 展，最终形成覆盖整个区域的三角网，其主要步骤为：第一步，生成初始三角形。在数据点中任取一点A（该点一般是位于数据点的几 何中心附近），并寻找距离此点最近的点B,两者相连形成初始基线AB,如图。利用三角剖分准则（空外接圆准则或张角最大准则），在数据域中寻找第三点C,从而形成第一个Delaunay三角形ABG第二步，扩展形成三角网。以初始三角形的三条边为初始基线， 利用空外接圆准则或张角最大准则，寻找能与该三条初始基线形成 点。Delauna

53、y三角形的D、E、FDBDBFAACCE、亠注意：（1）初始边界将整个数据域分成两个部分，搜寻第三点 般疋在初始三角形另一顶点的异侧范围进行。例如若初始三角形为ABC,初始边界为AB，第三个顶点为C,能与三角形ABC共用AB边的另一三角形ABD，D点要位于AB边的 另一侧，而不能与C同侧，判断方法为：设賣錢两端点的坐标先4（心.儿）占伽另两点分别対可通过下式判断点帆D在曲的同耳侧关系耳F（.xfy）= y-a-b口 =仏加（“f）卜在或中代入 UD坐标，则有若刊叱儿）旨戸JD）符号相同，则D位干肋的同一伽 若比）宵符号相副 则帆D分月惟于血的两帕君叽恥）=o或F（心则 u 或D乌屈共罐2)为避

54、免三角形的交叉和重复，通过上述异侧点判别所选的第三点还要进行进 一步的认定。其方法是根据三角形任一条边最多只能与两个三角形所共用这个条 件，进行三角形的全等比较，即判断新三角形的三条边是否被前面所形成的三角 形共用过两次，如果是，则新三角形无效，否则为有效三角形。逐点插入算法逐点插入算法的过程非常简单，基本步骤为：第一步，定义包含所有数据点的初始包容盒，并对该包容盒进行初始三角剖分； 第二步，对所有数据点进行循环，做如下工作(设当前处理的数据点为P)，在已存在的三角网中，查找包含p的三角形t:卩与t的三个顶点相连，形成t的三个初始三角剖分；用LOP算法对初始三角剖分进行优化处理。第三步，处理外

55、围三角形。1212规则格网 DEMDEM 读取实例：void CDemView： :OnDeiiiDeiti()(.7 IODO:在此添加命令处理稈子代码CDC *pDC=GtDC():int row=10, col=10：CStrin8 sir;int size=5:定文二錐数组int dem 100 100kchar strr 1(X5;char *p;FILE *in；in=fopenC*!): WVpatiWGIS算法原理deni2, txt*, *r*):fscanf (in,%dnftrcv, Icol);for (int i=l; i：=row;i+)flfgets(strr,

56、100, in)； pstrtok(strr, ”)； demil=Btoi (p):for (int j=l; j=Col-r： j+)pFstrtok (NULL, * *):demij+l=atoi(p);/str* Formatdem3 4): MessageBox (str);)fclose(in);for(int i=l;i=col;i+)for(int j=l;jRectangle( (t一1)水呂(j-Dsizp i*sizefj*size);/CRecxrt (i-l)*size, (j-1)*sizcri*size, j*size: /pDC-Fi 1ISolidRect(

57、ftrt, RGB(demj+1 i+l*5F0,0): pDC-TextOut (i-1)*size,(J-l)*size, itoa(deiij iFstrr, 10); J13缓冲区分析算法：56.缓冲区（bufferbuffer）概念：是根据空间数据库中的点、线、面地理实体或规划 目标，自动建立其周围一定宽度范围的多边形。分类：点缓冲区、线缓冲区、面缓冲区和复杂实体缓冲区。57.步进拟合的思想，即圆弧弥合的方法：（双侧平行线法）将圆心角等分，用等长的弦代替圆弧，即用均匀步长的直线段逼近圆弧段。 等分的圆心角越小，步长越小，误差越小；等分的圆心角越大，步长越大，误差 越大。58.凸角圆弧法，基本思想：在轴线的两端用半径为缓冲距的圆弧弥合；在 轴线的各转折点，判断该点的凸凹性，在凸侧用半