岛屿作为海图上一类重要的地理要素，通常以点状要素或面状要素的形式在海图上大量存在，其制图综合的优劣程度直接影响到最终海图的质量。长期以来，岛屿综合通常由制图作业人员根据规范^[1]要求，结合自身经验，采用手工方式来完成^[2]。这种手工作业方式效率低下，特别是对于某些复杂的岛礁区（如我国舟山海域、西沙群岛海域等），会极大地降低作业效率；另一方面，手工选取的效果在很大程度上取决于制图人员的业务水平和工作态度。

近年来，随着计算机制图技术的不断发展，有学者开始探索岛屿的自动综合算法^[3-11]，并取得一定突破。当前对于岛屿自动综合的研究主要集中于两个方面。一是基于点群综合思想，在利用Voronoi图对岛屿密集程度进行评估的基础上，优先删除密度最大的内部岛屿，并对边界岛屿借鉴曲线化简的原理进行取舍，实现了岛屿的自动选取^[3-6]；二是尝试使用各种模型^[8-11]对岛屿群的分布模式进行识别，试图对影响岛屿分布模式的重点岛屿进行保留，以达到选取的目的，其中文献[7-8]基于上述思想，以Delaunay三角网和最小生成树为工具，对岛屿群的重点骨架岛屿进行识别；同时，对剩余的岛屿，采用岛屿群空间等剖分结构（类似于多边形的Voronoi图）对密度较大的岛屿进行识别并删除。

以上这些算法大多是在利用Voronoi图对岛屿的密集程度进行量化评估的基础上，优先对分布较为密集区域的岛屿进行综合，以达到选取的目的。但经过笔者研究发现，使用Voronoi图在某些特殊区域并不能对要素的密集程度进行有效描述，从而导致选取结果难以满足实际的生产需求，制约了海图自动综合的研究。如何对要素的密集程度进行有效的评估，并在评估的基础上对岛屿要素进行有效综合，具有重要的理论价值与现实意义。因此，本文提出一种基于缓冲区生长模型的岛屿选取构想，采用缓冲区生长模型对岛屿的影响范围进行评估，优先删除影响范围最小的岛屿，并对剩下的岛屿重新构建缓冲区生长模型，以达到对岛屿影响范围进行实时检测的目的，并不断重复此过程，直至达到选取的指标，停止选取，输出选取结果。基于这一构想，本文设计了缓冲区生长模型构建算法以及岛屿自动选取机制，以对岛屿进行有效的选取。

1 缓冲区生长模型与Voronoi图表达空间数据的影响范围 1.1 Voronoi图表达空间数据影响范围的缺陷

不少学者采用Voronoi图表达空间中的群点要素的密集程度（图 1），这是由于Voronoi图中多边形元恰好表达了其所包含点的生成空间^{[4, 12]}, 其中任意一点p_i的密度定义为：

$\rho = 1/A\left( {V\left( {{p_i}} \right)} \right)$

(1)

式中，A(V(p_i))为点p_i所对应的Voronoi多边形元的面积^[4]。

根据制图综合的一般原则，在比例尺缩小后，应当优先对其中较为密集的点进行综合，即应当优先删除图 1（a）中p₁、p₂、p₃中的两个。但若采用上述方法对要素的密度进行定义，由图 1（b）可以看出，p₁、p₂、p₃三点的密度与点a₀相比更小，当采用优先删除密度较大点的原则进行综合时，会优先删除a₀而保留p₁、p₂、p₃，这与实际的制图综合原则相违背。

1.2 缓冲区生长模型表达空间数据影响范围的有效性分析

为了有效解决§1.1中所述的利用Voronoi图表达空间数据的影响范围的缺陷，本文提出了缓冲区生长模型，其构造过程如下。

如图 2所示，对于空间点要素c，其中|p₁p₂|=2r，|p₁p₃|=2.5r，对其分别设置缓冲区（如图 2（b）所示），其缓冲区宽度为w，并使w逐渐增大；当缓冲区宽度w增大到r时（如图 2（c）所示），p₁、p₂的缓冲区相切，此时需要将这两个岛屿的缓冲区固定，不再变化；并在此基础上，使缓冲区宽度w继续增大，但此时只增大p₃的缓冲区，直到其缓冲区与p₁的缓冲区相切（如图 2（d）所示）；至此，缓冲区生长模型构建完毕。以此时的缓冲区大小表示空间要素的影响范围^[13-14]（如图 1（c）所示）。

