《1 前言》

1 前言

线状要素的注记方式依地物类型和地图用途的不同有较大的差别，可分为点定位注记配置模式和线定位注记配置模式（曲线注记模式）两种。无论从地图注记的功能还是从美学角度出发，曲线注记模式都是最重要的线状要素注记方式。本文重点研究曲线注记模式，提出了一种快速而高效的线状要素曲线注记的自动配置方法，可以对自然要素（如线状水系）和人工要素（如道路和街道）进行统一处理。

在以往线状注记的研究文献中，较多采用线点注记代替线状注记[1~3] ，不能处理曲线注记模式；注记压盖处理方式多采用栅格化的方式[4~7] ，注记处理过程中数据进行矢栅互转时，既影响效率，同时也影响注记的精度；线状要素的注记方式一般较多探讨散列方式[2~4] ，不能满足在实际应用中紧密型线状注记的需求；而避免由于点位密集引起的注记冲突和与地物的压盖—禁忌、回溯与神经元网络等方法，已被证明取得了较好的结果[3，8~10] 。因此，本文的自动注记过程采用全矢量化的方式，有利于提高自动注记的速度以及精度；对于压盖处理方式，由于采用全矢量化处理方式，这样方便利用R树索引来加快搜索速度；对于紧密型线状注记，本文采用整体移位的方式；对于散列型线状注记，本文采用禁忌法的单字移位达到整体最优；对于不足字长的线状要素，需要根据实际情况进行强制注记。

《2 线状要素注记解决方案》

2 线状要素注记解决方案

线状要素注记自动配置的基本流程大致可以分为以下6个步骤。

1）全要素数据预处理。

2）线要素的综合简化。

3）选择注记方式。采用中心线注记还是平行线注记。

4）求参考线。对平行线注记要先求平行线，并消除尖角、自相交、相近等。

5）对较长的线要素进行分段处理，以便对其进行分段注记。

6）对每一条曲线的注记进行注记定位与选优。

一般情况下，注记字的放置如图1所示，可以根据曲线段的两个端点构成的直线方位角判断是相对平行或垂直的线。相对平行的线，注记字从左往右放置，字头方向朝上，与曲线的切线垂直；相对垂直的线，注记字从上往下放置，字头方向朝上，与曲线的切线平行。

《图1》

图1 线注记的走向

Fig.1 Directions of line label

《3 线状要素注记关键算法》

3 线状要素注记关键算法

《3.1 全要素数据预处理》

3.1 全要素数据预处理

此处的全要素数据预处理需要解决的是参与注记的所有线图层中的所有要素的合并与拓扑分段，便于后续处理得到高质量的定位线。

1）要素合并，根据数据特点合并具有相同属性值的弧段。

2）拓扑分段，当对两个相互交叉弧段进行注记时，只有一个弧段可以跨越交叉口进行显示，否则注记就会出现所属关系不明确，影响注记效果。这里首先根据经典拓扑理论对所有线要素建立拓扑关系，然后分两种情况进行拓扑分段处理：a. 对于两个优先级高低有别的要素，在结点处，优先级高的合并（根据属性值是否相同），优先级低的打断；b. 对于两个优先级高低相同的要素，在结点处，计算相邻弧段的长度，长度短的合并（根据属性值是否相同），长度长的打断。

《3.2 要素综合简化》

3.2 要素综合简化

对于一个地理信息系统（GIS），由于受软硬件条件的限制，数据量的大小以及数据的质量将对整个系统的运行速度和效率产生直接的影响，如果是注记动态配置功能模块，要不断动态响应GIS用户的操作，对速度有更高的要求，精简的数据就显得更为重要。在注记自动配置中，要素简化不仅可以删除冗余数据，减少数据存储量，同时降低线状要素形状复杂度，这对于后期线目标的裁剪、平行线的求取以及提高注记动态配置的响应速度都很有意义。

本文采用的综合简化算法是Douglas算法。其基本步骤如下。

1）设定数据压缩的阀值，这个值一般情况下不会太大，是一个基本上不会影响视觉效果的值。

2）连接首尾两点，找出与两点连线有最大偏移距离的点。

3）如果这个点的偏移距离小于这个阀值，则去掉两点间所有的点，否则，把曲线以这个点为分段点分成两条曲线，执行第2步。

