郭林庚

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

關(guān)鍵詞：數(shù)據(jù)可視化；四色原理；最小外接矩形；空間位置分析

中圖分類號(hào)：P208 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2017）03-0159-02

1 前言

電信經(jīng)營(yíng)數(shù)據(jù)可視化系統(tǒng)使用百度地圖，手工繪制各管轄區(qū)域，地圖手工著色變得不可行。四色原理[1]，“任何一張地圖只用四種顏色就能使具有共同邊界的國(guó)家著上不同的顏色?！睂⑺纳惴☉?yīng)用到系統(tǒng)中，進(jìn)行自動(dòng)著色，能解決手工無(wú)法著色的問(wèn)題，提升系統(tǒng)展示感知。但不規(guī)范的多邊形覆蓋物空間位置相鄰性分析是四色算法應(yīng)用的難點(diǎn)。本文闡述了一些簡(jiǎn)單易懂圖形基本處理算法和過(guò)程，面對(duì)錯(cuò)綜復(fù)雜的非規(guī)范性地圖信息，提出著色的偽四色算法，使得沒有地理信息相關(guān)專業(yè)知識(shí)的內(nèi)部開發(fā)人員能快速掌握，迅速開發(fā)，減少開發(fā)投資成本。

2 空間位置相鄰性分析

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

分析實(shí)際繪圖情況，一線人員繪制的多邊形都出現(xiàn)相交的情況，因此可采用判斷多邊形上的每個(gè)點(diǎn)是否有在另一個(gè)多邊形內(nèi)，來(lái)判斷兩多邊形是否相鄰。幾何上判斷某個(gè)點(diǎn)是否在多邊形內(nèi)，可以采用射線法[2]進(jìn)行計(jì)算。射線法原理：從目標(biāo)點(diǎn)出發(fā)引一條射線，看這條射線和多邊形的多有邊的交點(diǎn)數(shù)目，如果有奇數(shù)個(gè)交點(diǎn)，則說(shuō)明在內(nèi)部，如果有偶數(shù)個(gè)交點(diǎn)，則說(shuō)明在外部。本算法內(nèi)容涉及到地理信息信息的基礎(chǔ)算法及圖形學(xué)的內(nèi)容，非本文介紹的重點(diǎn)，只做算法比較參考。

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

計(jì)算坐標(biāo)集的最大維度，最小緯度，最大經(jīng)度，最小經(jīng)度，形成一個(gè)多邊形的最小外接矩形，如圖（1）。當(dāng)兩個(gè)矩形的中心距離小于等于矩形1與矩形2的寬的和的一半時(shí)，兩個(gè)矩形相交或相鄰，如圖（2）所示，即

以此判定繪制的多邊形相鄰。此算法根據(jù)地理要素的大致位置來(lái)判斷區(qū)域相鄰，則會(huì)擴(kuò)大了實(shí)際區(qū)域的相鄰關(guān)系數(shù)。

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

分析實(shí)際繪圖情況，相鄰區(qū)域多邊形無(wú)法做到邊界重疊，但繪制邊界趨勢(shì)基本相當(dāng)，如圖（3）。因此計(jì)算兩個(gè)多邊形倆倆坐標(biāo)點(diǎn)間的距離，并取最小值。如果小于特定值，則可判斷兩多邊形區(qū)域相鄰。

2.4 算法應(yīng)用結(jié)果對(duì)比

經(jīng)過(guò)一線人員手工繪制，管轄區(qū)域分成三個(gè)層級(jí)，一級(jí)15個(gè)區(qū)縣局，二級(jí)113個(gè)分支局，三級(jí)912個(gè)社區(qū)。測(cè)試環(huán)境Oracle10g數(shù)據(jù)庫(kù)。特定值的選取，一級(jí)比例尺500m-1km，選擇100m；二級(jí)比例尺100m-200m，選擇50m；三級(jí)社區(qū)20m-50m，選擇20m。如表1所示。

2.5 算法優(yōu)化

如上表所示，最小外接矩形的算法2速度最快，但是它誤差大。最小相鄰距離的算法3，速度最慢，但是準(zhǔn)確率高，在一級(jí)層面準(zhǔn)確率100%。算法1，出現(xiàn)相交的時(shí)候，準(zhǔn)確度尚可，但無(wú)相交則判斷錯(cuò)誤，且運(yùn)行速度慢?？刹捎没旌纤惴?，即先進(jìn)行算法2大致相鄰區(qū)域判斷，然后在判斷的結(jié)果中對(duì)有相鄰關(guān)系區(qū)域再進(jìn)行算法3的判斷，既提高了算法準(zhǔn)確率，又提高了算法的計(jì)算速度。實(shí)際應(yīng)用結(jié)果顯示，在區(qū)縣局層面正確率100%，三級(jí)社區(qū)層面執(zhí)行時(shí)間在90秒內(nèi)。

3 偽四色原理算法設(shè)計(jì)

3.1 無(wú)遞歸的偽四色算法

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

3.2 帶遞歸的四色算法

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

3.3 實(shí)際著色結(jié)果驗(yàn)證（表2）

4 結(jié)語(yǔ)

通過(guò)實(shí)際著色測(cè)試結(jié)果可以看出，無(wú)論是使用那種算法，都能實(shí)現(xiàn)自動(dòng)著色。最后數(shù)據(jù)可視化系統(tǒng)選擇效率最高且顏色數(shù)最少的混合算法配合遞歸著色。規(guī)范繪圖，提高繪圖質(zhì)量，調(diào)整錯(cuò)誤的相鄰區(qū)域，使得最大倆倆相鄰數(shù)不超過(guò)4，則本文算法也可以實(shí)現(xiàn)四色地圖著色。

參考文獻(xiàn)

[l]徐志才.四色問(wèn)題的探討[J].北京郵電大學(xué)學(xué)報(bào)，2003，（2）：105-112.

[2]張宏，溫永寧，劉愛利.地理信息系統(tǒng)算法基礎(chǔ)[M].北京科學(xué)出版社，2006.