空间数据组织算法

1、1空间数据组织算法 地理信息系统算法基础第六章2本讲内容v1 矢量数据的压缩v2 栅格数据的压缩v3 拓扑关系的生成 31 矢量数据的压缩v矢量数据的压缩包括两个方面的内容：矢量数据的压缩包括两个方面的内容：v一是在不扰乱拓扑关系的前提下，对采样点数据进行合理的一是在不扰乱拓扑关系的前提下，对采样点数据进行合理的抽稀；抽稀；v二是对矢量坐标数据重新进行编码，以减少所需要的存储空二是对矢量坐标数据重新进行编码，以减少所需要的存储空间。间。v矢量数据的压缩往往是矢量数据的压缩往往是不可逆不可逆的，数据压缩后，数据量变小的，数据压缩后，数据量变小了，数据的精度降低了。了，数据的精度降低了。41 矢量

2、数据的压缩v1.1 1.1 间隔取点法间隔取点法v1.2 1.2 垂距法和偏角法垂距法和偏角法v1.3 1.3 道格拉斯道格拉斯- -普克法普克法v1.4 1.4 光栏法光栏法v1.5 1.5 曲线压缩算法的比较曲线压缩算法的比较v1.6 1.6 面域的数据压缩算法面域的数据压缩算法51.1 间隔取点法原理原理：每隔每隔K K个点取一点，或舍个点取一点，或舍去那些离已选点比规定距离更去那些离已选点比规定距离更近的点，但首、末点一定要保近的点，但首、末点一定要保留，如图留，如图5.15.1所示。所示。 优缺点优缺点：可大量压缩数字化仪可大量压缩数字化仪用连续方法获取的点列中的点、用连续方法获取的

3、点列中的点、曲率显著变化的点，但不一定曲率显著变化的点，但不一定能恰当地保留方向上曲率显著能恰当地保留方向上曲率显著变化的点。变化的点。61.2 垂距法和偏角法原理原理：按垂距或偏角按垂距或偏角的限差，选取符合或的限差，选取符合或超过限差的点。超过限差的点。优缺点优缺点：不能同时考不能同时考虑相邻点间的方向与虑相邻点间的方向与距离，且有可能舍去距离，且有可能舍去不该舍去的点，但较不该舍去的点，但较前一种方法有进步。前一种方法有进步。71.3 道格拉斯-普克法 v原理原理：将一条曲线首、末点连一条直线，求出其余各点到该将一条曲线首、末点连一条直线，求出其余各点到该直线的距离，选其最大者与规定的临

4、界值相比较，若大于临直线的距离，选其最大者与规定的临界值相比较，若大于临界值，则离该直线距离最大的点保留，否则将直线两端间各界值，则离该直线距离最大的点保留，否则将直线两端间各点全部舍去。点全部舍去。 如图如图5.35.3所示，经数据采样得所示，经数据采样得到的曲线到的曲线MNMN由点序由点序P1，P2，P3，Pn组成，组成，n n个点的坐标个点的坐标集集为(x1,y1), (x2,y2), (x3,y3),(xn,yn)。其中其中P1，Pn代分别对应曲线的起代分别对应曲线的起点点M和终点和终点N。根据应用需要和数据精度要求，给定控制数据压缩的极差为根据应用需要和数据精度要求，给定控制数据压缩

5、的极差为，表示为被舍弃的点偏离特征点连线之间的垂直距离。表示为被舍弃的点偏离特征点连线之间的垂直距离。 81.3 道格拉斯-普克法曲线的空间数据压缩过程如下：曲线的空间数据压缩过程如下：第一步第一步：确定：确定曲线MNMN对应弦的直线方程。对应弦的直线方程。 由起点由起点M M、终点、终点N N建立直线建立直线方程为方程为将上式化简为一般形式为将上式化简为一般形式为：Ax+By+C=0第二步第二步：求曲线求曲线MN上各点上各点Pi到弦线到弦线MN的距离的距离di。 Pi(xi，yi)到弦线到弦线MN的距离为的距离为第三步第三步：求距离求距离di的最大值的最大值dh第四步第四步：比较比较dh与与

6、的大小，并计算开关的大小，并计算开关Q：NMMMMNyyyyxxxx|iiidAxByC123max(,)hndd ddd1 0 hhdQd91.3 道格拉斯-普克法第五步第五步：决定取舍，提取中间特征点。：决定取舍，提取中间特征点。(1)如果如果Q=0，则直接可以用弦线，则直接可以用弦线MN(M、N为特征点为特征点)代替曲线代替曲线MN；转第六步。；转第六步。(2)如果如果Q = 1，则将，则将dh所对应的点所对应的点Pi(Xi，yi )抽出，暂时作为中抽出，暂时作为中间特征点；然后连接新弦线间特征点；然后连接新弦线MPj；转第一步；转第一步(以以MPj已代替已代替MN，继续计算和判断，继续

7、计算和判断)。 若若Q = 0，则可以用弦线，则可以用弦线MPj代替曲线代替曲线MPj；将；将Pj作为中间特作为中间特征点取出；顺序排在征点取出；顺序排在M点之后，成为继点之后，成为继M之后的第一个中间之后的第一个中间特征点；并连接特征点；并连接PjN，转第一步（以，转第一步（以PjN代替代替MN，继续计算，继续计算和判断和判断)101.3 道格拉斯-普克法 若若Q = 1，则不可以用弦线，则不可以用弦线MPj代替曲线代替曲线MPj；找到此时；找到此时dh所所对应的点对应的点Pk， 并连接新弦线并连接新弦线MPk；转第一步；转第一步(以以MPk代替代替MN，继续计算和判断继续计算和判断) 第六