根据图 2（d），将缓冲区相切模型中的空间元素的密度定义为：

$\rho = S/A\left( {V\left( {{p_i}} \right)} \right)$

(2)

式中，A(V(p_i))为元素p_i所对应的缓冲区的面积；S为其中元素p_i的面积，若为点状要素，则将其设置为1。

从图 1（c）中可以看出，当采用缓冲区生长模型对空间数据的影响范围进行表达时，点p₁、p₂、p₃三点相比于图 1（b）更容易识别，不会出现§1.1中所述的现象。

同理，对于空间中的面状要素，可采用与点状要素相类似的方法，先设置初始缓冲区，并不断扩大缓冲区，直到该要素缓冲区与其他要素的缓冲区相切为止。需要指出的是，采用上述模型可以对空间点密度进行衡量，但在岛屿综合时，为了使面积较大的岛屿在选取时具有优势，在实际选取时，不利用密度公式（2）计算岛屿密度，而仅考虑其缓冲区面积的大小。

采用这种模型对海图上岛屿的影响范围进行描述时，有如下特性：岛屿的面积越大，在模型中影响范围也就越大；岛屿越孤立，则在模型中其影响范围相对越大，反之，越密集，其影响范围相对越小。

这些特性与岛屿制图综合基本原则中优先选取保留面积较大、位置较为孤立岛屿的要求相吻合，能够对这些重要的、需要优先选取的岛屿进行有效识别，具有应用于岛屿选取的可能性。

2 缓冲区动态生长模型构建方法

根据缓冲区生长模型的定义及特点可知，构建缓冲区生长模型的关键点在于相切时各岛屿缓冲区宽度的求取。

本文在模型构建的过程中用到了各岛屿之间的距离、岛屿的缓冲区宽度以及该宽度是否固定、相切的判断、增长的缓冲区宽度值w等概念。为了对这些概念进行有效的描述以及方便计算，本文定义了距离矩阵、岛屿缓冲区标识、各岛屿缓冲区宽度矩阵、增长因子等概念，下面对这些概念进行详细说明，并对其赋予初始值。

2.1 相关概念

1）距离矩阵

求取各岛屿与其他所有岛屿之间的最小距离，并将其放在距离矩阵S中：

$\mathit{\boldsymbol{S}} = \left[ {\begin{array}{*{20}{c}} {{s_{00}}}& \cdots &{{s_{0n}}}\\ \vdots &{}& \vdots \\ {{s_{n0}}}& \cdots &{{s_{nn}}} \end{array}} \right]$

(3)

以元素s_ij为例，s_ij表示岛屿i与岛屿j之间的最小距离。为计算方便，将距离矩阵S对角线上的元素值设置为DBL_MAX（浮点型数值的最大值）。

2）岛屿缓冲区标识

本文对岛屿的缓冲区宽度以及宽度是否可以更改进行标识存储，定义为SYM：

$\mathit{\boldsymbol{SYM}} = \left[ {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {{\rm{sym}}\_{\rm{c}}{{\rm{h}}_0}}& \cdots &{{\rm{sym}}\_{\rm{c}}{{\rm{h}}_n}}\\ {{d_0}}& \cdots &{{d_n}} \end{array}}\\ {\begin{array}{*{20}{c}} {{\rm{sym}}\_{\rm{el}}{{\rm{e}}_0}}& \ldots &{{\rm{sym}}\_{\rm{el}}{{\rm{e}}_n}} \end{array}} \end{array}} \right]$

(4)

式中，sym_ch_i用于标识第i个岛屿的缓冲区宽度是否可更改；d_i表示第i个岛屿的缓冲区宽度，在初始状态时，将宽度是否可更改标识全部设置为可更改，将全部岛屿的缓冲区宽度设置为0；sym_ele_i表示第i个岛屿的属性，对面状岛屿、点状岛屿分别设置不同的值。

3）岛屿缓冲区宽度矩阵

为了之后对相切判断的方便，设置两个宽度矩阵，分别为行主导矩阵、列主导矩阵：