这是一个比较简单的容易实现的算法，可以用一个递归算法来实现。

《3.3 求参考线与平行线》

3.3 求参考线与平行线

对矢量数据平行线的求取，以往一般采用角平分线法，这种算法具有高精度、运行速度快等优点。图 2 给出了角平分线法的原理，其中，α 为角度，d 表示平行线与中心线的距离。

《图2》

图2 角平分线法

Fig.2 Internal bisector

这种方法生成的平行线有一个缺点，那就是小角度上的点，不管平行线是在角的外侧还是内侧，所求得的点都会离中心线非常远。如果是在外侧，平行线上的点就会非常突出，伸向很远的地方；如果是在内侧，平行线上的点就会缩到很远的地方，如果点两侧的边比较短的话，平行线就会因为这个点而改变其原有的形状。这个问题一直是一个待解决的问题。

为了解决这个问题，笔者分两步进行。

1）解决平行线内侧点回缩而改变形状的问题。这个问题的解决方法是生成平行线的参考线，通过生成的参考线来求取平行线。

具体的方法是扫描曲线上的每一个点，求这个点的夹角，如果角度 α ＜90°，且平行线是在这个角的内侧，则计算两条边的长。如果两条边的长度都小于 d/ tan(α /2) ，则删除该点和角两端的点。如果只有一边的长度小于 d/ tan(α /2) ，则用另一条边上距离该点与这条边的长度相同的点代替该点。

2）解决平行线外侧点突出的问题。这个问题的解决方法是改进角平分线法，在不求取平行线时添加辅助点。

具体的方法是在用角平分线求平行线的过程中，对于角度 α ＜90°，且平行线在这个角的外侧，则用角平分线上距离该点为 d 的点代替平行线上的点，在左右两侧各加一个辅助点。

上述求平行线的过程可以用图 3 来表示，图 3 中求了中心线的左平行线，中心线的方向是从左往右，图中先通过连接点1和2，3和4，生成了参考线，然后再通过改进的角平分线法生成了平行线。

《图3》

图3 改进的角平分线法

Fig.3 The reformative method of internal bisector

在求完平行线以后，平行线可能会出现自相交和自相近的情况。对于自相交的情况，在以往的研究中已经给出了解决方法，但对于自相近的情况，却没有人注意。在这里先介绍平行线自相交的处理方法，给出平行线自相近的描述、对注记的影响以及处理方案。

设平行的定位线有N 个坐标点，则包含的线段数为N -1，消除定位线自相交情况的具体步骤如下。

1）输入定位线的坐标数和坐标串。

2）从第1段到第N -1段线段，依次检查与每段线段相交的第一段线段。

3）两条相交的线段形成一个环路，环路从交点开始又终于交点，将环路之间顶点删除，将新的交点作为新顶点加入定位线坐标串中，并修改定位线的顶点数目。

4）输出最后的顶点和线段。

平行线自相交的示意图以及处理方案如图 4 所示。

《图4》

图4 平行线自相交示意图

Fig.4 The parallel line intersect

平行线自相近一直是一个被忽略的问题，但在注记过程中又很可能存在。如图5所示，其处理方法可以分以下几步。

《图5》

图5 平行线自相近示意图

Fig.5 The parallel line close

1）输入坐标点串。

2）从第一段开始，依次比较该段与后面线段的关系是否相近，并记录下最后一个与其相近的线段。

3）如果是端点相近，则连接端点，如果是端点与线段相近则连接这个端点和这个点在其相近线段上的垂足。

4）删除连接两点之间的点。

5）输出剩余的点作为平行线。

《3.4 动态分段》

3.4 动态分段

有些线状要素在地图上的长度比较长，需要进行分段注记，也就是说在注记之前，要对线状要素进行分段处理，然后再每一段或者选择其中的几段进行注记。在以往的曲线分段方法中，有两种分段方法，一种是根据方位角改变分段的方位角法，另一种是根据曲线的单调性进行分段的单调段法。方位角法在一定程度上可以将曲线分成较为光滑的曲线段，但是对一些复杂的曲线，特别是在一些线段比较短，方位角变化比较大的曲线中，容易把曲线划分得太细，以至于无法进行注记；单调段法能够保证曲线注记的通视性，但是不能提取出相对平滑的曲线。