8、步第六步：形成新的数据文件。形成新的数据文件。 将所有提取出的中间特征点从起点将所有提取出的中间特征点从起点M M开始，顺序排列至终开始，顺序排列至终点点N N，并写入新的数据文件，即得到化简后的折线的数据文，并写入新的数据文件，即得到化简后的折线的数据文件。件。111.3 道格拉斯-普克法如图如图5.3所示，曲线所示，曲线MN的特征点提取过程如下：的特征点提取过程如下：(1)找到曲线找到曲线MN上上dh对应点位为对应点位为1号点；经判断可以用弦线号点；经判断可以用弦线M1代替曲线代替曲线M1，故，故1号点是继似点之后提取出的第一个特征点；号点是继似点之后提取出的第一个特征点；(2)连接弦线连

9、接弦线1N；经判断，不可以用弦线；经判断，不可以用弦线1N代替曲线代替曲线1N；找到；找到曲线曲线lN上上dh的对应点位为的对应点位为2号点；故连接号点；故连接1、2号点之弦线号点之弦线12；经判断，还是不可以用弦线经判断，还是不可以用弦线 12代替曲线代替曲线12；找到曲线；找到曲线12上上dh的对应点位为的对应点位为3号点；再连接号点；再连接1、3号点之弦线号点之弦线13；经判断，；经判断，可以用弦线可以用弦线13代替曲线代替曲线13；故；故3号点是继号点是继1号点之后提取出号点之后提取出的第二个特征点；的第二个特征点；121.3 道格拉斯-普克法(3)连接弦线连接弦线3N；经判断，不可以

10、用弦线；经判断，不可以用弦线3N代替曲线代替曲线3N；找到；找到曲线曲线3N上之上之dh的对应点位仍为的对应点位仍为2号点；然后，连接号点；然后，连接3、2号点号点之弦线之弦线32；经判断，可以用弦线；经判断，可以用弦线32代替曲线代替曲线32；故；故2号点是号点是继继1号点、号点、3号点之后提取出的第三个特征点；号点之后提取出的第三个特征点；(4)连接连接2、N号点之弦线号点之弦线2N；经判断，可以用弦线；经判断，可以用弦线2N代替曲线代替曲线2N；中间特征点提取结束。；中间特征点提取结束。至此可知，曲线至此可知，曲线MN可以用特征点可以用特征点M、1、3、2、N顺序连接的顺序连接的折线简化

