地理信息系统第六章空间数据的处理方法

地理空间数据的获取与处理第三部分

主要内容第六章空间数据的处理方法第六章空间数据的处理方法◆图形屏幕编辑的基本操作算法介绍纠正数据采集错误的重要手段——图形编辑的基本功能、要求。◆空间数据拓扑关系的自动生成介绍矢量数据拓扑关系建立的基本步骤和要点。◆空间数据的压缩编码方法介绍矢量数据和栅格数据的压缩处理。◆空间数据的格式转换◆矢量和栅格数据的转换6.1图形屏幕编辑的基本操作算法点的捕捉线的捕捉面的捕捉图形编辑的关键是点、线、面的捕捉，即如何根据光标的位置找到需要编辑的要素，以及图形编辑的数据组织。点的捕捉设光标点为A(x,y)，图幅上某一点状要素的坐标为S(X，Y)，则可设一捕捉半径D(通常为3～5个象素)。d<D则选中，若有多个点，则要求出距A(x,y)的最近点。线的捕捉设光标点坐标为S(x,y)，D为捕捉半径，线的坐标为(x1,y1),(x2,y2),…(xn,yn)。通过计算S到该线的每个直线段的距离di(如左图所示)，若min(d1,d2,…dn-1)＜D，则认为光标S捕捉到了该条线。在计算前，用最小矩形，跳过图右的线条。•S(x,y)(X1,Y2)(X1,Y)(X1,Y’)面的捕捉面的捕捉实际上就是判断光标点S(x,y)是否在多边形内，若在多边形内则说明捕捉到。判断点是否在多边形内的算法主要有垂线法或转角法。垂线法先进行图右的判断（在线框内外），再做奇偶点数的判断。奇在内，偶在外。垂线、水平线、斜线的结果均相同，垂线或水平线运算方便。对于点在面的边界上，可以对点的坐标加微量解决。若精度要求高，不允许加微量，可以先解决点是否在面边界的判断，再使用垂线法。6.2空间数据拓扑关系的自动生成欧拉定理点线拓扑关系的建立多边形矢量数据拓扑关系自动建立多数情况下拓扑关系的建立可由GIS软件自动生成。特殊情况下，需要人工对拓扑关系进行人工修改，如建立管网或路网数据的分析网络时，就需要对结点、管段的方向等进行编辑。扫描后的栅格数据矢量化后的数字线划图矢量数据的常见错误公共边界的处理

12211矢量数据拓扑关系在空间数据的查询与分析中非常重要，矢量数据拓扑关系自动建立的算法是GIS中的关键算法之一。欧拉定理对于多边形图形，n、a、b分别表示结点数、弧段数、多边形数则：c=n-a+b或c+a=n+bc+弧=点+面c为常数，其取值为：c=2包含外多边形c=1不包含外多边形点线拓扑关系的建立记录结点——弧段表弧段——结点表弧段入库时，检测结点表，若存在记录点号；否则产生新的点号，再记录多边形的四种基本图形

独立公共边岛复合多边形矢量数据拓扑关系的自动建立链的组织结点匹配闭合检查建立多边形概念过程岛的判断确定多边形的属性链的组织1找出在链的中间相交(左图)，而不是在端点相交(右图)的情况，自动切成新链。链的组织2原来的两条链变成了四条链。再把链按一定顺序存储，如按最大或最小的x或y坐标的顺序，这样查找和检索都比较方便，然后把链按顺序编号。链的生成结点匹配结点匹配是指把一定限差内的链的端点作为一个结点，其坐标值取多个端点的平均值。然后，对结点顺序编号。X=(x1+x2+x3)/3;Y=(y1+y2+y3)/3去除悬线

