多条海岸线协同化简的层次化三角网分区法

张立华，唐露露，贾帅东，戴泽源

海军大连舰艇学院军事海洋与测绘系，辽宁 大连 116018

海岸线作为海图上一类重要的要素，其自动综合的研究一直受到人们的关注。与普通线要素化简不同，海岸线化简需要顾及“扩陆缩海”等特定原则，因此普通的线要素化简算法并不适用于海岸线化简[1-2]。

当前海岸线化简方法主要有双向缓冲区方法[3-8]和指标化简方法[9-22]两类。双向缓冲区方法利用其缩小或填平凹部的特性实现海岸线化简，但由于其基于固定半径的滚动圆进行变换，在一些瓶颈区域容易出现“潟湖沙嘴封死”、“岛礁上岸”、“海岸线相交”现象(如图1(a)、图1(b)、图1(c)所示，其中粗线条表示化简后的海岸线，较细的线条表示原始海岸线)；指标化简方法通常是采用弯曲识别方法(单调段识别方法[9-13]或Delaunay三角网法[14-22])对弯曲进行识别，并以海岸线弯曲的高度(最大垂距)、深度、面积、宽度及骨架线长度等作为化简的指标，对弯曲进行取舍以达到化简的目的，这类方法可避免上述“潟湖沙嘴封死”、“岛礁上岸”的现象。但由于其针对单一海岸线进行处理，在弯曲进行取舍时，对其与附近海岸线之间的空间关系考虑不足，仍避免不了“海岸线相交”现象(如图1(d)所示)，且上述两类方法对于一些不同海岸线之间相对较为狭窄的海峡区域(如图1(e)所示)，当比例尺缩小以后，不能有效处理邻近距离较小的问题，容易出现“海岸线相接”的视觉性错误。

图1 常见海岸线化简图理性问题Fig.1 The diagrammatic sketch of frequent faults

考虑到当前海岸线化简方法基本只考虑单一线要素，未顾及其与周围海岸线之间的空间邻近关系，在海岸线较为密集的复杂海区容易出现图理性错误，本文提出一种顾及空间邻近关系的多条海岸线协同化简方法。

1 基于层次化三角网分区的多海岸线协同化简

1.1 现有方法问题产生根源及解决思路

从现有方法的缺陷来看，主要是不能有效顾及化简海岸线与周围海岸线之间的空间邻近关系。Delaunay三角网作为空间分析的重要工具，已被证明具有探测要素间空间邻近关系的潜能[23-25]，且已有文献将Delaunay三角网用于海岸线化简，但这些方法均只对某单一海岸线单独构网并对其进行化简，并未顾及海岸线之间的空间邻近关系，这样易出现海岸线相交的图理性错误，如图2(a)所示，对海岸线L1上的数据点构建约束Delaunay三角网，取其海部三角形，并将其中的黄色多边形w1所包含海岸线弧段视为弯曲，根据三角形可视判别条件(根据三角形是否位于视觉缓冲区内[16]或该三角形区域宽度是否大于阈值[22])，将其中红色线条所示区域的三角形进行删除，在这一过程中并未对海岸线L1与L2的邻近关系进行考虑和处理，从而导致了海岸线相交的图理性错误，如图2(b)所示。为了有效处理好海岸线之间的空间邻近关系，本文将多条海岸线上的点同时参与构网，并将可能产生图理性错误的区域自动识别出来。如图2(c)所示，根据三角形所邻近的海岸线数目，可将其分为单一海岸线三角形(如三角形T1，该三角形的顶点A、B、C均为海岸线上L1的点)、非单一海岸线三角形(如三角形T2，该三角形的顶点D为海岸线L1上的点，顶点E、F为海岸线L2上的点)，并将非单一海岸线三角形均设置为不可删除的三角形，那么当再次利用视觉约束条件对海岸线进行化简时，则只会对图中的单一海岸线三角形(图2(c)中黄色多边形区域所示三角形)进行化简，不会出现图2(b)所示的海岸线相交的错误。

图2 本文方法与现有方法过程比对Fig.2 Comparison between the method and the literature method

为了将这一思想应用于多海岸线的协同化简，本文首先利用约束Delaunay三角网对能否化简的区域进行划分和标识；然后，利用二叉树构建层次关系模型，对各区域实体进行有序的组织；最后，有序地对可化简的标识区域进行渐进式化简，并对局部狭窄区域进行自适应夸大，从而实现多海岸线的协同化简，其主要流程如图3所示。

