简单的坐标转省市区的算法

在很早以前，就通过地图 api 抓取的相关的省市区信息，其中有一个字段是 polylines ，里面是一组 gps 的坐标。为了离线来根据 gps 坐标获取省市区的信息，最开始想到的是使用 geohash 来计算出每个区域所包含的hash值，把所有的hash值存下来，这样查询变成了键值查询，如果 geohash精确到第8位，值偏差大概是19米，这个精度已经在我所能够承受的范围内了。

于是，写了点代码跑了一下东城区围栏的 geohash，然后把区域在一起的32个值去掉一位，向前递进。最后得到了 5000 多个值，也就是用 5000 多个 geohash 的值可以表示出东城区整个区域，整个程序执行了 5 分钟左右，用笔在纸上算了一下全国的区县，按照这个规模，hash 值数量大概在亿的基本，这个也是存储能够接受的。

于是拿海淀区的围栏试了试，计算时间成倍增长，这个计算速度，估计今年底能算完就不错了，然后想了想改进的算法，从 geohash 5位开始算起，理论上能快一个数量级，实际上呢，地图区域不是规则的，计算速度依然不能够满足需要。

需要重新考虑计算方法，看着这一堆的数据表，数据表中有个 center 的字段，突然发现计算一个点是否在围栏里面的算法是线性的，也就是算法负责度为O(n).于是马上改变了思路。

计算方法，首先找到给坐标（x,y)点最近的4个区域，然后计算点在哪个区域里。

那么整么才能找到给定坐标的最近的点呢，这里就要请出 mongodb ，利用 mongodb 的 2d 索引，可以非常方便的找到临近的点。

collection.area.find({'gps': {'$near': {'lat': lat, 'lng': lng}}, 'leaf_note': 1}).limit(4)

找到临近点后，只需要循环算一下点在哪个区域内，这个算法是在入坑前就找到的，原理就是从目录点随便引出一条射线，如果射线与围栏区域的交点是奇数个，那么这个点就在区域内，算法代码如下：

def boundary(p, points):
    '''
    计算方法：射线法  从内部发出一条射线，判断与边的交点个数

    计算点是否在区域内

    算法来源 http://stackoverflow.com/questions/8721406/how-to-determine-if-a-point-is-inside-a-2d-convex-polygon
    '''
    result = False

    i = 0
    j = len(points) - 1

    while i < len(points):
        if (points[i].y > p.y) != (points[j].y > p.y) and (p.x < (points[j].x - points[i].x) * (p.y - points[i].y) / (points[j].y - points[i].y) + points[i].x):
            result = not result
        j = i
        i = i + 1

    return result

然后这个没几行代码、简单、快速、不占用什么存储、方便移植到其他语言的计算方法就算完成了。当然中间还有些细节的考虑