顾及地理特征保持的溺谷海岸线化简算法

黄亚锋，艾廷华，刘耀林，张航峰

1.南京电子技术研究所，江苏 南京 210039；2.武汉大学 资源与环境科学学院，湖北 武汉 430079

1 引 言

作为主要地图要素的海岸线化简一直是地图综合领域研究热点问题，典型算法包括点删除类方法［1－7］、光滑类方法［8－10］、弯曲类方法［11－12］等，但这些方法都将海岸线看做是单纯的几何要素，算法以曲线几何特征保持为目标。然而，地图上的海岸线并非单纯的几何图形，它更是表达海岸地理特征形态的典型要素。海岸线通过弯曲、弯曲程度等多种形式表达海岸地形单元特征，如岸线陆地侧弯曲表达沙嘴、半岛等，岸线海侧弯曲表示海湾等，又如堆积型海岸线岸线平缓、侵蚀型海岸岸线曲折等。因此，海岸线的化简过程不仅是简单的几何变换过程，更是在分析空间地理现象规律性基础上的通过调用底层的几何操作算法实现空间信息概括的过程［13］。海岸线综合目标在于保持（或突出）区域的地理规律性特征。海岸线化简是面向地理特征的空间决策操作。

制定海岸线化简策略时不仅考虑岸线几何特征保持，更需要考虑岸线所处区域的地理环境特征，在地理特征分析基础上设计岸线化简方法，用地理规律知识验证化简算法的有效性，将地理知识与数学模型相结合，制定面向地理特征的岸线化简策略。

在众多类型的海岸线中，溺谷海岸线在特定的地貌环境下特定的地质作用下形成，曲线形态复杂，具有区别于其他类型海岸线的典型树枝类型特征，很具有代表性。故本研究将以溺谷海岸线化简为例探讨面向地理特征线化简算法的设计与实现。

2 面向地理特征的溺谷海岸线综合决策

2.1 面向岸线化简的地貌特征分析

溺谷海岸发育于古地质时代海滨的河谷地区，因海侵作用淹没河道而形成。古河口谷在海水侵蚀作用下形成多个河口。多条河口间存在明显分枝关系，主河口分枝为次级河口，次级河口分枝为下一级河口，直至不可再分枝的河口。

溺谷海岸线通过几何形态表达海岸地貌形态结构。溺谷海岸线最大几何特征是其树枝状结构［14］，这与岬湾海岸线岬角、海湾交互出现，冲积平原海岸线平直单调等其他类型海岸线几何特征不同。

溺谷海岸线表征河口源头、河口交叉处、入海口等地理单元。河口源头，是整个河口范围内高程最大点，水面窄，水体浅。河口交叉处为多河口的交汇处。入海口，整个溺谷海岸内树枝状水体与外部水体交界处，水面宽阔，深度大。河口从源头到交汇处（或入海口）水面逐步变宽。图1以标注方式表示了溺谷海岸河口A所包含的地理目标。

图1 溺谷海岸线表达的地理目标Fig.1 Geographic objects represented by ria coastline

2.2 地理特征约束

溺谷海岸线化简至少需要满足两类约束条件：① 图形表达约束，如最小弯曲尺寸、最小符号间隔等条件；② 为地理特征约束，这是面向地理特征地图综合的研究重点。

地理特征约束，由地图目标所处区域地理特征所决定，是面向地理特征地图综合概念在逻辑层次上地进一步深化。在对溺谷海岸地理特征分析基础上，将溺谷海岸线所表征的地理目标分为3个层次：整条海岸线所表达的整个树枝状河系，海岸线弯曲所表达的河口，单个坐标点所表达河口源头等地理特征点。溺谷海岸线化简地理约束条件对应地分为3类：

（1）保持溺谷海岸线树枝状特征。从河口间相互关系角度看，树枝状特征约束指保持相邻河口间交汇关系不变、化简后不出现“悬挂”河口。从分形几何角度看，溺谷海岸线，具有树枝状特点，是典型的分形曲线（统计意义的），岸线化简需顾及其分形特征的保持。

