顾及拓扑一致性的水系三维曲线化简

刘民士，龙　毅，费立凡

1. 南京师范大学地理科学学院，江苏 南京210023； 2. 虚拟地理环境教育部重点实验室，江苏 南京210023； 3. 江苏省地理信息资源开发与利用协同创新中心，江苏 南京210023； 4. 滁州学院地理信息与旅游学院,安徽 滁州 239000; 5. 安徽省地理信息集成应用协同创新中心，安徽 滁州 239000



顾及拓扑一致性的水系三维曲线化简

刘民士1,2,3,4,5，龙毅1,2,3，费立凡4,5

1. 南京师范大学地理科学学院，江苏 南京210023； 2. 虚拟地理环境教育部重点实验室，江苏 南京210023； 3. 江苏省地理信息资源开发与利用协同创新中心，江苏 南京210023； 4. 滁州学院地理信息与旅游学院,安徽 滁州 239000; 5. 安徽省地理信息集成应用协同创新中心，安徽 滁州 239000

摘要：鉴于常规曲线化简方法应用于水系曲线化简时难以顾及水系要素的三维特征及其拓扑关系，本文提出了一种顾及拓扑一致性的水系三维曲线化简方法。该方法首先对D-P算法进行三维扩展,实现水系中单条河流三维曲线化简，然后构建水系树结构表达其拓扑关系，最后按照水系树的层次顺序依次进行河流曲线化简和干流与支流的拓扑关系重构。试验结果表明，该方法化简精度高，既能保持水系的三维形态特征，又能保证河流交汇处的拓扑一致性。

关键词：D-P算法；拓扑关系；三维曲线化简；水系化简

地貌与水系的自动综合是地图自动综合的重要研究内容，而水系作为地貌的骨架线，它的综合对其他要素有一定的控制和制约作用，其重要性通常要高于地貌要素[1]。近年来，关于水系的综合研究众多，主要集中在水系选取方法上，取得了较多的成果[2-4]，而对水系曲线化简的研究较少。究其原因，是因为水系各河流之间的等级结构使其差异明显，更适合于选取，并且通常也认为水系的形态相对简单，采用常规的曲线化简方法即可。

目前，曲线化简方法分为以下3类：一是基于几何特征分析的曲线化简方法，这类方法也称作点位信息度量方法[5]，即从几何特征角度分析曲线上各点的信息量大小，从而决定点是否选取，这类方法主要有D-P法[6]及其改进方法[7-9]、LI-OPENSHOW法[10-11]；二是基于结构特征分析的曲线化简方法，这类方法以曲线的弯曲结构为分析对象，通过对弯曲进行提取、结构组织与特征分析从而确定弯曲的保留与删除[12-15]；三是基于数学分析的曲线化简方法，主要有采用分形分析方法[16-17]和小波分析方法[18-19]。

然而，以上曲线化简方法都是针对二维曲线，且是对单条曲线处理。因此，当应用到水系曲线化简时，就存在以下两个问题：一是化简难以体现三维形态特征，特别是面对水系的“叠水”现象，难以保留其“叠水”特征(如图1所示)，虽然文献[20]提出利用3D D-P算法对等高线进行三维综合化简，但该方法的本质是将等高线看成三维散点，进行“体”的综合，并不是直接对三维曲线进行化简，故其并不适合于水系三维曲线化简；二是难以维护河流之间的拓扑关系，常规处理方法是将河流数据在交汇点处先分段再化简，如文献[21]采用分段D-P化简方法保留交汇点从而维护其拓扑关系，然而，河流分段将破坏河流曲线的整体形态特征。事实上，要保持水系拓扑关系的一致性，并不意味着水系交汇点的几何位置在化简过程不能变化，反而，从多尺度表达的角度上看，水系交汇点的几何位置原本就应该随着水系综合的程度而相应变化。

因此，本文对D-P算法进行三维曲线化简扩展，提出一种顾及拓扑一致性的水系三维曲线化简方法，在化简过程中既能保持水系三维形态，又能保证水系拓扑关系。

1顾及拓扑一致性的水系三维曲线化简方法

1.1基本思路

顾及拓扑一致性的水系三维曲线化简方法，需要解决两个问题：一是如何保持三维形态特征；二是如何维护水系中河流之间的拓扑关系。针对前者，将D-P算法进行三维曲线化简扩展，以点到空间直线的三维点线距代替平面上的点线距，从而使特征点的选取能顾及到整个三维形态特征。对于后者，通过构建水系树结构表达河流拓扑关系，并按照先干流后支流的顺序进行化简，在化简之后，检测河流交汇点处的拓扑关系并进行拓扑重构，从而保持河流交汇处的拓扑一致性。

