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

地理空间数据的获取(huòqǔ)与处理第三(dìsān)部分精品PPT主要(zhǔyào)内容第六章空间数据的处理(chǔlǐ)方法精品PPT第六章空间数据的处理(chǔlǐ)方法◆图形屏幕编辑的基本操作算法介绍纠正数据采集错误的重要手段——图形编辑的基本功能、要求。◆空间数据拓扑关系的自动生成介绍矢量(shǐliàng)数据拓扑关系建立的基本步骤和要点。◆空间数据的压缩编码方法介绍矢量(shǐliàng)数据和栅格数据的压缩处理。◆空间数据的格式转换◆矢量(shǐliàng)和栅格数据的转换精品PPT6.1图形屏幕(píngmù)编辑的基本操作算法点的捕捉(bǔzhuō)线的捕捉(bǔzhuō)面的捕捉(bǔzhuō)图形编辑的关键是点、线、面的捕捉，即如何根据光标的位置找到需要编辑的要素，以及图形编辑的数据组织。精品PPT点的捕捉(bǔzhuō)设光标点为A(x,y)，图幅上某一点状要素的坐标为S(X，Y)，则可设一捕捉半径D(通常为3～5个象素)。d<D则选中，若有多个(duōɡè)点，则要求出距A(x,y)的最近点。精品PPT线的捕捉(bǔzhuō)设光标点坐标为S(x,y)，D为捕捉半径(bànjìng)，线的坐标为(x1,y1),(x2,y2),…(xn,yn)。通过计算S到该线的每个直线段的距离di(如左图所示)，若min(d1,d2,…dn-1)＜D，则认为光标S捕捉到了该条线。在计算前，用最小矩形，跳过图右的线条。•S(x,y)精品PPT(X1,Y2)(X1,Y)(X1,Y’)精品PPT面的捕捉(bǔzhuō)面的捕捉实际上就是判断光标点S(x,y)是否在多边形内，若在多边形内则说明捕捉到。判断点是否在多边形内的算法主要(zhǔyào)有垂线法或转角法。精品PPT垂线(chuíxiàn)法先进行(jìnxíng)图右的判断（在线框内外），再做奇偶点数的判断。奇在内，偶在外。垂线、水平线、斜线的结果均相同，垂线或水平线运算方便。对于点在面的边界上，可以对点的坐标加微量解决。若精度要求高，不允许加微量，可以先解决点是否在面边界的判断，再使用垂线法。精品PPT精品PPT6.2空间数据拓扑关系的自动(zìdòng)生成欧拉定理点线拓扑关系的建立多边形矢量数据(shùjù)拓扑关系自动建立精品PPT多数情况下拓扑关系的建立可由GIS软件自动生成。特殊情况下，需要人工对拓扑关系进行人工修改，如建立管网或路网数据的分析网络(wǎngluò)时，就需要对结点、管段的方向等进行编辑。精品PPT扫描(sǎomiáo)后的栅格数据精品PPT矢量化后的数字(shùzì)线划图精品PPT精品PPT精品PPT矢量数据的常见(chánɡjiàn)错误精品PPT公共(gōnggòng)边界的处理12211精品PPT矢量数据拓扑关系在空间数据的查询(cháxún)与分析中非常重要，矢量数据拓扑关系自动建立的算法是GIS中的关键算法之一。精品PPT欧拉定理(dìnglǐ)对于多边形图形，n、a、b分别表示(biǎoshì)结点数、弧段数、多边形数则：c=n-a+b或c+a=n+bc+弧=点+面c为常数，其取值为：c=2包含外多边形c=1不包含外多边形精品PPT点线拓扑关系(guānxì)的建立记录结点——弧段表弧段——结点表弧段入库时，检测结点表，若存在记录点号；否则(fǒuzé)产生新的点号，再记录精品PPT多边形的四种基本(jīběn)图形独立(dúlì)公共边岛复合精品PPT多边形矢量数据拓扑(tuòpū)关系的自动建立链的组织(zǔzhī)结点匹配闭合检查建立多边形概念过程岛的判断确定多边形的属性精品PPT链的组织(zǔzhī)1找出在链的中间相交(左图)，而不是在端点(duāndiǎn)相交(右图)的情况，自动切成新链。精品PPT链的组织(zǔzhī)2原来的两条链变成了四条链。再把链按一定顺序存储，如按最大或最小的x或y坐标的顺序，这样查找(cházhǎo)和检索都比较方便，然后把链按顺序编号。精品PPT链的生成(shēnɡchénɡ)精品PPT结点(jiédiǎn)匹配结点匹配(pǐpèi)是指把一定限差内的链的端点作为一个结点，其坐标值取多个端点的平均值。然后，对结点顺序编号。X=(x1+x2+x3)/3;Y=(y1+y2+y3)/3精品PPT去除(qùchú)悬线精品PPT闭合(bìhé)检查检查多边形是否(shìfǒu)闭合可以通过判断一条链的端点是否(shìfǒu)有与之匹配的端点来进行。悬挂链不需参加多边形拓扑，可以作一标记，使之不参加下一阶段拓扑建立多边形的工作。精品PPT建立(jiànlì)多边形概念(gàiniàn)1顺时针方向构多边形。顺时针方向构多边形是指多边形在链的右侧精品PPT概念(gàiniàn)2最靠右边的链最靠右边的链是指从链的一个端点出发，在这条链的方向上最右边的第一条链。如图，a的最右边的链为d。找最靠右边的链可通过计算(jìsuàn)链的方向和夹角实现精品PPT求最右线段(xiànduàn)的方法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中最大者为最右方向(fāngxiàng)，其链为下一条发展链。精品PPT概念3用多边形面积判断(pànduàn)方向用面积值判断方向（需将绝对(juéduì)号去除）精品PPT建立多边形的基本(jīběn)过程1、顺序取一个结点为起始结点，至该点上所有链均用2次止；取过该结点的任一条链作为起始链。2、取这条链的另一结点，找这个结点上，靠这条链最右边的链，作为下一条链。3、是否回到起点：是，已形成一多边形，记录之，并转4；否，转2。4、取起始点上开始的，刚才所形成多边形的最后一条边反向作为新的起始链，转2；若这条链已用过两次，即已成为(chéngwéi)两个多边形的边，则转1。精品PPT岛的判断(pànduàn)岛的判断即指找出多边形互相包含的情况，即寻找多边形的连通边界。找出所有比该正面积多边形面积小的负面积多边形；用外接矩形法去掉(qùdiào)不可能包含的多边形；取负面积多边形上的一点，看是否在正面积多边形内。单多边形被追踪两次

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

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