方位角法和单调段法两种方法都不能满足在光滑部分注记的目的，为了解决这个问题，受Douglas算法的启发，提出了反Douglas算法。算法的基本思想是以曲线上所有的线段为基础，逐步合并相对光滑的曲线段。

在介绍反 Douglas 算法的具体实现步骤以前，先来进行如下两点说明。

1）相邻曲线高度 h，这是指当相邻的两条曲线合并成一条曲线时，曲线上所有点到曲线两端点所成直线的最大距离。

2）相邻曲线相对高度 hcomp ，设两曲线的长度分别为 l1 和 l2 ，两曲线的合成曲线两端点的距离为 d ，则 hcomp = hd 2 /(l12 + l22)。

反Douglas算法的计算步骤如下。

1）设定两曲线可以合并的曲线相对高度的阀值 Hcomp ，合并长度阀值 L合 ，这两个阀值的设定与注记字符串的长度和字大有关。

2）输入注记曲线的点串。

3）计算每个基础线段的长度 li 。

4）以每个基础线段为初始的曲线段，每个曲线段的长度为 Lk 。

5）从每一个曲线段开始扫描，计算相邻曲线相对高度 hk,k + 1 ，并且记录下最小的相对高度 hmin 。

6）判断是否终止。如果 hmin ＞ Hcomp ，转下一步。当 hmin ＜ Hcomp 时，合并相对高度等于 hmin 的相邻曲线，并求出新曲线的长 Lk,k + 1 = Lk + Lk + 1 。如果Lk,k + 1 ＜ L合，用新的曲线替换原来的两条曲线，转第5步。否则从剩下的相对高度中取出最小的值来替换 hmin ，重复第6步。

7）输出曲线段，对每一个曲线段进行注记。对于长度大于L合 的基础线线段，或将线段平均分割，再进行注记。

反 Douglas 算法有两个优点：a. 能够提取出相对光滑的曲线，相对原来的方法来说，对弯曲度的适应度较高；b. 可以限定合并长度，除非有长度较长的直线段，否则能够进行注记的线段没有必要进行分段注记。

《3.5 注记定位与选优》

3.5 注记定位与选优

求取定位参考线（平行线）以后，沿定位参考线（平行线）的自动最优注记定位问题是一个组合优化问题。本文采用禁忌搜索算法求解全局最优，为此，需要建立每个定位参考线（平行线）注记的备选位置组合以及合理有效的目标评价函数。线状要素注记定位过程可以概括为以下3步。

3.5.1 获取注记备选位置

1）注记配置将注记看成一个由其尺寸决定的矩形框。选择按照注记规则生成的一条定位参考线（平行线），放置注记的方式是先中间后两头。整个注记串放置的中点称为注记字串的定位点。如果注记包含奇数个汉字，先确定整个注记串的中点，配置中间的一个汉字，再配置紧靠中间汉字的两个汉字，以此类推。

2）注记配置的控制参数组（ParallelDis，FontSpace，LabelPos）唯一确定一个备选位置。其中 ParallelDis（PD）为注记定位参考线（平行线）与线状要素的偏离距离，FontSpace（FS）为注记字符的间隔，LabelPos（LP）为注记串的定位点，即注记字符连接线的中点。

给定上述3个参数的变化范围和变化步长，可以获得所有的备选位置。先定义几个参数：定位参考线（平行线）长度L，注记字符串字数CN，单个字宽 CW，注记首（末）字到定位参考线（平行线）起（终）点的距离 FL，定位参考线（平行线）中点位置 MP。便于后续计算，对3个参数的变化步长这里我们统一取值为5。

偏离距离PD的范围 [MinD ,MaxD ] ，对于紧密注记，取 MinD = MaxD =0；对于散列注记，取 MinD =×CW/2， MaxD =CW。

字符间隔 FS 的范围 [MinS ,MaxS ] ，对于紧密注记，取 MinS  = MaxS  =0.1CW；对于散列注记，取 MinS = 3，MaxS =5。

注记定位点LP的范围[MP-Delta，MP+Delta]，对于任意给定的字符间隔FS，注记定位点 LP 的活动邻域 Delta 表达式为：