图1　水系的“叠水”特征Fig.1　The superimposed characteristic of water system

1.2D-P算法在三维曲线化简上的扩展

图2　三维扩展D-P算法的三维点线距表达Fig.2　Three-dimensional point-line distance principle of 3D extended D-P algorithm

1.3水系树结构建立

水系树结构的构建关键在于建立干流与支流的关系，文献[22]给出完整的河系树结构建立方法，但其构建的河系树结构只包含河流编号之间的父子关系，缺少河流交汇点信息，且该方法通过人为指定确定主干流，不利于全自动处理，尤其是当水系数据中包含多个河系，多条主干流时。为了便于水系中河流交汇点的描述与处理，本文设计了一个河流信息结构RS，其包括河流本身标识BID、该河流汇入的河流标识TID(“父”河流或干流河流)以及河流汇点坐标SP3个要素。该结构的设计是基于每一条河流仅汇入一条干流河流或不汇入任何河流，如果是后者，则该河流为主干流。从树的逻辑结构来看，水系树结构是由节点组成的，每个节点包括一个数据域和若干个指针域，RS即为该节点的数据域，而其指针域则存储干流与支流的关系。

水系树结构的建立过程分为河流信息结构构造(RS构造)、主干流确定，干流-支流关系建立3步：①RS构造：RS包括BID、TID、SP3要素，其中BID可直接从当前河流数据中获取，SP可通过比较河流两个端点高程的大小确定(高程值小即为河流汇点SP)，TID则通过遍历其他所有河流的所有点，找到与SP坐标一致的点，该点所在的河流标识即为TID；②主干流确定：由于主干流不汇入任何河流，因此当某河流RS结构中的TID数据为空(其值可设为-1)，则为主干流，故RS构造后主干流即可确定；③干流-支流关系建立：采用从上至下的层次构建方法，即从主干流开始，依次建立各干流-支流的关系。首先从主干流的RS结构中获取其河流标识，记为BID0；然后依次遍历其他所有河流RS结构中的干流河流标识，记为TIDi；最后查找与BID0相等的TIDi，将相匹配的河流记为主干流的一级支流。同理，根据一级支流确定二级支流，依次进行，整个水系树结构建立成功。图3为水系示意图，其中数字1—10为各条河流，字母A—J则为各个交汇点，图4为根据图3构建的水系树结构图，其中字母A—J表示交汇点SP，第1个数字表示结点当前河流的编号BID，第2个数字表示汇入河流编号TID，其中，-1表示河流不存在。

图3　水系示意图Fig.3　Schematic diagram of water system

图4　水系树结构Fig.4　Tree structure of water system

1.4拓扑关系变化检测与重构

干流化简后，原有交汇点处拓扑关系可能破坏，因此需要进行拓扑关系变化检测与拓扑重构，拓扑重构过程又分为干流交汇点重新生成和支流汇点移位两个过程。

1.4.1拓扑关系变化检测

交汇点处拓扑关系是否变化，是在干流化简后，判断该交汇点是否仍然存在于干流曲线上。由于单条河流曲线上高程值是单调变化的，从河流源点到汇点高程逐渐降低，因此，可以从干流源点开始依次遍历曲线上点，判断该点的高程Zi与交汇点高程Zsp的关系：如果Zi=Zsp，则遍历结束，交汇点存在，拓扑关系没有变化；如果Zi

1.4.2干流交汇点重新生成

当干流中的交汇点删除后，需要生成新的交汇点，新的交汇点应取支流汇点到干流的旧交汇点相邻两点(未被删除)所构空间直线的垂足。如图5所示，干流R1的交汇点Qi删除后，从支流R2的汇点Pn作空间直线Qi-1Qi+1的垂足O为新的交汇点。考虑到空间直线Qi-1Qi+1相对于支流前进的方向有可能后退，即PnO与PnPn-1所成夹角θ小于90°(图5(b))，此时，支流流向不合常理，因此从Pn点逆流向上依次取支流上的点，重新计算相应的垂足O与角度θ，直到θ大于90°为止(图5(b)中O′点为新交汇点)。

图5　拓扑重构过程Fig.5　Process of topology reconstruction

1.4.3支流汇点移位