Morton=00110111=55这样，在一个2n×2n的图像中，每个像元点都给出一个Morton码。精品PPT十进制和二进制的转换(zhuǎnhuàn)十进制转二进制：

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

将余数(yúshù)从下向上倒序写就是二进制值例如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精品PPT二进制转十进制

从最后一位开始(kāishǐ)算，依次列为第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十进制和二进制的转换(zhuǎnhuàn)精品PPT6.4空间数据的格式(géshi)转换数据格式转换的内容空间定位、空间关系、属性信息(xìnxī)转换的方式通过外部数据交换文件转换通过标准空间数据文件转换通过标准API函数转换精品PPT6.5矢量(shǐliàng)和栅格数据的转换矢量─栅格转换由于矢量数据的点到栅格数据的点只是(zhǐshì)简单的坐标变换，线和面(多边形)的矢量数据向栅格数据的转换是主要内容。栅格─矢量转换栅格数据到矢量数据转换的一般过程为：二值化、二值图像的预处理、细化、追踪、拓扑化精品PPT精品PPT精品PPT精品PPT矢量(shǐliàng)─栅格转换点的栅格化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精品PPT线的栅格化方法(fāngfǎ)线是由多个直线段组成的，因此(yīncǐ)，线的栅格化的核心就是直线段如何由矢量数据转换为栅格数据。精品PPT⑴DDA法(数字(shùzì)微分分析法)直线段的两端点坐标转换(zhuǎnhuàn)到栅格数据的坐标系后为(xA,yA),(xB,yB)。设(xA,yA),(xB,yB)与栅格网的交点为(xi,yi)，则:精品PPT精品PPT精品PPT直线生成(shēnɡchénɡ)算法直线生成(shēnɡchénɡ):求与直线段充分接近的像素集当直线作为一系列像素位置生成时产生的阶梯效果精品PPT天津大学(tiānjīndàxué)计算机科学与技术学院直线(zhíxiàn)方程直线的斜率截矩方程:给定线段的两个端点,可以计算斜率m和y轴截矩b:精品PPT生成直线(zhíxiàn)的常用算法 均假定所画直线的斜率k∈[0，1]。DDA画线算法 DDA（DigitalDifferentialAnalyzer）画线算法也称数值微分法，是一种增量算法。它的算法实质(shízhì)是用数值方法解微分方程，通过同时对x和y各增加一个小增量，计算下一步的x、y值。精品PPTDDA算法(suànfǎ)数值(shùzí)微分算法(DigitalDifferentialAnalyzer)条件：待扫描转换的直线段：斜率：直线方程：,算法步骤：划分区间[x0,x1]:计算纵坐标：精品PPTDDA算法(suànfǎ)取整：算法(suànfǎ)复杂度:加法+取整精品PPTDDA算法(suànfǎ)其他斜率(xiélǜ)情况:交换x和y的位置步长dx或dy取-1不足之处：取整操作和浮点运算仍十分耗时精品PPT 已知一条直线段L（P0,P1）,其端点坐标为：P0(x0,y0),P1(x1,y1)。可计算出直线的斜率k为： 假定端点坐标均为整数，取直线起点P0(x0,y0)作为初始坐标。画线过程(guòchéng)从x的左端点x0开始，向x右端点步进，每步x递增1，y递增k（即直线斜率）；取像素点（x，round（y））作为当前点的坐标。精品PPT数值(shùzí)微分(DDA)法假定直线的起点、终点分别(fēnbié)为：（x0,y0),(x1,y1)，且都为整数。(Xi+1,Yi+k)(Xi,Int(Yi+0.5))(Xi,Yi)栅格交点表示象素点位置。。。。精品PPT数值(shùzí)微分(DDA)法基本思想已知过端点P0(x0,y0),P1(x1,y1)的直线段Ly=kx+b直线斜率为这种方法直观(zhíguān)，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。精品PPT数值(shùzí)微分(DDA)法计算yi+1=kxi+1+b =kxi+b+kx =yi+kx当x=1; yi+1=yi+k即：当x每递增1，y递增k(即直线斜率)；注意上述(shàngshù)分析的算法仅适用于k≤1的情形。在这种情况下，x每增加1,y最多增加1。当k1时，必须把x，y地位互换精品PPT数值(shùzí)微分(DDA)法增量算法：在一个(yīɡè)迭代算法中，如果每一步的x、y值是用前一步的值加上一个(yīɡè)增量来获得，则称为增量算法。DDA算法就是一个(yīɡè)增量算法。精品PPT⑵Bresenham算法(suànfǎ)该算法原来是为绘图机设计的，同样(tóngyàng)适合于栅格化。该算法的基本思路为：若直线的斜率为1∕2≤△y∕△x≤1，则下一点取(1，1)点，若0≤△y∕△x＜1∕2，则下一点取(1，0)点。根据直线的斜率，把直线分为8个卦限。以斜率在第一卦限为例，其余卦限的情况类似。精品PPT精品PPTBresenham