若字数为奇数，则Delta=L/2-（FL+CN+1/2CW+ CN/2FS）；

若字数为偶数，则Delta=L/2-（FL+CN/2CW+CN/2- 1FS+FS/2）。

3.5.2 对备选注记位置评分

一般认为，最好的注记位置是离线状要素最近、位置越接近中心、字符间隔最小的备选位置。对备选位置的评价考虑注记位置优先级、注记最小外接矩形框是否相交、注记最小外接矩形框是否压盖背景注记（一般指面注记或其他限制条件）等3个因素，从而建立目标函数

式中，Ci = ∙Preference(i )+ b∙Conflict(i )+ c∙Overlap(i ) ，Conflict(i )=，n 表示待配置注记的总数， Ci 表示每个点注记的代价值。、b、c 分别为注记位置优先级、冲突量和压盖量的权重值，本文中这3个权重值都为1。Preference（i）为注记位置优先级， pj 为每个线状要素的等级大小， Preference(i ) 与 pj 设计为0.2的倍数取值， Overlap(i ) 为压盖背景注记的个数。

3.5.3 注记点位的搜索与选优

1）读入所有待注记的定位参考线。

2）产生初始解：产生初始解 X ，设置迭代次数 k=0，最佳解向量 Xbest = X ，若目标函数值为0，直接返回。

3）产生一组候选解：按代价值从大到小得到一组可行的候选解。

4）搜索邻域：在上述每个候选解中通过改变 3 个控制参数 (ParallelDis, FontSpace, LabelPos) ，计算比较每个代价值，通过最小代价值得到一个最好的候选解 X * ，如果 X * 不在禁忌表中，或者即使在禁忌表中，但已经满足释放准则，则用 X * 更新 X ；如果该解在禁忌表中，但是不满足释放准则，则寻找次优解，并重复此过程。

5）更新禁忌表：将寻优得到一个最好的候选解 X * 压栈到禁忌表中，如果禁忌表已满，则首先释放最先记录的候选解。

6）更新 Xbest ：如果 X * 的目标函数值小于Xbest 的目标函数值，则用 X * 更新 Xbest ，否则 Xbest 保持不变。

7）判断终止条件：若连续n 次迭代之后目标函数值没有改进，或者达到最大允许迭代次数，则停止优化，输出结果；否则迭代次数加1，并转到步骤 3），继续优化。

初始解 X 以偏离距离PD的最小值MinD、字符间隔FS的最小值MinS、LP的活动邻域Delta=0求取所有注记备选位置。在产生初始解 X 后根据所有注记最小外接矩形框建立 R 树，在步骤 4）中 X * 更新X过程中动态更新R树，通过R树提高注记相交与压盖的查询速度。

《4 结语》

4 结语

图6给出了直接用角平分线法求取的左右平行线的效果图，图6中暗灰色部分是中心线，黑色是平行线，星号是对平行线的分段点。由图6可以看出角平分线法的不足，以图中A 所示的点为例，它对应的平行线上的点发生了点的远离，其外侧点突出到 B 所示的位置，内侧点回缩到C所示的位置，而图中D 和E 所示的位置则发生了平行线自相交的情况，如果平行线的距离再小一点，那么E 所示的位置就会出现平行线自相近的情况。

《图6》

图6 角平分线法求平行线

Fig.6 Parallel line obtained according to the internal bisector

平行线即注记线，是地图注记过程中注记字所在的线，所注记字的中心就在平行线上，而图6中所示的平行线显然无法进行注记。

图7给出了用改进算法求取上述平行线，然后用反Douglas算法对平行线进行分段的效果图。与图6相比，在这几条平行线上注记显然会取得更好的效果。

《图7》

图7 改进算法求平行线

Fig.7 Parallel line obtained according to improved algorithm

使用本文提出的算法，进行线状要素自动注记，速度较快，注记质量也比较理想。图8是道路自动注记结果的一部分，图9是线状水系自动注记结果的一部分。从图9可以看出，左上方的线状水系为紧密型线状注记，其余部分为散列方式线状注记。

《图8》

图8 道路注记

Fig.8 Road label

《图9》

图9 河流注记

Fig.9 River label