（2）保持河口从源头至入海口（或河口交汇处）宽度逐步变大的特征。

（3）保持重要的河口源头点。河口源头是溺谷海岸地区重要的地理特征点，也是保持岸线整体形态特征的重要“骨架点”，因此需要保留。

2.3 面向地理特征的综合操作

溺谷海岸线化简过程是删除次要细节形态特征、保持岸线主体形态特征的过程，综合结果要反应区域地理规律。从溺谷海岸地理特征分析结果可知树枝状特征是溺谷海岸线区别于其他类型海岸线的显著特征，河口是溺谷海岸线所表达的重要地理单元。河口一方面尺度变换后由于人眼视觉分辨率的限制次要河口不再可分辨，另一方面合理地删除次要河口后溺谷海岸线的树枝状主体形态特征仍可得到保持。因此，次要河口的删除是面向地理特征的溺谷海岸线化简操作。

次要河口的删除是地理层次上的溺谷海岸线化简操作，将地理层次上的溺谷海岸线化简操作转换为几何层次上坐标串操作需要解决两个问题：一是如何建立几何坐标串与河口间对应关系；二是如何量度河口的重要性，进而实现河口选取问题。这两个问题的解决有相当难度，一方面河口识别需要从地图认知角度以一定的数据模型为支撑结构解决；另外河口选取目标在于保持溺谷海岸线的树形特征和河口区域密度对比，这要求选取时不仅考虑河口本身特征（如长度、宽度等），同时顾及河口所处上下文环境（如河口间距、密度等）。

3 基于Delaunay三角网的河口层次树构建

溺谷海岸线最主要的地理特征是侵蚀层次性，岸线在几何分布上呈二维扩展，在总体结构上呈树枝状。识别出岸线具备这种树枝状特征是溺谷海岸线的化简的先决条件，树枝状特征的识别需要把二维面状分枝抽象为一维线性分枝，同时建立线性分枝间关联关系。将二维的面状分枝抽象为一维的线性分枝具有多种方法：垂线族法、数学形态学方法、Delaunay三角网方法等。在上述方法中利用Delaunay三角网提取骨架分方法得到图形效果较好［15］。这里将以Delaunay三角网为支撑结构提取溺谷海岸线的线性分枝，建立溺谷海岸线河口层次树结构，为进一步的溺谷海岸化简作准备。

溺谷海岸河口层次树结构的基本思路：以Delaunay三角网为工具，提取海岸线海洋一侧骨架线，骨架线呈树枝状分布，应用主流识别准则探测出各级河口骨架线建立其间层次关系，根据河口骨架线与河口弯曲间对应关系，反算各级河口弯曲间层次树结构。

3.1 构建约束Delaunay三角网

提取溺谷海岸线上点构成点集，为避免狭长三角形的出现，对局部线段相邻点距离过大的情况，采用文献［15］的方法进行加密。在点集合上以原始曲线为约束条件构建约束Delaunay三角网。溺谷海岸在海侵作用下形成，为分析海岸侵蚀形态，只考虑位于岸线海洋一侧的三角形。

三角形分类是后继操作骨架线提取和溺谷海岸空间分析的基础。文献［15］提出的分类方法是按照其拥有邻近的三角形个数分为Ⅰ、Ⅱ、Ⅲ类三角形，主要考虑了几何意义上的空间邻近特征，却忽视在特殊地理环境下三角形所隐含的地理含义。在上述研究基础上，从溺谷海岸空间表征的地理含义出发，将三角形分为如下4类：① 入海口三角形，与未铺设三角网的非封闭外部区域具有邻近关系的三角形；② 河口分叉三角形，非入海口三角形的Ⅲ类三角形；③ 源头三角形，非上述两类的I类三角形；④ 连接三角形，除上述3类之外的三角形。采用上述方法对三角形分类结果如图2所示。从结果可看出，该分类法有效揭示了溺谷海岸特定地理单元与三角形间的关联性。