图3 基于层次化三角网分区的多条海岸线协同化简方法Fig.3 Multiple coastline collaborative simplification methods based on hierarchical triangulation

1.2 约束Delaunay三角网构建

本文首先采用文献[24]所述方法对海岸线的数据点进行加密处理，之后构建约束Delaunay三角网，并根据重心点坐标提取位于海部的三角形。对于一种相对较为特殊的情形，如图4所示，根据文中所述三角形划分方法，可将这一区域的三角形分为单一海岸线三角形(图中褐色多边形A、B所含三角形，绿色多边形D所含三角形,紫色多边形E所含三角形)和非单一海岸线三角形(图中黄色多边形C所含三角形)。根据之前的分析，只针对单一海岸线三角形区域进行化简，但对于如图4所示区域而言，若对单一海岸线三角形区域D、E删除，而其中的非单一海岸线三角形区域C进行保留，则会出现不合理的“内陆湖”现象。所以在上述区域中，真正可化简的区域仅有A、B。通过上述分析，可以知道，对于相对较为复杂的区域而言，真正可化简的区域为弯曲支路上不含岛屿的弯曲(即在该弯曲支路上不存在岛屿，如图中区域B)和支路末端的单一海岸线三角形区域(如图中区域A)。为对这一区域进行有效识别并进行化简操作，就必须对这些三角形所组成的各区域进行系统组织，并有序建立各区域之间的层次关系。

借鉴文献[24]所述三角形分类方法，再将其分为Ⅰ类、Ⅱ类、Ⅲ类、Ⅳ类三角形，以用于层次模型的构建。如图4所示，将这些Ⅰ类、Ⅱ类、Ⅲ类、Ⅳ类三角形分别填充为红色、白色、蓝色、黄色。其中Ⅰ类三角形主要分布在峡湾末端，也称为源头三角形；Ⅲ类三角形主要分布在岔路口；Ⅳ类三角形主要分布在岸线的边界处，称为边界三角形；而Ⅱ类三角形则主要是对上述这些三角形进行连接。

图4 多海岸线约束Delaunay三角网Fig.4 Multiple coastline Delaunay triangle network diagram

需要说明的是，为便于之后化简，本文将未闭合的单一海岸线，与海图图廓一起形成闭合的陆地多边形。

为了便于后续处理过程中对岸线自身弯曲以及多海岸线之间关系的表达，对三角形建立如下数据结构：

struct TRIANGLE

{

int ID; ∥三角形序号

int Type; ∥三角形类型

int NumberVertex[3]; ∥三角形顶点序号

int belong_to[3]; ∥三角形顶点所属海岸线编号

int neighbor[3]; ∥三角形的邻近三角形编号

point Gpt; ∥三角形重心点坐标

bool Mark; ∥标记，用于构建结构化层次关系模型，初始值为“假”

}

1.3 带悬挂节点的层次关系模型建立

由上文的分析可知，约束Delaunay三角网可对其不可化简区域进行识别，但对一些复杂区域(图4)，单一海岸线三角形区域与非单一海岸线三角形区域相间、交错分布，可化简区域不易自动识别，因此，本文采用二叉树模型对这些区域进行系统组织，利用节点与节点之间的父子和兄弟关系表达区域之间邻近关系，以对其中的可化简区域进行识别。需要说明的是，在构建过程中，始终以左子节点为“主子节点”，即在两子节点产生冲突时，优先顾及左子节点。本文所述层次关系模型构建步骤如下：

(1) 获取标记为“假”的边界三角形作为二叉树的根三角形，将其放入当前根节点进行存储，并将该三角形标记设置为“真”，转步骤(2)，若所有的边界三角形均标记为“真”，则模型构建完毕。

(2) 由当前节点的当前三角形出发，根据三角形之间的邻近关系搜索附近的三角形，若该邻近三角形为Ⅱ类三角形，则将该Ⅱ类三角形放入当前节点进行存储，并将其标记为“真”，之后继续寻找“新标记”三角形附近的三角形，直到该邻近三角形为I类三角形、已标记为“真”的三角形、Ⅲ类三角形、边界三角形时停止，若为I类三角形、已标记为“真”的三角形时，则转步骤(3)，若为Ⅲ类三角形、边界三角形，则转步骤(4)。

