简单的坐标转省市区的算法
在很早以前,就通过地图 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 | collection.area.find({'gps': {'$near': {'lat': lat, 'lng': lng}}, 'leaf_note': 1}).limit(4) |
找到临近点后,只需要循环算一下点在哪个区域内,这个算法是在入坑前就找到的,原理就是从目录点随便引出一条射线,如果射线与围栏区域的交点是奇数个,那么这个点就在区域内,算法代码如下:
1 | def boundary(p, points): |
然后这个没几行代码、简单、快速、不占用什么存储、方便移植到其他语言的计算方法就算完成了。当然中间还有些细节的考虑
简单的坐标转省市区的算法