基于横向循环配置的线状符号填充算法

摘要：针对GIS地图符号中线状符号填充时出现的符号重叠、交叉、断裂、空白等失真现象，该文在已有的算法上利用横向循环配置的线状符号填充思想做了一定的改进。该算法通过对线状符号进行旋转、变形、裁剪等步骤来解决一些失真现象，不仅在视觉上达到了很好的效果，而且还提高了算法的填充效率。

关键词：横向循环配置；填充算法；线状符号；失真

中图分类号：TP312文献标识码：A文章编号：1009-3044(2008)29-0420-03

The Filling Algorithm of Linear Symbol Based on the Horizontal Circle Configuration

ZHANG Ming-wang, LIU Rong-qi

(School of Mathematics and Computer Engineering,Xihua University,Chengdu 610039,China)

Abstract: For the distortion Phenomenon of Overlap, Cross, rupture, Blank and so on in the GIS map Symbol when fill linear Symbol, this paper do a certain improvement use the thinking of horizontal circle fill linear symbols base On the existing algorithms. The algorithm through the circumrotate, deformation, cutting to the linear symbols to solve distortion Phenomenon, not only reached very good results in the visual, but also improve the efficiency of the filling algorithm.

Key words: horizontal circle configuration; filling algorithm; linear Symbol; distortion

1 引言

地图符号是地图的语言，是构成地图的基本元素，因此地图符号的设计与地图符号填充算法的实现在GIS以及各种电子制图系统中占有重要的地位。根据演绎的方法可将地图符号分成三种：点状符号、线状符号和面状符号[1]。线状符号是地图符号中使用最多的一类，也是地图符号中最复杂的一类。线状符号的线状单元一般由直线、折线、矩形、椭圆、多边形等基本图元组成，绘制一条线状地理要素就是沿地物位置的定位线循环的填充为该线状地理要素定义的线状符号单元。

2 线状符号的基本概念

2.1 线状符号的特点

地图线状符号除了具有地图符号的一般特点之外，还有一些主要的特点：

1) 线状符号都有一条有形或无形的定位线。

2) 线状符号单元可以看作是由若干基本图元组合而成的。

3) 其填充过程可以看作是线状符号单元沿着定位线的前进方向循环填充。

2.2 线状符号填充方法的分类

线状符号是长度依比例尺而宽度不依比例尺的符号，它是用来表达地理空间上沿某个方向延伸的线状或带状现象的地理要素，如河流、道路、国界线等。线状符号在地图上占据较大的比重，因此可以说线状符号是地图上应用最广泛的地图符号。

线状符号的填充是一个难点，目前对于线状符号的填充，国内外采用的思路一般分为以下三种：

1) 纯函数绘制法：该方法是按照符号表示的地物种类进行分类并为每一类符号写一个绘制函数。由于这种方法采用纯函数实现符号的绘制，所以这种方法的缺点是符号可编辑性和维护性差。一旦符号确定下来，用户要做大量修改将十分困难。

2) 纵向叠加图元法：该方法利用线符号的可分解性，将线符号纵向拆分为多个基本符号单元，并按顺序分别从定位线的起点到终点绘制基本符号单元来实现。比如图1所示的铁路符号，可以先从起点到终点连续两次绘制铁路的边线单元，再从起点到终点绘制铁路的矩形填充符号。这种算法增强了符号的可编辑性和可维护性，算法简单，速度也比较快。但如果符号组合比较复杂的话，其速度将会减慢，对过于复杂的线状符号不一定具有可分解性。

3) 横向循环配置图元法：这种方法的线状符号单元是一个定长的图元组合，在符号化时将提供的线状符号单元沿着地理要素的定位线一块块循环填充下来直到终点。比如图2所示的铁路符号，它可以看成是由一个黑色矩形和白色矩形组成的线状符号单元循环填充而成的。这种方法更加增强了符号的可编辑性与可维护性，且绘制复杂线状符号的速度较之纵向叠加图元法要快；其缺点是绘制简单线状符号的效率反而比纵向叠加图元法要慢，而且实现起来较为复杂。

以上三种线状符号的填充思路各有其优缺点和适合范围。但是不论是哪种填充思路，在定位线拐点转角相对较大的情况下，都不可避免地出现重叠、交叉、断裂、空白等失真现象，从而影响了视觉上的整体性，甚至影响整幅地图的美感。