(3) 由该当前节点向上层节点回溯遍历，寻找是否存在未设置的节点。首先寻找当前节点的兄弟节点是否设置完毕，若未设置则将该节点设为当前节点转步骤(2)，若设置完毕，则向上继续判断父节点的兄弟节点，逐渐向上层追溯，直到该二叉树的所有节点均设置完成后，转步骤(1)。

(4) 为当前节点设置子节点，并将步骤(2)中搜索到的Ⅲ类三角形或边界三角形放入当前节点和两子节点进行存储，将其中的左子节点设置为当前节点，转步骤(2)。

基于上述模型，可将多条海岸线分区域分层次系统存储，每一节点均为某一待处理的区域。对于上述二叉树模型，具有以下特点：

(1) 除悬挂节点外，层次二叉树中的每一节点均代表了图中某一待处理区域，且节点与区域一一对应，这些节点所表示的区域，相互独立，互不影响。

(2) 对于表达可化简区域的节点，其存储的最后一个三角形为Ⅰ类三角形，且该节点不存在子节点。

图6 两种特殊类型的层次二叉树模型构建Fig.6 The construction of two special types of hierarchical binary tree model

1.4 顾及空间邻近关系的多海岸线协同化简

1.4.1 基本过程步骤

根据层次二叉树模型的特点可知，在层次关系模型中，节点与待处理区域一一对应，而可进行化简的区域则主要集中于层次树模型的末端海岸线自身弯曲部分，且这些节点的最后一个三角形为Ⅰ类三角形。本文首先利用这一特性将表达可化简区域节点进行识别并化简，之后对图中全体较为狭窄区域进行自适应夸大。其具体步骤如下：

(1) 输入海岸线数据，并根据文中所述方法构建结构化层次关系模型，获取集合Δend={node|(Typenode_endtri=1)∩(belong_tonode_endtri[0]=belong_tonode_endtri[1]=belong_tonode_endtri[2])}(其中，Typenode_endtri表示节点的末端三角形类型，belong_tonode_endtri表示节点末端三角形顶点所属海岸线编号，Δend描述的是所有末端三角形为Ⅰ类三角形且该三角形顶点属于同一海岸线的节点集合)。

(2) 遍历集合Δend，根据式(1)计算节点的面积

(1)

式中，SΔi表示节点中第i个三角形的面积，n表示该节点中三角形的数目；由于末端节点是从Ⅲ类三角形开始，到 Ⅰ 类三角形结束，但该Ⅲ类三角形不属于海岸线自身弯曲的一部分，因此该求和公式从第2个三角形开始，但该节点的第1个三角形为其他类型的三角形，那么上述求和公式从1开始。

若弯曲面积S

(3) 遍历集合Δend中所有节点三角形，判断是否存在标记为“待删除”的三角形，若有，将其中所有标记为“待删除”的三角形区域进行填充删除，更新海岸线数据，转步骤(1)，反之，转步骤(4)。

(4) 遍历模型中全体节点，对其进行局部自适应夸大操作。

1.4.2 可化简弯曲部分删除

对于那些面积相对较大，不足删除条件的节点，需要考虑部分删除操作。其具体过程为首先从节点的源头三角形(该节点的末端三角形)向上进行回溯，逐一获取其宽度Ltri，并进行判断Ltri

本文将三角形的宽度作如下定义：如图7所示，对于Ⅰ类三角形，将其与邻接三角形的公共边(p0p1)长度作为三角形的宽度，将Ⅱ类三角形中与海岸线重合的边和其相对顶点之间的最短距离作为该三角形的宽度(Δp3p4p5为支路节点上的Ⅱ类三角形，其中边p4p5为海岸线上的线段，将点p3到线段p4p5的最短距离[26]定义为该三角形的宽度)，Ⅲ类三角形不予求取三角形宽度。Ld为宽度阈值。

1.4.3 顾及空间关系的局部自适应夸大

为了对各节点区域中的部分较为狭窄区域进行夸大，针对单一节点，采用如下操作进行处理：

(1) 由节点数据提取节点三角形如图8(b)所示，遍历节点中的三角形，获取各三角形宽度Ltri，并判断其中是否存在三角形满足Ltri

