GIS算法原理知识点总结

GIS算法原理知识点总结算法设计和分析：1、算法设计的原则：正确性：若一个算法本身有缺陷，那么它将不会解决问题；确定性：指每个步骤必须含义明确，对每种可能性都有确定的操作。清晰性：一个良好的算法，必须思路清晰，结构合理。2、算法的复杂性包括：时间复杂性和空间复杂性。3、时间复杂性：用一个与问题相关的整数量来衡量问题的大小，该整数量表示输入数据量的度，称为问题的规模。利用某算法处理一个问题规模为n 的输入所需要的时间，称为该算法的时间复杂性。4、算，去的概念：算法是完成特定任务的有限指令集。所有的算法必须满足下面的标准：明确性有限性有效性♦ ♦5.矢量叉积：计算矢量叉积是直线和线段相关算法的核心部分。GIS1把这种线段称为有向线段(directedsegment)«plp2Pl在坐标原点，我们P25.矢量叉积：计算矢量叉积是直线和线段相关算法的核心部分。P=(xl,yl),Q=(x2,y2)，则矢量叉积定义为(0,0)、plp2plp2所组成的平PXQxby2-X2.yl,其结果是个标量。显然有性质PXQ=-(QXP)Px-Q=-(PxQ)oPXQ〉0,则P在Q的顺时针方向；voidCpntToDemDlg::RecToDemO3(//TODO:在此添加控件通知处理程序代码CDC*pDC-GetDC()；FILE*OUt；out=fopen("d:Wraster.txt","w");Invalidate();UpdateWindow();UpdateData(true);returnRecO;intdy»(ymax-ymin)/(row-);intdx»(xmax-xmin)/(col-);booljudge-false;fprintf(out,"'did\n",row,col);for(inti=l;i<row+;i++)(for(intj«;j<col+;j++){for(intn=;n<cnt+;n++)<if(arr[n].x>(xmin+(j-)*dx)&&arr[n].x<(xmin+j*dx)&&arr[n].y>(ymin+(i-)*dy)arr(nJ.y<(ymin+i*dy))(judge-true;break;if(judge){pDC->Rectangle(xmin+(j-：)*dx,ymin+(i・)*dy,xmin+j*dxzymin+i*dy);CRectrt(xmin+(j-)*dx,ymin+(i-)*dy,xmin+j*dx,ymin+i*dy);pDC->FinSolidRect(&rt,RGB(255,,0));fprintf(outz"%d",1);judge=false;}else{pDC->Rectangle(xmin+(j-)*dxrymin+(i-)*dy,xmin+j*dxzymin+i*dy);fprintf(out,"%d",0);judge=false;}} voidCpntToDemDlg::returnRec(void)fprintf(out,"Xn");xmax=arr[1].xzymax=arr[1].y;xmin=arr[1].xzymin=arr[1].y;i=l;i<cnt+l;i++){

for(intxmin=arr[i].x;ymin=arr[i].y;xmax=arr[i].x;ymax=arr[i].y;Col:if(xmin>arr[i].x) if(ymin>arr[i].y)if(xmax<arr[i].x)if(ymax<arr[i].y)Col:io 确定 取消矢量数据的压缩：矢量数据的压缩包括两个方面的内容，一是在不扰乱拓扑关系的前提下，对采样点数据进行合理的抽稀。二是对矢量坐标数据重新进行编码，以减少所需要的存储空间。间隔取点法：每隔K个点取一点，或舍去那些比规定距离更近的点，首末点一定要保留。垂距法:。原始曲。线"线.Q-一3II，，1-3，1-，，，．，，，，．，，3 ，夕3 ，夕｀r,20，1

对点2测试距离大于规定的限差4,Q4限差|限差|21-，2r，，321-，2r，，3)＇

对点3测试距离小于规定的限差||，aPnao1--.-.c2

一三．一光栏法的基本思想是（上图）：还是舍去。设曲线上的点列为{pi},i1,2,d,可根据压缩量的大小自己定义，则光栏法的实施步骤可描述为：1p1p2点，过p2点作一条垂直于p1p2的直线，在该垂线上取两点a1a2,a1p2=a2p2=d/2,a1a2为“光栏”边界点，p1a1、p1a2的连线为以p1）p1并在扇形内的所有直线都具有这种性质，即p1p2±d您。2p3点在扇形内，则舍去p2点。然后连接p1和p3,过p3p1p1c1C2。在垂线上找到b1和b2p3b1=p3b2=d/2,b1b2点（（图4-4-3b2点）落在原扇形c1c2取代（图4-4-3c2b2）p1b1p1c2定义一个新的扇形，这当然是口径（b1c2）缩小了的“光栏”。3。、检查下一节点，若该点在新扇形内，则重复第（2）步；直到发现有一个节点在最新定义的扇形外为止。44-4-3中的p4,此时保留p3点，以p31。〜3。。如此继续下去，直到整个点列检测完为止。所有被保留的节点（含首、末点），顺序地构成了简化后的新点列。4）道格拉斯一普克法：首先将一条曲线首、末点连一直线，求出各点到该直线的距离，选其最大者与规定的临界值相比较若大于临界值，则离该直线距离最大的点保留，否则，将直线两端间各点全部舍去，并将原线条分成两部分，对每部分线条再实施该抽稀过程，直到结束。抽稀结果点数随选取限差临界值的增大而减少，应用时应根据精度要求来确定抽稀限差临界值，以获得最好的结果。即道格拉斯一普克（Douglas-peuker）算法。PResultP】弦第一轮垂距第二轮垂距I|阈值栅格数据的压缩:1）链式编码：3,1,7,0,1,2,3,4,5,64,1,6,7,0,1,2,3,4,5（Freeman）2）游程编码：所谓游程是指按行的顺序连续且属性值相同的若干栅格。游程长度的记录方式有两种记录每个游程起（迄）列号①记录每个游程像元数②记录每个游程像元数5,5A A B BA C C C

2, AB1,A3,C1,AD1, C2,A划分成若干具性的方形后对各个正方形进行编码。块式编码的数据结构由初始DDDDCAADDAAA1,2,M；1,3,1,R；1,1,M； 1,5,1,M；M 1 7,2,M1,6,3,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, M法之一。四分树将整个图像区域逐步分解为一系列方形区域，且每一个方形区域具有单一的属性。最小区域为一个象元。2345678MM R MM M MMMM R R MR MMM R RR RR RMM R RR RR RMM R RR RR RMM R RR RR RMMM R R R R RMMM MR R MMM四叉树编码方法记录每个叶子结点的地址和属性NW(0)NE(1)SW SE(3)(2)200201202203230231232233隔点取样法实例:ttdefineMax100-typedefstructEi{intx;inty;}Pnt;Pntarr[Max];Pntarr2[Max];intnum=0;intnum2=0;//定义俩数组intn;voidCcompress2Dlg::OnBnClickedCompress(){|//TODO:在此添加控件通知处理程序代码CDC*pDC=GetDC();//Invalidate();//UpdateWindow();UpdateData(TRUE);for(inti=l;i<=num;i++)(if(i%n—1)(num2++；arr2[num2].x=arr[i].x;arr2[num2].v=arr[i]・v;})y+5);

if(num%n!=l)(num2++;arr2[num2].x=arr[num].x;arr2[num2].y=arr[num],y;}for(intj=2;j<=num2;j++)(CDC*pDC=GetDC();pDC->El1ipse(arr2[j].x-5,arr2[j].y-5,arr2[j].x+5,arr2[j].pDC->MoveTo(arr2j-1x,arr2[j-1].y);pDC->LineTo(arr2[j].x,・y);}voidCcompress2Dlg::OnLButtonDown(UINTnFlags,CPointpoint)//TODO:在此添加消息处理程序代码和/或调用默认值CDC*pDC=GetDC():pDC->Rectangle(point,x-2,point,y-2,point,x+2,point,y+2);num++;arr[num].x=point.x;arr[num].y=point.y;if(num>l)(pDC->MoveTo(arr[num-1].x,arr[num-1],y);pDC->LineTo(arr[num].x,arr[num],y);}CDialogEx::OnLButtonDown(nFlags,point);空间数据内插算法1.空间数据内插的定义：根据已知的空间数据估计(预测)未知空间的数据值。空间数据内插目标：① 缺值估计：估计某一点缺失的观测数据，以提高数据密度。② 内插等值线：以等值线的形式直观地显示数据的空间分布。③ 三角网等。模型模拟方法和综合方法。方法。果进行严格的检验。6空间数据内插的分类依据：①确定或随机；点与面；②全局或局部等标准分类；内插方法的基本假设和数学本质。较近控制点的影响比较远控制点的影响更大。反距离权重方法的通用方程是：式中，Z00的估计值；Z,zi与点0间的趾离；sK为指定的慕。20双线性插值算法：是一种数字图像处理、DEM部插值算法。原理：如图8.5所示，设犬0,0)=Z|,/(I,0)=Z2,/(0,1)=Z3,/(I,1)Z4,f(x,y)点的值,其中知，e[0,l]of(0,0)、/(I,0)、f(0,1)、/(1,1)J(x,y)=or+by+cxy+d求出各参数小b、c、d的值，再将代入，解得TUy)。5反距离权重插值实例:PXQ<(),则P在Q的顺逆针方向；PXQ>0,则PQ共线，但可能同向也可能反向。6、判断线段的拐向：折线段的拐向判断方法，可以直接由矢量叉积的性质推出，对于有公共端点的线段pOpl和P1P2,通过计算(p2-p0)X(Pl-pO)的符号便可以给出折线段的拐向。基(p2・p0)X(P1.pO)vO,POP1

基(p2-p0)X(P1-p0)=0,po则P0P1P2三点共线

pO基(p2・p0)X(P1-p0)>0,则P0P1在P1点拐向右侧后得到在P1点拐向左侧后得到P1P2 P1P2理解矢量的概念通过矢量差积的方法就可以判断的拐向了。7.判断点是否在线段上：设点为Q,线段为PlP2：(Q-Pl)X(P2-Pl)=O且Q在以Pl,P2为对角顶点的矩形内。前者抱走点在直线上，后者保证点不在线段延长线或反向延长线上。8、判断两线段是否相交(算法一)：快速排斥实验：设以线段P1P2为对角线的矩形为R,设以线段Q1Q2为对角的矩形为T,如果R和T不相交，显然两线段不会相交#include<math.h>#defineMAX100etypedefstructs{intx,y,z;}Pnt;Pntarr[MAX];intnum=0;-voidCinterpolationDlg::OnLButtonDown(UINTnFlags,CPointpoint){//TODO:在此添加消息处理程序代码和/或调用默认值CDC*pDC=GetDC();pDC->El1ipse(point,x-3,point,y-3,point,x+3,point,y+3);num++;arr[num].x=point.arr[num],y=point,UpdateData(TRUE);arr[num].z=IDWy；//IDWy就是IDWz,纯属手误CStringstr;str.Formatarr[num],z);pDC->TextOutA(arr[num].x-30,arr[num],y-30,str);J-vil:tolnlg,inckedButtonIDW()(//TODO:doublenAtor=0,dAtor=0;doubledis=0,Z;CStringstr;for(inti=l;i<=num;i++)(dis=sqrtf((arr[i].x-X)*(arr[i].x-X)+(arr[i].y-Y)*(arr[i].y-Y));str.Formatdis);nAtor+=(arr[i].z/dis);I} dAtor+=(1.0/dis);Z=nAtor/dAtor;str.FormatZ);CDC*pDCGetDCOTIN、DEM、DAT1.1.2.数字高程模型：是通过有限的地形高程数据实现对地形曲面的数字化模拟或者说是地形表面形态的数字化表示，英文为DigitalElevationModel,简称DEM。2.DEMDTM（，DEM也常常称为DTMo要说明的是由于“Terrain”一词的含义比较广泛，不同专业背景对“Terrain”的理解也不一样，DTM趋向于表达比DEM更为广泛的内容，详见后文的分析。表2数字地面模型有关术语术语全称 特点与含义DigitalElevationDEM ModelDHM DigitalHeightModelDigitalGroundModelDGMDigitalGeomorphologyModelDTM DigitalTerrainDTEDDigitalTerrain

以绝对高程或海拔表示的地形模型以任意高程表示的地形模型，包括绝对高程和相对高程，为德国所使用具有连续变化特征的地表实体模型，为英国所使用除高程外的其他地貌形态模型，如坡度、坡向等泛指地形表面自然、人文、社会景观模型,为美国国防制图局所使用的地形模型，强 调模型的I取决于aidl

c大TINDEMTIN如山脊点、山谷线、地形变化线等表示地形特征。规则格网DEM优点•简单的数据存储结构；；好的表面分析功能缺点•i+W缺点效率较低；•数据冗余；•格网结构规则

不规则三角网TIN优点•较少的点可获取较高的精度・•可隽分辨率；•良好的拓扑结构缺点•i®缺点分析能力较差；•构建比较费时；•算法设计比较复杂DEM

格网DEM数据结构不规则三角形DEM数据结构DEM的边界范围一般是规则矩形，而实际地形范围却是不规则的,DEM高程值的表示方法（无效区域数据）,一般是给出一个特殊的常数值，如-9999等。规则格网DEMDEM数据进行说明的数据头和DEM数据体两部分。1）数据头：一般包括定义DEM及高程放大系数等内容；2）数据体：按行或列分布记录的高程数字阵列。例 困术我15敏酮角格咐利蠕网B酗角格怫无冷蠕处'、格网幄里融幅靴

2512345.054321.010*999912,14,15,£n蚌倾的DEM 蹴件 咖观・"3I

绕T与序属号性XyZ123456坐标表三角形表XyZ号性1点2点XyZ号性1点2点3111622226333364444655 5 5 6 16基本铤表结构图TIN模型的基本链表结构TIN模型的面结构最大特点是：由于存储了三角形之间的邻接关系，TIN内插、检索、等高线提取、显示以及局部结构分析都比较方便，不足之处是：存储量较大，而且在TIN的编辑中要随时维护这种关系。DEMDEM的第一步是获取地形数据。DEM的数据源和数据获取方式对于DEM的最终质量至关重要。DEMDEM应用目的、数据采集效率和成本、技术熟DEM/*目前DEM的数据主要来源于地形图、摄影测量与遥感影像数据、地面测量、既有DEM数据等。*/坡度：坡度是地表形态最为重要的因子，通过坡度可以完整地形成地形曲面(Evans,1972；Strahler,1956)；坡度是地形曲面函数一阶微分的函数，表达了高程随距离变化的比率(坡度定义为地面一点的切平面与水平面之间的夹角)，而坡度的变率是地形曲面的二阶微分，进一步刻画了坡度的变化，从而反映地形的复杂程度；DEM高程精度与平均坡度值之间存在强相关，通过模型的平均坡度可DEM的精度(Ackermann,1979;Ley,坡度通过相互垂直的两个坐标轴方向的高程变化表达地形曲面局部单元的倾斜程度，也就是通过地形表面的凸面和凹面来描述地形表面特性，即地表的陡峭方向和大小。TIN数据的建立：基于不规则三角网的数字高程模型(BasedonTriangulatedIrregularNetwork

DEM,简写为 Based on

DEM,俗称 TIN)就是用一系列11.互不交叉、互不重叠的连接在一起的三角形来表示地形表面。TIN是DEM11.N几TINA所示；最大最凸四边形对角线后所形成的两三角形的最小内角，如图B所示；最短距离和准则：图C,最短距离和就是指一点到基边两端的距离和为最小；D,E,三角形内切圆面积与三角形面积或三角形面积与周长平方之比最小；F,两三角形组成的凸四边形的两条对角线之比。超过给定限定值时对三角形进理论上可以证明：张角最大准则、空外接圆准则及最大最小角准则是等价的，其余的则不然。行优化。理论上可以证明：张角最大准则、空外接圆准则及最大最小角准则是等价的，其余的则不然。三角形剖分准则是建立三角形网络的基本原则，应用不同的准则将会得到不 同的三角形网络。一般而言，应尽量保持三角网的唯一性，即在同一准则下由不 同的位置开始建立三角形网络，其最终的形状和结构应是相同的，在这-点上,张伯最大准则、空外接圆准则及最大最小们准则可以做到对角线准则含有主观因素，现今使用已不多。通常将在空外接圆准则、最大最小角准则下进行三角剖分称为DelaunayDT,Delaunay三角网的两个基本性质。DT三角剖分是目前应用最为广泛的三角剖分方法，其特性是可最大限度避免狭长三角形的出现以及不管从何处开始构网都能保持三角形网络的唯一性，这一点在实际应用中相当重要。实际上，在任何三角剖分准则下得到TIN,LOP法则（localoptimalprocedureDT三角网络。LOPLawson1977DT三角网的空外接圆性质对由两个有公共边的三角形组成的四边形进行判断。如果其中一个三角形的外接圆中含有第四个顶点，则交换四边形的对角线。无约束散点域的三角剖分算法与实现：•分割合并算法*三角法生长算法无约束散点域的三角剖分算法与实现：★逐点插入算法@1*分割合并算法：分割合并算法(divideandconquerdelaunaytriangulationalgorithm)ShamosHoey1975年提出V-图的构成(V-VorinoiDT三角网的对偶图，DTV-义、性质和分割算法参见计算几何方面的书籍)。LewisRobinson1978DTLeeSchachler、DwyerLewisRobinsonLeeSchachter1980Dwyer1987优化策略，因而能处理带约束条件的数据。LOP算法保证三角DT三角网。当每个子集剖分完成后，对每个子集的三角剖分进行合并，形成最终的整体三角网。不同的实现方法可有不同的点集划分方法、子三角网生成方法及合并方法等。分割合并算法的基本步骤为：'｀．'｀．对每一个子集进行三角剖分对每一个子集进行三角剖分LOP绊法进行优化线（租实线），底线开始自下而^｀，第一步，把数据集以横坐标为主、纵坐标为辅按升序进行排序;第二步，如果数据集中的数据个数大于给定的阈值，则把数据域划分为个数近似相等的左右两个子集，并对每一子集做如下的工作，①计算每一子集的凸壳；②以凸壳为数据边界，对每一数据子集LOPDT三角剖分；③找出连接左右子集两个凸壳的底线和顶线；④由底线到顶线，合并两个子三角网；第三步：如果数据集中的数据个数小于给定的阈值，则直接输出三角剖分结果；Z和夫，NZ和夫上的点，A.8下条件：AzAX=max{X[}底线查找：从N8有向线段开始，对于夫中点，如果沿逆时针且与8相邻的匕点位于43的右侧，则J5=F； 在新的方向上，如顺时针且与N相邻的X点位于48的右侧，则A=X.直到，和人中没有位于43线段右侧的点为止，4月为连接/和&的底线。A= B=

顶线查找：从义8有向线段开始，对于夫中点，如果顺时针且与&相邻的匕点位于幽的左侧，则8=1;在新的方向上，如果逆时针且与义相邻的X点位于48的左侧，则A=X,直到£和夫中没有位于43线段左侧的点为止，48为连接E和&的上线。子三角网合并：合并的方式是同层优先，从下至上的递归方式进（这是分割合并算法“合并一词的由来）。合并时先找出两个邻子三角网凸壳在上下（或左右）的公共切线，这些公共切 线将是最终三角网的一部分。上下公切线查找完后，即可从连接两三角网的底线开始，在两子 三角网中寻找与Delaunay三角形的第三点，中外接圆半径小的一个插入到最终的三角网中。新生成的连接左右两个子三角网的边成为新的底线，逐步上推到顶线结束，如图所示。在第一步中，主要工作是对数据点进行排序，目的是使 子三网不相互重叠和交叉。一般是以横坐标为主、纵坐标为辅按升序进行排序，即数据点之间满足如下的条件：（也况）＜不等式成立的条件是t +1 x<x. <zt +1 且排序的方法采用以递归方式进行的分割快速排序方法,详见数据结构书籍的介瓦第二步是该算法的主体，包括数据集的连续分割、凸壳生成、凸壳三角剖分、子网合并 计算R和其余数据点/的连线与水等内容，集中体现了该算法的基本思想，即分割（数据点的分割），合并（子三角网的合并）。@2*三角网生长算法：顾名思义，三角网生长算法就是从一个“源”开始，

水平线

平线的夹角.并按夹伯进行排序（央角相同.按距离排序）将排序后的定点顺次连接成一个多边形R.PiPio循环删除非凸顶点％PTPg，得到凸光顶点R・Pv逐步形成覆盖整个数据区域的三角网。从生长过程角度，三角网生长算法分为收缩生长算法和扩张生长算法两种。收缩生长算法是先形成整个数据域的数据边界（凸壳），并以此作为源头，逐步缩小以形成整个三角网。收缩生长算法与数据点的分布密度有关，实际情况往往比较复杂，例如当边界收缩后一个完整的区域可能会分解成若干个相互独立的子区域，这就增加了三角剖分的复杂性扩张生长算法与收缩算法过程刚好相反，该算法是从一个三角形开始向外层层扩 展，最终形成覆盖整区域的三角网，其主要步骤为：第一步，生成初始三角形。在数据点中任取一点A（该点一般是位于数据点的几何中心附近），并8,AB,（空外接圆准则或张角最大准则），C,DelaunayA8C。第二步，扩展形成三角网。以初始三角形的三条边为初始基线，利用空外接圆准 则或张角最大准则寻找能与该三条初始基线形成Delaunay三角形的。、£、F点。AACC注意：（1）ABC,AB.C，ABCD,C同侧，判断方法为：设直线两端点的坐标为』

,3（喝力），另两点分别为C（x

y）,y'可通过下式判断点。刀在他的同异侧关系,

Cfc f DDx）=y-ax-3。次_小人）/（十位）.在式中代入D坐标，则有若F（Dc）与F（知,&）符号相同，则C、D位于AF的同一侧IF（xc，〉c）与尸（勺＞，&）D若映，沁=。或夕（勺）,＞摄=0,CD与朋共线・跨立实验：如果两线段相交，则两线段必然相互跨立对方。若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)二0时，说明(Pl-Ql)X(Q2-Q1)共线，但是因为已经通过快速排斥实验，所以PI一定在线段Q1Q2上；同理(Q2-Q1)X(P2-Q1)=0说明P2Q1Q2上。所以判断P1P2跨立Q1Q2的依据是：(Pl-Ql)X(Q2-Q1)X(Q2-Q1)X(P2-Q1。同理判断Q1Q2跨立P1P2的依据是(Ql-Pl)X(P2-P1X(P2-P1)X(Q2-P1)30。注意在进行“跨立判断”的时候是进行两次跨立判断判断矩形内是否包含点：只要判断该店的横坐标和纵坐标是否都夹在矩形的左右边和上下边之间。判断线段、折线、多边形是否在矩形中：因为矩形是个凸集，所以只要判断所有端点都在矩形就行了。判断矩形是否在矩形中：只要比较左右边界和上下边界就行了。判断圆是否在矩形中：圆心在矩形中且圆的半径小于或等于圆心到矩形四边的距离的最小值。1)

判断点是否在多边形内:射线法：一条射线从点P开始，穿过多边形的边界的次数称为交点数目。当交点数目是偶数时，点P在多边形外部；否则，为奇数时，在多边形内部。点

(c)位于滨点上下两点下倒 侧(方向向下〉B〜Rz:多边形的顶点;①〜⑤,判断

(方向向上)

点三@逐点插入算法逐点插入算法的过程非常简单，基本步骤为：第一步，定义包含所有数据点的初始包容盒，并对该包容盒进行初始三角剖分；第二步，对所有数据点进行循环，做如下工作(设当前处理的数据点为P),在已存在的三角网中，查找包含p的三角形t；②pttLOP算法对初始三角剖分进行优化处理。第三步，处理外围三角形。DEM读取实例：-voidCDemView::OnDemDem()(//TODO:在此添加命令处理程序代码CDC*PDC=GetDC();introw=10,col=10;CStringstr;intsize=50;//定义二维数组intdemtlOO][100];charstrrflOO]:char*p;FILE*in;in=fopenCD:\\Upan\\GIS算法原理\\dem2.txt”,"r”);fscanf(in,"%d%d\n",&row,&col);for(inti=l;i〈=row；i++)fgets(strr,100,in);p=strtok(strr,"")：dem[i][l]=atoi(p);for(intj=l;j<=col-l：j++)(p=strtok(NULL,"");dem[i][j+l]=atoi(p);}//str.FormatC%d*,dem[3][4]);MessageBox(str);)fclose(in);for(inti=l;i<=col;i++)(for(int(pDC->Rectangle((i-1)*size,(j-l)*size,i*size,j*size);3//CRectrt((i-l)*size,(j-l)*size,i*size,j*size);//pDC->Fi1ISolidRect(&rt,RGB(dem[j+l][i+l]*5,0,0));pDC->TextOut((i-1)*size,(j-l)*size,itoa(dem[j][i],strr,10));}13缓冲区分析算法：缓冲区（buffer）立其周围一定宽度范围的多边形。分类：点缓冲区、线缓冲区、面缓冲区和复杂实体缓冲区。步进拟合的思想，即圆弧弥合的方法：（双侧平行线法）将圆心角等分，用等长的弦代替圆弧，即用均匀步长的直线段逼近圆弧段。等分的圆心角越小，步长越小，误差越小；等分的圆心角越大，步长越大，误差越大。凸角圆弧法，基本思想：在轴线的两端用半径为缓冲距的圆弧弥合；在轴线的各转折点，判断该点的凸凹性，在凸侧用半径为缓冲距的圆弧弥合，在凹 侧用与该点关联的前后两相邻线段偏移量为缓冲距的两平行线的交点作为对应顶点。关于缓冲区自相交处理：（P194）自相交多边形的两种情况：岛屿，多边形缓冲区边线只绘制外围边线和岛屿轮廓。缓冲区检索时，在外边线所形成的多边形检索后，再扣除所有岛屿多边形。网络分析1网络中基本组成部分：结点（Node）：网络中任意两条线段的交点，属性如资源数量等链（Link）：连接两个结点的弧段。供物体运营的通道，链间的连 接关系由孤段■结点拓扑数据结构来表达。属性如资源流动的时间、速度等中心（Center）：网络中位于结点处，具有沿着链收集和发放资源 能力的设施，如邮局、电站、水座等站点（Stop）：资源沿着网络路径流动时被分配或收集的位置，如 邮件投放点、公共汽车站，属性如资源需求量转向点（拐点，Turn）：链路相交处，资源流向发生改变的点边/边集图：是一个非空的有限结点和有限边的集合。网络流：指网络中任意一条弧的物流量。2.给定单源点的最短路径的求解（三步）：1）vv出发的所有边为到各顶点的最短路径（确定数据结构：vdist[],开始时,diStVidiStV行。②设一个用pathn,pathi个顶点的前驱顶点）。2）dist[]中选一条最短的，并将其终点（即＜v,k＞）ks3）TvksvT中剩余的jkjvUj原来的最短的还要dist[k]+g[k,j]dist|j]，取其中的较小者。4)再选出一个到源点v路径长度最小的顶点k,从T中删去后加入S中，再回去到第三步，如此重复，直到集合S中的包含图G的所有顶点。3(要求掌握基本概念和步骤，他们的区别)带权图分为有向和无向，无向图的最短路径又叫做最小生成树，有prime算法和kruskal算法；有向图的最短路径算法有dijkstra算法和tloyd算法。(-)Floyd算法(P209)：Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。AB21AB,2AXBDis(AB)AB的最短路X,Dis(AX)Dis(XB)Dis(AB)是否成立，如果成立AXBABDis(AB)Dis(AX)Dis(XB),X,Dis(AB)AB步骤：1)从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。2)uv,wuwvGViVj有路可达，G[i,j]=d,dG[ij]=DViVjD[i,j]=jmin(G[iJ],G[i,k]+G[kj]),G[i,j]D[ij]=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：实验三计算几何基础(2)地图量算作业5：实验三计算儿何基础(3)三角形面积量算作业6：实验四(一)坐标变换作业7：实验四(二)格式转换作业8：实验四(三)矢量数据压缩作业9：实验四(四)栅格数据压缩作业10：实验五空间数据的内插射线法要考虑几种特殊的情况，并且射线法适用于凸多边形2）转角法：多边形环绕点P的次数称为环绕数，环绕数为0时，点P在多边形外部，否则在多边形内部。判断线段是否在多边形内：（折线是判断它的每条线段条件一：线段的两个端点都在多边形内条件二：线段和多边形的所有边都不内交。判断多边形否在多边形内：mn个顶点O（mXn）判断矩形是否在多边形内：将矩形转化为多边形，然后再判断是否在多边形内。径，则该圆在多边形内。判断点是否在圆内：计算圆心到该点的距离，若小于或等于半径，则该点在圆内。要判断是否每个顶点都在圆内即可。判断圆是否在圆内：01,02,半径为rl,r2rl,r2rl<r2,0201内；若两圆rl-r2,0201内；反之，0201内。会点即为要求目标点（注意方向二选其中一个）。距离量算算法的实现：ftdefineMAX100ftypedefstruct{intx;inty;}Pnt;〔Pntarr[MAX];intnum;floatDis;CStringstr;CStringpvoidCDistanceAddView::OnLButtonDown(CINTnFlags,CPointpoint)//TODO:在此添加消息处理程序代码和/或调用默认值CDC*pDOGetDC();pDC->Rectangle(point.x~2,point,y-2,point,x+2,point.y+2);num++;arrtnum].x=point.x;arr[num].y=point.y;if(num>l){pDC->MoveTo(arr[num].x,arrtnum].y);pDC->LineTo(arr[num-1].x,arr[num-1],y);Dis=Dis+sqrtf((arr[num].x-arr[num-1],x)*(arr[num],x-arr[num-1],x)+(arr[num],y-arr[num-1],y)*(arr[num],y-arr[num-1],y));str.FormatDis);MessageBox(str);}CView::OnLButtonDown(nFlags,point);}空间数据的变换算法1.了解平面坐标变换的儿种形式：x=x0cosex—sinexy=x0sina+%cosax=x04-D、y=Dyx=Sxx0y=Sy2.仿射•变换：它是使用最多的一种几何纠正方式。在保留线条平行条件下，仿射变换允许对长方xy轴；平移是指把源点移动xy方向同时或单独增大和缩小比例尺。X=(zwvcosa)x-(zwvsina)y+An=(mysina)x+(〃八cosa)y+B。xKvrAl=mxKvr

cosa,A,=

sinaBl=

sina,B2=

cosa、4=4+4*_=+Bx+By、2平移变换实例代码：ttdefineMaxNum100typedefstruct(intx;inty;}Pnt;PntarrPnt[MaxNum];intnumPnt:avoidCmoveDlg::OnLButtonDown(UINTnFlags,CPointpoint){//TODO:在此添加消息处理程序代码和/或调用默认值CDC pDC->Rectangle(point,x-5,point,y-5,point,x+5,point,y+5);numPnt++;arrPnt[numPnt]. x=point. x; arrPnt [numPnt]. y=point.CDialogEx::OnLButtonDown(nFlags,point);J「voidCpanDlg::OnBnClickedButtonUP()(CDC*pDC=GetDC():Invalidate0:UpdateWindow()；for(inti=l;i<=numPnt;i++)(arrPnt[i].y-=10;|pDC->Rectangle(arrPnt[i].x-5,arrPnt[i].arrPnt[