由于线状要素的定位线具有连续性，因而如何依据地理要素定位线的形态连续、光滑地填充线状符号，如何提高填充速度，这些都是线状符号填充算法的核心问题，也是线状符号填充的难点。本文针对地图线状符号填充过程中的常见问题，在采用横向循环配置的线状符号填充方法的同时，对线符号转折处的重叠、压盖和交叉等失真情况作了一定的优化处理。

3 横向循环配置线状符号填充算法

3.1 横向循环配置思想

线状符号的填充比较复杂，尤其是在定位线的拐点处要作适当的变形处理，以防止出现失真现象。对于横向循环配置思想我们可以归纳为：

1) 计算定位线中的每一条直线段的长度，根据第一条直线段的长度确定可完整填充的符号的个数以及每一条直线段完整填充后余留的不足填充完整符号的定位线长度。填充最后一段不足填充完整符号的定位线并裁剪掉不能填充的剩余符号，计算其长度并把它转入填充到下一条直线段中。

2) 根据上一条直线段的最后一个线状符号填充裁剪后剩下的符号长度来确定本条直线段的有效长度，从而计算出可填充的完整的线状符号的数目、完整填充后所余留的定位线长度以及最后一个符号填充裁剪后转入填充到下一条直线段中的剩余符号的长度。依次下去直到最后一条直线段。

3) 计算每个拐点的角平分线。当填充拐角处的符号时，如果与拐点的角平分线相交则利用裁剪方法裁剪掉平分线之外的线状符号。这样可避免角平分线两边的的线状符号填充时发生自交以保证整体视觉效果。

3.2 算法描述

在文献[6]中详细的介绍了线状符号的填充算法，但是经过研究发现，此填充方法存在一定的不足。如当拐点角度在一定范围内时将出现拐点在扇形区域的外部、计算线状符号外接矩形顶点的坐标时还要依靠前面所有的拐点角度以至重复计算很多以及算法有多余计算部分增加了计算复杂性等。为此，本文在文献[6]的线状符号填充算法的基础上针对一些不足之处做了有效的改进。

对于任意给定的一条线状要素的定位线，其填充原理可概述为：完整填充并对线状符号单元做旋转处理（如图3的AB段、FG段），对不能完整填充的符号单元要做变形（如图3的BCD 段、DEF 段）或裁减（如图3的GH段）处理，以符合弧段的形状变化和长度。

根据上述填充算法的概括描述，结合横向循环配置的思想，我们可以得到下面详细的填充过程：

1) 计算符号完整填充的个数

完整填充处理是指首先确定要填充的直线段，然后计算其有效长度，根据其长度来确定可以完整填充的线状符号的个数。首先令

其中，d表示线状符号单元的长度；Li表示定位线的每一条直线段的长度；li 表示相邻上一条直线段填充的最后一个线状符号被裁剪后转入本直线段的长度，且l1=0；ni表示每一条直线段可完整填充的符号数目；mi表示每一条直线段完整填充符号后所余留的长度；i表示直线段的条数。

以图3为例，按照上述方法有：

第一条直线段的长度：L1=AC

可完整填充的线状符号的个数：n1=(L1-li)/d ；l1=0

直线段完整填充后余留的长度：m1=(L1-l1)%d

转入到下一条直线段的余留符号长度：l2= d - m1

这样一直下去就可以求出所有直线段上可完整填充的线状符号个数。

2) 旋转处理

旋转处理是指以被填充线状符号的起始点作为旋转点，将同一条直线段上的所有线状符号旋转适当的角度，以满足填充的需要。

①旋转角度的计算方法。在旋转处理中规定：旋转角度θ∈(-180°，180°)，其中逆时针旋转的角度为正，顺时针旋转的角度为负。根据两条直线段的向量 V1、V2，可通过向量点乘来求取拐点旋转角度θ的大小（0°～180°），而由向量叉乘来获得旋转角度θ的正负。

②旋转的坐标变换求法。设（x，y）为初始点，（x1，y1）为旋转后的点，旋转角度为θ，则坐标变换公式为：

利用上述的旋转处理方法，我们可以简单的对图4进行线状符号的旋转处理，使得线状符号的方向和定位线的方向一致。

