GIS算法原理知识点总结.docx

《GIS算法原理知识点总结.docx》由会员分享，可在线阅读，更多相关《GIS算法原理知识点总结.docx（31页珍藏版）》请在装配图网上搜索。

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

2、概念：如果一条线段的端点是有次序之分的，我们把这种线段 称为有向线段(directed segment)如果有向线段plp2的起点Pl在坐 标原点，我们可以把它称为矢量P2。5. 矢量叉积：计算矢量叉积是直线和线段相关算法的核心部分。设矢量P= (xl,yl), Q= (x2,y2)，则矢量叉积定义为(0,0)、pl、p2 和plp2所组成的平行四边形的带符号的面积，即PXQ = xby2-X2.yl, 其结果是个标量。显然有性质PXQ=- (QXP)和Px-Q=- (PxQ)oP X Q0,则P在Q的顺时针方向；void CpntToDemDlg: RecToDemO3(/ TODO:在此添

3、加控件通知处理程序代码CDC *pDC-GetDC()；FILE *OUt；out=fopen (d: Wraster. txt, w);Invalidate();UpdateWindow();UpdateData(true);returnRecO ;int dy(ymax-ymin)/(row-);int dx(xmax-xmin)/(col-);bool judge-false;fprintf(out,d idn,row,col);for(int i=l;irow+ ;i+)(for(int j ;jcol+ ;j+)for(int n= ;ncnt+ ;n+)(xmin+(j- )*dx

4、)&arrn.x(ymin+(i- )*dy)& arr(nJ.yRectangle(xmin+(j-：)*dx,ymin+(i)*dy,xmin+j*dxzymin+i*dy); CRect rt(xmin+(j- )*dx,ymin+(i- )*dy,xmin+j*dx,ymin+i*dy); pDC-FinSolidRect(&rt,RGB(255, ,0);fprintf(outz%d ,1); judge=false;elsepDC-Rectangle(xmin+(j- )*dxrymin+(i- )*dy,xmin+j*dxzymin+i*dy); fprintf(out,%d ,

5、0);judge=false;fprintf(out,Xn);void CpntToDemDlg:returnRec(void)xmax=arr1.xzymax=arr1.y; xmin=arr1.xzymin=arr1.y; for(int i=l;iarri.x) if(yminarri.y) if(xmaxarri.x) if(ymaxarri.y)Col:Col:io确定取消矢量数据的压缩：矢量数据的压缩包括两个方面的内容，一是在不扰乱拓扑关系的前提下，对采样点数据进行合理的抽稀。二是对矢量坐标数据重新进 行编码，以减少所需要的存储空间。1）间隔取点法：每隔K个点取一点，或舍去那些比规

6、定距离更近的点，首末点 一定要保留。2）垂距法:原始曲线。.Q-一3对点2测试距离大于规定的限差43b 2。-一对点3测试距离小于规定的限差,Q4限差|光栏法的基本思想是（上图）：定义一个扇形区域，通过判断曲线上的点在扇形外还是在扇 形内，确定保留还是舍去。设曲线上的点列为pi, i = 1, 2, n,光栏口经为d,可根据 压缩量的大小自己定义，则光栏法的实施步骤可描述为：1。、连接p1和p2点，过p2点作一条垂直于p1p2的直线，在该垂线上取两点a1和a2,使 a1p2=a2p2=d / 2,此时a1和a2为“光栏”边界点，p1与a1、p1与a2的连线为以p1为 顶点的扇形的两条边，这就定

7、义了一个扇形（这个扇形的口朝向曲线的前进方向，边长是任意 的）。通过p1并在扇形内的所有直线都具有这种性质，即p1p2各点到这些直线的垂距都不 大于d您。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）步；直到发现有一个

8、节点在最新定义的 扇形外为止。4。、当发现在扇形外的节点，如图4-4-3中的p4,此时保留p3点，以p3作为新起点，重复 1。3。如此继续下去，直到整个点列检测完为止。所有被保留的节点（含首、末点），顺序地 构成了简化后的新点列。4）道格拉斯一普克法：首先将一条曲线首、末点连一直线，求出各点到该直线的距离，选其最大者与规定的临 界值相比较若大于临界值，则离该直线距离最大的点保留，否则，将直线两端间各点全 部舍去，并将原线条分成两部分，对每部分线条再实施该抽稀过程，直到结束。抽稀结 果点数随选取限差临界值的增大而减少，应用时应根据精度要求来确定抽稀限差临界 值，以获得最好的结果。即道格拉斯一普克

9、（Douglas-peuker）算法。ResultP】弦第一轮垂距第二轮垂距I | 阈值6. 栅格数据的压缩:1）链式编码：3,1,7,0,1,2,3,4,5,64,1,6,7,0,1,2,3,4,5费里曼链码（Freeman）2）游程编码：所谓游程是指按行的顺序连续且属性值相同的若干栅格。游程长度的记录方式有两种记录每个游程起（迄）列号 记录每个游程像元数AABBBACCCADCCAADDCAADDAAA记录每个游程像元数5, 52, AB1, A3, C1, AD1, C2, A3）块式编码：块式编码是将游程扩大到两维情况，把多边形范围划分成若干具有同一属性的正方形，然后对各个正方形进行编

10、码。 块式编码的数据结构由初始位置（行列号）、半径和属性代码组成。1,2,M；1,3,1,R；1,1,M；1,5,1,M；1,6,M；1,7,2,M3,2,R；2,5,1,M；2,1,R1,1,M；3,2,1,R；3,3,R；3,8,1,M1,1,M；4,2,3,R;8,1,M1,1,M：5,8,1,M3）四叉树编码：四叉树又称四元树或四分树，是最有效的栅格数据压缩编码方法之一。四分树将整个图像区域逐步分解为一系列方形区域，且每一个方形区域具有单一的属性。最小区域为一个象元。2 3 4 5 6 7 81M MM MRMMMM MM M2RRMR3MRR RR RR RR RRM4MRRM5MR

11、R RR RR RR RRM6MRRM7M MM MRRRRRM8MRRMMM四叉树编码方法记录每个叶子结点的地址和属性NW (0)SW (2)200 201 202 203 230 231 232 233NE (1)SE (3)7. 隔点取样法实例:ttdefine Max 100-typedef structEiint x;int y;Pnt;Pnt arrMax;Pnt arr2Max;int num=0; int num2=0; /定义俩数组 int n;void Ccompress2Dlg:OnBnClickedCompress()| / TODO:在此添加控件通知处理程序代码CDC

12、 *pDC=GetDC();/Invalidate();/UpdateWindow();UpdateData(TRUE);for(int i=l;i=num;i+)(if (i%n1)(num2+；arr2num2. x=arri. x;arr2num2. v=arri v;)if (num%n!=l)( num2+;arr2num2. x=arrnum. x;arr2num2. y=arrnum, y;for(int j=2;jEl 1 ipse(arr2 j. x-5, arr2j. y-5, arr2j. x+5, arr2j. y+5);pDC-MoveTo (arr2 j-1 . x

13、, arr2 j-1. y); pDC-LineTo(arr2j. x, arr2j y);void Ccompress2Dlg:OnLButtonDown(UINT nFlags, CPoint point)/ TODO:在此添加消息处理程序代码和/或调用默认值CDC *pDC=GetDC():pDC-Rectangle(point, x-2, point, y-2, point, x+2, point, y+2); num+;arrnum. x=point. x;arrnum. y=point. y;if(numl)(pDC-MoveTo(arrnum-1. x, arrnum-1, y)

14、; pDC-LineTo(arrnum. x, arrnum, y);CDialogEx:OnLButtonDown(nFlags, point);空间数据内插算法1 .空间数据内插的定义：根据已知的空间数据估计(预测)未知空间的数据值。2. 空间数据内插目标： 缺值估计：估计某一点缺失的观测数据，以提高数据密度。 内插等值线：以等值线的形式直观地显示数据的空间分布。 数据网格化。把无规则分布的空间数据内插为规则分布的空间数据集，如规则矩形格网、三角网等。3. 空间内插法的种类：儿何方法、统计方法、空间统计方法、函数方法、随机模拟方法、物理模型模拟方法和综合方法。4. 优缺点比较：每一种方法均

15、有其适用范围、算法和优缺点，因此，没有绝对最优的空间内插方法。5. 如何选择：对数据进行空间探索分析，根据数据的特点，选择最优方法；同时，应对内插结果进行严格的检验。6空间数据内插的分类依据： 确定或随机；点与面； 全局或局部等标准分类；内插方法的基本假设和数学本质。3. 反距离权重插值算法：是一种局部插值算法，它假设未知值的点受较近控制点 的影响比较远控制点的影响更大。反距离权重方法的通用方程是：20式中，Z0为点0的估计值；Z,为控制点，的z 值；，为控制点i与点0间的趾离；s为在估算中 用到的控制点的数目；K为指定的慕。部插值算法。5反距离权重插值实例:4. 双线性插值算法：是一种数字图

16、像处理、DEM数据处理等方面使用较多的局原理：如图8.5所示，设犬0, 0) = Z|, /(I, 0)=Z2, /(0, 1) = Z3, /(I, 1) = Z4,求f(x,y)点的值,其中知，e 0, lo 将f(0, 0)、/(I, 0)、f(0, 1)、/(1, 1)代入双线 性内插方程：J(x,y) = or + by + cxy + d求出各参数小b、c、d的值，再将代入，解得 TUy)。P X Q0,则PQ共线，但可能同向也可能反向。6、判断线段的拐向：折线段的拐向判断方法，可以直接由矢量叉积的性质推 出，对于有公共端点的线段pOpl和P1P2,通过计算(p2-p0) X(Pl

17、-pO)的符 号便可以给出折线段的拐向。pO基(p2p0) X(P1-p0)0, 则 P0P1在P1点拐向右侧后得到P1P2基(p2p0) X(P1.pO)vO,则 POP1在P1点拐向左侧后得到P1P2po基(p2-p0) X(P1-p0)=0,则P0P1P2三点共线理解矢量的概念通过矢量差积的方法就可以判断的拐向了。7. 判断点是否在线段上：设点为Q,线段为Pl P2： (Q-Pl)X(P2-Pl)=O且Q在以Pl, P2为对角顶点的矩形内。前者抱走点在直线上，后者保 证点不在线段延长线或反向延长线上。8、判断两线段是否相交(算法一)：快速排斥实验：设以线段P1P2为对角线的矩形为R,设以

18、线段Q1Q2为对角的矩形为T,如果R和T不相交，显然两线段不会相交#include#define MAX 100 etypedef struct s int x, y, z; Pnt;Pnt arrMAX;int num=0;-void CinterpolationDlg:OnLButtonDown(UINT nFlags, CPoint point)/ TODO:在此添加消息处理程序代码和/或调用默认值CDC *pDC=GetDC();pDC-El1 ipse(point, x-3, point, y-3, point, x+3, point, y+3);num+;arrnum. x=poi

19、nt. x;arrnum, y=point, y;UpdateData(TRUE);arr num. z=IDWy ； / IDWy就是IDWz,纯属手误CString str;str. Formatarrnum, z); pDC-TextOutA(arrnum. x-30, arrnum, y-30, str);CDialogEx:OnLButtonDown(nFlags, point);J-void CinterpolationDlg:OnBnClickedButtonIDW()(/ TODO:在此添加控件通知处理程序代码double nAtor=0, dAtor=0;double dis

20、=0,Z;CString str;for(int i=l;iTextOutA(X,Y,str);TIN、DEM、DAT数字高程模型概念与理解：高程常常用来描述地形表面的起伏形态，传统的高 程模型是等高线，其数学意义是定义在二维地理空间上的连续曲面函数，当此高 程模型用计算机来表达时，称为数字高程模型。1. 数字高程模型：是通过有限的地形高程数据实现对地形曲面的数字化模拟或者 说是地形表面形态的数字化表示，英文为Digital Elevation Model,简称DEM。2. 理解DEM和DTM：由于高程数据常常采用绝对高程或海拔（即从大地水准面起算的高 度），DEM也常常称为DTMo要说明的是

21、由于“Terrain”一词的含义比较广泛，不同专业背 景对“Terrain”的理解也不一样，DTM趋向于表达比DEM更为广泛的内容，详见后文的分析。表2数字地面模型有关术语术语全称特点与含义DEMDigital Elevation Model以绝对高程或海拔表示的地形模型DHMDigital Height Model以任意高程表示的地形模型，包括绝对高 程和相对高程，为德国所使用DGMDigital Ground Model具有连续变化特征的地表实体模型，为英 国所使用Digital Geomorphology Model除高程外的其他地貌形态模型，如坡度、 坡向等DTMDigital Ter

22、rain Model泛指地形表面自然、人文、社会景观模型,DTEDDigital Terrain Elevation Model为美国国防制图局所使用的地形模型，强 调模型的格网结构特征cTIN和规则DEM的区别：不规则三角网数字高程模型由连续的三角面组成，三角形的 形状、大小取决于不规则分布的点的位置和密度。地形变化越简单，采样点就越少，则单元 格就越大；反之地形变化比较复杂，数据点分布比较密集，格网单元就越小。因此TIN与规则格网DEM显著不同之处在于TIN模型不需要维护模型的结构规则性，不但 能灵活地随地形的复杂程度而改变格网单元大小，避免平坦地形的数据冗余，而且又能按地 形特征点线如山

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

24、进行说明的数据头和DEM数据体两部分。1）数据头：一般包括定义DEM西南角起点坐标、坐标类型、格网间距、行列 数、最低高程以及高程放大系数等内容；2）数据体：按行或列分布记录的高程数字阵列。例我1525敏酮角格咐利蠕网12345.0B 酗角格怫无冷蠕处54321.0、格网幄10里融幅靴*999912,14,15,咛 6n 蚌倾的DEM蹴件咖观3困术TIN：在TIN模型中，基本的结构元素有三角形顶点、边和面。它们之间存在 着点与线、点与面、线与面、面与面等拓扑关系。理论上，通过组成三角形的三 顶点可完整地表达三角形的构成以及三角形顶点、三角形边、三角形之间的拓扑 关系（下图），这种结构只需要两个

25、文件，即三角形顶点坐标文件和组成三角形三 顶点（通常用点在坐标文件中的序号表示）文件。这种结构虽然简单，三角形结 构元素的拓扑关系却是隐含的，不利于TIN模型的检索与应用。因此，围绕三角 形的拓扑关系描述而产生了多种TIN的数据结构。坐标表三角形表序号属性XyZ123456序号属性XyZ123456A顶 点1顶点2顶点311622263336444655561基本铤表结构图TIN模型的基本链表结构TIN模型的面结构最大特点是：由于存储了三角形之间的邻接关系，TIN内插、检 索、等高线提取、显示以及局部结构分析都比较方便，不足之处是：存储量较大， 而且在TIN的编辑中要随时维护这种关系。7. D

26、EM数据获取：建立DEM的第一步是获取地形数据。DEM的数据源和数据获 取方式对于DEM的最终质量至关重要。DEM原始数据主要是高程和平面位置数 据，在可能条件下还应包括各种地形结构线如山脊线、山谷线、断裂线等。另外， DEM应用目的、数据采集效率和成本、技术熟练程度也影响着DEM数据采集的 方法和策略。/*目前DEM的数据主要来源于地形图、摄影测量与遥感影像数据、地面测量、 既有DEM数据等。*/坡度：(1) 坡度是地表形态最为重要的因子，通过坡度可以完整地形成地形曲面(Evans,1972； Strahler,1956)；坡度是地形曲面函数一阶微分的函数，表达了高程随距离变化的比率(坡 度

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

28、ed on TIN DEM,俗称 TIN)就是用一系列 互不交叉、互不重叠的连接在一起的三角形来表示地形表面。TIN是DEM的 又一个主要数据模型，TIN的特点在其字而意思中表露无遗。11. TIN的三角剖分准则：TIN的三角剖分准则是指TIN中三角形的形成法则，它决定 着三角形的几何形状和TIN的质量。目前在GIS、计算几何和计算机图形学邻域常用的 三角剖分准则有以下儿种(1) 空外接圆准则：在TIN中，过每个三角形的外接圆均不包含点集的其余任 何点，如图A所示；最大最小角准则:在两相邻三角形形成的凸四边形中，这两三角形中的最 小内如一定大于交换凸四边形对角线后所形成的两三角形的最小内角，如

29、图B所示；最短距离和准则：图C,最短距离和就是指一点到基边两端的距离和为最 小；(2) 张角最大准则：图D, 点到基边的张角为最大；面积比准则：图E,三角形内切圆面积与三角形面积或三角形面积与周长 平方之比最小；(3) 对角线准则：图F,两三角形组成的凸四边形的两条对角线之比。超过给 定限定值时对三角形进行优化。理论上可以证明：张角最大准则、空外接圆准则及最大最小角准则是等价的，其 余的则不然。三角形剖分准则是建立三角形网络的基本原则，应用不同的准则将会得到不 同的三角形网络。一般而言，应尽量保持三角网的唯一性，即在同一准则下由不 同的位置开始建立三角形网络，其最终的形状和结构应是相同的，在这

30、-点上, 张伯最大准则、空外接圆准则及最大最小们准则可以做到。对角线准则含有主观 因素，现今使用已不多。通常将在空外接圆准则、最大最小角准则下进行三角剖分称为Delaunay 三角剖分，简称为DT,同时空外接圆和最大最小角也是Delaunay三角网的两个 基本性质。DT三角剖分是目前应用最为广泛的三角剖分方法，其特性是可最大 限度避免狭长三角形的出现以及不管从何处开始构网都能保持三角形网络的唯 一性，这一点在实际应用中相当重要。实际上，在任何三角剖分准则下得到的 TIN,只要用LOP法则（局部优化过程,local optimal procedure , LOP）对其进 行优化处理，就能得到唯一

31、的DT三角网络。LOP法则是Lawson在1977年提出 的，其基本思想是运用DT三角网的空外接圆性质对由两个有公共边的三角形组 成的四边形进行判断。如果其中一个三角形的外接圆中含有第四个顶点，则交换 四边形的对角线。无约束散点域的三角剖分算法与实现：分割合并算法*三角法生长算法逐点插入算法1*分割合并算法：分割合并算法(divide and conquer delaunay triangulation algorithm)的思想最早是由Shamos和Hoey在1975年提出的，并将其应用于 V-图的构成(V-图是Vorinoi图的简称，是DT三角网的对偶图，为DT三角网 中相邻三角形边垂直平

32、分线交点的连线所形成的多边形，有关V-图的定义、性 质和分割算法参见计算几何方面的书籍)。Lewis和Robinson于1978年将该方 法用来进行DT三角网的剖分，随后Lee和Schachler、Dwyer等相继对Lewis 和Robinson的算法进行了优化和改进，其中Lee和Schachter于1980年的算法 适合于无约束数据域的三角剖分，而Dwyer于1987年的算法则考虑了带约束条 件的LOP优化策略，因而能处理带约束条件的数据。分割合并算法的思想很简单，就是将复杂问题简单化，首先将数据点分割成 易于进行三角剖分的子集，如一个子集中包括三个、四个点，然后对每个子集进 行三角剖分，并

33、用LOP算法保证三角剖分为DT三角网。当每个子集剖分完成 后，对每个子集的三角剖分进行合并，形成最终的整体三角网。不同的实现方法 可有不同的点集划分方法、子三角网生成方法及合并方法等。分割合并算法的基本步骤为：第一步，把数据集以横坐标为主、纵坐标为辅按升序进行排序;第二步，如果数据集中的数据个数大于给定的阈值，则把数据域划分为个数近似 相等的左右两个子集，并对每一子集做如下的工作，计算每一子集的凸壳； 以凸壳为数据边界，对每一数据子集进行三角剖分，并用LOP进行优化，使之 成为DT三角剖分；找出连接左右子集两个凸壳的底线和顶线；由底线到顶 线，合并两个子三角网；第三步：如果数据集中的数据个数小

34、于给定的阈值，则直接输出三角剖分结果；A= 制 B=X设左右凸壳分别为Z和夫，N和召分 别是Z和夫上的点，A. 8满足如下 条件：Az AX=maxX底线查找：从N8有向线段开始， 对于夫中点，如果沿逆时针且与8 相邻的匕点位于43的右侧，则J5=F； 在新的方向上，如果顺时针且 与N相邻的X点位于48的右侧，则 A=X.直到，和人中没有位于43线段右侧的点为止，4月为连接/ 和&的底线。顶线查找：从义8有向线段开始， 对于夫中点，如果顺时针且与&相 邻的匕点位于幽的左侧，则8=1; 在新的方向上，如果逆时针且 与义相邻的X点位于48的左侧，则 A=X,直到和夫中没有位于43线段左侧的点为止，

35、48为连接E 和&的上线。子三角网合并：合并的方式是同 层优先，从下至上的递归方式进 行（这是分割合并算法中“合并 一词的由来）。合并时先找出两 个相邻子三角网凸壳在上下（或 左右）的公共切线，这些公共切 线将是最终三角网的一部分。上 下公切线查找完后，即可从连接 两子三角网的底线开始，在两子 三角网中寻找与底线组成 Delaunay三角形的第三点，选 其中外接圆半径小的一个插入到 最终的三角网中。新生成的连接 左右两个子三角网的边成为新的 底线，逐步上推到顶线结束，如 图所示。在第一步中，主要工作是对数据点进行排序，目的是使 子三角网不相互重叠和交叉。一般是以横坐标为主、纵 坐标为辅按升序进

36、行排序，即数据点之间满足如下的条 件：（也况） 不等式成立的条件是xt x.+1 且 z+i水平线循环删除非凸顶点 Pt Pg，得到凸光顶点RPv计算R和其余数据点/的连线与 水平线的夹角.并按夹伯进行排 序（央角相同.按距离排序）将排序后的定点顺次连接成一个 多边形R. PiPio排序的方法采用以递归方式进行的分割快速排序方法, 详见数据结构书籍的介瓦第二步是该算法 的主体，包括数 据集的连续分割、 凸壳生成、凸壳 三角剖分、子网 合并等内容，集 中体现了该算法 的基本思想，即 分割（数据点的 分割），合并（子三角网的合 并）。2*三角网生长算法：顾名思义，三角网生长算法就是从一个“源”开始

37、，逐步 形成覆盖整个数据区域的三角网。从生长过程角度，三角网生长算法分为收缩生 长算法和扩张生长算法两种。收缩生长算法是先形成整个数据域的数据边界（凸 壳），并以此作为源头，逐步缩小以形成整个三角网。收缩生长算法与数据点的 分布密度有关，实际情况往往比较复杂，例如当边界收缩后一个完整的区域可能 会分解成若干个相互独立的子区域，这就增加了三角剖分的复杂性扩张生长算法与收缩算法过程刚好相反，该算法是从一个三角形开始向外层层扩 展，最终形成覆盖整个区域的三角网，其主要步骤为：第一步，生成初始三角形。在数据点中任取一点A （该点一般是位于数据点的几 何中心附近），并寻找距离此点最近的点8,两者相连形成

38、初始基线AB,如图。 利用三角剖分准则（空外接圆准则或张角最大准则），在数据域中寻找第三点C, 从而形成第一个Delaunay三角形A8C。第二步，扩展形成三角网。以初始三角形的三条边为初始基线，利用空外接圆准 则或张角最大准则，寻找能与该三条初始基线形成Delaunay三角形的。、F 点。AACC注意：（1）初始边界将整个数据域分成两个部分，搜寻第三点一般是在初始三角 形另一顶点的异侧范围进行。例如若初始三角形为ABC,初始边界为AB.第三 个顶点为C，能与三角形ABC共用48边的另一三角形他D,。点要位于福边的 另一侧，而不能与C同侧，判断方法为：设直线两端点的坐标为（”g）,3（喝力），

39、另两点分别为C（xCfyc）fD（xD,yD）可 通过下式判断点。刀在他的同异侧关系,F（xty） = y-ax-b3 =。次_小人）/（十位）.在式中代入D坐标，则有若F（Dc）与F（知,&）符号相同，则C、D位于AF的同一侧I若F（xc，c）与尸（勺，&）符与相异，则D分别位于他的两侧：若映，沁=。或夕（勺）,摄=0,则C成D与朋共线跨立实验：如果两线段相交，则两线段必然相互跨立对方。若plp2跨立Q1Q2,则矢量(P1-Q1)和(P2-Q2)位于矢量(Q2-Q1)的两侧，则(P1-Q1) X (Q2-Q1) X (P2-QI) X (Q2.Q1)O 当(P1-Q1) X (Q2-Q1 )

40、 二0时，说明(Pl-Ql ) X (Q2-Q1)共线，但是因为已经通过快速 排斥实验，所以PI一定在线段Q1Q2上；同理(Q2-Q1) X (P2-Q1) =0说明P2 一定在线段Q1Q2上。所以判断P1P2跨立Q1Q2的依据是：(Pl-Ql) X (Q2-Q1) X (Q2-Q1) X (P2-Q1 30。同理判断Q1Q2跨立P1P2的依据是(Ql-Pl) X (P2-P1 ) X (P2-P1) X (Q2-P1) 30。注意在进行“跨立判断”的时候是进行两次跨立判断8. 判断矩形内是否包含点：只要判断该店的横坐标和纵坐标是否都夹在矩形的左右边和上下边之间。9. 判断线段、折线、多边形是

41、否在矩形中：因为矩形是个凸集，所以只要判断所有端点都在矩形就行 了。10. 判断矩形是否在矩形中：只要比较左右边界和上下边界就行了。11. 判断圆是否在矩形中：圆心在矩形中且圆的半径小于或等于圆心到矩形四边的距离的最小值。12. 判断点是否在多边形内:1) 射线法：一条射线从点P开始，穿过多边形的边界的次数称为交点数目。当 交点数目是偶数时，点P在多边形外部；否则，为奇数时，在多边 形内部。BRz :多边形的顶点;,判断点；:由判断点引出的射线(a)位于预侧(方向向下(b)位于膜(c)位于滨点上下两点点下倒(方向向上)P.Q.#边形II点中与射线相交的康点美边为避免三角形的交叉和重复，通过上述

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

43、EM读取实例：-void CDemView:OnDemDem()(/ TODO:在此添加命令处理程序代码CDC *PDC=GetDC();int row=10, col=10;CString str;int size=50;/定义二维数组int demtlOO100;char strrflOO:char *p;FILE *in;in=fopenCD:UpanGIS算法原理dem2. txt”, r”);fscanf(in, %d %dn, &row, &col);for(int i=l;i=row；i+)fgets(strr, 100, in);p=strtok(strr,)：demil=at

44、oi(p);for(int j=l;j=col-l：j+)(p=strtok(NULL,);demij+l=atoi(p);/str. Format C%d*, dem3 4) ;MessageBox(str);)fclose(in);for(int i=l;i=col;i+)(for(int j=l;jRectangle(i-1)*size, (j-l)*size,i*size,j*size);3/CRect rt(i-l)*size, (j-l)*size, i*size,j*size);/pDC-Fi1ISolidRect(&rt, RGB(demj+li+l*5,0,0); pDC-T

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

46、的凸凹性，在凸侧用半径为缓冲距的圆弧弥合，在凹 侧用与该点关联的前后两相邻线段的偏移量为缓冲距的两平行线的交点作为对 应顶点。59. 关于缓冲区自相交处理：（P194）自相交多边形的两种情况：岛屿，多边形当存在岛屿和重叠自相交多边形时，最终计算的边线被分为外部边线和若干 岛屿。缓冲区边线只绘制外围边线和岛屿轮廓。缓冲区检索时，在外边线所形成的多边形检索后，再扣除所有岛屿多边形。网络分析1网络中基本组成部分：1）结点（Node）：网络中任意两条线段的交点，属性如资源数量等 链（Link）：连接两个结点的弧段。供物体运营的通道，链间的连 接关系由孤段结点拓扑数据结构来表达。属性如资源流动的时间、速

47、度 等 中心（Center）：网络中位于结点处，具有沿着链收集和发放资源 能力的设施，如邮局、电站、水座等 站点（Stop）：资源沿着网络路径流动时被分配或收集的位置，如 邮件投放点、公共汽车站，属性如资源需求量 转向点（拐点，Turn）：链路相交处，资源流向发生改变的点2）边/边集3）图：是一个非空的有限结点和有限边的集合。4）网络5）流：指网络中任意一条弧的物流量。2.给定单源点的最短路径的求解（三步）：1）选一顶点v为源点，并视从源点v出发的所有边为到各顶点的最短路径 （确定数据结构：因为求的是最短路径，所以就要用一个记录从源点v 到其它各顶点的路径长度数组dist,开始时,diSt是源

48、点V到顶点i的直接 边长度，即diSt中记录的是邻接阵的第V行。设一个用来记录从源点到 其它顶点的路径数组pathn,path中存放路径上第i个顶点的前驱顶点）。2）在上述的最短路径dist中选一条最短的，并将其终点（即v,k） k加入 到集合s中。3）调整T中各顶点到源点v的最短路径。因为当顶点k加入到集合s中后，源 点v到T中剩余的其它顶点j就又增加了经过顶点k到达j的路径，这条路径 可能要比源点v至Uj原来的最短的还要短。调整方法是比较distk+gk,j与 dist|j，取其中的较小者。4) 再选出一个到源点v路径长度最小的顶点k,从T中删去后加入S中，再回去 到第三步，如此重复，直到

49、集合S中的包含图G的所有顶点。3 (要求掌握基本概念和步骤，他们的区别)带权图分为有向和无向，无向图的最短路径又叫做最小生成树，有prime 算法和kruskal算法；有向图的最短路径算法有dijkstra算法和tloyd算法。(-)Floyd算法(P209)： Floyd算法又称为弗洛伊德算法，插点法，是 一种用于寻找给定的加权图中多源点之间最短路径的算法。基本思想如下：从任意节点A到任意节点B的最短路径不外乎2种可 能，1是直接从A到B, 2是从A经过若干个节点X到B。所以，我们假设 Dis(AB)为节点A到节点B的最短路径的距离，对于每一个节点X,我们检 查Dis(AX) + Dis(X

50、B) Dis(AB)是否成立，如果成立，证明从A到X再到B 的路径比A直接到B的路径短，我们便设置Dis(AB) = Dis(AX) + Dis(XB), 这样一来，当我们遍历完所有节点X, Dis(AB)中记录的便是A到B的最短 路径的距离。步骤：1)从任意一条单边路径开始。所有两点之间的距离是边的权， 如果两点之间没有边相连，则权为无穷大。2)对于每一对顶点u和v,看 看是否存在一个顶点w使得从u到w再到v比己知的路径更短。如果 是更新它。把图用邻接矩阵G表示出来,如果从Vi到Vj有路可达，则Gi,j=d, d表示该路的长度；否则Gij=无穷大。定义一个矩阵D用来记录所插入点 的信息，Di

51、,j表示从Vi到Vj需要经过的点，初始化Di,j=j。把各个顶点 插入图中，比较插点后的距离与原来的距离，Gi,j = min( GiJ, Gi,k+Gkj),如果Gi,j的值变小,则Dij=ko在G中包含有两点之间最 短道路的信息，而在D中则包含了最短通路径的信息。比如,要寻找从V5到VI的路径。根据D,假如D(5,l)=3则说明从V5到VI 经过V3,路径为V5,V3,V1，如果D(5,3)=3,说明V5与V3直接相连，如果 D(3,l)=l,说明V3与VI直接相连。实验作业作业1：实验1空间数据(矢量)的采集作业2：实验2空间数据的保存作业3：实验三计算几何基础(1)折线拐向判断作业4：

52、实验三计算几何基础(2)地图量算作业5：实验三计算儿何基础(3)三角形面积量算作业6：实验四(一)坐标变换作业7：实验四(二)格式转换作业8：实验四(三)矢量数据压缩 作业9：实验四(四)栅格数据压缩 作业10：实验五空间数据的内插射线法要考虑几种特殊的情况，并且射线法适用于凸多边形2）转角法：多边形环绕点P的次数称为环绕数，环绕数为0时，点P在多边形外 部，否则在多边形内部。13. 判断线段是否在多边形内：（折线是判断它的每条线段）条件一：线段的两个端点都在多边形内条件二：线段和多边形的所有边都不内交。14. 判断多边形否在多边形内：只要判断多边形的每条边是否都在多边形内即可。判断有m个顶点

53、的多边形是 否在一个有n个顶点的多边形内的复杂度为O（mXn）判断矩形是否在多边形内：将矩形转化为多边形，然后再判断是否在多边形内。15. 判断圆是否在多边形内：计算圆心到多边形每条变边的最短距离，若该距离大于或等于圆半径，则该圆在多边形内。16. 判断点是否在圆内：计算圆心到该点的距离，若小于或等于半径，则该点在圆内。17. 判断线段、折线、矩形、多边形是否在圆内：因为圆是凸集，所以只要判断是否每个顶点都在圆内即可。18. 判断圆是否在圆内：设两圆为01,02,半径为rl,r2。先比较rl,r2的大小，若rlRectangle(point. x2, point, y-2, point, x+

54、2, point.y+2); num+;arrtnum. x=point. x;arrnum. y=point. y;if(numl)pDC-MoveTo(arrnum. x, arrtnum. y); pDC-LineTo(arrnum-1. x, arrnum-1, y);Dis=Dis+sqrtf(arrnum. x-arrnum-1, x)*(arrnum, x-arrnum-1, x) + (arrnum, y-arrnum-1, y)*(arrnum, y-arrnum-1, y);str. Format Dis);MessageBox (str);CView:OnLButtonD

55、own(nFlags, point);空间数据的变换算法1 .了解平面坐标变换的儿种形式：x = x0 cos ex sin ex y = x0 sin a + % cos ax = x0 4- D、y =比 + Dyx = Sxx0y = Sy。2. 仿射变换：它是使用最多的一种几何纠正方式。在保留线条平行条件下，仿 射变换允许对长方形目标做旋转、平移、倾斜和不均匀缩放。旋转指在原点 旋转x和y轴；平移是指把源点移动到新的位置；倾斜是指以一个倾向将形 状改变为平行四边形；不均匀缩放是指在x或y方向同时或单独增大和缩小比例尺。X = (zwv cos a)x - (zwv sin a)y +

56、An= (my sin a)x + (八 cos a)y + B。Al = mx cos a, A, = mK sin aBl = mv sin a, B2 = mr cos a4 = 4 + 4* _=+ B、x + B2y平移变换实例代码：ttdefine MaxNum 100 typedef struct(int x;int y;Pnt;Pnt arrPntMaxNum;int numPnt:avoid CmoveDlg:OnLButtonDown(UINT nFlags, CPoint point)/ TODO:在此添加消息处理程序代码和/或调用默认值CDC *pDC=GetDC();

57、 pDC-Rectangle(point, x-5, point, y-5, point, x+5, point, y+5); numPnt+;arrPntnumPnt. x=point. x; arrPnt numPnt. y=point. y;| CDialogEx:OnLButtonDown(nFlags, point);Jvoid CpanDlg:OnBnClickedButtonUP()(CDC *pDC=GetDC():Invalidate 0:UpdateWindow()；for(int i=l;iRectangle(arrPnt i. x-5, arrPnt i. y-5, arrPnt