闭合检查检查多边形是否闭合可以通过判断一条链的端点是否有与之匹配的端点来进行。悬挂链不需参加多边形拓扑，可以作一标记，使之不参加下一阶段拓扑建立多边形的工作。建立多边形概念1顺时针方向构多边形。顺时针方向构多边形是指多边形在链的右侧概念2最靠右边的链最靠右边的链是指从链的一个端点出发，在这条链的方向上最右边的第一条链。如图，a的最右边的链为d。找最靠右边的链可通过计算链的方向和夹角实现求最右线段的方法1、从起始点Pi出发，到达结点P0，设方位角P0Pi为起始方位角f1；2、求终结点P0到其他节点的方位角：f2f3…….fn；3、用f(i+1)-f(i)求解夹角P(i)P0P(i+1)，，形成夹角串jj1j2……jn；4、jj1j2……jn中最大者为最右方向，其链为下一条发展链。概念3用多边形面积判断方向用面积值判断方向（需将绝对号去除）建立多边形的基本过程1、顺序取一个结点为起始结点，至该点上所有链均用2次止；取过该结点的任一条链作为起始链。2、取这条链的另一结点，找这个结点上，靠这条链最右边的链，作为下一条链。3、是否回到起点：是，已形成一多边形，记录之，并转4；否，转2。4、取起始点上开始的，刚才所形成多边形的最后一条边反向作为新的起始链，转2；若这条链已用过两次，即已成为两个多边形的边，则转1。岛的判断岛的判断即指找出多边形互相包含的情况，即寻找多边形的连通边界。找出所有比该正面积多边形面积小的负面积多边形；用外接矩形法去掉不可能包含的多边形；取负面积多边形上的一点，看是否在正面积多边形内。

单多边形被追踪两次

