基于C語言的GIS地圖著色問題的實現

郭仁安，郭先春

(1.福建省國土測繪院，福建廈門 361012; 2.東華理工大學，江西 撫州 344000)

1 引言

地理信息系統(GIS)是一項以計算機為基礎的新興技術，圍繞著這項技術的研究、開發和應用形成了一門交叉性、邊緣性的學科，是管理和研究空間數據的技術系統。GIS的發展在國內外的發展大致可分兩個階段:早期階段是20世紀90年代初期主要解決的問題涉及:信息提供、工作發布及數據管理;中期主要是基于圖像導航的多功能3D虛擬現實［1］國土資源調查、流域調查［2］等。這階段的GIS能高效的使外業人員與GIS中心部門之間傳輸空間數據，消除了往返辦公室取“硬地圖”的必要。在這階段國內外都有相應的產品，特別值得一提的是國內武漢大學的GeoStar、中國地質大學的MapGIS、北京超圖SuperMap平臺等。然而地圖著色問題一致是人們困擾的問題:究竟只要幾種顏色就能將地圖一一區分開來是人們研究的熱點。1852年英國人格思里于提出四色猜想，1878年英國數學家凱萊重新提出這問題，引起人們關注，1890年英國人希伍德沿著這方向證明了任何地圖只用5種顏色著色便夠了，取得初步進展。1968年挪威數學家奧雷等人證明了用4種顏色把不超過40個國家的地圖著色，推進了四色問題的研究。70年代人們通過數學歸納法證明四色問題。本文就在此基礎上，結合數據結構的算法，用C語言編程，對地圖著色問題給予了實現，現就其實現過程加以論述。

2 地圖著色問題的數據模型

在地圖中兩個城市之間只可能存在著兩種關系相離和相交關系。因此在計算機中可用0、1表示這兩種關系，用0、1分別來表示兩城市之間的相離和相鄰(相鄰是指兩城市之間有公共的邊界)，并人為規定相同的城市與城市之間的關系是0。由于一幅圖中城市太多，為使問題簡化，現就用如下9個區域(設每個區域所代表不同的城市)來進行模擬，如圖1所示。用0、1將兩者的關系由矩陣加以表示，如圖2所示，不難看出它們兩兩之間的關系是鄰接對稱矩陣。

圖1 9個區域模擬圖

圖2 9個區域的關系圖

3 地圖著色的原理及算法

地圖著色的原理是任何平面地圖可以使用4種顏色給每個不同的城市著色，而保證相鄰的城市著不同的顏色，可采用“貪心算法”來完成。貪心算法［3］是求最優解的一種比較不錯的算法，其思想為:先用一種顏色給盡可能多的結點上色，然后用另一種顏色在未著色結點中給盡可能多的結點上色，如此反復直到所有結點都著色為止。因此可把地圖上的每個城市抽象為一個點，并給每個城市編號，相鄰的城市之間用直線連接。據此做出鄰接矩陣，若第i個城市與第j個城市相鄰，則 metro［i］［j］=1，否則 metro［i］［j］=0，照編號從小到大的順序檢查每個城市，對每個城市從1到4使用4種顏色著色，若當前顏色可用(即不與相鄰城市顏色相同)，則著色;否則測試下一種顏色。

地圖著色問題可以轉化為圖來處理，假設要著色的圖為G，集合V1包括圖中所有未被著的結點，著色開始時V1是G1所有結點的集合(用 G.V表示)。NEW表示已確定可以用新顏色著色的結點的集合。

從V1中找出可用新顏色著色的結點集的工作可以用下面的程序框架描述:

通過上面的程序框架便可完成。

4 地圖著色問題的實現

有了上面的數據模型、原理、算法及開發思路以后，可對圖1的9個城市區域加以模擬，選擇C語言作為開發工具，其主要代碼如下:

5 實現結果展示

運行上面的程序，即可看到運行后的結果，并將其結果對著前面的區域分別用1、2、3、4進行填充和用1、2、3、4 所代表的 red、green、blue、yellow 結果進行填充，得到如圖5展示的結果圖。

圖3 C語言程序運行的界面圖

圖4 用C語言數字結果進行填充圖

圖5 用C語言顏色進行填充圖

6 結論

本文重點介紹了GIS中地圖著色問題，并將其轉化為計算機能表達的數據結構，接著介紹了其數據結構及其算法，然后用C語言給予了實現，最后展示了實現的結果。本程序也存在著不足，就是如何將其結果進行優化的問題，還有待進一步的研究。

［1］T CHEN，R SHIBASAKI.A Versatile AR Type 3D Mobile GIS Based on Image Navigation Technology。Systems，Man，and Cybernetica，1999.IEEE SMC’99 Conference Proceedings.1999 IEEE International Conference on 1999，8:1070～1075.

［2］Hardy pundt，Yaser Bishr，Domain On tologies for Data Sharing an Example from Environmental Monitoring Using Fiels GIS［J］.computers and Geosciences，2002，28(1):95 ～102.

［3］Congalton R G，Green K.Assessing the accuracy of remotely sensed data:Principles and practices［M］.New York:Lewis Publishers，1999.

［4］張乃孝.算法與數據結構—C語言描述［M］.北京:高等教育出版社，2002.

［5］何宗宜.地圖數據處理模型的原理與方法［M］.武漢:武漢大學出版社，2004.

［6］龔健雅.地理信息系統基礎.北京:科學出版社，2001.