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

第三部分主要内容第六章空间数据的处理方法第六章空间数据的处理方法◆图形屏幕编辑的基本操作算法介绍纠正数据采集错误的重要手段——图形编辑的基本功能、要求。◆空间数据拓扑关系的自动生成介绍矢量数据拓扑关系建立的基本步骤和要点。◆空间数据的压缩编码方法介绍矢量数据和栅格数据的压缩处理。◆空间数据的格式转换◆矢量和栅格数据的转换6.1图形屏幕编辑的基本操作算法点的捕捉线的捕捉面的捕捉图形编辑的关键是点、线、面的捕捉，即如何根据光标的位置找到需要编辑的要素，以及图形编辑的数据组织。点的捕捉设光标点为A(x,y)，图幅上某一点状要素的坐标为S(X，Y)，则可设一捕捉半径D(通常为3～5个象素)。dD则选中，若有多个点，则要求出距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用多边形面积判断方向用面积值判断方向（需将绝对号去除）niiiiixxyy111A)()(21S建立多边形的基本过程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值去掉而失真。栅格数据的压缩JPG27KBMP529K栅格的压缩和编码直接栅格编码链码(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）栅格到