${\mathit{\boldsymbol{D}}_{{\rm{row}}}} = \left[ {\begin{array}{*{20}{c}} {{d_0}}& \cdots &{{d_0}}\\ \vdots &{}& \vdots \\ {{d_n}}& \cdots &{{d_n}} \end{array}} \right]$

(5)

${\mathit{\boldsymbol{D}}_{{\rm{col}}}} = \left[ {\begin{array}{*{20}{c}} {{d_0}}& \cdots &{{d_n}}\\ \vdots &{}& \vdots \\ {{d_0}}& \cdots &{{d_n}} \end{array}} \right]$

(6)

式中，行主导矩阵D_row的任意一行的所有元素相同，如第i行中的值均为d_i，d_i为SYM中第i个岛屿的缓冲区宽度。同理，对于列主导矩阵而言，其任意一列的所有元素均相同，其值为第i个岛屿的缓冲区宽度。

4）缓冲区宽度增长因子

由于在之前的设计中，需要使岛屿的影响域宽度不断地增大，因此本文设置了一个增长因子w，使w以一定的速率逐渐增大，其初始值设置为0。在模型中，若w增长过慢，会导致算法效率变慢，因此，本文将其每次增长的步长设为岛屿间的平均距离。

5）拓扑关系表

在之后的设计中，需要对岛屿之间的相互关系进行描述，以便对模型进行更新。因此，本文设计一个n维数组，对缓冲区生长模型中岛屿缓冲区相切的信息进行记录。

2.2模型构建方法

求取相切时各岛屿的缓冲区宽度步骤如下：

1）为SYM、D_row、D_col赋值。其过程为：使增长因子sym_ch增大，获取全部SYM中sym_ch设置为可更改的岛屿，将这些岛屿的缓冲区宽度d设置为w；将宽度矩阵中的行主导矩阵D_row每一行的值都设置为SYM中的对应岛屿缓冲区宽度值，例如，取行主导矩阵D_row的第i行的全部元素，记为D_row(i)，令D_row(i)=d（i其中d_i为SYM中第i个岛屿的缓冲区宽度），对于列主导矩阵D_col，其赋值过程与行主导矩阵类似。

2）判断当前缓冲区宽度下，是否有岛屿的缓冲区相交。利用步骤1）设置好的D_row、D_col进行矩阵运算S-D_row-D_col，其结果矩阵记为S_res（在此结果矩阵中，任意一元素S_res(i，j)表达了在当前所述的岛屿缓冲区宽度下岛屿i与岛屿j缓冲区之间的最小距离）。遍历结果矩阵S_res，获取其中最小的元素S_res(row，col)，并判断S_res(row，col)是否 > 0，若是，则表明在当前缓冲区宽度下，各岛屿的缓冲区没有相切或相交，返回步骤1）；若 < 0，则表明在此缓冲区宽度下岛屿row与岛屿col的缓冲区相交，此时将row和col进行记录，进入步骤3）；若等于0，此时无法判断是否是已经完成宽度求取的两岛屿缓冲区，转入步骤1）。

3）为出现相交的岛屿缓冲区设置最终的宽度值，并对增长因子重新赋值。利用步骤2）获取的row、col获取这两个岛屿的相关信息，即第row个岛屿与第col个岛屿之间的最小距离s_rowcol、岛屿缓冲区标识SYM中的sym_ch_row、sym_ch_col、sym_ele_row、sym_ele_col；针对不同的sym_ch_row、sym_ch_col，分以下3种情况对增长因子w和SYM中的岛屿缓冲区宽度d进行赋值：

① 当sym_ch_row、sym_ch_col均标识为可更改时，增长因子为：

$w = \frac{{{s_{{\rm{rowcol}}}}}}{2}$

(7)

岛屿缓冲区宽度为：