p1p2p3记录多边形多边形的记录格式可由节点或链构成ID，n，[P]，AID，n，[L]，A确定多边形的属性在追踪出每个多边形的坐标后，经常需确定该多边形的属性。如果多边形有内点，则可以把内点与多边形匹配后，把内点的属性赋于多边形。思考：若无内点，能否记录多边形的属性？如果没有内点，则必须通过人机交互，对每个多边形赋属性。拓扑处理注意事项1）可以根据实际数据的情况和使用目的，选择不同的拓扑处理选项组合；2）如果需要进行拓扑错误检查，必须选择弧段求交，弧段求交是进行后续拓扑处理的基础。3）线数据集经过拓扑处理后，原来数据集的线对象将会在各线对象交点处被打断，而生成新的线对象，如用户还需继续使用原来的线数据集，可以在拓扑处理前对线数据集先进行备份，以保护原数据集；4）弧段求交操作得到的是一个真正的节点，而合并临近点操作有时却得到一个假节点，因此合并临近点操作后可能还要继续做合并假节点操作；5）线数据集必须关闭才能进行拓扑处理；6）拓扑处理的结果与拓扑容限大小的设置有关。中间数据集重名延伸长悬线1延伸长悬线26.3空间数据的压缩编码方法矢量数据的压缩矢量数据压缩的目的是删除冗余数据，减少数据的存贮量，节省存贮空间，加快后继处理的速度。栅格数据的压缩栅格数据压缩的目的是删除冗余数据，减少数据的存贮量，节省存贮空间，但在处理时会增大运算量。是用时间换空间。矢量数据的压缩道格拉斯——普克法(Douglas—Peucker)道格拉斯——普克法对每一条曲线的首末点虚连一条直线，求所有点与直线的距离，并找出最大距离值dmax。用dmax与限差D相比：若dmax＜D，这条曲线上的中间点全部舍去；若dmax≥D，保留dmax对应的坐标点，并以该点为界，把曲线分为两部分，对这两部分重复使用该方法垂距法每次顺序取曲线上的三个点，计算中间点与其它两点连线的垂线距离d，并与限差D比较。若d＜D，则中间点去掉；若d≥D，则中间点保留。然后顺序取下三个点继续处理，直到这条线结束。光栏法定义一个扇形区域，通过判断曲线上的点在扇形外还是在扇形内，确定保留还是舍去。设曲线上的点列为｛pi｝，i＝1，2，…，n，光栏口经d可根据压缩量确定几种方法的比较标准既能精确地表示图形，又能最大限度地淘汰不必要的点，那就是一种好的算法。可以依据简化后曲线的总长度、总面积、坐标平均值等与原始曲线的相应数据的对比来判别。分析大多数情况下道格拉斯——普克法的压缩算法较好，但必须在对整条曲线数字化完成后才能进行，且计算量较大；光栏法的压缩算法也很好，并且可在数字化时实时处理，每次判断下一个数字化的点，且计算量较小；垂距法算法简单，速度快，但有时会将曲线的弯曲极值点p值去掉而失真。栅格数据的压缩JPG27KBMP529K栅格的压缩和编码直接栅格编码链码(chainEncoding)游程长编码(Run_lengthEncoding)块码四叉树编码(quarter_treeEncoding)直接栅格编码将栅格数据当成数据矩阵，逐行(或逐列)记录代码，每行都从左到右记录，也可奇数行从左到右，偶数行从右到左。为了特定的目的还可采用其他特殊的顺序。图右：AAAAABBBAABBAABB同时记录行、列数特点是处理方便，但没有压缩。AAAAABBBAABBAABB直接栅格编码0，2，2，5，5，5，5，5；2，2，2，2，2，5，5，5；2，2，2，2，3，3，5，5；0，0，2，3，3，3，5，5；0，0，3，3，3，3，5，3；0，0，0，3，3，3，3，3；0，0，0，0，3，3，3，3；0，0，0，0，0，3，3，3。栅格数据的组织方法无论如何取值，在计算机中，如果矩阵的每个元素用一个双字节表示，则一个图层的全栅格数据所需要的存储空间为m（行）×n（列）×2（字节）。如：一个面积为100km2的区域，如果网格边长取为1m，每个网格用一个双字节表示，则一个图层的要素就占用？兆字节的存储空间。200因此，栅格数据的压缩是栅格数据结构要解决的重要任务。是将原始栅格阵列中属性值相同的连续若干个栅格单元映射为一个游程，每个游程的数据结构为（A，P）整数对。其中，A代表属性值，P代表该游程最右端栅格的列号。游程长度(行程)编码按行扫描，将相邻等值的象元合并记录。右图编码为A4A1B3A2B2A2B2。若在行与行之间不间断地连续编码，则为A5B3A2B2A2B2。对于游程长度编码，区域越大，数据的相关性越强，则压缩越大。其特点是，压缩效率较高，叠加、合并等运算简单，编码和解码运算快AAAAABBBAABBAABB游程长度编码只在各行（或列）数据的代码发生变化时依次记录该代码以及相同代码重复的个数；沿行方向进行编码：(0，1），（2，2），（5，5）；（2，5），（5，3）；（2，4），（3，2），（5，2）；（0，2），（2，1），（3，3），（5，2）；（0，2），（3，4），（5，1），（3，1）；（0，3），（3，5）；（0，4），（3，4）；（0，5），（3，3）。游程长度编码逐个记录各行（或列）代码发生变化的位置和相应代码（1,0），（2,2），（4,5）（1,2），（6,5）（1,2），（5,3），（7,5）（1,0），（3,2），（4,3），（7,5）（1,0），（3,3），（7,5），（8,3）（1,0），（4,3）（1,0），（5,3）（1,0），（6,3）四叉树编码

四叉树编码是最有效的栅格数据压缩编码方法之一，在GIS中有广泛的应用。其基本思路为：将2n×2n象元组成的图像(不足的用背景补上)所构成的二维平面按四个象限进行递归分割，直到子象限的数值单调为止，最后得到一颗四分叉的倒向树，该树最高为n级。用一倒立树表示这种分割和分割结果。根：整个区域高：深度、分几级，几次分割叶：不能再分割的块树叉：还需分割的块每个树叉均有4个分叉，叫四叉树。四叉树编码四叉树分解，各子象限大小不完全一样，但都是同代码栅格单元组成的子块，其中最上面的一个结点叫做根结点，它对应于整个图形。不能再分的结点称为叶子结点，可能落在不同的层上，该结点代表子象限单一的代码，所有叶子结点所代表的方形区域覆盖了整个图形。从上到下，从左到右为叶子结点编号，最下面的一排数字表示各子区的代码。为了保证四叉树分解能不断的进行下去，要求图形必须为2n×2n的栅格阵列。n为极限分割次数，n＋1是四叉树最大层数或最大高度8*8四叉树编码①②③④⑤⑥⑦⑧⑨⑩1112131415161718192021222324252627282930313233363738393435400000333033333530022232222022225255533355西南东南西北东北四叉树编码法的优点：1）容易而有效地计算多边形的数量特征；2）阵列各部分的分辩率是可变的，边界复杂部分四叉树较高即分级多，分辩率也高，而不需表示许多细节的部分则分级少，分辩率低，因而既可精确表示图形结构又可减少存贮量；3）栅格到四叉树及四叉树到简单栅格结构的转换比其它压缩方法容易；4）多边形中嵌套异类小多边形的表示较方便。练习0231练习由直接栅格编码转换成四叉树编码的树状表示333331111111333331111111333111144441333111444444332221114441322221111411222221111111222221111111222222111111222222111111答案3331111031331111411311441332221444103211141122211122221110210000000000用Morton码表示四叉树地址Morton码表示的叶结点Morton码的转换Morton码—叶节点码叶节点码—Morton码Morton码—行列值行列值—Morton码四叉树地址和Morton码Morton码—叶节点码将十进制Morton码转为二进制码39——100111将二进制Morton码每二位转为十进制数100111213叶节点码—Morton码将叶节点码逐位转为二进制213100111将二进制叶节点码转为Morton码100111——391*25+0*24+0*23+1*22+1*21+1*2032+0+0+4+2+1=39Morton码—行列值将Morton码39转为二进制100111将二进制的Morton码奇偶分开100111101011将奇偶分别变成十进制的行列10101153行列值—Morton码将十进制的行列分别变成二进制53101011将二进制的行列值奇偶合并得Morton码101011100111将二进制Morton码变为十进制1*25+0*24+0*23+1*22+1*21+1*2032+0+0+4+2+1=39十进制地址码——Morton码例如，对于第5行、第7列的Moton码为：行数=5(0101)；列数=7(0111)

Morton=00110111=55这样，在一个2n×2n的图像中，每个像元点都给出一个Morton码。十进制和二进制的转换十进制转二进制：

用2辗转相除至结果为0，

将余数从下向上倒序写就是二进制值例如302转二进制

302/2=151余0

151/2=75余1

75/2=37余1

37/2=18余1

18/2=9余0

9/2=4余1

4/2=2余0

2/2=1余01/2=0余1

故十进制302=二进制100101110二进制转十进制

从最后一位开始算，依次列为第0、1、2...位、第n位的数（0或1）乘以2的n次方，得到的结果相加就是十进制值。例如:01101011.转十进制:

第0位:1乘2的0次方=1

1乘2的1次方=2

0乘2的2次方＝0

1乘2的3次方＝8

0乘2的4次方＝0

1乘2的5次方＝32

1乘2的6次方＝64

0乘2的7次方＝0

然后：1＋2＋0＋8＋0＋32＋64＋0＝107．

二进制01101011＝十进制107十进制和二进制的转换6.4空间数据的格式转换数据格式转换的内容空间定位、空间关系、属性信息转换的方式通过外部数据交换文件转换通过标准空间数据文件转换通过标准API函数转换6.5矢量和栅格数据的转换矢量─栅格转换由于矢量数据的点到栅格数据的点只是简单的坐标变换，线和面(多边形)的矢量数据向栅格数据的转换是主要内容。栅格─矢量转换栅格数据到矢量数据转换的一般过程为：二值化、二值图像的预处理、细化、追踪、拓扑化矢量─栅格转换点的栅格化IJ、xyI=1+[(y顶-y)/Dy]；J=1+[x/Dx]

21,12A:1.7,4.5B:19,10.6y顶=12Dx=Dy=3yA=1+[(12-4.5)/3]=1+[2.5]=3xA=1+[1.7/3]=1+[0.56]=1线的栅格化方法

线是由多个直线段组成的，因此，线的栅格化的核心就是直线段如何由矢量数据转换为栅格数据。⑴DDA法(数字微分分析法)直线段的两端点坐标转换到栅格数据的坐标系后为(xA,yA),(xB,yB)。设(xA,yA),(xB,yB)与栅格网的交点为(xi,yi)，则:直线生成算法直线生成:求与直线段充分接近的像素集当直线作为一系列像素位置生成时产生的阶梯效果天津大学计算机科学与技术学院直线方程直线的斜率截矩方程:给定线段的两个端点,可以计算斜率m和y轴截矩b:生成直线的常用算法 均假定所画直线的斜率k∈[0，1]。DDA画线算法 DDA（DigitalDifferentialAnalyzer）画线算法也称数值微分法，是一种增量算法。它的算法实质是用数值方法解微分方程，通过同时对x和y各增加一个小增量，计算下一步的x、y值。DDA算法数值微分算法(DigitalDifferentialAnalyzer)条件：待扫描转换的直线段：斜率：直线方程：,算法步骤：划分区间[x0,x1]:

计算纵坐标：DDA算法取整：算法复杂度:加法+取整DDA算法其他斜率情况:交换x和y的位置步长dx或dy取-1不足之处：取整操作和浮点运算仍十分耗时 已知一条直线段L（P0,P1）,其端点坐标为：P0(x0,y0),P1(x1,y1)。可计算出直线的斜率k为： 假定端点坐标均为整数，取直线起点P0(x0,y0)作为初始坐标。画线过程从x的左端点x0开始，向x右端点步进，每步x递增1，y递增k（即直线斜率）；取像素点（x，round（y））作为当前点的坐标。数值微分(DDA)法

假定直线的起点、终点分别为：（x0,y0),(x1,y1)，且都为整数。

