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

1、第三部分第三部分 主要内容主要内容第六章第六章 空间数据的处理方法空间数据的处理方法第六章第六章 空间数据的处理方法空间数据的处理方法图形屏幕编辑的基本操作算法图形屏幕编辑的基本操作算法介绍纠正数据采集错误的重要手段图形编辑的基本功能、要求。空间数据拓扑关系的自动生成空间数据拓扑关系的自动生成介绍矢量数据拓扑关系建立的基本步骤和要点。空间数据的压缩编码方法空间数据的压缩编码方法介绍矢量数据和栅格数据的压缩处理。空间数据的格式转换空间数据的格式转换矢量和栅格数据的转换矢量和栅格数据的转换6.1 6.1 图形屏幕编辑的基本操作算法图形屏幕编辑的基本操作算法点的捕捉点的捕捉线的捕捉线的捕捉面的捕捉面

2、的捕捉图形编辑的关键是点、线、面的捕捉，即如何根据光标的位置找到需要编辑的要素，以及图形编辑的数据组织。点的捕捉设光标点为A(x,y)，图幅上某一点状要素的坐标为S(X，Y)，则可设一捕捉半径D(通常为35个象素)。dD 则选中，若有多个点，则要求出距A(x,y)的最近点。线的捕捉线的捕捉设光标点坐标为设光标点坐标为S(x,y)，D为捕捉半径，线的坐为捕捉半径，线的坐标为标为(x1,y1),(x2,y2),(xn,yn)。通过计算。通过计算S到该到该线的每个直线段的距离线的每个直线段的距离di(如左图所示如左图所示)，若，若min(d1,d2,dn-1)D，则认为光标，则认为光标S捕捉到了捕捉

3、到了该条线。在计算前，用最小矩形，跳过图右的该条线。在计算前，用最小矩形，跳过图右的线条。线条。S(x,y)(X1,Y2)(X1,Y)(X1,Y)面的捕捉面的捕捉面的捕捉实际上就是判断光标点面的捕捉实际上就是判断光标点S(x,y)是否是否在多边形内，若在多边形内则说明捕捉到。在多边形内，若在多边形内则说明捕捉到。判断点是否在多边形内的算法主要有垂线判断点是否在多边形内的算法主要有垂线法或转角法。法或转角法。垂线法垂线法先进行图右的判断（在线框内外），再做奇偶点数的判断。先进行图右的判断（在线框内外），再做奇偶点数的判断。奇在内，偶在外。奇在内，偶在外。垂线、水平线、斜线的结果均相同，垂线或水平

4、线运算方垂线、水平线、斜线的结果均相同，垂线或水平线运算方便。便。对于点在面的边界上，可以对点的坐标加微量解决。若精对于点在面的边界上，可以对点的坐标加微量解决。若精度要求高，不允许加微量，可以先解决点是否在面边界的度要求高，不允许加微量，可以先解决点是否在面边界的判断，再使用垂线法。判断，再使用垂线法。6.2 6.2 空间数据拓扑关系的自动生成空间数据拓扑关系的自动生成欧拉定理欧拉定理点线拓扑关系的建立点线拓扑关系的建立多边形矢量数据拓扑关系自动建立多边形矢量数据拓扑关系自动建立多数情况下拓扑关系的建立可由GIS软件自动生成。特殊情况下，需要人工对拓扑关系进行人工修改，如建立管网或路网数据的

5、分析网络时，就需要对结点、管段的方向等进行编辑。扫描后的栅格数据矢量化后的数字线划图矢量数据的常见错误公共边界的处理公共边界的处理 12211矢量数据拓扑关系在空间数据的查询与分析中非常重要，矢量数据拓扑关系自动建立的算法是GIS中的关键算法之一。欧拉定理欧拉定理对于多边形图形，对于多边形图形，n、a、b 分别表示结点数、分别表示结点数、弧段数、多边形数弧段数、多边形数则：则： c=n-a+b 或或 c+a=n+b c+弧弧=点点+面面c为常数，其取值为：为常数，其取值为： c=2 包含外多边形包含外多边形 c=1 不包含外多边形不包含外多边形点线拓扑关系的建立点线拓扑关系的建立记录记录 结点

