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

在很早以前,就通过地图 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 索引,可以非常方便的找到临近的点。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

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

作者

张巍

发布于

2016-07-04

更新于

2016-07-04

许可协议

评论