据经纬度实现附近搜索Java实现

快来打我* 2021-12-14 10:07 429阅读 0赞

*本文转载自* *[http://hai0378.iteye.com/blog/2213829][http_hai0378.iteye.com_blog_2213829]*

现在很多手机软件都用附近搜索功能，但具体是怎么实现的呢？  
在网上查了很多资料，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版本）* ##

*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 双核四线程。

转载于:https://www.cnblogs.com/gaorongyi/p/9397239.html

[http_hai0378.iteye.com_blog_2213829]: http://hai0378.iteye.com/blog/2213829