6、结点弧段表弧段表 弧段弧段结点表结点表弧段入库时，检测结点表，若存在记录点弧段入库时，检测结点表，若存在记录点号；否则产生新的点号，再记录号；否则产生新的点号，再记录多边形的四种基本图形多边形的四种基本图形 独立独立 公共边公共边 岛岛 复合复合多边形多边形矢量数据拓扑关系的自矢量数据拓扑关系的自动建立动建立链的组织结点匹配闭合检查建立多边形 概念 过程岛的判断确定多边形的属性链的组织链的组织 1 1找出在链的中间相交找出在链的中间相交(左图左图)，而不是在端点相，而不是在端点相交交(右图右图)的情况，自动切成新链。的情况，自动切成新链。链的组织链的组织 2原来的两条链变成了四条链。再把链按一

7、定顺序原来的两条链变成了四条链。再把链按一定顺序存储，如按最大或最小的存储，如按最大或最小的x或或y坐标的顺序，这样坐标的顺序，这样查找和检索都比较方便，然后把链按顺序编号。查找和检索都比较方便，然后把链按顺序编号。链的生成链的生成结点匹配结点匹配结点匹配是指把一定限差内的链的端点作为一个结点，其结点匹配是指把一定限差内的链的端点作为一个结点，其坐标值取多个端点的平均值。然后，对结点顺序编号。坐标值取多个端点的平均值。然后，对结点顺序编号。X=(x1+x2+x3)/3 ; Y=(y1+y2+y3)/3X=(x1+x2+x3)/3 ; Y=(y1+y2+y3)/3去除悬线去除悬线 闭闭合合检检查

8、查检查多边形是否闭合可以通过判断一条链的端检查多边形是否闭合可以通过判断一条链的端点是否有与之匹配的端点来进行。点是否有与之匹配的端点来进行。悬挂链悬挂链不需不需参加多边形拓扑，可以作一标记，使之不参加参加多边形拓扑，可以作一标记，使之不参加下一阶段拓扑建立多边形的工作。下一阶段拓扑建立多边形的工作。建立多边形概念概念1 顺时针方向构多边形。顺时针方向构多边形。 顺时针方向构多边形是指多边形在链的右侧顺时针方向构多边形是指多边形在链的右侧概念2 最靠右边的链最靠右边的链是指从链的一个端点出发，在这条链的最靠右边的链是指从链的一个端点出发，在这条链的方向上最右边的第一条链。如图，方向上最右边的第

9、一条链。如图，a的最右边的链为的最右边的链为d。找最靠右边的链可通过计算链的方向和夹角实现找最靠右边的链可通过计算链的方向和夹角实现求最右线段的方法1、从起始点、从起始点Pi出发，到达结出发，到达结点点P0，设方位角，设方位角P0 Pi为起为起始方位角始方位角f1；2、求终结点、求终结点P0到其他节点的到其他节点的方位角：方位角： f2 f3 .fn ；3、用、用f(i+1)-f(i)求解夹角求解夹角P(i) P0 P(i+1)，形成夹角串，形成夹角串 j j1 j2 jn；4、 j j1 j2 jn中最大者为中最大者为最右方向，其链为下一条最右方向，其链为下一条发展链。发展链。概念概念3 3

