poi 附近搜索

原创
2016/06/08 17:24
阅读数 45

简单列举一下已经了解到的方案:
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缺点不再赘述
不支持距离排序。支持分页查询。不支持多条件筛选。
可满足实时性需求。
资源占用最小。查询速度很快。

SQL:

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秒左右。

距形算法:

/**

 * 默认地球半径

 */

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;

}

 

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));

        }
 
}

 

展开阅读全文
打赏
0
0 收藏
分享

作者的其它热门文章

加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部