「笔记」省市县四色地图实现记录

算法

上一篇说过四色定理的算法，套三层循环找出最佳方案。

// 行政区划详情
type sqlStruct struct {
    name string
    grade int
    code string
    geom string
    color int
}

// arr行政区划相邻状况
// record 四色分布
// length 行政区划总数
// data 行政区划详情列表
func colorSetting(arr [][]int, record []int, length int, data map[int]sqlStruct){
    // 位置序号
    cur := 1
    // 颜色序号
    color := 1
    // 初始化颜色
    record[0] = 1
    for {
        if cur >= length {
            // 计算结束打印结果
            log.Debug("%v", record)
            break
        }
        for {
            // 通过日志观察计算
            log.Debug("cur, color, name: %v %v %v", cur, color, data[cur].name)
            if color > 4 || cur >= length || data[cur].color != 0 {
                break
            }
            k := 0
            for ; k < cur; k++ {
                if arr[cur][k] == 1 && record[k] == color {
                    break
                }
            }
            if k < cur {
                color++
            } else {
                record[cur] = color
                color++
                color = 1
            }
        }
        if color > 4 && data[cur].color != 9 {
            // 跳过难算的
            cur--
            color = record[cur] + 1   
        } else if data[cur].color == 9 {
            // 跳过难算的
            cur++
            color =1
        } else if data[cur].grade != 0 {
            // 跳过算过的，要小心不能随便覆盖
            record[cur] = data[cur].color
            cur++
            color = record[cur] + 1
        }
    }
}

这个算法的优点是计算量小时能快速得出结果，比如省份。但遇到市级乃至县级，你就等服务器猴年马月给你跑出结果吧。我这里说的市和县的四色是显示全国的，而不是某个省。我国市级行政单位有约380个，县级约2800个，可想而知这计算量有多大了。

过程

解决方案谈不上有多快，毕竟我把省市县颜色全算出来花了一周。

数据来源自天地图。解析shp文件后，能拿到行政等级grade字段，其中1、2、3分别表示省、市、县/区。code就是行政区划编了，前一篇也讲过，省以下的编码基本按身份证前六位数来的。数据全存入数据库中，并新增color字段用来存颜色。

首先根据省市县的不同，机算过程也不同。顺序为：市→省→县。我国有省级市、市级县等区划等级，天地图并不会重复给某一层的数据，比如查grade=2时，北京、上海、重庆等行政区划是查不到的，所以查市时我会加上这几个特殊行政区划的code一起查。

市：

1. 直接算全国的市，机算过程中跳过难算的行政单位，将它的颜色改成9（随手定的，你也可以自己定）
2. 机算完毕后，前端获取数据绘制所有市级区划，能直观看到跳过的区划在哪里
3. 人为补充修改所有颜色，注意某些区划是拆开的，改动后对周围区划颜色的影响很大
4. 大概一个下午能得出结果

省

1. 直接机算全国的省，应该不会卡，能直接得出结果
2. 前端界面查看北京、重庆、上海等地附近的区划颜色是否需要重复，手动修改就结束了

县/区

县的四色需要根据省份拆分计算。此处依据code查出不同省下的县/区。

// 北京所有区的头两位数都是11，模糊查询匹配
select code,name,grade,color from table where grade=3 and code like '11%' order by code

1. 先从中国内陆地区计算，比如湖北、陕西等地
2. 机算、跳过等步骤都和上面说的一样
3. 每机算出一个省，和邻省颜色比较，修改重合颜色
4. 天地图数据中，南昌市西湖区这块不符合四色定理，自行想办法解决吧
5. 忽略南昌市，全中国的县都能用四色绘制
6. 用时大约三天