10、 用多边形面积判断方向用多边形面积判断方向用面积值判断方向（需将绝对号去除）用面积值判断方向（需将绝对号去除）niiiiixxyy111A)()(21S建立多边形的基本过程建立多边形的基本过程1、顺序取一个结点为起始、顺序取一个结点为起始结点，至该点上所有链均用结点，至该点上所有链均用2次止；取过该结点的任一次止；取过该结点的任一条链作为起始链。条链作为起始链。2、取这条链的另一结点，、取这条链的另一结点，找这个结点上，靠这条链最找这个结点上，靠这条链最右边的链，作为下一条链。右边的链，作为下一条链。3、是否回到起点：是，已、是否回到起点：是，已形成一多边形，记录之，并形成一多边形，记录之，并

11、转转4；否，转；否，转2。4、取起始点上开始的，刚、取起始点上开始的，刚才所形成多边形的最后一条才所形成多边形的最后一条边反向作为新的起始链，转边反向作为新的起始链，转2；若这条链已用过两次，；若这条链已用过两次，即已成为两个多边形的边，即已成为两个多边形的边，则转则转1。岛的判断岛的判断岛的判断即指找出多边形互相包含的情况，即岛的判断即指找出多边形互相包含的情况，即寻找多边形的连通边界。寻找多边形的连通边界。 找出所有比该正面积多边形面积小的负面积多边形；找出所有比该正面积多边形面积小的负面积多边形； 用外接矩形法去掉不可能包含的多边形；用外接矩形法去掉不可能包含的多边形； 取负面积多边形上

12、的一点，看是否在正面积多边形内。取负面积多边形上的一点，看是否在正面积多边形内。 单多边形被追踪两次单多边形被追踪两次 p1p1p2p2p3p3记录多边形记录多边形多边形的记录格式可由节点或链构成多边形的记录格式可由节点或链构成 ID ，n ， P ，A ID ，n ， L ，A确定多边形的属性确定多边形的属性在追踪出每个多边形的坐标后，经常需确在追踪出每个多边形的坐标后，经常需确定该多边形的属性。定该多边形的属性。如果多边形有内点，则可以把内点与多边如果多边形有内点，则可以把内点与多边形匹配后，把内点的属性赋于多边形。形匹配后，把内点的属性赋于多边形。思考思考：若无内点，能否记录多边形的属性

13、？若无内点，能否记录多边形的属性？如果没有内点，则必须通过人机交互，对每个多边形赋属性。拓扑处理注意事项拓扑处理注意事项1）可以根据实际数据的情况和使用目的，选择不同的拓）可以根据实际数据的情况和使用目的，选择不同的拓扑处理选项组合；扑处理选项组合；2）如果需要进行拓扑错误检查，必须选择弧段求交，弧）如果需要进行拓扑错误检查，必须选择弧段求交，弧段求交是进行后续拓扑处理的基础。段求交是进行后续拓扑处理的基础。3）线数据集经过拓扑处理后，原来数据集的线对象将会）线数据集经过拓扑处理后，原来数据集的线对象将会在各线对象交点处被打断，而生成新的线对象，如用户还在各线对象交点处被打断，而生成新的线对象

14、，如用户还需继续使用原来的线数据集，可以在拓扑处理前对线数据需继续使用原来的线数据集，可以在拓扑处理前对线数据集先进行备份，以保护原数据集；集先进行备份，以保护原数据集；4）弧段求交操作得到的是一个真正的节点，而合并临近）弧段求交操作得到的是一个真正的节点，而合并临近点操作有时却得到一个假节点，因此合并临近点操作后可点操作有时却得到一个假节点，因此合并临近点操作后可能还要继续做合并假节点操作；能还要继续做合并假节点操作；5）线数据集必须关闭才能进行拓扑处理；）线数据集必须关闭才能进行拓扑处理；6）拓扑处理的结果与拓扑容限大小的设置有关。）拓扑处理的结果与拓扑容限大小的设置有关。中间数据集重名延

15、伸长悬线延伸长悬线1 1延伸长悬线延伸长悬线2 26.3 6.3 空间数据的压缩编码方法空间数据的压缩编码方法矢量数据的压缩矢量数据的压缩 矢量数据压缩的目的是删除冗余数据，减少数据的存贮量，节省存贮空间，加快后继处理的速度。栅格数据的压缩栅格数据的压缩 栅格数据压缩的目的是删除冗余数据，减少数据的存贮量，节省存贮空间，但在处理时会增大运算量。是用时间换空间。矢量数据的压缩道格拉斯普克法(DouglasPeucker)道格拉斯道格拉斯普克法普克法对每一条曲线的首末点虚连一条直线，对每一条曲线的首末点虚连一条直线，求所有点与直线的距离，并找出最大距求所有点与直线的距离，并找出最大距离值离值dma

16、x。用。用dmax与限差与限差D相比：相比： 若若dmaxD，这条曲线上的中间点全部舍去；，这条曲线上的中间点全部舍去； 若若dmaxD，保留，保留dmax对应的坐标点，并以该对应的坐标点，并以该点为界，把曲线分为两部分，对这两部分重点为界，把曲线分为两部分，对这两部分重复使用该方法复使用该方法垂距法垂距法每次顺序取曲线上的三个点，计算中间点与其每次顺序取曲线上的三个点，计算中间点与其它两点连线的垂线距离它两点连线的垂线距离d，并与限差，并与限差D比较。若比较。若dD，则中间点去掉；若，则中间点去掉；若dD，则中间点保留。，则中间点保留。然后顺序取下三个点继续处理，直到这条线结然后顺序取下三个

17、点继续处理，直到这条线结束。束。 光栏法定义一个扇形区域，通过判断曲线上的点在扇形外还是在扇形内，确定保留还是舍去。设曲线上的点列为pi，i1，2，n，光栏口经d可根据压缩量确定几种方法的比较标准 既能精确地表示图形，又能最大限度地淘汰不必要的点，那就是一种好的算法。可以依据简化后曲线的总长度、总面积、坐标平均值等与原始曲线的相应数据的对比来判别。分析 大多数情况下道格拉斯普克法的压缩算法较好，但必须在对整条曲线数字化完成后才能进行，且计算量较大；光栏法的压缩算法也很好，并且可在数字化时实时处理，每次判断下一个数字化的点，且计算量较小；垂距法算法简单，速度快，但有时会将曲线的弯曲极值点p值去掉

18、而失真。栅格数据的压缩栅格数据的压缩JPG 27K BMP 529K 栅格的压缩和编码栅格的压缩和编码直接栅格编码直接栅格编码链码链码(chain Encoding)游程长编码游程长编码(Run_length Encoding)块码块码四叉树编码四叉树编码(quarter_tree Encoding)直接栅格编码将栅格数据当成数据矩阵，逐行(或逐列)记录代码，每行都从左到右记录，也可奇数行从左到右，偶数行从右到左。为了为了特定的目的还可采用其他特殊特定的目的还可采用其他特殊的顺序。的顺序。图右：AAAAABBBAABBAABB同时记录行、列数特点是处理方便，但没有压缩。A A A AA B B

19、 BA A B BA A B B直接栅格编码直接栅格编码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，每个网格用一个双字节表示，则一个图层的要素就占用 兆字节的存储

20、空间。200是将原始栅格阵列中属性值相同的连续若干个栅格单元映射为一个游程，每个游程的数据结构为（A，P）整数对。其中，A代表属性值，P代表该游程最右端栅格的列号。游程长度(行程)编码 按行扫描，将相邻等值的象元合并记录。 右图编码为 A4 A1 B3 A2 B2 A2 B2。若在行与行之间不间断地连续编码，则为 A5 B3 A2 B2 A2 B2。 对于游程长度编码，区域越大，数据的相关性越强，则压缩越大。其特点是，压缩效率较高，叠加、合并等运算简单，编码和解码运算快A A A AA B B BA A B BA A B B游程长度编码游程长度编码只在各行（或列）数据的代码发生变化时依次记录只

21、在各行（或列）数据的代码发生变化时依次记录该代码以及相同代码重复的个数；该代码以及相同代码重复的个数；沿行方向进行编码：沿行方向进行编码：( 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）。）。游程长度编码游程长度编码逐个记录各行（或列）代码发生变化的位置和逐

22、个记录各行（或列）代码发生变化的位置和相应代码相应代码（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中有广泛的应用。其基本思路为：将2n2n象元组成的图像(不足的用背景补上)所构成的二维平面按四个象限进行递归分割，直到子象限的数值单

23、调为止，最后得到一颗四分叉的倒向树，该树最高为n级。用一倒立树表示这种分割和分用一倒立树表示这种分割和分割结果。割结果。根：根：整个区域整个区域高：高：深度、分几级，几次分割深度、分几级，几次分割叶：叶：不能再分割的块不能再分割的块树叉：树叉：还需分割的块还需分割的块 每个树叉均有每个树叉均有4个分叉，叫四个分叉，叫四叉树。叉树。四叉树编码四叉树编码 四叉树分解，各子象限大小不完全一样，四叉树分解，各子象限大小不完全一样，但都是同代码栅格单元组成的子块，其中最上但都是同代码栅格单元组成的子块，其中最上面的一个结点叫做根结点，它对应于整个图形。面的一个结点叫做根结点，它对应于整个图形。 不能再分

24、的结点称为叶子结点，可能落在不不能再分的结点称为叶子结点，可能落在不同的层上，该结点代表子象限单一的代码，所同的层上，该结点代表子象限单一的代码，所有叶子结点所代表的方形区域覆盖了整个图形。有叶子结点所代表的方形区域覆盖了整个图形。 从上到下，从左到右为叶子结点编号，最下从上到下，从左到右为叶子结点编号，最下面的一排数字表示各子区的代码。面的一排数字表示各子区的代码。 为了保证四叉树分解能不断的进行下去，要为了保证四叉树分解能不断的进行下去，要求图形必须为求图形必须为2 2n n2 2 n n的栅格阵列。的栅格阵列。n n 为极限分为极限分割次数，割次数，n n1 1是四叉树最大层数或最大高度

25、是四叉树最大层数或最大高度8 8* *8 8四叉树编码四叉树编码 1112131415161718192021222324252627282930313233363738393435400 0 00 3 3 3 0 3 3 33 3 5 3 0 0 2 2 2 3 2 2 2 2 0 22 2 2 5 2 5 5 53 33 5 5西南东南西北东北 四叉树编码法的优点：1）容易而有效地计算多边形的数量特征；2）阵列各部分的分辩率是可变的，边界复杂部分四叉树较高即分级多，分辩率也高，而不需表示许多细节的部分则分级少，分辩率低，因而既可精确表示图形结构又可减少存贮量；3）栅格到四叉树及四叉树到简单

26、栅格结构的转换比其它压缩方法容易；4）多边形中嵌套异类小多边形的表示较方便。0231由直接栅格编码转换成四叉树编码的树状表示3333311111113333311111113331111444413331114444443322211144413222211114112222211111112222211111112222221111112222221111113331111031331111411311441332221444103211141122211122221110210000000000用用MortonMorton码表示四叉树地址码表示四叉树地址Morton码表示的叶结点码表示的叶

27、结点Morton码的转换码的转换 Morton码码叶节点码叶节点码 叶节点码叶节点码Morton码码 Morton码码行列值行列值 行列值行列值Morton码码0123四叉树地址和四叉树地址和MortonMorton码码01230123MortonMorton码码叶节点码叶节点码将十进制将十进制Morton码转为二进制码码转为二进制码 39 100111将二进制将二进制Morton码每二位转为十进制数码每二位转为十进制数 10 01 11 2 1 3叶节点码叶节点码MortonMorton码码将叶节点码逐位转为二进制将叶节点码逐位转为二进制 2 1 3 10 01 11将二进制叶节点码转为将二

28、进制叶节点码转为Morton码码 100111 39 1*25+0*24+0*23+1*22+1*21+1*20 32+0+0+4+2+1=39MortonMorton码码行列值行列值将将Morton码码39转为二进制转为二进制100111将二进制的将二进制的Morton码奇偶分开码奇偶分开 10 01 11 101 011将奇偶分别变成十进制的行列将奇偶分别变成十进制的行列 101 011 5 3行列值行列值MortonMorton码码将十进制的行列分别变成二进制将十进制的行列分别变成二进制 5 3 101 011将二进制的行列值奇偶合并得将二进制的行列值奇偶合并得Morton码码 101

29、011 10 01 11将二进制将二进制Morton码变为十进制码变为十进制 1*25+0*24+0*23+1*22+1*21+1*20 32+0+0+4+2+1=39十进制地址码Morton码例如，对于第5行、第7列的Moton码为：行数 = 5 ( 0 1 0 1 ) ；列数 = 7 ( 0 1 1 1 ) Morton = 0 0 1 1 0 1 1 1 = 55 这样，在一个2 n2 n 的图像中，每个像元点都给出一个Morton码。十进制和二进制的转换十进制和二进制的转换十进制转二进制：十进制转二进制： 用用2辗转相除至结果为辗转相除至结果为0， 将余数从下向上倒序写将余数从下向上倒

30、序写 就就是二进制值是二进制值例如例如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 余余0 1/2 = 0 余余1 故十进制故十进制302 =二进制二进制100101110 二进制转十进制二进制转十进制 从最后一位开始算，依次列为第从最后一位开始算，依次列为第0、1、2.位位 、第第n位的数（位的数（0或或1）乘以）乘以2的的n次方，得到的结次方，得到的结果相加就是十进制值。果相加就是十进制值。例如例如:0110

31、1011.转十进制转十进制: 第第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 然后：然后：120 8032640107 二进制二进制01101011十进制十进制107十进制和二进制的转换十进制和二进制的转换6.4 6.4 空间数据的格式转换空间数据的格式转换数据格式转换的内容数据格式转换的内容 空间定位、空间关系、属性信息空间定位、空间关系、属性信息转换的方式转换的方式 通过外部数据交换文件转换通过外部数据交换文件转

32、换 通过标准空间数据文件转换通过标准空间数据文件转换 通过标准通过标准API函数转换函数转换6.5 6.5 矢量和栅格数据的转换矢量和栅格数据的转换矢量矢量栅格转换栅格转换 由于矢量数据的点到栅格数据的点只是简单由于矢量数据的点到栅格数据的点只是简单的坐标变换，线和面的坐标变换，线和面(多边形多边形)的矢量数据向栅的矢量数据向栅格数据的转换是主要内容。格数据的转换是主要内容。栅格栅格矢量转换矢量转换 栅格数据到矢量数据转换的一般过程为：二栅格数据到矢量数据转换的一般过程为：二值化、二值图像的预处理、细化、追踪、拓扑值化、二值图像的预处理、细化、追踪、拓扑化化矢量矢量栅格转换栅格转换点的栅格化点

33、的栅格化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线的栅格化方法线的栅格化方法 线是由多个直线段组成的，因此，线的栅线是由多个直线段组成的，因此，线的栅格化的核心就是直线段如何由矢量数据转格化的核心就是直线段如何由矢量数据转换为栅格数据。换为栅格数据。DDADDA法法( (数字微分分析法数字微分分析法) )直线段的两端点坐标转换到栅格数据的坐标系直线段的两端点坐标转换到栅格数据的坐标系后为后为(xA,yA),

34、(xB,yB)。设。设(xA,yA),(xB,yB)与栅格网与栅格网的交点为的交点为(xi,yi)，则，则:直线生成算法直线生成算法直线生成直线生成: 求与直线段充分接近的像素集求与直线段充分接近的像素集当直线作为一系列像素位置生成时产生的阶梯效果当直线作为一系列像素位置生成时产生的阶梯效果天津大学计算机科学与技术学院直线方程直线方程直线的斜率截矩方程直线的斜率截矩方程:给定线段的两个端点给定线段的两个端点 , 可可以计算斜率以计算斜率m和和y轴截矩轴截矩b:ym xB00(,) (,)endendxyxy00endendyymxx00 xmyb生成直线的常用算法均假定所画直线的斜率k0，1。

35、DDA画线算法DDA（Digital Differential Analyzer）画线算法也称数值微分法，是一种增量算法。它的算法实质是用数值方法解微分方程，通过同时对x和y各增加一个小增量，计算下一步的x、y值。DDA算法算法 数值微分算法数值微分算法(Digital Differential Analyzer) 条件：条件： 待扫描转换的直线段：待扫描转换的直线段： 斜率：斜率： 直线方程：直线方程： , 算法步骤：算法步骤： 划分区间划分区间x0,x1: 计算纵坐标：计算纵坐标：01( 0, 0)( 1, 1)P xyP xy10,10 xxxyyy /myx ym xB011,1nii

36、x xxxx其中11(1)iiiiiym xBmxBm xBmym01mDDA算法算法 取整：取整： 算法复杂度算法复杂度: 加法加法+取整取整11()(int)(0.5)iiiyround yymDDA算法算法其他斜率情况其他斜率情况:1m 交换交换x和和y的位置的位置0m 步长步长dx或或dy取取-1不足之处：取整操作和浮点运算仍十分耗时不足之处：取整操作和浮点运算仍十分耗时已知一条直线段L（P0, P1）,其端点坐标为：P0 (x0, y0), P1(x1, y1)。可计算出直线的斜率k为： 假定端点坐标均为整数，取直线起点P0 (x0, y0)作为初始坐标。画线过程从x的左端点x0开始

37、，向x右端点步进，每步x递增1，y递增k（即直线斜率）；取像素点（x，round（y）作为当前点的坐标。0101xxyyk数值微分(DDA)法 假定直线的起点、终点分别为：（x0,y0), (x1,y1)，且都为整数。(X i+1 ,Yi + k)(X i , Int(Yi +0.5)(X i , Yi)栅格交点表示象素点位置。数值微分(DDA)法基本思想已知过端点P0 (x0, y0), P1(x1, y1)的直线段Ly=kx+b直线斜率为这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。 0101xxyyk)(,;10yroundxbkxystepxxxxxx令数值微分(

38、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算法就是一个增量算法。BresenhamBresenham算法算法该算法原来是为绘图机设该算法原来是为绘图机设计的，同样适合于栅格化。计的，同样适合于栅格化。该算法的基本思路为：若该算法的基本思路为：若

39、直线的斜率为直线的斜率为12yx1，则下一点取，则下一点取(1，1)点，点，若若0yx12，则下一点，则下一点取取(1，0)点。点。n根据直线的斜率，把直线分为根据直线的斜率，把直线分为8个卦限。以斜率在第个卦限。以斜率在第一卦限为例，其余卦限的情况类似。一卦限为例，其余卦限的情况类似。BreseBresenhamnham算例算例斜率为斜率为13， 起始点：起始点：e12， 即即e3，取点，取点第第2点：点：e12 + 1316，e32y1取点取点第第3点：点：e16 + 13 = 16，即，即e121， 取点取点，且且e5/6,e=3；第第4点：点：e16 + 13 = 12 0，即，即e5

40、23， 取点取点因因e12，所以，所以，e12112。面面( (多边形多边形) )的栅格化方法的栅格化方法内部点扩散法内部点扩散法 由一个内部的种子点，向其由一个内部的种子点，向其4个方向的邻点扩散。判个方向的邻点扩散。判断新加入的点是否在多边形边界上，如果是，不作断新加入的点是否在多边形边界上，如果是，不作为种子点，否则当作新的种子点，直到区域填满，为种子点，否则当作新的种子点，直到区域填满，无种子点为止。无种子点为止。该算法比较复杂，而且该算法比较复杂，而且可能造成阻塞而造成扩可能造成阻塞而造成扩散不能完成，此外若多散不能完成，此外若多边形不完全闭合时，会边形不完全闭合时，会扩散出去。扩散

41、出去。区域区域是指已经表示成点阵形式的填充图形，它是像素集合。4-邻接点邻接点和8-邻接点邻接点表示内点表示边界点 四个方向运动 八个方向运动 四连通区域 八连通区域区域连通方式对填充结果的影响区域连通方式对填充结果的影响4连通区域边界填充算法的填充结果8连通区域边界填充算法的填充结果扫描法扫描法按扫描线的顺序，计算多边形与扫描线的相按扫描线的顺序，计算多边形与扫描线的相交区间，再用相应的属性值填充这些区间，交区间，再用相应的属性值填充这些区间，即完成了多边形的栅格化。这种算法的缺点即完成了多边形的栅格化。这种算法的缺点是计算量较大。是计算量较大。边填充算法边填充算法边填充算法2 2上行时，左

42、侧加上行时，左侧加-a；下行时左侧减；下行时左侧减-a。栅格栅格矢量转换矢量转换多边形边界提取二值化 细化 二值图像二值图像矢量转换矢量转换二值化二值化 对于地图，通常在灰度级直方图上出现两个对于地图，通常在灰度级直方图上出现两个峰值，这时，取波谷处的灰度级为阈值，二峰值，这时，取波谷处的灰度级为阈值，二值化的效果较好值化的效果较好二值图像的预处理二值图像的预处理 对于扫描输入的对于扫描输入的图幅，会出现一些图幅，会出现一些飞白、污点、线划飞白、污点、线划边缘凹凸不平等。边缘凹凸不平等。可以通过一些算法可以通过一些算法来进行处理。来进行处理。对飞白、污点给定对飞白、污点给定其最小尺寸，不足其最小尺寸，不足的消除的消除；对于断对于断线，采取先加粗后减细的方法进行断线相连；用低通线，采取先加粗后减细的方法进行断线相连；用低通型滤波进行破碎地物的合并，用高通滤波提取区域范型滤波进行破碎地物的合并，用高通滤波提取区域范围等等围等等细化细化所谓细化就是将二值图像象元阵列逐步剥除轮所谓细化就是将二值图像象元阵列逐步剥除轮廓边缘的点，使之成为线划宽度只有一个象元廓边缘的点，使之成为线划宽度只有一个象元的骨架图形。细化后的图形便于跟踪处理。的骨架图形。细化后的图形便于跟踪处理。细化的基本过程是：细化