对于很多初学者来说,“附近的人”或者类似功能,在技术实现上还有点摸不着头脑。本文将简要的为你讲解“附近的人”的基本理论原理,并以redis的GEO系列地理位置操作指令为例,理论联系实际地为你讲解它们是如何被高效实现的。
阅读提示:本文适合有一定Redis使用经验和经纬度知识的服务器后端开发人员阅读。
以经纬度值:(116.389550, 39.928167)进行算法说明,对纬度39.928167进行逼近编码 (地球纬度区间是[-90,90])
它需要做以下两件事情:
1)在使用“附近的人”功能前提交自己的地理位置;
2)根据“我”的地理位置,计算出别人跟我的距离;
3)将第2步中计算出的距离由近及远,进行排序。
具体在产品技术上的实现原理和技术难点
1)现在移动端(IOS、Android等),通过系统的API很容易抓到用户当前的位置(即经纬度数据);
2)根据第1步中的经纬度数据,很容易计算出两个点之间的距离
3)对第2步中的计算结果排序就更简单了。
技术难点
1)如何高效地进行两点距离的计算
2)如何高效地进行地理围栏的圈定
public class GeoHash {
public static final double MINLAT = -90;
public static final double MAXLAT = 90;
public static final double MINLNG = -180;
public static final double MAXLNG = 180;
private static int numbits = 3 * 5; //经纬度单独编码长度
private static double minLat;
private static double minLng;
private 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 GeoHash(){
setMinLatLng();
}
public 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');
}
String code = base32(Long.parseLong(buffer.toString(), 2));
//Log.i("okunu", "encode lat = " + lat + " lng = " + lon + " code = " + code);
return code;
}
public ArrayList<String> getArroundGeoHash(double lat, double lon){
//Log.i("okunu", "getArroundGeoHash lat = " + lat + " lng = " + lon);
ArrayList<String> list = new ArrayList<>();
double uplat = lat + minLat;
double downLat = lat - minLat;
double leftlng = lon - minLng;
double rightLng = lon + minLng;
String leftUp = encode(uplat, leftlng);
list.add(leftUp);
String leftMid = encode(lat, leftlng);
list.add(leftMid);
String leftDown = encode(downLat, leftlng);
list.add(leftDown);
String midUp = encode(uplat, lon);
list.add(midUp);
String midMid = encode(lat, lon);
list.add(midMid);
String midDown = encode(downLat, lon);
list.add(midDown);
String rightUp = encode(uplat, rightLng);
list.add(rightUp);
String rightMid = encode(lat, rightLng);
list.add(rightMid);
String rightDown = encode(downLat, rightLng);
list.add(rightDown);
//Log.i("okunu", "getArroundGeoHash list = " + list.toString());
return list;
}
//根据经纬度和范围,获取对应的二进制
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;
}
//将经纬度合并后的二进制进行指定的32位编码
private 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));
}
private void setMinLatLng() {
minLat = MAXLAT - MINLAT;
for (int i = 0; i < numbits; i++) {
minLat /= 2.0;
}
minLng = MAXLNG - MINLNG;
for (int i = 0; i < numbits; i++) {
minLng /= 2.0;
}
}
//根据二进制和范围解码
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 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();
//偶数位,经度
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);
}
//奇数位,纬度
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};
}
public static void main(String[] args) throws Exception{
GeoHash geohash = new GeoHash();
// String s = geohash.encode(40.222012, 116.248283);
// System.out.println(s);
geohash.getArroundGeoHash(40.222012, 116.248283);
// double[] geo = geohash.decode(s);
// System.out.println(geo[0]+" "+geo[1]);
}
}
xxxxxxxxxxbr public class GeoHash {brpublic static final double MINLAT = -90;brpublic static final double MAXLAT = 90;brpublic static final double MINLNG = -180;brpublic static final double MAXLNG = 180;brbrprivate static int numbits = 3 * 5; //经纬度单独编码长度brbrprivate static double minLat;brprivate static double minLng;brbrprivate final static char[] digits = { '0', '1', '2', '3', '4', '5', '6', '7', '8',br '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n', 'p',br 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };brbr//定义编码映射关系brfinal static HashMap<Character, Integer> lookup = new HashMap<Character, Integer>();br//初始化编码映射内容brstatic {br int i = 0;br for (char c : digits)br lookup.put(c, i++);br}brbrpublic GeoHash(){br setMinLatLng();br}brbrpublic String encode(double lat, double lon) {br BitSet latbits = getBits(lat, -90, 90);br BitSet lonbits = getBits(lon, -180, 180);br StringBuilder buffer = new StringBuilder();br for (int i = 0; i < numbits; i++) {br buffer.append( (lonbits.get(i))?'1':'0');br buffer.append( (latbits.get(i))?'1':'0');br }br String code = base32(Long.parseLong(buffer.toString(), 2));br //Log.i("okunu", "encode lat = " + lat + " lng = " + lon + " code = " + code);br return code;br}brbrpublic ArrayList<String> getArroundGeoHash(double lat, double lon){br //Log.i("okunu", "getArroundGeoHash lat = " + lat + " lng = " + lon);br ArrayList<String> list = new ArrayList<>();br double uplat = lat + minLat;br double downLat = lat - minLat;brbr double leftlng = lon - minLng;br double rightLng = lon + minLng;brbr String leftUp = encode(uplat, leftlng);br list.add(leftUp);brbr String leftMid = encode(lat, leftlng);br list.add(leftMid);brbr String leftDown = encode(downLat, leftlng);br list.add(leftDown);brbr String midUp = encode(uplat, lon);br list.add(midUp);brbr String midMid = encode(lat, lon);br list.add(midMid);brbr String midDown = encode(downLat, lon);br list.add(midDown);brbr String rightUp = encode(uplat, rightLng);br list.add(rightUp);brbr String rightMid = encode(lat, rightLng);br list.add(rightMid);brbr String rightDown = encode(downLat, rightLng);br list.add(rightDown);brbr //Log.i("okunu", "getArroundGeoHash list = " + list.toString());br return list;br}brbr//根据经纬度和范围,获取对应的二进制brprivate BitSet getBits(double lat, double floor, double ceiling) {br BitSet buffer = new BitSet(numbits);br for (int i = 0; i < numbits; i++) {br double mid = (floor + ceiling) / 2;br if (lat >= mid) {br buffer.set(i);br floor = mid;br } else {br ceiling = mid;br }br }br return buffer;br}brbr//将经纬度合并后的二进制进行指定的32位编码brprivate String base32(long i) {br char[] buf = new char[65];br int charPos = 64;br boolean negative = (i < 0);br if (!negative){br i = -i;br }br while (i <= -32) {br buf[charPos--] = digits[(int) (-(i % 32))];br i /= 32;br }br buf[charPos] = digits[(int) (-i)];br if (negative){br buf[--charPos] = '-';br }br return new String(buf, charPos, (65 - charPos));br}brbrprivate void setMinLatLng() {br minLat = MAXLAT - MINLAT;br for (int i = 0; i < numbits; i++) {br minLat /= 2.0;br }br minLng = MAXLNG - MINLNG;br for (int i = 0; i < numbits; i++) {br minLng /= 2.0;br }br}brbr//根据二进制和范围解码brprivate double decode(BitSet bs, double floor, double ceiling) {br double mid = 0;br for (int i=0; i<bs.length(); i++) {br mid = (floor + ceiling) / 2;br if (bs.get(i))br floor = mid;br elsebr ceiling = mid;br }br return mid;br}brbr//对编码后的字符串解码brpublic double[] decode(String geohash) {br StringBuilder buffer = new StringBuilder();br for (char c : geohash.toCharArray()) {br int i = lookup.get(c) + 32;br buffer.append( Integer.toString(i, 2).substring(1) );br }brbr BitSet lonset = new BitSet();br BitSet latset = new BitSet();brbr //偶数位,经度br int j =0;br for (int i=0; i< numbits*2;i+=2) {br boolean isSet = false;br if ( i < buffer.length() )br isSet = buffer.charAt(i) == '1';br lonset.set(j++, isSet);br }brbr //奇数位,纬度br j=0;br for (int i=1; i< numbits*2;i+=2) {br boolean isSet = false;br if ( i < buffer.length() )br isSet = buffer.charAt(i) == '1';br latset.set(j++, isSet);br }brbr double lon = decode(lonset, -180, 180);br double lat = decode(latset, -90, 90);brbr return new double[] {lat, lon};br}brbrpublic static void main(String[] args) throws Exception{br GeoHash geohash = new GeoHash();br// String s = geohash.encode(40.222012, 116.248283);br// System.out.println(s);br geohash.getArroundGeoHash(40.222012, 116.248283);br// double[] geo = geohash.decode(s);br// System.out.println(geo[0]+" "+geo[1]);br}b核心算法获取任意两点距离
核心算法获取任意两点距离
/**
* 计算地球上任意两点(经纬度)距离
*
* @param long1 第一点经度
* @param lat1 第一点纬度
* @param long2 第二点经度
* @param lat2 第二点纬度
* @return 返回距离 单位:米
*/
public static double Distance(double long1, double lat1, double long2, double lat2)
{
double a, b, R;
R = 6378137; // 地球半径
lat1 = lat1 * Math.PI / 180.0;
lat2 = lat2 * Math.PI / 180.0;
a = lat1 - lat2;
b = (long1 - long2) * Math.PI / 180.0;
double d;
double sa2, sb2;
sa2 = Math.sin(a / 2.0);
sb2 = Math.sin(b / 2.0);
d = 2* R * Math.asin(Math.sqrt(sa2 * sa2 + Math.cos(lat1) * Math.cos(lat2) * sb2 * sb2));
return d;
}
xxxxxxxxxxbr /**brbr * 计算地球上任意两点(经纬度)距离 brbr * brbr * @param long1 第一点经度 brbr * @param lat1 第一点纬度 brbr * @param long2 第二点经度 brbr * @param lat2 第二点纬度 brbr * @return 返回距离 单位:米brbr */brbrpublic static double Distance(double long1, double lat1, double long2, double lat2)brbr{brbr double a, b, R;brbr R = 6378137; // 地球半径 brbr lat1 = lat1 * Math.PI / 180.0;brbr lat2 = lat2 * Math.PI / 180.0;brbr a = lat1 - lat2;brbr b = (long1 - long2) * Math.PI / 180.0;brbr double d;brbr double sa2, sb2;brbr sa2 = Math.sin(a / 2.0);brbr sb2 = Math.sin(b / 2.0);brbr d = 2* R * Math.asin(Math.sqrt(sa2 * sa2 + Math.cos(lat1) * Math.cos(lat2) * sb2 * sb2));brbr return d;brbr}
关注下我的公众号吧,只为开源精神