新交汇点O生成之后，就需将支流的汇点移位到该点位置，因此将河流R2的SP结构中的汇点SP重置为O点；同时，修改R2的河流数据，根据在上述干流交汇点重新生成过程获得到支流汇点的前一点Pi(图5(a)中为Pn，5(b)中为Pn-1)，将Pi后续点删除，并在Pi之后插入O点。

2试验与分析

2.1试验设计

试验过程采用两份1∶5万水系数据，数据1是丘陵地貌区域的水系，其等高线间距为10 m，河流条数28条(图6(a))；数据2是黄土地貌区域的水系，其等高线间距为20 m，河流条数21条(图6(b))。试验采用D-P化简方法[6]、分段D-P化简方法[21]和本方法对数据进行9种尺度的化简(压缩率为0.1到0.9)。考虑到原始河流数据通常为二维数据，必须先对水系数据进行三维化处理，水系三维化方法采用文献[23]提出的根据等高线进行反距离权重内插与分段线性内插相结合的方法，对河流源点与汇点采用反距离权重插值计算高程，对其他内部点先计算河流与等高线的交点，然后以相邻交点对河流分段，之后采用流水线线性内插方法计算高程。此外，为了能得到固定的压缩率，采用“智能阻尼震荡法”[24]，通过一个可变步长智能调整阈值，直到化简结果满足预设的压缩率为止。算法步骤如下，给定初始阈值dis、阈值调整的初始步长step、一个目标压缩率rat_o和目标压缩率的容差tol：

(1) 采用阈值dis进行化简并计算压缩率rat_c，并令diff=rat_c-rat_o；

(2) 如果|diff|≤tol，结束；否则，分以下4种情况分别处理返回步骤(1)：①如果diff<0，且上一次diff<0，则dis=dis+step；②如果diff<0，且上一次diff>0，则step=step/2，dis=dis+step；③如果diff>0，且上一次diff>0，则dis=dis-step；④如果diff>0，且上一次diff<0，则step=step/2，dis=dis-step。

图6　水系试验数据Fig.6　Experimental data of water system

2.2化简精度对比分析

线化简算法评价的研究很多，但主要集中在位置精度和形态结构特征两个方面[25]。文献[26]提出应从几何精度、结构形态、空间关系和适用范围4个方面评估曲线化简算法，其中前两者分别对应于位置精度与形态结构特征。因此，考虑到水系化简的实际情况，分别从几何精度、结构形态与空间关系3个方面对本方法进行评估。

2.2.1几何精度评估

几何精度评估的指标很多，如矢量位移、面积偏差、长度变化、曲折度等，各指标都存在一定的相关性。本文采用水系二维长度变化、三维长度变化(化简后水系长度减去原始水系长度)为评价指标，将本方法与D-P法和分段D-P法对比分析。

图7为数据1的水系长度变化对比图，水系二维总长度为35 973.6m，三维总长度为37 086.9m。从二维长度变化来看，3种算法在各个压缩率上结果都相差不大(图7(a))，相比较而言，D-P算法的变化最小；从三维长度变化来看，D-P算法和分段D-P算法相差不大，而本方法的变化则要远小于另外两种方法，且随着压缩率的增加差距更大(图7(b))。

图7　3种化简方法对数据1的水系长度变化对比Fig.7　Contrast among length change of water system using three methods in data 1

图8为数据2的水系长度变化对比图，河流二维总长度为87 109.1m，三维总长度为87 433.6m。从二维长度变化来看，3种算法差别很小，但仍然表现为随压缩率增大差距逐渐增大，相比较而言，本方法变化最小，D-P法次之(图8(a))；从三维长度变化来看，本方法在各个压缩率上的变化要明显小于其他两种算法，D-P法的变化比分段D-P法略小(图8(b))。

图8　3种化简方法对数据2的水系长度变化对比Fig.8　Contrast among length change of water system using three methods in data 2

2.2.2结构形态评估

评价曲线的形态结构特征可从分维数和特征点保持两方面进行[26]。文献[26]提出基于分形理论评估化简后曲线形态的一般方法，通过比较化简后曲线分维数与原始曲线分维数的相似程度，从而判定算法优劣。本文采用二维分维数与三维分维数为评价指标，前者基于二维曲线计算，后者基于三维曲线计算。分维数采用“脚规”法计算，通过不同步长量测曲线长度，并以线性回归模型拟合[17,26]。

