基于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.