图2 三角形分类图Fig.2 Triangle classification

3.2 提取骨架线网络

骨架线网络由网络节点和骨架线段组成。骨架线网络节点由入海口三角形、河口分叉三角形、源头三角形充当。骨架段连接不同的网络节点，骨架段的搜索过程即骨架线网络的构建过程。作为骨架段建立前的准备，首先根据三角形间相邻关系搜索连接相邻网络节点的三角形路径。在建立相邻节点的三角形路径基础上，利用骨架线变化提取骨架线段。按照相邻节点的不同，区分3类骨架线段，即入海口—分叉口间、分叉口—分叉口间、分叉口—源头骨架线段。使用文献［15］的方法提取3类骨架线段。在遍历全部网络相邻节点对后，完成骨架线建立，得到如图3所示网络结构。

图3 基于Delaunay三角网的骨架线提取Fig.3 Skeleton generation based on Delaunay triangulation

3.3 建立河口层次关系

上述步骤所构建的骨架线网络由骨架线段组成，呈树型分布，但骨架线段难以建立与河口实体间直接联系。因此可尝试将骨架线段网络组织成河口骨架线结构，类似将以基于河段的河系组织转化为基于河流的河系形式的过程。

最大长度准则或180°准则都可作河口骨架线探测原则。以最大长度准则为例，说明骨架线层次组织过程。首先，以骨架线网络根节点为起点，根据网络连接关系求出与根节点具有连接关系的多个源头点，计算源头点与根节点间路径长度，取路径最长者为1级河口骨架线；而后，以1级河口骨架线内包含的河口分叉点为起点，探测2级河口骨架线，以此类推，直至所有的骨架线段都被搜索过一遍。图4为使用上述方法建立的河口骨架线图，其中红色、蓝色、绿色、黄色分别为1、2、3、4级河口骨架线。

以河口骨架线为节点，河口骨架线间汇合关系为边，建立如图4（b）所示的河口骨架线树结构。这是描述河口实体层次关系的方法之一，直接利用海岸线弯曲（河口弯曲）树结构表达河口层次关系是另一种方法。河口弯曲多叉树的建立可使用如下方法：首先，探测河口骨架线对应的河口弯曲：计算河口骨架线根节点对应的河口分叉三角形，由骨架线与三角形的相交关系确定剖分边，剖分边划分的曲线段即对应河口弯曲，如同图4（a）中骨架线52－59－60对应的河口弯曲为2－7；而后，将河口弯曲定义为节点，将河口弯曲间的直接包含关系定义为边，建立如图4（c）所示河口弯曲多叉树结构。

图4（b）河口骨架线树图4（c）河口弯曲多叉树都可用来表示河口实体层次结构，两者网络结构相同，但树节点与河口实体的对应关系不一致：骨架线树中的骨架节点对应于河口主干，河口弯曲多叉树节点则对应于由河口主干及其汇入该河口上游河口组成的河口系。

图4 两种河口层次树结构Fig.4 Two kinds of hierarchical estuary tree structures

3.4 河口实体相关参数量算

在形式化表达河口实体层次关系基础上，计算河口实体相关参数，为后继溺谷海岸线的综合作准备。河口长度与宽度是最基本的两个参量。

（1）河口长度

对于任一河口r，其对应的河口主干骨架线记为skeleton（r），将河口长度定义为其主干骨架线长度，则河口长度len（r）计算公式为

（2）河口宽度

河口r对应的河口弯曲为bend（r），利用河口弯曲多叉树，提取河口弯曲bend（r）下一级弯曲bend（b1）、bend（b2）、…、bend（bn）。 河 口 弯 曲bend（r）由河口主干及下一级河口组成，则河口主干面积area（r）为

利用面积与长度反算宽度，则河口r主干平均宽度为

4 河口选取