表1为本方法与D-P法化简后水系分维数计算结果，其中数据1的原始二维分维数为1.038 16，三维分维数为1.037 89；数据2的原始二维分维数为1.036 84，三维分维数为1.036 83。图8为根据表1生成的分维数变化(原始分维数减去化简后分维数)对比图。对于二维分维数，本方法与D-P法相差不大，仅在个别压缩尺度上，D-P法的变化更小；对于三维分维数，本方法在各个化简尺度数据上的变化都明显小于D-P法，尤其是数据1(图9(a))表现更突出。

表1　本方法与D-P法化简后水系分维数计算结果

图9　D-P法与本方法化简后水系分维数对比Fig.9　Contrast between fractal dimension of water system using this method and D-P algorithm

特征点保持主要考察不同化简方法对二维、三维特征点的保留情况。图10为本方法与D-P法在同一化简尺度下水系特征点保留对比图(部分)，其中圆点为本方法保留特征点，三角形点为D-P法保留特征点。从二维特征点保持来看，两种方法差异不大，其保留的特征点都能较好呈现曲线的二维特征；然而，从三维特征点保持来看(借助地形)，本方法保留的特征点更好，尤其是像A、B等“叠水”位置，本方法保留的两点为曲线上三维拐点，显然优于D-P保留的两点。

2.2.3空间关系评估

水系的空间关系评估，主要是评价河流之间的拓扑关系一致性，即河流交汇处的拓扑关系能否保持。图11为上述试验数据在3种算法化简后的部分结果图(图11(a)为本方法与D-P的对比，图11(b)为本方法与分段D-P法的对比)，图中灰色曲线为原始水系数据，黑色曲线为D-P算法化简结果，红色曲线为分段D-P算法化简结果，绿色曲线为本方法化简结果。如图所示，D-P法不能保持河流交汇处的拓扑关系(图11(a)红色虚线圆圈处)，分段D-P算法和本方法能够保持其拓扑关系一致性，但分段D-P算法通过对干流曲线分段，降低了干流曲线化简精度，而本方法通过重构交汇点，使之不影响干流化简精度(图11(b))。

图11　3种算法化简后拓扑一致性结果对比(部分)Fig.11　Contrast among topological consistency of water system using three methods

3结论

本文提出了顾及拓扑一致性的三维水系化简方法，通过构建水系树结构、三维曲线扩展的D-P算法以及拓扑一致性检测与拓扑重构处理方法，实现了保持拓扑一致性的水系三维形态化简并进行了试验验证。结果显示：①该方法能保证河流间的拓扑关系，避免常规河流化简出现的拓扑不一致现象，且其拓扑一致性处理更合理；②该方法化简精度可靠，能最大限度地保证三维形态，随着综合尺度的增大，效果相对更优。该方法的不足之处在于常规河流数据大多不包含高程信息，需在化简之前先将河流曲线数据三维化，因此，设计一种快速高精度的水系高程信息提取方法非常关键，这也是后续的研究方向之一。

参考文献：

[1]王家耀,孙群,王光霞,等. 地图学原理与方法[M]. 北京: 科学出版社, 2006: 209-339.

WANG Jiayao, SUN Qun, WANG Guangxia, et al. Principle and Method of Cartography[M]. Beijing: Science Press, 2006: 209-339.

[2]张青年. 顾及密度差异的河系简化[J]. 测绘学报, 2006, 35(2): 191-196.

ZHANG Qingnian. Generalization of Drainage Network with Density Differences[J]. Acta Geodaetica et Cartographica Sinica, 2006, 35(2): 191-196.

[3]艾廷华,刘耀林,黄亚锋.河网汇水区域的层次化剖分与地图综合[J]. 测绘学报, 2007, 36(2): 231-236, 243.

