基于橫向循環配置的線狀符號填充算法

摘要：針對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.