河口选取是面向地理特征的溺谷海岸线综合实施过程中的重要一环，其基本要求为保留主要河口，保持河口树枝状分形特征。这里使用定额法实现河流选取，选取涉及两个子问题，一是河口的重要性如何量度，二是河口选取的数目如何确定。

河口重要性的测度需要考虑河口本身的特征，如等级、长度、宽度，同时兼顾河口所在地理环境上下文特征，如相邻河口间距。综合考虑多种因素对河口重要性的影响，设计一种复合指标表达河口重要性。复合指标定义为河口主干面积及各级支流面积之和，对于河口r，其各级子河口为childi（r），则复合指标comlex＿area为以河口r为主干的河口河系面积，即

一般而言，河口长度越大，其包含的子河口越多，复合面积越大，河口越重要。

以复合面积为选取指标，河口选取结果得到改善。首先，对任意河口复合面积必然大于其子河口复合面积，故综合结果不会出现河口悬空的现象。其次，顾及子河口复杂性对河口选取的影响。如图5（a）所示河口A、B宽度、长度相近，此时使用河口宽度、长度等选取指标已不能区分两者重要差别。但河口A包含子河口条数要多于河口B包含子河口条数，人工选取时会认为河口A比河口B重要，复合面积很好反应河口A、河口B间差异。

图5 河口选取Fig.5 Estuary selection

保持溺谷海岸线树枝特征从定量角度理解即保持岸线分维数不变。使用分形方法确定河口选取数目，基本思路为以分维数不变为约束条件确定综合后曲线长度，根据综合后曲线长度反推河口选取数目。首先以分维数不变为条件确定综合后岸线曲线长度。设综合前后比例尺分母分别为MA、MF，综合前后曲线长度分别为LMA、LMF，曲线分维数D，根据文献［16］综合后曲线长度LMF可使用如下公式确定

根据LMF计算需删除河口的数目。设溺谷海岸表达的河口数目为n，对此n个河口按复合面积从小到大排序。定义函数f（t）为删除第t（1≤t≤n）个河口后的岸线长度，f（t）单调递减。t从1到n循环，当f（ti）≤LMF时，停止循环，比较｜f（ti－1）－LMF｜与｜f（ti）－LMF｜，取较小者所对应的序号为需删除的河口数目。

5 试验与讨论

为验证本研究所提出溺谷海岸线化简算法的有效性，设计对比试验将本算法综合结果与Douglas－Peucker算法结果作比较。采用如图6所示典型溺谷海岸区域Chesapeake湾1∶10万图为试验数据（尺寸压缩至原图的50%）。采用系列比例尺综合结果图验证算法有效性，综合比例尺设定为1∶20万、1∶25万、1∶50万。图7展示了使用本研究算法生成1∶25万综合结果的步骤，包括Delaunay三角网构建（图7（a））、三角形分类（图7（b））、河口层次树的建立（图7（c）、（d））、河口剪枝（图7（e））等步骤。最终1∶25万化简结果如图7（e）所示。

图6 化简前溺谷海岸线数据（尺寸为原图的1／2）Fig.6 Ria coastline before generalization（size is 50%of original map）

图7 溺谷海岸线化简过程Fig.7 Generalization process of ria coastline

图8、图9为对比试验的结果。其中，图8是采用本研究算法所得综合结果，由于本研究算法具有高度曲线抖动敏感性，会探测出微小的溺谷河口弯曲，故在实现化简前，采用小阈值的Perkal算法对矢量点密集的海岸线进行光滑处理。图9采用顾及分形特征的 Douglas－Peucker算法［16］化简，通过设置合适压缩矢高，使得化简后曲线长度满足公式（5）。图8、图9中，在综合比例尺相同情况下，分别采用本研究算法与Douglas－Peucker算法所得到化简曲线（如图8（b）与图9（b））长度相近，两者间具有可比性。

图8 利用本文算法化简溺谷海岸线结果Fig.8 Generalization result generated by algorithm proposed in this study