(2) 将该节点的所有三角形进行“合并”，得到节点多边形plydeal，遍历节点三角形，将则将其中满足条件(Ltri

(3) 根据拓宽后的节点多边形plydeal(如图8(c)所示)，将海岸线上较为狭窄的部分采用节点多边形边界进行替代(如图8(d)所示)，即得到最终夸大以后的海岸线(在这一过程，为防止夸大操作使得原有海岸线形态发生较大变化，作以下判断，若经夸大以后陆地变化区域(图8(d)中的Δ1和Δ2)面积占原有陆地面积的比值大于1/4，则放弃这一海岸线的夸大操作)。

需要说明的是，本文虽主要针对海岸线要素进行化简，但若海岸线周围存在点状岛屿，也可将其视为一类特殊的海岸线进行存储，同样参与构网，并建立层次关系模型。这样做的优势在于，在之后的化简过程中，不会出现“点岛上岸”的错误，同时在局部夸大时，若该点状岛屿与海岸线距离较近，此时只夸大海岸线一侧，对点状岛屿不作处理。

图8 局部自适应夸大过程Fig.8 Schematic diagram of local adaptive exaggeration process

2 试验与分析

为对本文方法的有效性及适用性进行评估，本文将双向缓冲区方法以及文献[16]所提河口湾化简方法作为比对算法。参照文献[16]的研究，本文设置面积阈值Sd为0.003 2 cm2，设置曲线宽度为0.01 cm，根据人眼最小识别距离0.02 cm，将视觉宽度阈值Ld设为人眼最小识别距离与曲线线划宽度的和(0.03 cm)。对于综合结果的评估包括定性及定量两方面，试验海区包括潟湖海岸线和河口湾海岸线，其中潟湖海岸线取自海图编号16100，河口湾海岸线取自海图编号16700，原始比例尺为1∶25万。双向缓冲区的宽度设置为0.015 cm，河口湾方法与本文方法的基本参数设置相同。利用C++以及动态库GDAL2.2.0编程实现，并利用ArcGIS进行结果显示，以完成本文试验。

需要说明的是，根据海图制图综合的一般原则，应当先选取，之后再进行岸线的化简，但由于本文的研究重点在于海岸线的化简，对于岛屿要素的选取不作为本文研究重点。考虑到实际应用，在本文的所有实验中，按分界尺度进行选取，即对于面积小于0.5 mm2的岛屿直接进行删除，对剩余的岸线进行化简。

2.1 定性评估

分别将试验海图化简至1∶50万、1∶75万、1∶100万、1∶125万。潟湖海岸线在双向缓冲区、河口湾化简方法、本文方法的综合效果图分别展示如图9、图10、图11所示，并对其中的局部细节部分进行放大显示。河口湾海岸线在上述3种方法下的综合效果图分别展示如图12、图13、图14所示，并对局部细节进行放大显示。以下图像由于文章篇幅限制，均未按实际比例尺绘制，在图中，为方便对化简方法的化简效果进行展示，本文将化简前后的海岸线同时在文中进行绘出，蓝色线条为化简过后的海岸线，而黑色线条则为原始海岸线。

2.1.1 试验1：潟湖区域

对本试验海区而言，最主要的特征是潟湖海岸，对于这一区域的评估主要包括以下几个方面：

(1) 潟湖沙嘴是否予以保留，若不易识别时，是否予以适当夸大。

(2) 对于潟湖中相对较为尖锐且不可视的弯曲是否予以删除，且其曲线是否平滑。

图9 双向缓冲区化简效果Fig.9 Bidirectional buffer comprehensive rendering

图10 河口湾化简方法化简效果Fig.10 Comprehensive effect map of the comprehensive method of the estuary

图11 本文方法化简效果Fig.11 The comprehensive effect diagram of this method

图12 双向缓冲区方法化简效果Fig.12 Bidirectional buffer comprehensive rendering

图13 河口湾化简方法化简效果Fig.13 Comprehensive effect map of the comprehensive method of the estuary

图14 本文方法化简效果Fig.14 The comprehensive effect diagram of this method

(3) 对于其中不可合并的岛屿，当其距离较近时，是否予以适当夸大。

(4) 是否出现自相交、岸线相交等图理性错误。

对上述4个方面的综合效果情况统计如表1所示。

表1 潟湖区域化简效果统计

需要说明的是，在图中圆圈1所示区域的尖锐弯曲，文献[16]所述河口湾化简方法，在对弯曲进行识别时，需要其骨架线长度大于平均宽度的2倍，才被认为是条带状弯曲，并进行部分删除操作。而上述弯曲明显不能达到上述条件，因而被认为是普通弯曲，但该弯曲面积始终达不到删除的阈值，因而始终进行了保留，本文对这一处理进行了改进，对全体面积大于阈值的弯曲进行了部分删除操作，使之更符合化简的需求，从结果来看，本文方法取得了较好的效果。

2.1.2 试验2：河口湾区域

本次试验区域为典型的河口湾海岸，对于这一区域的评估主要包含以下方面内容：

(1) 对图中较为尖锐且不可视的弯曲进行删除。

(2) 对于其中相对较为狭窄的区域是否予以适当夸大拓宽。

(3) 对于当出现不同岛屿以及岸线距离相近时，是否予以适当的夸大拓宽。

(4) 是否出现自相交或不同海岸线相交的现象。

对于上述几个方面的评估情况统计如表2所示。

综上所述，双向缓冲区方法可以得到较为平滑的曲线，但由于其自身算法原理的限制，使得其在综合部分潟湖区域，以及出现狭长弯曲的河谷区域时，容易综合尺度过大，且没有夸大操作；而河口湾综合方法，主要用于解决单一河口湾海岸线的化简问题，在河口湾的化简效果较好，但对于部分不为条带状的弯曲，难以进行有效化简，其化简的曲线平滑性不够。综合来看，本文方法则取得较好的综合效果。

表2 河口湾区域综合效果统计

2.2 位置精度评估

为了对各算法的综合效果进行更加科学性的定量评估，将文中所述不同方法综合结果的平均位置偏移量进行统计，其统计数据如表3、表4所示。由于位置偏移的数值一般十分微小，因此，在这里将其统一换算到实地距离(单位为cm)，以方便比对。

表3 各方法效果位置精度统计(潟湖区域)

表4 各方法效果位置精度统计(河口湾区域)

由上述两表可以看出，双向缓冲区方法的正向位置偏移量较大，特别是在表3中，在比例尺小于1∶100万后，其位置偏移量超出其他2种方法两个数量级；本文方法与河口湾化简方法相比，其正向和负向偏移量都大于河口湾化简方法。

单独从表3、表4来看，本文方法相比于河口湾化简方法，其位置偏移量较大。出现这一现象的主要原因在于：一方面，对于正向偏移而言，其正向的位置精度主要体现在化简后海岸线在原始海岸线的基础上向海部方向的偏移量，在本文方法中，对全体弯曲的不可视部分进行了适当地部分删除操作，而河口湾方法则只针对其中的“条带状弯曲”进行了部分删除操作，从而显得本文方法的正向偏移较大；另一方面，负向偏移量主要体现在夸大方面，对于一些“瓶颈”区域或者不同海岸线相距较近区域，对于这一部分，一般需要制图作业员对其进行适当地夸大，从而防止出现视觉性错误，而河口湾方法不是一种顾及多条海岸线间协调关系的方法，因而对于不同海岸线相距较近的区域未进行处理，而本文方法则对这一部分进行了夸大操作，从而使得在精度评估时，本文方法负向偏移量较大。由于上述两方面的原因，从而显得本文的偏移量较大。但本文这样做的目的是使得化简结果更加贴近实际作业，提高化简质量，减少化简过程中出现的图理性错误。

3 结 论

通过分析、计算及试验比对，得出如下结论：

(1) 相比于双向缓冲区方法，本文方法在化简精度上有较大提高，且有效克服了其在瓶颈区域化简尺度过大的问题；相比于河口湾化简方法，对于一些面积较大且宽度变化较大的非条带状弯曲，本文方法化简效果更好。

(2) 相较于以上两种海岸线化简方法，本文充分顾及了复杂海区，多岛屿、多海岸线条件下的不同海岸线之间的空间邻近关系，有效解决了可能出现的图理性问题，海岸线的化简质量有了明显的提高。

当然，任何方法都有其适用范围，本文只是考虑了复杂海区，多岛屿、多海岸线条件下，各海岸线之间协调处理问题，但对于一些变化剧烈且存在大量河流支流的入海口区域自动综合，这里还未涉及，这些问题有待进一步研究。