$\left\{ {\begin{array}{*{20}{c}} {{d_{{\rm{row}}}} = w}\\ {{d_{{\rm{col}}}} = w} \end{array}} \right.$

(8)

并将sym_ch_row、sym_ch_col设置为不可更改。

② 当sym_ch_row标识为可更改，sym_ch_col标识为不可更改时，增长因子为：

$w = {s_{{\rm{rowcol}}}} - {d_{{\rm{col}}}}$

(9)

岛屿缓冲区宽度为：

${d_{{\rm{row}}}} = w$

(10)

并将sym_ch_row设置为不可更改。

③ 当sym_ch_row标识为不可更改、sym_ch_col标识为可更改时，该情形与情况②中所述类似，此处不再赘述。

赋值结束后，在拓扑表中将岛屿row与岛屿col的缓冲区相切的信息进行记录，之后转到步骤4）。

4）判断最终的岛屿缓冲区宽度是否设置完毕。遍历岛屿缓冲区标识SYM，判断sym_ch是否均为不可更改，若是, 则设置完毕，进入步骤5）；否则转到步骤1）。

5）构建缓冲区生长模型中各岛屿的缓冲区。利用前述步骤生成的SYM中的各岛屿缓冲区宽度，求取岛屿的缓冲区，输出结果，模型构建完成。

3 缓冲区生长模型在岛屿自动选取中的应用

海图制图综合中，选取要素的目的是解决海图内容详细性与清晰易读性之间的矛盾，是选择保留更为重要的、有用的、相互联系紧密的制图物体，舍去那些相对来说次要的、无用的物体^{[2, 15-16]}。为此，本文采用上述缓冲区生长模型对岛屿的影响范围进行评估，优先删除缓冲区面积最小的要素，并对模型进行实时更新维护，直到达到选取指标，输出选取结果。其具体步骤如下。

1）输入岛屿群数据，并按比例尺缩放到对应比例尺，对缩小后不足表示尺度的岛屿用点状岛屿表示。如图 3（a）所示，将岛屿I₁、I₂、I₃、I₄、I₅、I₆、I₇按比例尺缩小到目标比例尺，其中岛屿I₁、I₂、I₃、I₄、I₅不足表示尺度，用点状岛屿表示。

2）根据§2所述缓冲区生长模型构建方法构建缓冲区生长模型，如图 3（b）所示。

3）删除模型中缓冲区面积最小的岛屿并重新构建模型。如图 3（b）所示，将其中缓冲区面积最小的岛屿I₂删除，根据拓扑表，将其中与岛屿I₂相切的岛屿I₆设置为可更改，并根据§2所述方法对其重新构建缓冲区生长模型。

4）判断被删除的岛屿缓冲区面积是否大于阈值，若是，则退出选取，输出选取结果，否则转步骤3）。如图 3（c）所示，重新构建模型后，将其中的岛屿I₄删除，并将与其相邻的岛屿I₅、I₆、I₇的sym_ch设置为可更改，利用§2所述方法重新构建缓冲区生长模型（如图 3（e）所示），此时其中缓冲区最小的岛屿I₃达到选取指标，因此输出选取结果。

特别说明，对于步骤3）的选取中可能会出现很多缓冲区面积相同且最小的岛屿（如图 3中的岛屿I₃与I₄），在对这些岛屿进行取舍时，按以下步骤处理。首先根据拓扑关系表，优先删除那些与其他岛屿缓冲区相切数目较多的要素，若其数目相同，则获取以该岛屿为中心的一定范围内的岛屿，优先删除该范围岛屿数目较多者；若相切岛屿数目相同，则计算该岛屿到该范围以内的全部岛屿的距离和，优先删除距离和较小者。以此步骤保证所删除的岛屿周围的密集程度最大。

4 实验与分析 4.1 与文献[4]方法的比对实验

为对本文所提缓冲区生长模型的有效性进行验证，选取我国某岛屿分布复杂多样，具有典型性的海域为实验区域。由于文献[8]中所述方法难以确定其模式识别算法的相关参数（空间距离、面积差异、角度阈值等阈值参数），因而仅与文献[4]所提方法进行比对。本文在海图比例尺缩小以后，对于面积不足0.5 mm²的岛屿，采用点状岛屿表示，资料图取自海图13300。因此将目标图比例尺设置为1:50万并将资料图按比例尺缩小后，目标区域如图 4（a）所示，其化简结果图分别按比例显示如图 4（b）~图 4（d）所示。

对比图 4（c）与图 4（d），不难看出，当对该区域提取一次时，其综合结果稍显拥挤，对其提取第二次之后，其综合结果稍好。因此将图 4（d）作为文献[4]所述方法的综合结果图，将图 4（a）中A、B、C所示区域的综合结果按原图比例尺显示为图 5~7所示。

本文只列举了图中一部分区域。从图 5（b）、图 7（b）可以看出，文献[4]所述方法保留了大量的距离面状岛屿较近的小点岛，同时出现了删除孤立岛屿的错误（如图 6（b）、图 7（b）所示）。这是由于文献[4]方法采用Voronoi图对岛屿的密度进行量化评估，该方法存在利用Voronoi图表达岛屿影响范围的缺陷，使得在选取过程中对上述孤立岛屿以及密集岛屿难以有效识别，选取结果不佳。相比之下，本文所提方法则取得了较好的效果。

4.2 与文献[8]方法的比对实验

为了与文献[8]方法进行比较评估，将文献[8]实验资料图（图 8（a）)和选取结果图（图 8（b）、8（e））进行扫描数字化，并对该资料图采用本文方法进行化简，两种方法的实验结果图分别按比例显示如图 8（c）、8(f)所示。