图9 利用Douglas－Peucker算法化简溺谷海岸线结果Fig.9 Generalization result generated by Douglas－Peucker algorithm

综合结果的比较从几何层次的几何精度、拓扑一致性，地理层次的地理特征的保持，应用层次上的航海安全性3方面进行。首先，无论是本研究算法或Douglas－Peucker算法，随着综合比例尺逐渐变小，综合程度逐渐变大，几何位置精度逐渐下降。比较结果的拓扑一致性，发现本研究算法很好地保持结果自身拓扑关系的一致性，在各种综合比例尺下都不会发生自交情况，这是Douglas－Peucker算法所不具备的。本研究算法能保证结果的拓扑一致性与河口剪枝过程中建立的合理河口层次树结构密切相关。

从地理层次上看，本研究算法很好地保持了溺谷海岸线的地理形态特征。首先从定性角度看，使用本研究算法，各综合比例尺结果图很好保持了溺谷海岸线的树形结构特征，地理层次上的主要河口得到保留，河口个体保留了从源头到分叉处水体宽度逐步变大的特点。相反，Douglas－Peucker算法仅保持了几何特征点，丢失了河口树形层次结构、河口个体特征等重要地理特征信息，特别在综合程度较大的情况下，河口形态及组织结构已不能分辨。在定量方面使用分维数（盒维数）量度海岸线分形特征的保持。综合前分维值为1.414，使用本研究算法所得1∶20万、1∶25万、1∶50万结果分维值分别为1.370、1.425、1.417，与综合前岸线分维值相近，算法保持了岸线分形特征。

保证航海安全是海图岸线化简原则。本算法通过海洋侧弯曲剪枝实现岸线化简，化简后曲线始终保持在海洋一侧，保证了航海安全性。这是Douglas－Peucker算法无法保证的。

综合上述评价，本研究算法有效保持溺谷海岸线的树枝状结构特征，综合后河口层次结构、河口个体宽度渐变特征等溺谷海岸重要特征信息得以保留。另外，该算法能保持结果的拓扑一致性，符合制图美观性原则，能保证航海安全性。这些特点是传统的 Douglas－Peucker算法所不具备的。

6 结 论

本研究提出的溺谷岸线化简算法有以下特点：① 面向地理特征的地图综合，算法设计时，以区域地理特征的保持为目标，在分析溺谷海岸地理特征基础上制定化简策略，在算法评价时，以区域地理特征是否保持评判化简策略的优劣；② 几何模型与面向地理特征综合方法相结合，以Delaunay三角网为支撑几何构造通过三角形分类识别河口入海口、分叉处、源头等地理单元，通过建立河口骨架线模型表达溺谷海岸线树枝状地理特征，通过次要河口的删除实现岸线化简；③ 试验表明，算法在几何层次上能够保证化简后曲线自身拓扑关系的一致性，在地理层次能够保证河口层次性关系，在应用层次上保证航海安全性。

有待进一步研究的问题：各类型的海岸线化简策略，在制定合理的海岸线分类体系的基础上，以面向地理特征的地图综合方法为指导，将对溺谷海岸线化简方法的研究拓展到对各类型海岸线化简方法的研究；多种海岸地貌要素的协调综合问题，由目前单一要素的面向地理特征综合方法拓展到对多种地图要素的面向地理特征保持的协同综合。

［1］ DOUGLAS D H，PEUCKER T K.Algorithms for the Reduction of the Number of Points Required to Represent a Line or Its Caricature［J］.The Canadian Cartographer，1973，10（2）：112－122.

［2］ 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.（陈轶，彭认灿，郑义东，等.基于Douglas双侧多叉树的曲线综合算法研究［J］.测绘学报，2010，39（3）：310－315.）

［3］ SAALFELD A.Topologically Consistent Line Simplification with the Douglas－Peucker Algorithm［J］.Cartography and Geographic Information Science，1999，26（1）：7－18.