AI Tinghua, LIU Yaolin, HUANG Yafeng. The Hierarchical Watershed Partitioning and Generalization of River Network[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(2): 231-236, 243.

[4]STANISLAWSKI L V. Feature Pruning by Upstream Drainage Area to Support Automated Generalization of the United States National Hydrography Dataset[J]. Computers, Environment and Urban Systems, 2009, 33(5): 325-333.

[5]邓敏,陈杰,李志林,等. 曲线简化中节点重要性度量方法比较及垂比弦法的改进[J]. 地理与地理信息科学, 2009, 25(1): 40-43.

DENG Min, CHEN Jie, LI Zhilin, et al. An Improved Local Measure Method for the Importance of Vertices in Curve Simplification[J]. Geography and Geo-Information Science, 2009, 25(1): 40-43.

[6]DOUGLAS D H, PEUCKER T K. Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or its Caricature[J]. Cartographica: The International Journal for Geographic Information and Geovisualization, 1973, 10(2): 112-122.

[7]VAN OOSTEROM P, SCHENKELAARS V. The Development of an Interactive Multi-scale GIS[J]. International Journal of Geographical Information Systems, 1995, 9(5): 489-507.

[8]毋河海. 基于多叉树结构的曲线综合算法[J]. 武汉大学学报(信息科学版), 2004, 29(6): 479-483.

WU Hehai. Multi-Way Tree Structure Based on Curve Generalization Method[J]. Geomatics and Information Science of Wuhan University, 2004, 29(6): 479-483.

[9]陈轶, 彭认灿, 郑义东, 等. 基于Douglas双侧多叉树的曲线综合算法研究[J]. 测绘学报, 2010, 39(3): 310-315.

CHEN Yi, PENG Rencan, ZHENG Yidong, et al. Line Generalization Based on Douglas Both-sides Multi-way Tree[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(3): 310-315.

[10]LI Zhilin, OPENSHAW S. Algorithms for Automated Line Generalization1 Based on a Natural Principle of Objective Generalization[J]. International Journal of Geographical Information Systems, 1992, 6(5): 373-389.

[11]朱鲲鹏, 武芳, 王辉连, 等. Li-Openshaw算法的改进与评价[J]. 测绘学报, 2007, 36(4): 450-456.

ZHU Kunpeng, WU Fang, WANG Huilian, et al. Improvement and Assessment of Li-Openshaw Algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(4): 450-456.

[12]艾廷华, 郭仁忠, 刘耀林. 曲线弯曲深度层次结构的二叉树表达[J]. 测绘学报, 2001, 30(4): 343-348.

AI Tinghua, GUO Renzhong, LIU Yaolin. A Binary Tree Representation of Curve Hierarchical Structure in Depth[J]. Acta Geodaetica et Cartographica Sinica, 2001, 30(4): 343-348.

[13]WANG Zeshen, MüLLER J C. Line Generalization Based on Analysis of Shape Characteristics[J]. Cartography and Geographic Information Systems, 1998, 25(1): 3-15.

[14]钱海忠, 武芳, 陈波, 等. 采用斜拉式弯曲划分的曲线化简方法[J]. 测绘学报, 2007, 36(4): 443-449, 456.

QIAN Haizhong, WU Fang, CHEN Bo, et al. Simplifying Line with Oblique Dividing Curve Method[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(4): 443-449, 456.

[15]DU Shihong.Analyzing Topological Changes for Structural Shape Simplification[J]. Journal of Visual Languages & Computing, 2014, 25(4): 316-332.

[16]MULLER J C. Fractal and Automated Line Generalization[J]. The Cartographic Journal, 1987, 24(1): 27-34.

[17]王桥. 线状地图要素的自相似性分析及其自动综合[J]. 武汉测绘科技大学学报, 1995, 20(2): 123-128.

WANG Qiao. Self-Similarity Analysis of Cartographic Lines and the Automated Line Generalization[J]. Journal of Wuhan Technical University of Surveying and Mapping, 1995, 20(2): 123-128.

[18]吴纪桃, 王桥. 小波分析在GIS线状数据图形简化中的应用研究[J]. 测绘学报, 2000, 29(1): 71-75.

WU Jitao, WANG Qiao. A Study on Automatic Cartographic Generalization Using Wavelet Analysis in GIS[J]. Acta Geodaetica et Cartographica Sinica, 2000, 29(1): 71-75.

[19]朱长青,王玉海,李清泉, 等. 基于小波分析的等高线数据压缩模型[J]. 中国图象图形学报, 2004, 9(7): 841-845.

ZHU Changqing, WANG Yuhai, LI Qingquan, et al. A Model to Compress Contour Data Based on Wavelet Analysis[J]. Journal of Image and Graphics, 2004, 9(7): 841-845.

[20]何津, 费立凡, 黄丽娜, 等. 三维Douglas-Peucker算法的等高线间接综合方法研究[J]. 测绘学报, 2013, 42(3): 467-473.

HE Jin, FEI Lifan, HUANG Li’na, et al. Study on the Method of Indirect Generalization for Contour Lines Based on the 3D Douglas-Peucker Algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(3): 467-473.

[21]应申, 李霖. 基于约束点的曲线一致性化简[J]. 武汉大学学报(信息科学版), 2003, 28(4): 488-491.

YING Shen, LI lin. Consistent Line Simplification Based on Constraint Points[J]. Geomatics and Information Science of Wuhan University, 2003, 28(4): 488-491.

[22]毋河海. 河系树结构的自动建立[J]. 武汉测绘科技大学学报, 1995, 20(S): 7-14.

WU Hehai. Automatic Establishment of River Tree Structure[J]. Journal of the Wuhan Technical University of Surveying and Mapping, 1995, 20(S): 7-14.

[23]黄丽娜. 基于广义DEM的地貌与水系要素一体化综合研究[D]. 武汉: 武汉大学, 2010: 97-99.

HUANG Li’na. Study on the Integrated Generalization of Relief and Water System Based on General DEM[D]. Wuhan: Wuhan University, 2010: 97-99.

[24]何津, 费立凡. 解决图形冲突的受限变形所涉及的数学原则—以道路与建筑物的关系为例[J]. 武汉大学学报(信息科学版), 2007, 32(4): 326-330.

HE Jin, FEI Lifan. Mathematical Methods Involved in Constrained Reshaping for Solving Graphic Conflicts between Streets and Buildings[J]. Geomatics and Information Science of Wuhan University, 2007, 32(4): 326-330.

[25]邓敏, 樊子德, 刘慧敏. 层次信息量的线要素化简算法评价研究[J]. 测绘学报, 2013, 42(5): 767-773, 781.

DENG Min, FAN Zide, LIU Huimin. Performance Evaluation of Line Simplification Algorithms Based on Hierarchical Information Content[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(5): 767-773, 781.

[26]武芳, 邓红艳, 钱海忠, 等. 地图自动综合质量评估模型[M]. 北京: 科学出版社, 2009: 95-138.

WU Fang, DENG Hongyan, QIAN Haizhong, et al. Quality Assess Model of Map Automatic Generalization[M]. Beijing: Science Press, 2009: 95-138.

(责任编辑：宋启凡)

修回日期： 2016-01-06

First author： LIU Minshi( 1983—), lecturer, PhD candidate，majors in automatic map generalization.

E-mail： liuminshi1983@126.com

E-mail： longyi@njnu.edu.cn

Line Simplification of Three-dimensional Drainage Considering Topological Consistency

LIU Minshi1,2,3,4,5，LONG Yi1,2,3，FEI Lifan4,5

1. School of Geography Science, Nanjing Normal University, Nanjing 210023,China; 2. Key Laboratory of Virtual Geographic Environment of Ministry of Education, Nanjing 210023,China; 3. Jiangsu Center for Collaborative Innovation in Geographical Information Resource Development and Application, Nanjing 210023,China; 4. School of Geographic Information and Tourism, Chuzhou University, Chuzhou 239000, China; 5. Anhui Center for Collaborative Innovation in Geographical Information Integration and Application, Chuzhou 239000, China

Abstract：In view of the fact that drainage line simplification using conversional methods is usually hard to keep the three-dimensional characteristics and topological relationships, this paper proposes a new method of three-dimensional drainage line simplification which maintains topological consistency. It firstly expends the conversional D-P algorithm to three-dimensional in order to keep three-dimensional characteristics during the simplification. Then it constructs tree structures for drainage lines to express their topological relations. Finally, it simplifies river lines and reconstructs topological relations of main streams and their branches according to the hierarchical order of water system tree. The experimental results show that this method has a higher accuracy in simplification and can maintain not only three-dimensional shape characteristics of water system but also the topological consistency at river confluences.

Key words：D-P algorithm; topological relationship; three-dimensional line simplification; water system simplification

Corresponding author：LONG Yi

通信作者：龙毅

第一作者简介：刘民士(1983—)，讲师，博士生，主要从事地图自动综合的理论与方法研究。

收稿日期：2015-06-01

基金项目：国家自然科学基金(41171350;41301514;41501496)；滁州学院校级培育项目(2014PY03)

中图分类号：P208

文献标识码：A

文章编号：1001-1595(2016)04-0494-08

Foundation support： The National Natural Science Foundation of China (Nos.41171350; 41301514; 41501496);The Cultivation Projiect of Chuzhou University (No.2014PY03)

引文格式：刘民士，龙毅，费立凡.顾及拓扑一致性的水系三维曲线化简[J].测绘学报，2016,45(4)：494-501. DOI:10.11947/j.AGCS.2016.20150288.

LIU Minshi，LONG Yi，FEI Lifan.Line Simplification of Three-dimensional Drainage Considering Topological Consistency[J]. Acta Geodaetica et Cartographica Sinica,2016,45(4):494-501. DOI:10.11947/j.AGCS.2016.20150288.