首页 > 代码库 > 搜索附近的人的搜索算法实现
搜索附近的人的搜索算法实现
随着移动终端的普及，很多应用都基于LBS功能，附近的某某（餐馆、银行、妹纸等等）。
基础数据中，一般保存了目标位置的经纬度；利用用户提供的经纬度，进行对比，从而获得是否在附近。
目标：
查找附近的XXX，由近到远返回结果，且结果中有与目标点的距离。
针对查找附近的XXX，方案如下：
Geohash算法；geohash是一种地址编码，它能把二维的经纬度编码成一维的字符串。
以下是具体实现的例子：
比如，成都永丰立交的编码是wm3yr31d2524
优点:
1、利用一个字段，即可存储经纬度；搜索时，只需一条索引，效率较高
2、编码的前缀可以表示更大的区域，查找附近的，非常方便。 SQL中，LIKE ‘wm3yr3%’，即可查询附近的所有地点。
3、通过编码精度可模糊坐标、隐私保护等。
缺点: 距离和排序需二次运算（筛选结果中运行，其实挺快）
具体算法步骤如下：
1、geohash的编码算法
成都永丰立交经纬度(30.63578,104.031601)
1.1、纬度范围(-90, 90)平分成两个区间(-90, 0)、(0, 90)，如果目标纬度位于前一个区间，则编码为0，否则编码为1。
由于30.625265属于(0, 90)，所以取编码为1。
然后再将(0, 90)分成 (0, 45), (45, 90)两个区间，而39.92324位于(0, 45)，所以编码为0，
然后再将(0, 45)分成 (0, 22.5), (22.5, 45)两个区间，而39.92324位于(22.5, 45)，所以编码为1，
依次类推可得永丰立交纬度编码为101010111001001000100101101010。
1.2、经度也用同样的算法，对(-180, 180)依次细分，(-180，0)、(0,180) 得出编码110010011111101001100000000000
1.3、合并经纬度编码，从高到低，先取一位经度，再取一位纬度；得出结果 111001001100011111101011100011000010110000010001010001000100
1.4、用0-9、b-z（去掉a, i, l, o）这32个字母进行base32编码，得到(30.63578,104.031601)的编码为wm3yr31d2524。
11100 10011 00011 11110 10111 00011 00001 01100 00010 00101 00010 00100 => wm3yr31d2524
十进制 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
2、具体匹配策略
1、在纬度和经度入库时，数据库新加一字段geohash，记录此点的geohash值
2、查找附近，利用 在SQL中 LIKE ‘wm3yr3%’；且此结果可缓存；在小区域内，不会因为改变经纬度，而重新数据库查询
3、查找出的有限结果，如需要求距离或者排序，可利用距离公式和二维数据排序；此时也是少量数据，会很快的。
import java.util.HashMap;
import java.util.Map;
public class GeoHashKit {
private static char[] base32 = { ‘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‘ };
private final static Map<Character, Integer> decodemap = new HashMap<Character, Integer>();
static {
int sz = base32.length;
for (int i = 0; i < sz; i++) {
decodemap.put(base32[i], i);
}
}
private static int precision = 10;
private static int[] bits = { 16, 8, 4, 2, 1 };
/**
* 设置精度
* @param int precision 设置精确位数，此参数决定了该算法的经度
*
* */
public static void setPrecision(int precision) {
GeoHashKit.precision = precision;
}
public static double getPrecision(double x, double precision) {
double base = Math.pow(10, -precision);
double diff = x % base;
return x - diff;
}
public static String encode(double latitude, double longitude) {
double[] lat_interval = { -90.0, 90.0 };
double[] lon_interval = { -180.0, 180.0 };
StringBuilder geohash = new StringBuilder();
boolean is_even = true;
int bit = 0, ch = 0;
while (geohash.length() < precision) {
double mid = 0.0;
if (is_even) {
mid = (lon_interval[0] + lon_interval[1]) / 2;
if (longitude > mid) {
ch |= bits[bit];
lon_interval[0] = mid;
} else {
lon_interval[1] = mid;
}
} else {
mid = (lat_interval[0] + lat_interval[1]) / 2;
if (latitude > mid) {
ch |= bits[bit];
lat_interval[0] = mid;
} else {
lat_interval[1] = mid;
}
}
is_even = is_even ? false : true;
if (bit < 4) {
bit++;
} else {
geohash.append(base32[ch]);
bit = 0;
ch = 0;
}
}
return geohash.toString();
}
public static double[] decode(String geohash) {
double[] ge = decode_exactly(geohash);
double lat, lon, lat_err, lon_err;
lat = ge[0];
lon = ge[1];
lat_err = ge[2];
lon_err = ge[3];
double lat_precision = Math.max(1, Math.round(-Math.log10(lat_err))) - 1;
double lon_precision = Math.max(1, Math.round(-Math.log10(lon_err))) - 1;
lat = getPrecision(lat, lat_precision);
lon = getPrecision(lon, lon_precision);
return new double[] { lat, lon };
}
public static double[] decode_exactly(String geohash) {
double[] lat_interval = { -90.0, 90.0 };
double[] lon_interval = { -180.0, 180.0 };
double lat_err = 90.0;
double lon_err = 180.0;
boolean is_even = true;
int sz = geohash.length();
int bsz = bits.length;
double latitude, longitude;
for (int i = 0; i < sz; i++) {
int cd = decodemap.get(geohash.charAt(i));
for (int z = 0; z < bsz; z++) {
int mask = bits[z];
if (is_even) {
lon_err /= 2;
if ((cd & mask) != 0) {
lon_interval[0] = (lon_interval[0] + lon_interval[1]) / 2;
} else {
lon_interval[1] = (lon_interval[0] + lon_interval[1]) / 2;
}
} else {
lat_err /= 2;
if ((cd & mask) != 0) {
lat_interval[0] = (lat_interval[0] + lat_interval[1]) / 2;
} else {
lat_interval[1] = (lat_interval[0] + lat_interval[1]) / 2;
}
}
is_even = is_even ? false : true;
}
}
latitude = (lat_interval[0] + lat_interval[1]) / 2;
longitude = (lon_interval[0] + lon_interval[1]) / 2;
return new double[] { latitude, longitude, lat_err, lon_err };
}
public static void main(String[] args) {
GeoHashKit ghf = new GeoHashKit();
String gc1 = ghf.encode(31.277631, 120.53916300000003);
String gc2 = ghf.encode(51.4797, -0.0124);
System.out.println(gc1);
System.out.println(gc2);
double[] gd1 = ghf.decode(gc1);
double[] gd2 = ghf.decode(gc2);
System.out.println(gd1[0] + ", " + gd1[1]);
System.out.println(gd2[0] + ", " + gd2[1]);
}
}