［4］ ZHANG L，TIAN Z.Refinement of Douglas－Peucker Algorithm to Move the Segments toward Only One Side［C］∥Proceedings of 18th International Cartographic Conference.Stockholm：ICA，1997.

［5］ VISVALINGAM M，WHYATT J D.Line Generalization by Repeated Elimination of Points［J］.The Cartographic Journal，1993，30（1）：46－51.

［6］ WU Fang，DENG Hongyan.Using Genetic Algorithms for Solving Problems in Automated Line Simplification［J］.Acta Geodaetica et Cartographica Sinica，2003，32（4）：349－355.（武芳，邓红艳.基于遗传算法的线要素自动化简模型［J］.测绘学报，2003，32（4）：349－355.）

［7］ ZHENG Chunyan，GUO Qingsheng，HU Huake.The Simplification Model of Linear Objects Based on Ant Colony Optimization Algorithm［J］.Acta Geodaetica et Cartographica Sinica，2011，40（5）：635－638.（郑春燕，郭庆胜，胡华科.基于蚁群优化算法的线状目标简化模型［J］.测绘学报，2011，40（5）：635－638.）

［8］ LI Z，OPENSHAW S.A Natural Principle for the Objective Generalization of Digital Maps［J］.Cartography and Geographic Information Science，1993，20（1）：19－29.

［9］ BURGHARD T D.Controlled Line Smoothing by Snakes［J］.Geoinformatica，2005，9（3）：237－252.

［10］ BALBOA J L G，LOPEZ F J A.Frequency Filtering of Linear Features by Means of Wavelets：A Method and an Example［J］.The Cartographic Journal，2000，37（1）：39－49.

［11］ 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.（艾廷华，郭仁忠，刘耀林.曲线弯曲深度层次结 构 的 二 叉 树 表 达 ［J］.测 绘 学 报，2001，30（4）：343－348.）

［12］ 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.（钱海忠，武芳，陈波，等.采用斜拉式弯曲划分的曲线化简方法［J］.测绘学报，2007，36（4）：443－449.）

［13］ QI Qingwen，LIU Yue.The Theory and Approaches of Geographic－feature Oriented Generalization in GIS Environment［J］.Acta Geographica Sinica，1998，53（4）：303－313.（齐清文，刘岳.GIS环境下面向地理特征的制图概括的理论和方法［J］.地理学报，1998，53（4）：303－313.）

［14］ SHEPARD F P.Revised Classification of Marine Shorelines［J］.The Journal of Geology，1937，45（6）：602－624.

［15］ AI Tinghua，GUO Renzhong.Extracting Centerlines and Building Street Network Based on Constrained Delaunay Triangulation［J］.Acta Geodaetica et Cartographica Sinica，2000，29（4）：348－354.（艾廷华，郭仁忠.基于约束 Delaunay结构的街道中轴线提取及网络模型建立［J］.测绘学报，2000，29（4）：348－354.）

［16］ WANG Qiao，WU Hehai.Research on the Fractal Analysis and Automatic Cartographic Generalization of Map Objects［M］.Wuhan：Wuhan Technical University of Surveying and Mapping Press，1998.（王桥，毋河海.地图信息的分形描述与自动综合研究［M］.武汉：武汉测绘科技大学出版社，1998.）

［17］ PENG W.Automated Generalization in GIS［D］.The Netherlands：Wageningen Agricultural University and ITC，1997.

［18］ LI Z.Digital Map Generalization at the Age of Enlightenment：A Review of the First Forty Years［J］.The Cartographic Journal，2007，44（1）：80－93.

［19］ SHI Wenzhong，CHEUNG Chuikwan.Performance Evaluation of Line Simplification Algorithms for Vector Generalization［J］.The Cartographic Journal，2006，43（1）：27－44.

［20］ JONES C B，BUNDY L，WARE J M.Map Generalization with a Triangulated Data Structure［J］.Cartography and Geographic Information System，1995，22（4）：317－331.