11、表示。折线简化表示。 131.4 光栏法 原理：预先定义的一个扇形原理：预先定义的一个扇形( (“喇叭口喇叭口”），根据曲线上各节点），根据曲线上各节点是在扇形外还是在扇形内，决定节点是保留还是舍去。是在扇形外还是在扇形内，决定节点是保留还是舍去。设有曲线点列设有曲线点列Pi，i=1，2，n，“光栏口径光栏口径”为为d(由用户自己定由用户自己定义），则该方法实施的具体步骤：义），则该方法实施的具体步骤：(1)(1)连接连接p1和和p2，过过p2点作一条垂直点作一条垂直于于p1p2的直线，在该垂线上取两点的直线，在该垂线上取两点a1和和a2，使使a1p1=a2p2=d/2，此时此时a1和和a2为

12、为“光栏光栏”边界点边界点，p1与与a1、p1与与a2的连线为以的连线为以P P1 1为顶点的扇形的两条边，这就定义了一个扇为顶点的扇形的两条边，这就定义了一个扇形形( (这个扇形的口朝向曲线的前进方向，边长是任意的）。通过这个扇形的口朝向曲线的前进方向，边长是任意的）。通过p p1 1并在扇形内的所有直线都具有这种性质，并在扇形内的所有直线都具有这种性质， 即即p p1 1p p2 2上各点到这上各点到这些直线的垂距都不大于些直线的垂距都不大于d d/2/2。141.4 光栏法(2)若若p3点在扇形内，则舍丢点在扇形内，则舍丢p2点。然后连接点。然后连接p1和和p3，过过p3作作p1p3的垂

13、线，该垂线与前面定义的扇形边交于的垂线，该垂线与前面定义的扇形边交于c1和和c2。在垂线上。在垂线上找到找到b1和和b2点，使点，使p3b1 =p3b2=d/2，若若b1和和b2点落在原扇形外点落在原扇形外面（图面（图5.4中为中为b2点），则用点），则用c1或或c2取代取代(图图5.4中由中由c2取代取代b2)。此时用此时用p1b1和和p1c2定义一个新的扇形，这当然是口径定义一个新的扇形，这当然是口径(b1c2)缩缩小了的小了的“光栏光栏”。(3)检查下一节点，若该点在新扇形内，则重复第检查下一节点，若该点在新扇形内，则重复第(2)步；直到步；直到发现有一个节点在最新定义的扇形外为止发现有

14、一个节点在最新定义的扇形外为止。(4)当发现在扇形外的节点，如图当发现在扇形外的节点，如图5.4中的中的p4，此时保留点此时保留点p3，以以p3作为新起点，重复作为新起点，重复(1)(2)步。步。如此继续下去，直到整个点列检测完为止。所有被保留的点如此继续下去，直到整个点列检测完为止。所有被保留的点（含首、末点），顺序地构成了简化后的新点列。（含首、末点），顺序地构成了简化后的新点列。 151.4 光栏法161.5曲线压缩算法的比较 v评价依据：评价依据：压缩后的总长度、原曲线及压缩后曲线的线性位压缩后的总长度、原曲线及压缩后曲线的线性位移移( (矢高和面积矢高和面积) ) 等。等。v线性位移

15、量评价：道格拉斯线性位移量评价：道格拉斯- -普克法具有最小的线性位移；普克法具有最小的线性位移；偏角法在所有的压缩水平上较其他偏角法在所有的压缩水平上较其他3 3种方法具有更大的线性种方法具有更大的线性位移量，但仅依据矢高位移量又很难对间隔取点法的算法作位移量，但仅依据矢高位移量又很难对间隔取点法的算法作出结论，而在出结论，而在舍去舍去30%-70%30%-70%的点时，无论按矢高位移量还是的点时，无论按矢高位移量还是按面积位移量来评价，垂距法显然较偏角法和间隔取点法好按面积位移量来评价，垂距法显然较偏角法和间隔取点法好171.5曲线压缩算法的比较v结论：淘汰的点数越多，它们的压缩效果越趋于

16、一致。结论：淘汰的点数越多，它们的压缩效果越趋于一致。在一在一般情况下般情况下， 道格拉斯道格拉斯- -普克方法压缩效果占优普克方法压缩效果占优，其次是垂距，其次是垂距法、间隔取点法和偏角法，但道格拉斯法、间隔取点法和偏角法，但道格拉斯- -普克方法需对整条普克方法需对整条曲线完成数字化后方能进行压缩，曲线完成数字化后方能进行压缩， 且计算工作量较大。光且计算工作量较大。光栏法则不仅算法严密，能按给定阈值保留曲线特征点，并能栏法则不仅算法严密，能按给定阈值保留曲线特征点，并能实时处理，运算量少，占用内存少。实时处理，运算量少，占用内存少。181.6面域的数据压缩算法v面域空间数据的压缩过程面域

17、空间数据的压缩过程可以看成是组成其边界的曲线段的可以看成是组成其边界的曲线段的分别压缩，每段边界曲线的压缩过程如前所述分别压缩，每段边界曲线的压缩过程如前所述。 v封闭曲线的数据压缩封闭曲线的数据压缩v公共节点的取舍问题公共节点的取舍问题191.6面域的数据压缩算法封闭曲线的数据压缩封闭曲线的数据压缩v面域由首尾相连的封闭曲线组成。此时，可以人为地将该封面域由首尾相连的封闭曲线组成。此时，可以人为地将该封闭线分割为首尾相连的两段曲线，然后就可以按前述方法进闭线分割为首尾相连的两段曲线，然后就可以按前述方法进行压缩。曲线分割的原则是：行压缩。曲线分割的原则是：v（1 1）原节点是分割点之一；）原

18、节点是分割点之一；v（2 2）离原节点最远的下一节点是分割点之二。）离原节点最远的下一节点是分割点之二。201.6面域的数据压缩算法v如图如图5.75.7所示，多边形所示，多边形P P的边界曲线由从节点的边界曲线由从节点A A出发的曲线封出发的曲线封闭而成；其中曲线上闭而成；其中曲线上B B点离节点点离节点A A最远。因而，多边形最远。因而，多边形P P的边的边界曲线可以分割为界曲线可以分割为AMBAMB和和 BNABNA两段，进而对曲线段两段，进而对曲线段AMBAMB和和 BNABNA分别进行压缩。分别进行压缩。211.6面域的数据压缩算法公共节点的取舍问题公共节点的取舍问题v在某些特定情况

19、下，面域的边界曲线由多段首尾相连的曲线在某些特定情况下，面域的边界曲线由多段首尾相连的曲线连接而成，其压缩可以分段进行。此时各段曲线的起点和终连接而成，其压缩可以分段进行。此时各段曲线的起点和终点必然作为特征点提取出来，因而可能产生数据冗余。比如，点必然作为特征点提取出来，因而可能产生数据冗余。比如，当前后曲线段过渡时很平缓，曲线段的公共节点可以不成为当前后曲线段过渡时很平缓，曲线段的公共节点可以不成为特征点，即该点前后的两段曲线可以直接用该点前后的两个特征点，即该点前后的两段曲线可以直接用该点前后的两个特征点的连线来代替。特征点的连线来代替。221.6面域的数据压缩算法v如图如图5.95.9

20、所示，所示，1 1、2 2号点分别是面域号点分别是面域P P的边界曲线的边界曲线ABAB、BCBC段的段的内部特征提取点，内部特征提取点， 因而可以用弦因而可以用弦1B1B、B2B2分别代替曲线分别代替曲线1B1B和和B2B2。而实际上，整个曲线。而实际上，整个曲线1B21B2仍可以用弦仍可以用弦1212来代替来代替。231.6面域的数据压缩算法v在处理面域空间数据压缩时，可以在边界曲线分段压缩的基在处理面域空间数据压缩时，可以在边界曲线分段压缩的基础上，础上，增加一个步骤，即对边界曲线的端点进行可删性检验增加一个步骤，即对边界曲线的端点进行可删性检验：如果前一曲线最后提取的中间特征点与后一曲

21、线最先提取的如果前一曲线最后提取的中间特征点与后一曲线最先提取的中间特征点之间的曲线满足极差控制条件，则两条曲线的连中间特征点之间的曲线满足极差控制条件，则两条曲线的连接节点可以删减；否则，不可删减接节点可以删减；否则，不可删减。v由于各段边界曲线的数据文件要重新生成，所以当两段曲线由于各段边界曲线的数据文件要重新生成，所以当两段曲线的公共节点删减之后，相当于两条曲线合并为一条曲线。此的公共节点删减之后，相当于两条曲线合并为一条曲线。此时可能会扰乱拓扑关系时可能会扰乱拓扑关系( (如曲线如曲线ABAB或或BCBC为多边形的公共边，为多边形的公共边，或或ABAB和和BCBC均为多边形的公共边），

22、因此在处理公共节点的取均为多边形的公共边），因此在处理公共节点的取舍时要慎重，应该对此加以限制。舍时要慎重，应该对此加以限制。242 栅格数据的压缩v2.1 2.1 链式编码链式编码v2.2 2.2 游程长度编码游程长度编码v2.3 2.3 块式编码块式编码v2.4 2.4 差分映射法差分映射法v2.5 2.5 四叉树编码四叉树编码252 栅格数据的压缩v栅格数据文件记录有栅格数据文件记录有3 3个基本方式：个基本方式：基于像元、基于层和基基于像元、基于层和基于面域。于面域。v共同点：对像元坐标和属性的记录。共同点：对像元坐标和属性的记录。v因此基于栅格的空间数据压缩的因此基于栅格的空间数据压

23、缩的实质是研究栅格数据的编码实质是研究栅格数据的编码，通过编码尽量减少像元数量的存储。通过编码尽量减少像元数量的存储。v分类：栅格数据的压缩分为分类：栅格数据的压缩分为无损压缩技术和有损压缩技术无损压缩技术和有损压缩技术。262 栅格数据的压缩v无损压缩无损压缩方法利用数据的统计冗余进行压缩，可完全恢复原方法利用数据的统计冗余进行压缩，可完全恢复原始数据而不引入任何失真，但压缩率受到数据统计冗余度的始数据而不引入任何失真，但压缩率受到数据统计冗余度的理论限制，一般为理论限制，一般为2 2：1 5:11 5:1。v有损压缩有损压缩方法利用了数据在使用中存在某些成分不敏感的特方法利用了数据在使用中

24、存在某些成分不敏感的特性，允许压缩过程中损失一定的信息；虽然不能完全恢复原性，允许压缩过程中损失一定的信息；虽然不能完全恢复原始数据，但是所损失的部分对数据内涵的影响较小，却换来始数据，但是所损失的部分对数据内涵的影响较小，却换来了大得多的压缩比。了大得多的压缩比。272.1 链式编码v链式编码链式编码又称为弗里曼链码（又称为弗里曼链码（FreemanFreeman，19611961年）或边界链年）或边界链码。如图码。如图5.105.10所示，其中的多边形边界可表示为：由某一原所示，其中的多边形边界可表示为：由某一原点开始并按某些基本方向确定的单位矢量链。基本方向可定点开始并按某些基本方向确定

25、的单位矢量链。基本方向可定义为义为: :东东=0=0，东南，东南=1=1，南，南=2=2，西南，西南=3=3，西，西=4=4，西北，西北=5=5，北，北= 6= 6，东北东北=7=7，8 8个基本方向个基本方向。282.1 链式编码如果确定原点为像元如果确定原点为像元（1010，1)1)，则该多边形，则该多边形边界按顺时针方向的链边界按顺时针方向的链式编码式编码 ( (图图5.11)5.11)为：为：1010，1 1，7 7，0 0，1 1，0 0，7 7，1 1，7,07,0，0,20,2，3 3，2 2，2 2，1 1，0 0，7 7，0 0，0 0，0 0，0 0，2 2，4 4，3 3

26、，4 4，4 4，3 3， 4 4，4 4，5 5，4 4，5 5，4 4，5 5，4 4，5 5，4 4，6 6，6 6。292.1 链式编码v链式编码的优点链式编码的优点：链式编码对多边形的表示具有很强的数据：链式编码对多边形的表示具有很强的数据压缩能力，且具有一定的运算功能，如面积和周长计算等，压缩能力，且具有一定的运算功能，如面积和周长计算等，探测边界急弯和凹进部分等都比较容易；探测边界急弯和凹进部分等都比较容易；v链式编码的缺点链式编码的缺点是对叠置运算如组合、相交等则很难实施，是对叠置运算如组合、相交等则很难实施，对局部修改将改变整体结构，效率较低，而且由于链码以每对局部修改将改变

27、整体结构，效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的边界则被重复存储而产个区域为单位存储边界，相邻区域的边界则被重复存储而产生冗余。生冗余。302.2游程长度编码 v游程指相邻同值网格的数量，游程长度编码结构是逐游程指相邻同值网格的数量，游程长度编码结构是逐行行将相将相邻同值的网格合并，并记录合并后网格的值及合并网格的长邻同值的网格合并，并记录合并后网格的值及合并网格的长度，其目的是压缩栅格数据量，消除数据间的冗余。度，其目的是压缩栅格数据量，消除数据间的冗余。v游程长度编码结构的建立方法游程长度编码结构的建立方法是：将栅格矩阵的数据序列是：将栅格矩阵的数据序列X X1 1，X

28、 X2 2，X Xn n，映射为相应的二元组序列，映射为相应的二元组序列( (A Ai i，P Pi i），），i i=1=1，2,2,，K K，且，且K Knn。其中，。其中，A A为属性值，为属性值，P P为游程，为游程，K K为游程序为游程序号。号。312.2游程长度编码v游程长度编码这种数据结构特别适用于二值图像数据的表示游程长度编码这种数据结构特别适用于二值图像数据的表示 u游程编码能否压缩数据量，主要决定于栅格数据的性质，游程编码能否压缩数据量，主要决定于栅格数据的性质，通常可通过事先测试，估算图层的数据冗余度通常可通过事先测试，估算图层的数据冗余度Re：Re=1-Q/mn322.

29、2游程长度编码vQ Q为图层内相邻属性值变化次数的累加和；为图层内相邻属性值变化次数的累加和；m m为图层网格的行为图层网格的行数；数；n n为图层网格的列数。为图层网格的列数。v当当ReRe的值大于的值大于1/51/5的情况下，表明栅格数据的压缩可取得明的情况下，表明栅格数据的压缩可取得明显的效果。显的效果。v压缩效果可由压缩比压缩效果可由压缩比S =n /KS =n /K来表征，即压缩比的值愈大，来表征，即压缩比的值愈大，表示压缩效果愈显著。表示压缩效果愈显著。332.3块式编码 v块式编码是将游程长度编码扩大到二块式编码是将游程长度编码扩大到二维的情况，把多边形范围划分成由像维的情况，把

30、多边形范围划分成由像元组成的正方形，然后对各个正方形元组成的正方形，然后对各个正方形进行编码。进行编码。v块式块式编码的数据结构由初始位置（行编码的数据结构由初始位置（行号，列号号，列号) )和半径，再加上记录单元的和半径，再加上记录单元的代码组成。代码组成。v根据这一编码原则，图根据这一编码原则，图5.155.15所示多边所示多边形只需形只需1717个单位正方形，个单位正方形，9 9个个4 4单位的单位的正方形和正方形和1 1个个1616单位的正方形就能完整单位的正方形就能完整表示，总共要表示，总共要5757个数据，其中个数据，其中2727对坐对坐标，标，3 3个块的半径。个块的半径。342

31、.3块式编码v块式编码的特点：一个多边形所能包含的正方形越大，多边块式编码的特点：一个多边形所能包含的正方形越大，多边形的边界越简单，块式编码的效果越好。形的边界越简单，块式编码的效果越好。v游程和块式编码都对大的复杂多边形效果并不好。块式编码游程和块式编码都对大的复杂多边形效果并不好。块式编码在合并、插入、检查延伸性、计算面积等操作时有明显的优在合并、插入、检查延伸性、计算面积等操作时有明显的优越性。越性。352.4差分映射法 v差分映射法，差分映射法，就是选择某一参照值对有关栅格的属性值进行就是选择某一参照值对有关栅格的属性值进行求差运算，根据差值得到一个新的栅格数据层。求差运算，根据差值

32、得到一个新的栅格数据层。v参照值的选择有多种方式，即分行选取和全区选取。若分行参照值的选择有多种方式，即分行选取和全区选取。若分行选取，则可选为该行首列的属性值，也可以选为该行的属性选取，则可选为该行首列的属性值，也可以选为该行的属性平均值；若全区选取，则可选为首行首列的属性值，也可以平均值；若全区选取，则可选为首行首列的属性值，也可以选为全区的属性平均值。选为全区的属性平均值。 362.4差分映射法v图图5.165.16为栅格数据示例。图为栅格数据示例。图5.175.17所示为按分行选取方式，以所示为按分行选取方式，以行首属性值为参照，对图行首属性值为参照，对图5.165.16作差分映射后的

33、结果。可以看作差分映射后的结果。可以看出，经差分映射处理后，除第一列外，其余栅格的数据出现出，经差分映射处理后，除第一列外，其余栅格的数据出现为零、位数降低或数字减少。为零、位数降低或数字减少。372.4差分映射法v表表5.15.1为经差分映射处理前后的各栅格属性记录所需字节数为经差分映射处理前后的各栅格属性记录所需字节数的对比，可见，所需字节数由原来的的对比，可见，所需字节数由原来的7979减少为减少为 4444，减少，减少 44.3%44.3%。382.5 四叉树编码 v四叉树又称四元树或四分树，是四叉树又称四元树或四分树，是最有效最有效的栅格数据压缩编码的栅格数据压缩编码方法方法之一之一

34、。四分树将整个图像区域逐步分解为一系列方形区。四分树将整个图像区域逐步分解为一系列方形区域，且每一个方形区域具有单一的属性。最小区域为一个像域，且每一个方形区域具有单一的属性。最小区域为一个像元。元。 393 拓扑关系的生成 v拓扑空间关系是一种对空间结构进行明确定义的数学方法，拓扑空间关系是一种对空间结构进行明确定义的数学方法，具有拓扑关系的矢量数据结构就是拓扑数据结构。具有拓扑关系的矢量数据结构就是拓扑数据结构。v它描述了基本空间目标点、线、面之间的关联、邻接和包含它描述了基本空间目标点、线、面之间的关联、邻接和包含关系。关系。v矢量数据拓扑关系在空间数据的查询和分析过程中非常重要，矢量数

35、据拓扑关系在空间数据的查询和分析过程中非常重要，拓扑数据结构是地理信息系统分析和应用功能所必需的。拓扑数据结构是地理信息系统分析和应用功能所必需的。v拓扑空间关系信息是空间分析、辅助决策等的基础，也是拓扑空间关系信息是空间分析、辅助决策等的基础，也是GISGIS区别于区别于CAD(CAD(计算机辅助设计计算机辅助设计) )等的主要标志。等的主要标志。 对于拓扑对于拓扑关系的自动建立问题，研究的关系的自动建立问题，研究的焦点焦点是是如何提高算法与过程的如何提高算法与过程的效率和自动化程度，本节将讲述其实现的基本步骤和要点。效率和自动化程度，本节将讲述其实现的基本步骤和要点。403 拓扑关系的生成

36、v拓扑关系自动生成算法的一般过程为：拓扑关系自动生成算法的一般过程为：（1 1）弧段处理：弧段处理：使整幅图形中的所有弧段，除在端点处相交使整幅图形中的所有弧段，除在端点处相交外，没有其他交点，即没有相交或自相交的弧段。外，没有其他交点，即没有相交或自相交的弧段。（2 2）结点匹配：结点匹配：建立结点、弧段关系。建立结点、弧段关系。（3 3）建立多边形：建立多边形：以左转算法或右转算法跟踪，生成多边形，以左转算法或右转算法跟踪，生成多边形，建立多边形与弧段的拓扑关系。建立多边形与弧段的拓扑关系。（4 4）建立多边形与多边形的拓扑关系：建立多边形与多边形的拓扑关系：调整弧段的左右多边调整弧段的左

37、右多边形标识号。多边形标识号。多边 形内部标识号的自动生成。形内部标识号的自动生成。413 拓扑关系的生成v3.1 3.1 基本数据结构基本数据结构v3.2 3.2 弧段的预处理弧段的预处理v3.3 3.3 结点匹配算法结点匹配算法 v3.4 3.4 建立拓扑关系建立拓扑关系 423.1 基本数据结构v（1 1）拓扑结点）拓扑结点v（2 2）拓扑弧段及其表示）拓扑弧段及其表示v（3 3）拓扑面及其表示）拓扑面及其表示v（4 4）拓扑结点、弧段和面之间的关系）拓扑结点、弧段和面之间的关系433.1 基本数据结构v（1 1）拓扑结点）拓扑结点v结点用来描述如管线的交点、道路路口等现实世界的特征对结

38、点用来描述如管线的交点、道路路口等现实世界的特征对象，结点可以用来检测弧段与弧段的连接关系和多边形特征象，结点可以用来检测弧段与弧段的连接关系和多边形特征是否能正确地完成。只与一条弧段相连接的起点或终点叫做是否能正确地完成。只与一条弧段相连接的起点或终点叫做悬挂结点悬挂结点，如图，如图5.185.18所示的所示的P P点就是悬挂结点。点就是悬挂结点。v结点一般包括结点号、结点坐标、与该结点连接的弧段集合。结点一般包括结点号、结点坐标、与该结点连接的弧段集合。443.1 基本数据结构v结点的数据结构可以表示为：结点的数据结构可以表示为：453.1 基本数据结构v（2 2）拓扑弧段及其表示）拓扑弧

39、段及其表示 拓扑弧段指处于两个结点之间的点序列串拓扑弧段指处于两个结点之间的点序列串，可以给弧，可以给弧段定义一个方向，或者定义为数字化弧段时从一个结点到另一段定义一个方向，或者定义为数字化弧段时从一个结点到另一个结点的采点方向，或者硬性定义一个方向。个结点的采点方向，或者硬性定义一个方向。 定义方向后弧段开始的结点就称为定义方向后弧段开始的结点就称为起始结点起始结点，弧段结，弧段结束的结点就称为束的结点就称为结束结点结束结点，由起始结点到终止结点的方向称为，由起始结点到终止结点的方向称为“起终方向起终方向”，由终止结点到起始结点的方向称为，由终止结点到起始结点的方向称为“终起方终起方向向”。

40、弧段。弧段起终方向左侧的多边形称为弧段的左多边形起终方向左侧的多边形称为弧段的左多边形，弧段，弧段起终方向右侧的多边形称为弧段的右多边形起终方向右侧的多边形称为弧段的右多边形。463.1 基本数据结构v如果弧段的起始结点或终止结点只与一条弧段相关联，则该如果弧段的起始结点或终止结点只与一条弧段相关联，则该弧段称为弧段称为悬挂弧段悬挂弧段，如图，如图5.195.19所示的弧段所示的弧段L L为悬挂弧。一般为悬挂弧。一般可以通过标识悬挂弧段来检测原始矢量数据的质量。可以通过标识悬挂弧段来检测原始矢量数据的质量。 弧段一般包括弧段号、弧段节点坐标串、弧段起始和弧段一般包括弧段号、弧段节点坐标串、弧段

41、起始和终止结点、弧段左右多边形。终止结点、弧段左右多边形。 473.1 基本数据结构483.1 基本数据结构v（3 3）拓扑面及其表示）拓扑面及其表示v拓扑面是由一条或若干条弧段首尾相连接而成的边线所包含拓扑面是由一条或若干条弧段首尾相连接而成的边线所包含的区域的区域，内部包含有其他拓扑面的拓扑面一般称为，内部包含有其他拓扑面的拓扑面一般称为复杂面复杂面，被包含的拓扑面称为被包含的拓扑面称为岛岛，没有岛的拓扑面称为，没有岛的拓扑面称为简单面简单面，如图，如图5.205.20所示。对于拓扑面也可以定义所示。对于拓扑面也可以定义正反方向正反方向，一般定义为：，一般定义为：当沿拓扑面的边界前进时，被

42、弧段所包围的面域始终处于弧当沿拓扑面的边界前进时，被弧段所包围的面域始终处于弧段的右侧时的方向就是正方向；反之，则是反方向。段的右侧时的方向就是正方向；反之，则是反方向。493.1 基本数据结构v如图如图5.215.21所示，箭头所指向的方向就是正方向，可以看出对所示，箭头所指向的方向就是正方向，可以看出对于拓扑面的外边界，顺时针方向是正方向，而对于内边界逆于拓扑面的外边界，顺时针方向是正方向，而对于内边界逆时针方向就是正方向。时针方向就是正方向。503.1 基本数据结构v多边形一般包括多边形一般包括多边形号、中心点坐标、多边形属性数据、多边形号、中心点坐标、多边形属性数据、多边形的组成弧段号

43、、多边形岛多边形的组成弧段号、多边形岛的信息。考虑到组成弧段的的信息。考虑到组成弧段的方向和多边形顶点序列的方向存在可能的不一致性以及效率方向和多边形顶点序列的方向存在可能的不一致性以及效率问题，可以改为记录组成多边形的弧段指针和方向性信息，问题，可以改为记录组成多边形的弧段指针和方向性信息，即弧段方向与多边形的方向是否一致。即弧段方向与多边形的方向是否一致。v对于岛的信息则通过将构成多边形的边线分块来处理的方式对于岛的信息则通过将构成多边形的边线分块来处理的方式体现，比如多边形包含岛屿，则可以使多边形的外边界成为体现，比如多边形包含岛屿，则可以使多边形的外边界成为多边形的第一部分，岛屿作为多

44、边形的第二、三、四等部分多边形的第一部分，岛屿作为多边形的第二、三、四等部分的方式加以解决。的方式加以解决。 51523.1 基本数据结构(4)(4)拓扑结点、弧段和面之间的关系拓扑结点、弧段和面之间的关系533.2弧段的预处理 v拓扑关系自动建立的第一步就是处理弧段，使得弧段不存在拓扑关系自动建立的第一步就是处理弧段，使得弧段不存在自相交和相交现象。自相交和相交现象。v（1 1）直线段相交的判断方法）直线段相交的判断方法v（2 2）自相交弧段处理）自相交弧段处理v（3 3）弧段相交打断处理）弧段相交打断处理54(1)直线段相交的判断方法v直线相交的判定方法有很多种，这里介绍较快的一种算法。直

45、线相交的判定方法有很多种，这里介绍较快的一种算法。v设直线设直线L L过点过点P P0 0（x x0 0，y y0 0）和点）和点P P1 1（x x1 1，y y1 1），则直线），则直线L L的方程的方程可以表示为：可以表示为：v将方程化为参数形式：将方程化为参数形式：y y= =y y0 0+(+(y y1 1- -y y0 0) )t t, , x x= =x x0 0+(+(x x1 1- -x x0 0) )t t，其，其中中t t0,10,1。v设有两条直线设有两条直线L L1 1和和L L2 2，它们的参数方程分别为，它们的参数方程分别为y y= =y y0 0+(+(y y1

46、 1- -y y0 0) )t t，x x= =x x0 0+(+(x x1 1- -x x0 0) )t t 和和y y= =y y0 0+(+(y y1 1- -y y0 0) )，x x= =x x0 0+(+(x x1 1- -x x0 0) )001010yyxxtyyxx55(1)直线段相交的判断方法v判断两线段有无交点的关键变为判断判断两线段有无交点的关键变为判断t t和和v v；是否符合不等式；是否符合不等式00t t11且且00v v11。令：。令：如果如果dxdx dydy - - dydy dxdx = 0= 0，说明两线段平行或者重，说明两线段平行或者重合，没有交点，或

47、者交点在两线段的头或尾上；否则如果合，没有交点，或者交点在两线段的头或尾上；否则如果满足不等式满足不等式00t t11且且00v v11，两线段有交点，交点在两，两线段有交点，交点在两线段的中间。线段的中间。56（2）自相交弧段处理v具有自相交特征的弧段至少具有具有自相交特征的弧段至少具有4 4个个( (结结) )节点，由节点，由3 3个点或个点或2 2个点组成的弧段不可能自相交。依次取出每一条弧段，如果个点组成的弧段不可能自相交。依次取出每一条弧段，如果弧段的弧段的( (结结) )节点个数不少于节点个数不少于4 4个，就利用直线段相交的方法，个，就利用直线段相交的方法，对组成弧段的各直线段进

48、行判断，如果相交，将线段断开为对组成弧段的各直线段进行判断，如果相交，将线段断开为两条，自相交的弧段可能不止有一处相交，可以通过递归的两条，自相交的弧段可能不止有一处相交，可以通过递归的方法将弧段分开。方法将弧段分开。575859（3）弧段相交打断处理v弧段与弧段相交关系的判断，可以通过取每一条弧段与其他弧段与弧段相交关系的判断，可以通过取每一条弧段与其他未判断过的所有弧段目标进行相交关系判断而得，从而要进未判断过的所有弧段目标进行相交关系判断而得，从而要进行行（n - 1) + ( n - 2) + 3 + 2 + 1 = n（n 1）/2次判断。次判断。v具体方法具体方法为：取出第一条弧段

49、，与其他为：取出第一条弧段，与其他n - 1n - 1条弧段进行相条弧段进行相交判断，求得交点后，将交点分别插入第一条弧段和与其相交判断，求得交点后，将交点分别插入第一条弧段和与其相交弧段的对应位置上，并记录位置。将第一条弧段与所有其交弧段的对应位置上，并记录位置。将第一条弧段与所有其他弧段的相交关系判断完毕后，通过记录下的交点位置将第他弧段的相交关系判断完毕后，通过记录下的交点位置将第一条弧段分割，然后依次取出下一条弧段进行同样的处理，一条弧段分割，然后依次取出下一条弧段进行同样的处理，直到所有弧段处理完毕直到所有弧段处理完毕。 60（3）弧段相交打断处理v由于由于GISGIS的数据量大，造

50、成了判断的工作量大、效率低下的的数据量大，造成了判断的工作量大、效率低下的弊端，在判断两条弧段的关系时，应尽可能地减少计算量。弊端，在判断两条弧段的关系时，应尽可能地减少计算量。v减少计算量方法减少计算量方法：分两步，首先是判断两条弧段的最小矩形：分两步，首先是判断两条弧段的最小矩形壁包壁包(MBR)(MBR)是否相交或具有包含关系，如果不相交或没有包是否相交或具有包含关系，如果不相交或没有包含关系，那么可以断定两条弧段是互不相交的；如果相交或含关系，那么可以断定两条弧段是互不相交的；如果相交或具有包含关系，则进一步判断第一条弧段的每一条组成线段具有包含关系，则进一步判断第一条弧段的每一条组成

51、线段是否和第二条弧段的是否和第二条弧段的MBRMBR相交或被包含，如果不相交或没有相交或被包含，如果不相交或没有被包含则可以判断这一部分线段不会和第二条弧段相交，否被包含则可以判断这一部分线段不会和第二条弧段相交，否则可以使用这一条线段与组成第二条弧段的各个线段进行相则可以使用这一条线段与组成第二条弧段的各个线段进行相交关系的判定来确定交点。交关系的判定来确定交点。613.3结点匹配算法 v结点匹配结点匹配就是把一定容差范围内的弧段的结点合并成为一个就是把一定容差范围内的弧段的结点合并成为一个结点，其坐标值可以是取多个结点的平均值，或者选中一个结点，其坐标值可以是取多个结点的平均值，或者选中一

52、个结点作为所有结点的坐标区中心的坐标。结点作为所有结点的坐标区中心的坐标。623.3结点匹配算法v每条弧段对应着两个结点，每个结点在合并前对应着一条弧每条弧段对应着两个结点，每个结点在合并前对应着一条弧段，在合并结点的过程中，需要将结点对应的弧段也合并在段，在合并结点的过程中，需要将结点对应的弧段也合并在一起。一起。v具体的思路具体的思路是将所有的结点加入结点集合，从结点集合中取是将所有的结点加入结点集合，从结点集合中取出一个结点作为中心点，从余下的结点中找出容差范围内的出一个结点作为中心点，从余下的结点中找出容差范围内的其他结点，将这些结点所对应的弧段加入中心结点的弧段集其他结点，将这些结点

53、所对应的弧段加入中心结点的弧段集合中，同时将弧段的对应的结点变为中心结点，并修改弧段合中，同时将弧段的对应的结点变为中心结点，并修改弧段的相应坐标。的相应坐标。 633.4建立拓扑关系 v（）计算结点关联弧段的方位角（）计算结点关联弧段的方位角, ,并按由小到大排序并按由小到大排序v（）左转算法（）左转算法v（）岛的判断（）岛的判断64（）计算结点关联弧段的方位角v每个结点都关联有若干条弧段，结点或者为弧段的头结点或每个结点都关联有若干条弧段，结点或者为弧段的头结点或者为弧段的尾结点，设结点为者为弧段的尾结点，设结点为N N，则弧段的，则弧段的方位角方位角定义为：定义为：结点结点N N与弧段上

54、与其最接近结点与弧段上与其最接近结点V V的连线与的连线与轴的正向夹角。轴的正向夹角。65（）计算结点关联弧段的方位角v设结点设结点N N的坐标为的坐标为( (x x0 0，y y0 0 ) )，节点，节点v v的坐标为的坐标为( (x x1 1，y y1 1) )，则有：，则有：dxdx= =x x1 1- -x x0 0，dydy= =y y1 1- -y y0 0，那么有，那么有 v当当dx=0dx=0时时: :计算出结点计算出结点N N所关联的弧段的方位角后，按角的大小将这些所关联的弧段的方位角后，按角的大小将这些弧排序，形成排序的关联弧段集合弧排序，形成排序的关联弧段集合。66（2）

55、左转算法v算法基本思想算法基本思想：从组成多边形边界的某一条弧段开始，如果：从组成多边形边界的某一条弧段开始，如果该弧段的方向角最小或介于同一结点的其他弧段方向角之间，该弧段的方向角最小或介于同一结点的其他弧段方向角之间，则则逆时针方向逆时针方向寻找最小夹角偏差所对应的弧段为多边形的后寻找最小夹角偏差所对应的弧段为多边形的后续弧段；如果该弧段与续弧段；如果该弧段与X X轴正向夹角为最大，则从该弧段的轴正向夹角为最大，则从该弧段的同一结点出发的其他弧段中，方向角最小的弧段是该多边形同一结点出发的其他弧段中，方向角最小的弧段是该多边形的后续弧段。的后续弧段。67（2）左转算法v算法描述如下：算法描

56、述如下：（1 1）顺序取一个结点作为起始结点，取完为止；取过该结点）顺序取一个结点作为起始结点，取完为止；取过该结点的方位角最小的未使用过的或仅使用过一次，且使用过的方的方位角最小的未使用过的或仅使用过一次，且使用过的方向与本次相反的弧段作为起始弧段。向与本次相反的弧段作为起始弧段。（2 2）取这条弧段的另一个结点，找这个结点关联的弧段集合）取这条弧段的另一个结点，找这个结点关联的弧段集合中的本条弧段的下一条弧段，如果条弧段是最后一条弧段，中的本条弧段的下一条弧段，如果条弧段是最后一条弧段，则取弧段集合的第一条弧段，作为下一条弧段。则取弧段集合的第一条弧段，作为下一条弧段。68（2）左转算法（

57、3 3）判断是否回到起点，如果是，则形成了一个多边形，记）判断是否回到起点，如果是，则形成了一个多边形，记录下它，并且根据弧段的方向，设置组成该多边形的左右多录下它，并且根据弧段的方向，设置组成该多边形的左右多边形信息；否则转边形信息；否则转(2)(2)。（4 4）取起始点上开始的，刚才所形成多边形的最后一条边作）取起始点上开始的，刚才所形成多边形的最后一条边作为新的起始弧段，为新的起始弧段， 转转(2)(2)；若这条弧段已经使用过两次，即；若这条弧段已经使用过两次，即形成了两个多边形，转形成了两个多边形，转(1)(1)。v在构建多边形时要注意悬挂结点和悬挂线的标识，一般可以在构建多边形时要注

58、意悬挂结点和悬挂线的标识，一般可以采用栈的形式处理。采用栈的形式处理。69（2）左转算法（1 1）从）从N N1 1结点开始，选择具有最小结点开始，选择具有最小方位角的弧段方位角的弧段N N1 1N N2 2作为起始弧段；转作为起始弧段；转入入N N2 2点，根据左转算法选择点，根据左转算法选择N N2 2N N5 5弧段，弧段，转入转入N N5 5结点选择结点选择N N5 5N N1 1弧段，形成多边弧段，形成多边形形A A1 1，设置组成多边形，设置组成多边形A A1 1的弧段的左的弧段的左右多边形信息。右多边形信息。（2 2）A A1 1的结束弧段为的结束弧段为N N5 5N N1 1，

59、选，选N N1 1作作为起始点，为起始点，N N1 1N N5 5作为起始弧段，根据作为起始弧段，根据左转算法，形成多边形左转算法，形成多边形A A2 2，设置左，设置左右多边形信息。右多边形信息。 70（2）左转算法（3 3）A A2 2的结束弧段为的结束弧段为N N4 4N N1 1，选，选N N1 1作为起始点，作为起始点，N N1 1N N4 4作为起始弧作为起始弧段，根据段，根据 、左转算法，形成多边形、左转算法，形成多边形A A3 3，这个多边形的方向，这个多边形的方向是逆时针方向，对于逆时针方向的多边形，不设置左右多边是逆时针方向，对于逆时针方向的多边形，不设置左右多边形信息。形信息。71（2）左转算法（4 4）A A3 3的结束弧段为的结束弧段为N N2 2N N1 1， N N1 1N N2 2已经被使用过两次，所以选取已经被使用过两次，所以选取下一个结点下一个结点N N2 2作为起始结点。从作为起始结点。从N N2 2结点开始，具有最小方结点开始，具有最小方位角的弧段是位角的弧段是N N2 2N N1 1，但，但N N2 2N N1 1已经被使用两次，不选；已经被使用两次，不选； 继续选取下一条弧段继续选取下一条弧段N N2 2N N5 5；然而上一次该弧段的访问；然而上一次该弧段的访问方向与本次相同，所以也不选；继续选取下一条弧段方