首先令定位线的拐点分别为O1、O2、O3和O4，设其坐标分别为：O1(x1，y1)、O2(x2，y2)、O3(x3，y3)、O4(x4，y4)，线状符号的高度为h，长度为d，第一次旋转角度为α，在符号坐标系中，线状符号（如图4的矩形ABCD）在旋转之前，其顶点坐标分别为A(xA，yA)、B(xB，yB)、C(xC，yC)、D(xD，yD)，其中xA=xB= x1、xC=xD= x1+d、yA=yD= y1-h/2、yB=yC= y1+h/2。

线状符号绕拐点O1（x1，y1）旋转α角度。此过程中 A、B、C、D 四点的处理方法一致，以（x，y）代表A、B、C、D四点的坐标，旋转后的新坐标为（x’，y’），则有如下关系：

而对于其他线状符号的处理方式也一样。

3) 变形处理

变形处理主要用于线状符号填充时遇到拐点外侧出现的断裂情形，此时线状符号单元填充到拐点（如图5中的拐点O2）时和下一条直线段开始的一段线状符号之间的断裂部分用扇行（O2GH）填充。

扇行O2GH的顶点坐标很好求得，O2为坐标已知的拐点，而点G和H又恰好是拐点前后两个地图符号的顶点坐标。对扇形颜色的填充要分两步进行，首先用拐点角的角平分线将扇形划分为两个区域，其次对两个区域用与之想邻符号的颜色填充。而其他的扇行处理方式也一样。

4) 裁减处理

裁减处理是为了解决拐点处出现的符号重叠、交叉的现象。主要是裁剪最后一条直线段填充的线状符号和拐点相邻前后的两个线状符号与拐点角平分线相交的位于平分另一侧的部分线状符号。

4 算法复杂度分析

对于文献[6]中的算法，通过计算：如果有N个拐点的话，我们要对第N-1条直线段的填充符号的顶点进行16(N-1)次乘法和32(N-1)次加减法，对所有顶点共进行8N(N-1)次乘法和16 N(N-1)次加减法。数量级为O(n2)。

文献[6]中方法是从定位线的末端向前端对符号进行旋转处理，每次计算顶点的坐标时还要依靠前面所有的旋转角度，显然重复计算很多。同时，经过多次的绘制尝试发现在变形处理过程中拐点外侧所填充的扇形，当拐点（如O2）的旋转角度在（120°，180°）或（-120°，-180°）时，拐点O2将会在扇形的外点，显然这样填充后很不美观。为解决这些问题，避免不必要的重复旋转计算和提高时符号化精度，我们得到了本文的改进算法。研究表明，此方法不仅很好的解决了扇形区域的填充问题提高了符号化精度，也对计算次数有进一步的减少，对有N个拐点的地理要素填充时，只需要做16(N-1)次乘法和32(N-1)次加减法，对此算法的计算次数的数量级是O(n)，相比文献[6]中算法的效率提高了很多。

5 结论

本文主要是解决线状符号填充时在拐点处出现的符号重叠、交叉、断裂、空白等失真现象，在已有的算法上本文利用横向循环配置的线状符号填充思想做了一定的改进，改进的算法通过对线状符号进行填充、旋转、变形、裁减等步骤来处理失真现象，不仅很好的解决了拐点超出扇形区域的可能，在视觉上达到了很好的效果，并且解决了重复计算的问题，大大提高了算法的通用性和填充效率。

参考文献：

[1] 胡鹏,黄杏元,华一新.地理信息系统教程[M].武汉:武汉大学出版社,2002:212-213.

[2] 程朋根.参数化线状符号设计思想与实现[J].华东地质学院学报,1999,2(23):283-287.

[3] 谈晓军,边馥苓,何忠焕.地图符号可视化系统的面向对象设计与实现[J].测绘通报,2003(1):11-13.

[4] 沈陈华.线状符号库的面向对象设计[J].重庆师范学院学报:自然科学版,2000,17(4):41-43.

[5] 何忠焕.GIS符号库中复杂线状符号设计技术的研究[J].武汉大学学报,2004(2):132-134.

[6] 张海泉,潘懋,吴焕萍,等.面向GIS的矢量线状符号填充算法研究[J].地理与地理信息科学,2004(7):12-14.

[7] 吴小芳,杜清运,徐智勇,等.杂线状符号的设计及优化算法研究[J].武汉大学学报,2006(7):632-635.