(Xi+1,Yi+k)(Xi,Int(Yi+0.5))(Xi,Yi)栅格交点表示象素点位置。。。。数值微分(DDA)法基本思想已知过端点P0(x0,y0),P1(x1,y1)的直线段Ly=kx+b直线斜率为这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。

数值微分(DDA)法计算yi+1=kxi+1+b =kxi+b+kx =yi+kx当x=1; yi+1=yi+k即：当x每递增1，y递增k(即直线斜率)；注意上述分析的算法仅适用于k

≤1的情形。在这种情况下，x每增加1,y最多增加1。当k

1时，必须把x，y地位互换数值微分(DDA)法增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。DDA算法就是一个增量算法。⑵Bresenham算法该算法原来是为绘图机设计的，同样适合于栅格化。该算法的基本思路为：若直线的斜率为1∕2≤△y∕△x≤1，则下一点取(1，1)点，若0≤△y∕△x＜1∕2，则下一点取(1，0)点。根据直线的斜率，把直线分为8个卦限。以斜率在第一卦限为例，其余卦限的情况类似。Bresenham

算例斜率为1∕3，起始点：e＝－1∕2，即e’＝－3，取点①第2点：e＝－1∕2+1∕3＝－1∕6，e’＝－3＋2△y＝－1取点②第3点：e＝－1∕6+1∕3=1∕6，即e’＝－1＋2＝1，取点③，且e＝－5/6,e’=－3；第4点：e＝1∕6+1∕3=1∕2＞0，即e’＝－5＋2＝－3，取点④因e≥1∕2，所以，e＝1∕2－1＝－1∕2。⒉面(多边形)的栅格化方法⑴内部点扩散法由一个内部的种子点，向其4个方向的邻点扩散。判断新加入的点是否在多边形边界上，如果是，不作为种子点，否则当作新的种子点，直到区域填满，无种子点为止。该算法比较复杂，而且可能造成阻塞而造成扩散不能完成，此外若多边形不完全闭合时，会扩散出去。区域是指已经表示成点阵形式的填充图形，它是像素集合。4-邻接点和8-邻接点

四个方向运动八个方向运动四连通区域八连通区域区域连通方式对填充结果的影响4连通区域边界填充算法的填充结果8连通区域边界填充算法的填充结果⑵扫描法按扫描线的顺序，计算多边形与扫描线的相交区间，再用相应的属性值填充这些区间，即完成了多边形的栅格化。这种算法的缺点是计算量较大。⑶边填充算法对于每一条扫描线和每条多边形边上的交点，将该扫描线上交点右方的所有象素取原属性值之补。对多边形的每条边作此处理，多边形的方向任意。边填充算法2上行时，左侧加-a；下行时左侧减-a。⒊栅格

矢量转换多边形边界