基于四色原理技術的偽四色算法研究

郭林庚

摘要：利用開放的電子地圖手工繪制的非規范性地圖信息，本文旨在針對這些錯綜復雜的不規范地理信息，提出一種偽四色原理算法，自動分析多邊形相鄰性，使用盡可能少的顏色進行地圖著色，開發者無須了解地理信息系統原理，即可快速掌握，快速開發，節約公司成本。

關鍵詞：數據可視化；四色原理；最小外接矩形；空間位置分析

中圖分類號：P208 文獻標識碼：A 文章編號：1007-9416（2017）03-0159-02

1 前言

電信經營數據可視化系統使用百度地圖，手工繪制各管轄區域，地圖手工著色變得不可行。四色原理[1]，“任何一張地圖只用四種顏色就能使具有共同邊界的國家著上不同的顏色。”將四色算法應用到系統中，進行自動著色，能解決手工無法著色的問題，提升系統展示感知。但不規范的多邊形覆蓋物空間位置相鄰性分析是四色算法應用的難點。本文闡述了一些簡單易懂圖形基本處理算法和過程，面對錯綜復雜的非規范性地圖信息，提出著色的偽四色算法，使得沒有地理信息相關專業知識的內部開發人員能快速掌握，迅速開發，減少開發投資成本。

2 空間位置相鄰性分析

2.1 射線法判斷多邊形覆蓋物相鄰（算法1）

分析實際繪圖情況，一線人員繪制的多邊形都出現相交的情況，因此可采用判斷多邊形上的每個點是否有在另一個多邊形內，來判斷兩多邊形是否相鄰。幾何上判斷某個點是否在多邊形內，可以采用射線法[2]進行計算。射線法原理：從目標點出發引一條射線，看這條射線和多邊形的多有邊的交點數目，如果有奇數個交點，則說明在內部，如果有偶數個交點，則說明在外部。本算法內容涉及到地理信息信息的基礎算法及圖形學的內容，非本文介紹的重點，只做算法比較參考。

2.2 最小外接矩形算法（算法2）

計算坐標集的最大維度，最小緯度，最大經度，最小經度，形成一個多邊形的最小外接矩形，如圖（1）。當兩個矩形的中心距離小于等于矩形1與矩形2的寬的和的一半時，兩個矩形相交或相鄰，如圖（2）所示，即

以此判定繪制的多邊形相鄰。此算法根據地理要素的大致位置來判斷區域相鄰，則會擴大了實際區域的相鄰關系數。

2.3 多邊形最小相鄰距離算法（算法3）

分析實際繪圖情況，相鄰區域多邊形無法做到邊界重疊，但繪制邊界趨勢基本相當，如圖（3）。因此計算兩個多邊形倆倆坐標點間的距離，并取最小值。如果小于特定值，則可判斷兩多邊形區域相鄰。

2.4 算法應用結果對比

經過一線人員手工繪制，管轄區域分成三個層級，一級15個區縣局，二級113個分支局，三級912個社區。測試環境Oracle10g數據庫。特定值的選取，一級比例尺500m-1km，選擇100m；二級比例尺100m-200m，選擇50m；三級社區20m-50m，選擇20m。如表1所示。

2.5 算法優化

如上表所示，最小外接矩形的算法2速度最快，但是它誤差大。最小相鄰距離的算法3，速度最慢，但是準確率高，在一級層面準確率100%。算法1，出現相交的時候，準確度尚可，但無相交則判斷錯誤，且運行速度慢。可采用混合算法，即先進行算法2大致相鄰區域判斷，然后在判斷的結果中對有相鄰關系區域再進行算法3的判斷，既提高了算法準確率，又提高了算法的計算速度。實際應用結果顯示，在區縣局層面正確率100%，三級社區層面執行時間在90秒內。

3 偽四色原理算法設計

3.1 無遞歸的偽四色算法

定義可變長的顏色組T，計算1到i-1個區域中，且與第i區域相鄰的區域的不同顏色組C，從T中剔除C中的顏色，并取最小顏色值賦給第i個區域賦，如果找不到顏色，則增加顏色組T的顏色，流程圖如圖（4）所示。

3.2 帶遞歸的四色算法

定義固定長度數組T，T的顏色值最大為待著色區域群眾的最大倆倆相鄰數。算1到i-1個區域中，且與第i區域相鄰的區域的不同顏色組C，從T中剔除C中的顏色，并取最小顏色值賦給第i個區域；如果找不到顏色，則回退到第i-1區域，并修改第i-1區域的顏色，重新開始著色，流程圖如圖（5）所示。

3.3 實際著色結果驗證（表2）

4 結語

通過實際著色測試結果可以看出，無論是使用那種算法，都能實現自動著色。最后數據可視化系統選擇效率最高且顏色數最少的混合算法配合遞歸著色。規范繪圖，提高繪圖質量，調整錯誤的相鄰區域，使得最大倆倆相鄰數不超過4，則本文算法也可以實現四色地圖著色。

參考文獻

[l]徐志才.四色問題的探討[J].北京郵電大學學報，2003，（2）：105-112.

[2]張宏，溫永寧，劉愛利.地理信息系統算法基礎[M].北京科學出版社，2006.