算例斜率(xiélǜ)为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。精品PPT⒉面(多边形)的栅格化方法(fāngfǎ)⑴内部点扩散法由一个内部的种子点，向其4个方向的邻点扩散。判断新加入的点是否在多边形边界上，如果是，不作为种子点，否则当作新的种子点，直到区域填满(tiánmǎn)，无种子点为止。该算法比较复杂，而且可能造成阻塞而造成扩散不能完成，此外若多边形不完全闭合时，会扩散出去。精品PPT区域是指已经表示成点阵形式的填充图形(túxíng)，它是像素集合。4-邻接点和8-邻接点四个方向运动八个方向运动四连通(liántōng)区域八连通(liántōng)区域精品PPT区域连通方式(fāngshì)对填充结果的影响4连通(liántōng)区域边界填充算法的填充结果8连通区域边界填充算法的填充结果精品PPT⑵扫描(sǎomiáo)法按扫描线的顺序，计算多边形与扫描线的相交区间，再用相应的属性值填充这些区间，即完成了多边形的栅格化。这种算法(suànfǎ)的缺点是计算量较大。精品PPT精品PPT精品PPT精品PPT精品PPT⑶边填充(tiánchōng)算法对于每一条(yītiáo)扫描线和每条多边形边上的交点，将该扫描线上交点右方的所有象素取原属性值之补。对多边形的每条边作此处理，多边形的方向任意。精品PPT边填充(tiánchōng)算法2上行(shàngxíng)时，左侧加-a；下行时左侧减-a。精品PPT⒊栅格

矢量(shǐliàng)转换精品PPT多边形边界(biānjiè)提取二值化

细化