方法"/>
LBS 查询附近的方法
最近一直做LBS图片分享应用,针对查询附近feed一直比较头疼,现在把项目中遇到问题总结下。一、查询附近feed的方法:
1.1 通过距离直接sql法 1.2 mongoDb建立geo索引法 1.3 geohash 法 1.4 正方形近似距离法二、各种方法原理:
2.1 根据经纬度算距离公式,再根据距离排序查询。(参考 备注:个人认为这个人的距离公式有问题,通过改方法查询出来的经纬度和网上公式算出来结果有很大出入) 不追究距离公式,参考文章内容如下: 以下 SQL 语句将会在与坐标 37, -122 相距 25 英里的半径范围内查找最近的 20 个位置。该语句根据行的纬度/经度以及目标纬度/经度计算距离,然后只请求距离值小于 25 的行,最后再按距离对整个查询进行排序,并将查询结果限制为只显示 20 个。要按公里而非英里进行搜索,请将 3959 替换为 6371。
SELECT id, ( 3959 * acos( cos( radians(37) ) * cos( radians( lat ) ) * cos( radians( lng ) - radians(-122) ) + sin( radians(37) ) * sin( radians( lat ) ) ) ) AS distance FROM markers HAVING distance < 25 ORDER BY distance LIMIT 0 , 20;
2.2 mongoDb建立geo索引法(参考 +Indexing 备注:这个方法也是基于geohash的)
首先建立geo索引 :
db.places.ensureIndex( { loc : "2d" } , { bits : 26 } )
添加代码如下:
db.points.insert({ pos : { lon : -10, lat : -20 } })
查找代码如下:
db.places.find( { location : { $near : [50,50] }, category : 'coffee' } );
2.3 geohash算法:(参考 /)
geohash是一种地址编码,它能把二维的经纬度编码成一维的字符串。比如,北海公园的编码是wx4g0ec1。
geohash有以下几个特点:
首先,geohash用一个字符串表示经度和纬度两个坐标。某些情况下无法在两列上同时应用索引 (例如MySQL 4之前的版本,Google App Engine的数据层等),利用geohash,只需在一列上应用索引即可。
其次,geohash表示的并不是一个点,而是一个矩形区域。比如编码wx4g0ec19,它表示的是一个矩形区域。 使用者可以发布地址编码,既能表明自己位于北海公园附近,又不至于暴露自己的精确坐标,有助于隐私保护。
第三,编码的前缀可以表示更大的区域。例如wx4g0ec1,它的前缀wx4g0e表示包含编码wx4g0ec1在内的更大范围。 这个特性可以用于附近地点搜索。首先根据用户当前坐标计算geohash(例如wx4g0ec1)然后取其前缀进行查询 (SELECT * FROM place WHERE geohash LIKE 'wx4g0e%'
),即可查询附近的所有地点。
geohash的算法
下面以(39.92324, 116.3906)为例,介绍一下geohash的编码算法。首先将纬度范围(-90, 90)平分成两个区间(-90, 0)、(0, 90), 如果目标纬度位于前一个区间,则编码为0,否则编码为1。由于39.92324属于(0, 90),所以取编码为1。然后再将(0, 90)分成 (0, 45), (45, 90)两个区间,而39.92324位于(0, 45),所以编码为0。以此类推,直到精度符合要求为止,得到纬度编码为1011 1000 1100 0111 1001。
纬度范围 | 划分区间0 | 划分区间1 | 39.92324所属区间 |
(-90, 90) | (-90, 0.0) | (0.0, 90) | 1 |
(0.0, 90) | (0.0, 45.0) | (45.0, 90) | 0 |
(0.0, 45.0) | (0.0, 22.5) | (22.5, 45.0) | 1 |
(22.5, 45.0) | (22.5, 33.75) | (33.75, 45.0) | 1 |
(33.75, 45.0) | (33.75, 39.375) | (39.375, 45.0) | 1 |
(39.375, 45.0) | (39.375, 42.1875) | (42.1875, 45.0) | 0 |
(39.375, 42.1875) | (39.375, 40.7812) | (40.7812, 42.1875) | 0 |
(39.375, 40.7812) | (39.375, 40.0781) | (40.0781, 40.7812) | 0 |
(39.375, 40.0781) | (39.375, 39.7265) | (39.7265, 40.0781) | 1 |
(39.7265, 40.0781) | (39.7265, 39.9023) | (39.9023, 40.0781) | 1 |
(39.9023, 40.0781) | (39.9023, 39.9902) | (39.9902, 40.0781) | 0 |
(39.9023, 39.9902) | (39.9023, 39.9462) | (39.9462, 39.9902) | 0 |
(39.9023, 39.9462) | (39.9023, 39.9243) | (39.9243, 39.9462) | 0 |
(39.9023, 39.9243) | (39.9023, 39.9133) | (39.9133, 39.9243) | 1 |
(39.9133, 39.9243) | (39.9133, 39.9188) | (39.9188, 39.9243) | 1 |
(39.9188, 39.9243) | (39.9188, 39.9215) | (39.9215, 39.9243) | 1 |
经度也用同样的算法,对(-180, 180)依次细分,得到116.3906的编码为1101 0010 1100 0100 0100。
经度范围 | 划分区间0 | 划分区间1 | 116.3906所属区间 |
(-180, 180) | (-180, 0.0) | (0.0, 180) | 1 |
(0.0, 180) | (0.0, 90.0) | (90.0, 180) | 1 |
(90.0, 180) | (90.0, 135.0) | (135.0, 180) | 0 |
(90.0, 135.0) | (90.0, 112.5) | (112.5, 135.0) | 1 |
(112.5, 135.0) | (112.5, 123.75) | (123.75, 135.0) | 0 |
(112.5, 123.75) | (112.5, 118.125) | (118.125, 123.75) | 0 |
(112.5, 118.125) | (112.5, 115.312) | (115.312, 118.125) | 1 |
(115.312, 118.125) | (115.312, 116.718) | (116.718, 118.125) | 0 |
(115.312, 116.718) | (115.312, 116.015) | (116.015, 116.718) | 1 |
(116.015, 116.718) | (116.015, 116.367) | (116.367, 116.718) | 1 |
(116.367, 116.718) | (116.367, 116.542) | (116.542, 116.718) | 0 |
(116.367, 116.542) | (116.367, 116.455) | (116.455, 116.542) | 0 |
(116.367, 116.455) | (116.367, 116.411) | (116.411, 116.455) | 0 |
(116.367, 116.411) | (116.367, 116.389) | (116.389, 116.411) | 1 |
(116.389, 116.411) | (116.389, 116.400) | (116.400, 116.411) | 0 |
(116.389, 116.400) | (116.389, 116.394) | (116.394, 116.400) | 0 |
接下来将经度和纬度的编码合并,奇数位是纬度,偶数位是经度,得到编码 11100 11101 00100 01111 00000 01101 01011 00001。
最后,用0-9、b-z(去掉a, i, l, o)这32个字母进行base32编码,得到(39.92324, 116.3906)的编码为wx4g0ec1。
十进制 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
base32 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | b | c | d | e | f | g |
十进制 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
base32 | h | j | k | m | n | p | q | r | s | t | u | v | w | x | y | z |
解码算法与编码算法相反,先进行base32解码,然后分离出经纬度,最后根据二进制编码对经纬度范围进行细分即可,这里不再赘述。 不过由于geohash表示的是区间,编码越长越精确,但不可能解码出完全一致的地址。
geohash的应用:附近地址搜索
geohash的最大用途就是附近地址搜索了。不过,从geohash的编码算法中可以看出它的一个缺点:位于格子边界两侧的两点, 虽然十分接近,但编码会完全不同。实际应用中,可以同时搜索当前格子周围的8个格子,即可解决这个问题。
以geohash的python库为例,相关的geohash操作如下:
>>> import geohash
>>> geohash.encode(39.92324, 116.3906, 5) # 编码,5表示编码长度
'wx4g0'
>>> geohash.expand('wx4g0') # 求wx4g0格子及周围8个格子的编码
['wx4ep', 'wx4g1', 'wx4er', 'wx4g2', 'wx4g3', 'wx4dz', 'wx4fb', 'wx4fc', 'wx4g0']
最后,我们来看看本文开头提出的两个问题:速度慢,缓存命中率低。使用geohash查询附近地点,用的是字符串前缀匹配:
SELECT * FROM place WHERE geohash LIKE 'wx4g0%';
而前缀匹配可以利用geohash列上的索引,因此查询速度不会太慢。另外,即使用户坐标发生微小的变化, 也能编码成相同的geohash,这就保证了每次执行相同的SQL语句,使得缓存命中率大大提高。
geohash java源码:
package com.outin.utils; import java.util.BitSet; import java.util.HashMap;public class Geohash { private static int numbits = 6 * 5; final static char[] digits = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' }; final static HashMap<Character, Integer> lookup = new HashMap<Character, Integer>(); static { int i = 0; for (char c : digits) lookup.put(c, i++); } public static void main(String[] args) { double[] latlon = Geohash.decode("dj248j248j24"); System.out.println(latlon[0] + " " + latlon[1]); String s = Geohash.encode(30, -90.0); System.out.println(s); latlon = Geohash.decode(s); System.out.println(latlon[0] + ", " + latlon[1]); } public static double[] decode(String geohash) { StringBuilder buffer = new StringBuilder(); for (char c : geohash.toCharArray()) { int i = lookup.get(c) + 32; buffer.append( Integer.toString(i, 2).substring(1) ); } BitSet lonset = new BitSet(); BitSet latset = new BitSet(); //even bits int j =0; for (int i=0; i< numbits*2;i+=2) { boolean isSet = false; if ( i < buffer.length() ) isSet = buffer.charAt(i) == '1'; lonset.set(j++, isSet); } //odd bits j=0; for (int i=1; i< numbits*2;i+=2) { boolean isSet = false; if ( i < buffer.length() ) isSet = buffer.charAt(i) == '1'; latset.set(j++, isSet); } double lon = decode(lonset, -180, 180); double lat = decode(latset, -90, 90); return new double[] {lat, lon}; } private static double decode(BitSet bs, double floor, double ceiling) { double mid = 0; for (int i=0; i<bs.length(); i++) { mid = (floor + ceiling) / 2; if (bs.get(i)) floor = mid; else ceiling = mid; } return mid; } public static String encode(double lat, double lon) { BitSet latbits = getBits(lat, -90, 90); BitSet lonbits = getBits(lon, -180, 180); StringBuilder buffer = new StringBuilder(); for (int i = 0; i < numbits; i++) { buffer.append( (lonbits.get(i))?'1':'0'); buffer.append( (latbits.get(i))?'1':'0'); } return base32(Long.parseLong(buffer.toString(), 2)); } private static BitSet getBits(double lat, double floor, double ceiling) { BitSet buffer = new BitSet(numbits); for (int i = 0; i < numbits; i++) { double mid = (floor + ceiling) / 2; if (lat >= mid) { buffer.set(i); floor = mid; } else { ceiling = mid; } } return buffer; } public static String base32(long i) { char[] buf = new char[65]; int charPos = 64; boolean negative = (i < 0); if (!negative) i = -i; while (i <= -32) { buf[charPos--] = digits[(int) (-(i % 32))]; i /= 32; } buf[charPos] = digits[(int) (-i)]; if (negative) buf[--charPos] = '-'; return new String(buf, charPos, (65 - charPos)); }}
2.4 正方形近似距离法( 参考 :/)
球面最短距离公式
球面上任意两点之间的距离计算公式可以参考维基百科上的下述文章,这里就不再赘述了。
- Great-circle distance
- Haversine formula
值得一提的是,维基百科推荐使用Haversine公式,理由是Great-circle distance公式用到了大量余弦函数, 而两点间距离很短时(比如地球表面上相距几百米的两点),余弦函数会得出0.999…的结果, 会导致较大的舍入误差。而Haversine公式采用了正弦函数,即使距离很小,也能保持足够的有效数字。 以前采用三角函数表计算时的确会有这个问题,但经过实际验证,采用计算机来计算时,两个公式的区别不大。 稳妥起见,这里还是采用Haversine公式。
其中
- R为地球半径,可取平均值 6371km;
- φ1, φ2 表示两点的纬度;
- Δλ 表示两点经度的差值。
距离计算函数
下面就是计算球面间两点(lat0, lng)-(lat1, lng1)之间距离的函数。
from math import sin, asin, cos, radians, fabs, sqrt EARTH_RADIUS=6371 # 地球平均半径,6371km def hav(theta): s = sin(theta / 2) return s * s def get_distance_hav(lat0, lng0, lat1, lng1): "用haversine公式计算球面两点间的距离。" # 经纬度转换成弧度 lat0 = radians(lat0) lat1 = radians(lat1) lng0 = radians(lng0) lng1 = radians(lng1) dlng = fabs(lng0 - lng1) dlat = fabs(lat0 - lat1) h = hav(dlat) + cos(lat0) * cos(lat1) * hav(dlng) distance = 2 * EARTH_RADIUS * asin(sqrt(h)) return distance
范围搜索算法
在庞大的地理数据库中搜索地点,索引是很重要的。但是,我们的需求是搜索附近地点, 例如,坐标(39.91, 116.37)附近500米内有什么地点?搜索条件是地点坐标与当前坐标之间的距离, 显然是无法应用索引的。
那么换个思路:首先算出“给定坐标附近500米”这个范围的坐标范围。 虽然它是个圆,但我们可以先求出该圆的外接正方形,然后拿正方形的经纬度范围去搜索数据库。
如图,红色部分为要求的搜索范围,绿色部分为实际搜索范围。
先来求东西两侧的的范围边界。在haversin公式中令φ1 = φ2,可得
写成python代码就是
dlng = 2 * asin(sin(distance / (2 * EARTH_RADIUS)) / cos(lat)) dlng = degrees(dlng) # 弧度转换成角度
然后求南北两侧的范围边界,在haversin公式中令 Δλ = 0,可得
写成python代码就是
dlat = distance / EARTH_RADIUS dlng = degrees(dlat) # 弧度转换成角度
这样,根据当前点坐标,我们可以得出搜索范围为
left-top : (lat + dlat, lng - dlng) right-top : (lat + dlat, lng + dlng) left-bottom : (lat - dlat, lng - dlng) right-bottom: (lat - dlat, lng + dlng)
然后利用这个范围构造SQL语句,即可实现范围查询:
SELECT * FROM place WHERE lat > lat1 AND lat < lat2 AND lng > lng1 AND lng < lng2;
在lat
和lng
列上建立索引,能从一定程度上提高范围查询的效率。
不过,这样查询到的地点是正方形范围内的地点,一些结果与当前点的距离可能会超出给定的距离。 如果要求严格,可以遍历结果并计算与当前点之间的距离,并过滤掉不符合要求的结果。
三、上面方法存在的问题
3.1 通过距离直接sql法问题
这个方法问题非常明显,就是查询效率很低,如果不想引入新的依赖包(如:mongoDB)并数据很小,可以采用该方法, 当然最好在上层加个缓存。
3.2 mongoDb建立geo索引法
项目引进该开源项目主要是因为有附近的应用需求,说实话在使用过程中对mongoDb非常失望。
1. mongoDb 在数据很大时,查询很慢,因此,不要把所以数据都放入mongoDB中,建议key尽量短。
2. mongoDb 进行geo查询排序翻页时,好像存在bug。
3.为了提高mongoDb 的查询效率,在mongoDB上层添加了redis缓存,因此,存在添加时更新问题,mongoDB数据和 redis缓存数据统一性问题(如存储数目不一致)。
3.3 geohash 方法
一直感觉这个方法挺靠谱的,由于项目早期是另一个同事用mongoDB实现的,前期大部分项目代码都没采用该方法,该方法在大数据量的情况下是有问题的,因此,可以在该方案的上层添加redis进行缓存。添加缓存之后,会引入另一个问题,就 是添加新数据时,怎么把该数据添加到缓存中。(该方案的解决方法,是redis中key只取geohash前几位)。当然该方案还存在一个问题,不能保证查询附近所有数据,只能保证查询出来的数据是附近的点。因为在geohash划分边界,两个相邻点被划分到不同区域。
这个方案的问题:
1、怎么进行查询时排序,而不是查询完之后排序,如果数据量很大是,把大量数据放入内存中排序,即影响又占用内存
2、不能精确查询,如附近1000m
3.4 正方形近似距离法
这个方法个人认为也比较靠谱,在小数据量的情况下,完全可用该方案。在大数据量时,可以在上层加人缓存,但是怎么 进行添加时,缓存更新呢?如果你有好的办法请告诉我。
小结
个人对倾向第三种方法。
基于LBS的不确定性应用开发
2012-10-04 10:09:59| 分类: 默认分类|字号 订阅
自从有了手机,基于地理位置的应用越来越多,如:微信,陌陌,大众点评。我所在的公司也光荣的加人了这一行业,公司应用下载地址:。因此,有必要总结下这段时间的经验。
刚开始,我们以为只要通过GPS活动经纬度,接着从第三方POI活动具体地理信息,LBS就完结了,但是在开发中发现这其中有很多难以处理的问题,如:手机获得经纬度不准确(iphone手机每次获得经纬度值不一样,经纬度之间有一定误差)。通过经纬度获得附近信息,无法做缓存,经纬度时刻在变化,只能缓存附近建筑物,数据存储问题,目前能存储地理位置的数据库只有MongoDB,但是MongoDB存在附近位置排序问题,网上有种基于GeoHash的mysql存储,但是该方案存在当数据量大时,分表分库的问题。
首先说说网上的几种地理位置存储策略。
1、mysql数据库存储(参考文档:/)
2、基于GeoHash的mysql数据存储(参考文档:/)。
3、mysql空间存储(参考文档:.1/zh/spatial-extensions-in-mysql.html)。
4、MongoDB的数据存储(参考文档:/)。
这几种存储方案的优劣(第三种方案之前没了解过,此处不做评价):
方法1 优点:理解和使用起来方便,不需要了解更多知识。缺点:当数据稍微大点,就马上会出现性能瓶颈。
方法2 优点:相对方法1查询速率大幅提高,学习和实现成本比较低。缺点:当数据到达一定级别之后的分表和分库方案难以实现,这种查询不是100准确。测评数据参考 。基于JAVA的GeoHash源码如下: .java?r=104
方法3 优点:是针对Geo专门设计滴,它滴主从原理能在一定程度上解决大数据查询问题。缺点:存储排序查询问题,学习成本很高,当占用内存较大时,存在查询慢的问题,建议减少key长度,如果有字段是唯一的,建议设置为document_id。
具体项目中选择哪种方案,还得看具体项目,如果数据量比较小,在一个相当长时间不会产生大数据,可以使用方案1.数据量千万级别滴,可以考虑用方案2,数据量非常大,建议用MongoDB。
接着说说各种POI服务。
我调研过的POI提供商有:街旁,Google,Foursquare。
我们开发的应用主要是针对国外市场,当希望中国地理信息能尽量显示中文。
国外的POI :
Google 优点:通过经纬度获得城市和国家信息非常准确,速度很快。缺点:POI信息不够全面,大部分是基于地理位置的,地点之间没有热度区分。因此,在我们应用中,关键用Google获得城市和国家信息
Foursquare 优点:POI信息比较全面,path等第三方使用数据相对比较准确。缺点:一些地点获得的维度信息为0,城市和国家信息有的会为空。
国内POI:
街旁 优点:国内POI信息非常准确,缺点:服务器不够稳定(一次api版本从1.0升级为2.0获得的数据完全不准确,之后和他们沟通,发现是程序有问题),服务器反应非常慢(经过我们测试,服务器有时请求会间隔15-30s才响应)
baidu等类似第三方地图提供接口:缺点:都存在和Google同样问题。
最后,国内POI信息,还是决定从Foursquare获取。
outin应用中有这样一个需求:
首页显示用户当前建筑物,点击当前位置,进入附近建筑物,用户修改当前建筑物。
在次,我们讨论提出了两个方案:
1、后台线程间隔一定时间,获取经纬度获得附近建筑物信息。
2、用户每次获取信息时,通过用户当前建筑物经纬度和实际经纬度判断是否在一定阀值范围内,从而决定是否需要修改当前经纬度。
分析这两个方案的优劣:
方案1:
优点:相对适时的获得用户当前附近建筑物(关键看时间间隔如何获取,建议采用斐波那契数列)。缺点:建筑物的准确性依赖于所选的时间间隔。(街旁是采用该种方案)
方案2:
优点:用户获得附近数据,都是在刷新时进行的,因此,获取数据时正确的。缺点:如果用户不刷新页面,当前建筑物数据将是错误的。
通过地理位置查附近新鲜事可参考:
更多推荐
LBS 查询附近的方法
发布评论