从图 8中可以发现，一方面，文献[8]方法对资料图所示区域中圆圈所标识的孤立岛屿均未能进行有效的保留，这一点与岛屿制图综合的原则不符。造成这一现象的主要原因在于，该方法采用岛屿群空间等剖分结构（类似于多边形的Voronoi图）对密度较大的岛屿进行识别，但由于本文§1.1所述Voronoi图描述岛屿密度的局限性，使得大量的孤立岛屿未能保留下来，反而对一些压盖的岛屿进行了选取保留。相比之下，本文方法的综合效果则显得更为合理。

4.3 分布范围及密度评估

由于当前对于岛屿原有模式是否保持的评估仍处于定性阶段，尚没有一种准确合理的评估方法，因此本文并未对这一原则进行定量分析。以上综合结果均由专业制图作业员及制图编辑进行主观评估。评估结果都认为合理且保持了原有岛屿群分布模式。

为了对综合后的岛屿群分布范围以及分布密度进行评估，本文将综合前后的岛屿群外边界所围区域的面积、岛屿间平均间距统计如表 1、表 2所示。

从表 1、表 2中可以看出，3种方法均能保持综合前后的分布范围大小。通过对比相同比例尺下的综合后的岛屿间平均间距不难发现，本文方法所得实验结果其平均间距相对较大，即压盖现象出现较少。

5 结语

本文首先总结了当前岛屿自动选取方法的研究现状，然后通过实例探讨了当前岛屿自动选取方法采用Voronoi图在表达空间密集程度时存在的缺陷，并设计了缓冲区生长模型来解决这一问题。在利用缓冲区生长模型对岛屿的影响范围进行评估的基础上，设计了岛屿自动选取机制，通过优先删除影响范围最小的岛屿，并对剩余岛屿重新构建缓冲区生长模型，实时检测岛屿影响范围，不断重复上述过程，直至达到选取指标，实现了自动选取岛屿的目的。

为了对本文方法的有效性进行验证，本文选取了两组形态各异的典型海域作为实验区域，选取文献[4]以及文献[8]方法作为比对算法，并对选取结果进行了定性的对比分析。考虑到文章的严谨性，本文采用岛屿群分布范围以及分布密度对选取结果进行了定量分析。从实验结果来看，文献[4]和文献[8]方法不可避免地容易删除一些较为重要的孤立岛屿，同时对于一些位于海岸线附近的小岛屿却难以进行综合。而本文方法采用了可有效避免上述缺陷的缓冲区生长模型，有效保留了对航行较为重要的孤立岛屿，并对上述需要删除的小岛屿进行了有效删除，提高了岛屿的选取质量。

当然，对于岛屿自动选取而言，影响岛屿选取的因素具有其复杂性。本文仅考虑到了岛屿之间的相互影响，而在多要素条件下，如何有效顾及其与周围水深、等深线以及岸线等要素之间的关系，实现多要素的协同化简^[17-19]，以及如何设计岛屿选取质量定量评估指标及模型，从而对岛屿选取质量进行科学定量的评估^[20]。这些问题还有待后续更为系统的分析和研究。