跟据经纬度实现附近搜索Java实现
现在很多手机软件都用附近搜索功能,但具体是怎么实现的呢》
在网上查了很多资料,mysql空间数据库、矩形算法、geohash我都用过了,当数据上了百万之后mysql空间数据库方法是最强最精确的(查询前100条数据只需5秒左右)。
接下来推出一个原创计算方法,查询速度是mysql空间数据库算法的2倍
$lng是你的经度,$lat是你的纬度
SELECT lng,lat, (POWER(MOD(ABS(lng - $lng),360),2) + POWER(ABS(lat - $lat),2)) AS distance FROM `user_location` ORDER BY distance LIMIT 100
经测试,在100万数据中取前100条数据只需2.5秒左右。
####################################
另外的几种算法还是在这里展示一下:
一、距形算法
define(EARTH_RADIUS, 6371);//地球半径,平均半径为6371km /** *计算某个经纬度的周围某段距离的正方形的四个点 * *@param lng float 经度 *@param lat float 纬度 *@param distance float 该点所在圆的半径,该圆与此正方形内切,默认值为0.5千米 *@return array 正方形的四个点的经纬度坐标 */ function returnSquarePoint($lng, $lat,$distance = 0.5){ $dlng = 2 * asin(sin($distance / (2 * EARTH_RADIUS)) / cos(deg2rad($lat))); $dlng = rad2deg($dlng); $dlat = $distance/EARTH_RADIUS; $dlat = rad2deg($dlat); return array( 'left-top'=>array('lat'=>$lat + $dlat,'lng'=>$lng-$dlng), 'right-top'=>array('lat'=>$lat + $dlat, 'lng'=>$lng + $dlng), 'left-bottom'=>array('lat'=>$lat - $dlat, 'lng'=>$lng - $dlng), 'right-bottom'=>array('lat'=>$lat - $dlat, 'lng'=>$lng + $dlng) ); } //使用此函数计算得到结果后,带入sql查询。 $squares = returnSquarePoint($lng, $lat); $info_sql = "select id,locateinfo,lat,lng from `lbs_info` where lat<>0 and lat>{$squares['right-bottom']['lat']} and lat<{$squares['left-top']['lat']} and lng>{$squares['left-top']['lng']} and lng<{$squares['right-bottom']['lng']} ";
java代码如下:
/** * 默认地球半径 */ private static double EARTH_RADIUS = 6371; /** * 计算经纬度点对应正方形4个点的坐标 * * @param longitude * @param latitude * @param distance * @return */ public static Map<String, double[]> returnLLSquarePoint(double longitude, double latitude, double distance) { Map<String, double[]> squareMap = new HashMap<String, double[]>(); // 计算经度弧度,从弧度转换为角度 double dLongitude = 2 * (Math.asin(Math.sin(distance / (2 * EARTH_RADIUS)) / Math.cos(Math.toRadians(latitude)))); dLongitude = Math.toDegrees(dLongitude); // 计算纬度角度 double dLatitude = distance / EARTH_RADIUS; dLatitude = Math.toDegrees(dLatitude); // 正方形 double[] leftTopPoint = { latitude + dLatitude, longitude - dLongitude }; double[] rightTopPoint = { latitude + dLatitude, longitude + dLongitude }; double[] leftBottomPoint = { latitude - dLatitude, longitude - dLongitude }; double[] rightBottomPoint = { latitude - dLatitude, longitude + dLongitude }; squareMap.put("leftTopPoint", leftTopPoint); squareMap.put("rightTopPoint", rightTopPoint); squareMap.put("leftBottomPoint", leftBottomPoint); squareMap.put("rightBottomPoint", rightBottomPoint); return squareMap; }
二、 空间数据库算法
以下location字段是跟据经纬度来生成的空间数据,如:
location字段的type设为point
"update feed set location=GEOMFROMTEXT('point({$lat} {$lng})') where id='{$id}'"
mysql空间数据查询
SET @center = GEOMFROMTEXT('POINT(35.801559 -10.501577)'); SET @radius = 4000; SET @bbox = CONCAT('POLYGON((', X(@center) - @radius, ' ', Y(@center) - @radius, ',', X(@center) + @radius, ' ', Y(@center) - @radius, ',', X(@center) + @radius, ' ', Y(@center) + @radius, ',', X(@center) - @radius, ' ', Y(@center) + @radius, ',', X(@center) - @radius, ' ', Y(@center) - @radius, '))' ); SELECT id,lng,lat, SQRT(POW( ABS( X(location) - X(@center)), 2) + POW( ABS(Y(location) - Y(@center)), 2 )) AS distance FROM `user_location` WHERE 1=1 AND INTERSECTS( location, GEOMFROMTEXT(@bbox) ) AND SQRT(POW( ABS( X(location) - X(@center)), 2) + POW( ABS(Y(location) - Y(@center)), 2 )) < @radius ORDER BY distance LIMIT 20
三、geo算法
参考文档:
http://blog.csdn.net/wangxiafghj/article/details/9014363geohash 算法原理及实现方式
http://blog.charlee.li/geohash-intro/ geohash:用字符串实现附近地点搜索
http://blog.sina.com.cn/s/blog_7c05385f0101eofb.html 查找附近点--Geohash方案讨论
http://www.wubiao.info/372 查找附近的xxx 球面距离以及Geohash方案探讨
http://en.wikipedia.org/wiki/Haversine_formula Haversine formula球面距离公式
http://www.codecodex.com/wiki/Calculate_Distance_Between_Two_Points_on_a_Globe 球面距离公式代码实现
http://developer.baidu.com/map/jsdemo.htm#a6_1 球面距离公式验证
http://www.wubiao.info/470 Mysql or Mongodb LBS快速实现方案
geohash有以下几个特点:
首先,geohash用一个字符串表示经度和纬度两个坐标。某些情况下无法在两列上同时应用索引 (例如MySQL 4之前的版本,Google App Engine的数据层等),利用geohash,只需在一列上应用索引即可。
其次,geohash表示的并不是一个点,而是一个矩形区域。比如编码wx4g0ec19,它表示的是一个矩形区域。 使用者可以发布地址编码,既能表明自己位于北海公园附近,又不至于暴露自己的精确坐标,有助于隐私保护。
第三,编码的前缀可以表示更大的区域。例如wx4g0ec1,它的前缀wx4g0e表示包含编码wx4g0ec1在内的更大范围。 这个特性可以用于附近地点搜索。首先根据用户当前坐标计算geohash(例如wx4g0ec1)然后取其前缀进行查询 (SELECT * FROM place WHERE geohash LIKE 'wx4g0e%'),即可查询附近的所有地点。
查找附近网点geohash算法及实现 (Java版本),geohashjava
Geohash比直接用经纬度的高效很多。
Geohash算法实现(Java版本)
package com.DistTest; 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 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); } //中国地理坐标:东经73°至东经135°,北纬4°至北纬53° double lon = decode(lonset, 70, 140); double lat = decode(latset, 0, 60); return new double[] {lat, lon}; } private 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 String encode(double lat, double lon) { BitSet latbits = getBits(lat, 0, 60); BitSet lonbits = getBits(lon, 70, 140); 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 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)); } }
球面距离公式:
package com.DistTest; public class Test{ private static final double EARTH_RADIUS = 6371000;//赤道半径(单位m) /** * 转化为弧度(rad) * */ private static double rad(double d) { return d * Math.PI / 180.0; } /** * 基于googleMap中的算法得到两经纬度之间的距离,计算精度与谷歌地图的距离精度差不多,相差范围在0.2米以下 * @param lon1 第一点的精度 * @param lat1 第一点的纬度 * @param lon2 第二点的精度 * @param lat3 第二点的纬度 * @return 返回的距离,单位m * */ public static double GetDistance(double lon1,double lat1,double lon2, double lat2) { double radLat1 = rad(lat1); double radLat2 = rad(lat2); double a = radLat1 - radLat2; double b = rad(lon1) - rad(lon2); double s = 2 * Math.asin(Math.sqrt(Math.pow(Math.sin(a/2),2)+Math.cos(radLat1)*Math.cos(radLat2)*Math.pow(Math.sin(b/2),2))); s = s * EARTH_RADIUS; s = Math.round(s * 10000) / 10000; return s; } public static void main(String []args){ double lon1=109.0145193757; double lat1=34.236080797698; double lon2=108.9644583556; double lat2=34.286439088548; double dist; String geocode; dist=Test.GetDistance(lon1, lat1, lon2, lat2); System.out.println("两点相距:" + dist + " 米"); Geohash geohash = new Geohash(); geocode=geohash.encode(lat1, lon1); System.out.println("当前位置编码:" + geocode); geocode=geohash.encode(lat2, lon2); System.out.println("远方位置编码:" + geocode); } //wqj7j37sfu03h2xb2q97 /* 永相逢超市 108.83457500177 34.256981052624 wqj6us6cmkj5bbfj6qdg s6q08ubhhuq7 */ }
附近网点距离排序
package com.DistTest; import java.sql.DriverManager; import java.sql.ResultSet; import java.sql.SQLException; import java.sql.Connection; import java.sql.Statement; public class sqlTest { public static void main(String[] args) throws Exception { Connection conn = null; String sql; String url = "jdbc:mysql://132.97.**.**/test?" + "user=***&password=****&useUnicode=true&characterEncoding=UTF8"; try { Class.forName("com.mysql.jdbc.Driver");// 动态加载mysql驱动 // System.out.println("成功加载MySQL驱动程序"); // 一个Connection代表一个数据库连接 conn = DriverManager.getConnection(url); // Statement里面带有很多方法,比如executeUpdate可以实现插入,更新和删除等 Statement stmt = conn.createStatement(); sql = "select * from retailersinfotable limit 1,10"; ResultSet rs = stmt.executeQuery(sql);// executeQuery会返回结果的集合,否则返回空值 double lon1=109.0145193757; double lat1=34.236080797698; System.out.println("当前位置:"); int i=0; String[][] array = new String[10][3]; while (rs.next()){ //从数据库取出地理坐标 double lon2=Double.parseDouble(rs.getString("Longitude")); double lat2=Double.parseDouble(rs.getString("Latitude")); //根据地理坐标,生成geohash编码 Geohash geohash = new Geohash(); String geocode=geohash.encode(lat2, lon2).substring(0, 9); //计算两点间的距离 int dist=(int) Test.GetDistance(lon1, lat1, lon2, lat2); array[i][0]=String.valueOf(i); array[i][1]=geocode; array[i][2]=Integer.toString(dist); i++; // System.out.println(lon2+"---"+lat2+"---"+geocode+"---"+dist); } array=sqlTest.getOrder(array); //二维数组排序 sqlTest.showArray(array); //打印数组 } catch (SQLException e) { System.out.println("MySQL操作错误"); e.printStackTrace(); } finally { conn.close(); } } /* * 二维数组排序,比较array[][2]的值,返回二维数组 * */ public static String[][] getOrder(String[][] array){ for (int j = 0; j < array.length ; j++) { for (int bb = 0; bb < array.length - 1; bb++) { String[] ss; int a1=Integer.valueOf(array[bb][2]); //转化成int型比较大小 int a2=Integer.valueOf(array[bb+1][2]); if (a1>a2) { ss = array[bb]; array[bb] = array[bb + 1]; array[bb + 1] = ss; } } } return array; } /*打印数组*/ public static void showArray(String[][] array){ for(int a=0;a<array.length;a++){ for(int j=0;j<array[0].length;j++) System.out.print(array[a][j]+" "); System.out.println(); } } }
一直在琢磨LBS,期待可以发现更好的方案。现在纠结了。
简单列举一下已经了解到的方案:
1.sphinx geo索引
2.mongodb geo索引
3.mysql sql查询
4.mysql+geohash
5.redis+geohash
然后列举一下需求:
1.实时性要高,有频繁的更新和读取
2.可按距离排序支持分页
3.支持多条件筛选(一个经纬度数据还包含其他属性,比如社交系统的性别、年龄)
方案简单介绍:
1.sphinx geo索引
支持按照距离排序,并支持分页。但是尝试mva+geo失败,还在找原因。
无法满足高实时性需求。(可能是不了解实时增量索引配置有误)
资源占用小,速度快
2.mongodb geo索引
支持按照距离排序,并支持分页。支持多条件筛选。
可满足实时性需求。
资源占用大,数据量达到百万级请流量在10w左右查询速度明显下降。
3.mysql+geohash/ mysql sql查询
不支持按照距离排序(代价太大)。支持分页。支持多条件筛选。
可满足实时性需求。
资源占用中等,查询速度不及mongodb。
且geohash按照区块将球面转化平面并切割。暂时没有找到跨区块查询方法(不太了解)。
4.redis+geohash
geohash缺点不再赘述
不支持距离排序。支持分页查询。不支持多条件筛选。
可满足实时性需求。
资源占用最小。查询速度很快。
------update
补充一下测试机配置:
1TB SATA硬盘。8GB RAM。I3 2350 双核四线程