geohash java 距离排序_APP筛选附近的人并排序（geohash算法）

之前做项目时有个tab是附近的人，思路是APP端上传定位(经纬度),服务端通过一个谷歌公式就能计算出两个定位的距离，因为数据本来就比较少，所有先取出所有符合条件的人，再计算出所有人和用户的距离值，然后排序。

//地球半径，单位米

private const double EARTH_RADIUS = 6378137;

///

/// 计算两点位置的距离，返回两点的距离，单位 米

/// 该公式为GOOGLE提供，误差小于0.2米

///

/// 第一点纬度

/// 第一点经度

/// 第二点纬度

/// 第二点经度

///

public static double GetDistance(double lat1, double lng1, double lat2, double lng2)

{

double radLat1 = Rad(lat1);

double radLng1 = Rad(lng1);

double radLat2 = Rad(lat2);

double radLng2 = Rad(lng2);

double a = radLat1 - radLat2;

double b = radLng1 - radLng2;

double result = 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))) * EARTH_RADIUS;

return result;

}

///

/// 经纬度转化成弧度

///

///

///

private static double Rad(double d)

{

return (double)d * Math.PI / 180d;

}

后来看到网上有一篇针对此话题的文章，研究了一下，受到了一些启发，特此记录。

如果用户数据比较多，把所有数据都取出来再挨个去计算距离排序就很耗性能。

1. 对着地图画格子

对于定位系统来说，我们的地球是被一个一个格子构成的，而每一个格子包含着一定的区域。我们拿北京城区为例，在画格子之前是：

这里写图片描述

将地图放入定位系统后，城区就不再是这个样子了，而是被分割成若干个格子，每一个格子都有格子的“名字”：

这里写图片描述

至于如何定义每一块的名称，后续章节-geohash算法会具体提及，这里不再复述。

2. 找到你所在的格子

定义了格子的名称，当然就有他的用处了，不然这不是白白定义了吗。其实在打开微信附近的人时，系统也会把设备的位置信息给记录，这时候系统依据设备的位置信息，通过geohash算法，计算出所在块名称。比如我们在天安门广场时，系统的计算名称可能是“EFACMDH”，名称有多少个字母主要看系统要求的定位精度最高为多少。我们发现设备位置名称的前5个字母是“EFACM”，正好是在地图中正中间的格子中，也就是包含了天安门的格子。但是设备位置名称后面还包含了“DH”，这说明当前格子包含的位置还不够详细，还不能说明设备所在更为精确的位置。因此我们还需要将格子更为细分，将“EFACM”格子放大，为下图：

这里写图片描述

这个范围内的所有格子前5个字符都是“EFACM”，但是都出现了第六个字符，而且第六个字符不同，其实就是因为这些位置范围都在“EFACM”中，只是对“EFACM”放大细分的结果。

而设备的位置信息为“EFACMDH”，也就是当前的位置范围任然不够精确，还需要继续细分，因此我们找出前六个字符为“EFACMD”的格子，再细分，如下图：

这里写图片描述

依据设备的位置编码，我们找出了设备所处的位置在红色框内，这时候我们把设备的位置信息记录在“EFACMDH”框内：

这里写图片描述

这样就将地图画成了格子，并且将设备的位置也记录在的相应的格子中。

3. 小结

整个定位，其实就是不断地进行着地图区域细化过程，我们依据系统设计的最高经度，计算出设备经纬度所在的区块名称，并将设备与经纬度记录在区块中，如下图：

这里写图片描述

接下来就是通过区块名称，将附件的人揪出来了。

揪出附近的人

上面这些区块与名称，作为用户的我们是看不到也不关心的，我们关心的是附近的人是如何选出来并展现在设备中。

1. 揪出第一批人

什么叫做第一批人，其实就像是微信中第一批大约展示20个人，这20人是离我们最近的20人，为了选出这20位好汉，系统进行了如下步骤：

这里写图片描述

找出所有在设备(浅蓝色点)所在的区块“EFACMDH”中的全部设备(蓝黑色的点)；

依据浅蓝色点与所有蓝黑色点的经纬度，计算出亮点之间的距离(这个网上有教程，很容易算)，并对两点距离进行排序；

读取蓝黑色所有点的用户信息(头像、名称、微信号等等)；

按距离有小到大发送给设备并显示在附近的人中。

通过这些步骤，系统既获得了附近人的位置，又获得了用户信息、与当前设备距离等信息。所以说不只是显示距离，甚至附近的人在哪里都可以查询到，只是可能涉及到了用户隐私，不提供这项功能而已。

2. 还想看其他人

当“EFACMDH”区块记录的用户小于20名，或者用户还想查看更多的附近的人时，就需要扩大查询范围了。其实扩大查询范围无非就是减少一位名称，从查询“EFACMDH”变成查询“EFACMD”。流程如下：

这里写图片描述

将名称英文字母减少一位，由“EFACMDH”变成“EFACMD”；

查询区块名称类似于“EFACMD”的所有区块，例如“EFACMDHA”至“EFACMDY”区块，共同组成“EFACMDH”区块；

找出“EFACMD”的所有位置信息，并依据“1. 揪出第一批人”的方法获得排序后的用户信息

将用户信息回传给设备，并显示。

扩大查询范围其实要比查询当前区块的消耗是要大一些的。因为需要将若干个小区块组合成一个大区块；同时还要进行区块名类似性匹配，比精确匹配的消耗是要高上不少的。这就是为何查询附近的人时，都是先显示少数最近的一些人。

3. 小结

知道了附近的人查询原理，是不是觉得原来实现这么简单。其实中间还设计一些hash匹配、数据存储等，只是这些过于技术，与业务联系不紧密，这里也就没必要过深入地研究了。有兴趣的同学可以查阅redis数据库的geohash模块。

geohash算法

本章节与附近人业务关系不大了，而且内容偏技术性，若不是技术方面的同学可以跳过了。

1. geohash简单原理

上面已经把如何查找附近的人技术原理梳理了一遍，但是留下了一个问题是每一个区块都有一个名字，这个名字是如何来的？接下来将揭晓这个谜团。

为了方便提取位置信息，人为地把地球划分了经度与纬度，依据经纬度，又可以画一些经纬度参考线。犹如地球仪中，人为地划分了若干条经度线与纬度线，依据这些参考线我们可以知道某一些位置在参考线以东或者以西、以南或者以北，从而估算出大概的经度纬度。

geohash算法就是依据这个原理，算法思路就是对参考线进行不断细分，判断当前位置是在参考线以东(右)或者参考线以西(左)，以东用1来标记，以西用0来标记，最后组成一个01串，再依据01串按照一定的编码格式转换成容易辨认的英文字符+数字的组合。

2. geohash计算过程

依据上述原理，接下来详细介绍一下geohash的计算过程，这里拿经纬度(116.389550， 39.928167)进行算法说明。

a. 纬度计算

中学学过的地理知识知道，地球分为南纬与北纬，分别都是0~90°，但是在计算机中，用文字定义南纬与北纬较为麻烦，所以计算机中用区间定义[-90,0)与[0,90]分为南北纬，同时叫做左右区间。区分了左右区间，接下来就是整个计算过程：

判断当前纬度39.928167是在左区间还是右区间，发现是在右区间[0,90]中，在右区间标识为1；

接着将区间[0,90]进行左右区间二分，二分后为 [0,45),[45,90]，可以确定39.928167属于左区间 [0,45)，标记为0；

不断重复上述过程39.928167总是属于某个区间[a,b]。随着每次迭代区间[a,b]总在缩小，并越来越逼近39.928167；

依据最大精度，定义一个最大重复次数，这里我们定义为15，这样就能得出一个01字串；

重复数

纬度范围

左区间

右区间

39.928167

1

[-90.0, 90.0]

[-90.0, 0.0)

[0.0, 90.0]

1

2

[0, 90.0]

[0.0, 45.0)

[45.0, 90]

0

3

[0.0, 45.0)

[0.0, 22.5)

[22.5, 45.0)

1

4

[22.5, 45.0]

[22.5, 33.75)

[33.75, 45.0]

1

5

[33.75, 45.0]

[33.75, 39.375)

[39.375, 45.0]

1

6

[39.375, 45.0]

[39.375, 42.1875)

[42.1875, 45.0]

0

7

[39.375, 42.1875)

[39.375, 40.7812)

[40.7812, 42.1875)

0

8

[39.375, 40.7812)

[39.375, 40.0781)

[40.0781, 40.7812)

0

9

[39.375, 40.0781)

[39.375, 39.7265)

[39.7265, 40.0781)

1

10

[39.7265, 40.0781)

[39.7265, 39.9023)

[39.9023, 40.0781)

1

11

[39.9023, 40.0781)

[39.9023, 39.9902)

[39.9902, 40.0781)

0

12

[39.9023, 39.9902)

[39.9023, 39.9462)

[39.9462, 39.9902)

0

13

[39.9023, 39.9462)

[39.9023, 39.9243)

[39.9243, 39.9462)

1

14

[39.9243, 39.9462)

[39.9243, 39.9353)

[39.9353, 39.9462)

0

15

[39.9243, 39.9353)

[39.9243, 39.9298)

[39.9298, 39.9353)

0

纬度最终得到的01字串为：1 0 1 1 1 0 0 0 1 1 0 0 1 0 0

b. 全局计算

经度计算与纬度计算类似，也是依据区间划分，左右判断来进行，这里就不在复述了，给出最终计算结果为：1 1 0 1 0 0 1 0 1 1 0 0 0 1 0，接下来就是如何通过经度与纬度的01字串，编码成相应的字母+数字的组合。

将经度与纬度的01字串进行合并，合并方法为：基数为放纬度，偶数位放经度，如下表：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

0

1

1

1

0

0

0

1

1

0

0

1

0

0

1

1

0

1

0

0

1

0

1

1

0

0

0

1

0

1

1

0

1

1

0

1

1

1

0

0

0

0

1

0

0

1

1

1

1

0

0

0

0

1

0

0

1

0

0

最终字串为：11011, 01110, 00010, 01111, 00001, 00100

将字串转换成十进制，得到：27, 14, 2, 15, 1, 4

对应base32编码表，如下：

数字

字符

0

0

1

1

2

2

3

3

4

4

5

5

6

6

7

7

8

8

9

9

10

b

11

c

12

d

13

e

14

f

15

g

16

h

17

j

18

k

19

m

20

n

21

p

22

q

23

r

24

s

25

t

26

u

27

v

28

w

29

x

30

y

31

z

最终得出(116.389550， 39.928167)所在区块为：VF2G14(可能有计算错误，不要在意这些细节)

这就是我们如何通过位置点，计算出位置所在区块的原理了。

3. 计算精度问题

通过上面的计算可以看到，循环计算15次才获得6位geohash字串，那6位geohash的精度是多少呢？如下表：

geohash长度

纬度位数

经度位数

纬度误差

经度误差

距离误差(km)

1

2

3

± 23

± 23

± 2500

2

5

5

± 2.8

± 56

± 630

3

7

8

± 0.7

± 0.7

± 78

4

10

10

± 0.087

± 0.18

± 20

5

12

13

± 0.022

± 0.022

± 2.4

6

15

15

± 0.0027

± 0.0055

± 0.61

7

17

18

± 0.00068

± 0.00068

± 0.076

8

20

20

± 0.000086

± 0.000172

± 0.01911

9

22

23

± 0.000021

± 0.000021

± 0.00478

10

25

25

± 0.00000268

± 0.00000536

± 0.0005971

11

27

28

± 0.00000067

± 0.00000067

± 0.0001492

12

30

30

± 0,00000008

± 0.00000017

± 0.0000186

可以看出geohash的长度达到6个字符的误差是610m，长度达到8以上时精度已经达到了10m级。

但是当前民用领域定位系统的定位误差都在10m以上，如果在城区由于高楼、大树等影响定位系统型号，所以误差可以达到50m(不要看到导航软件那么准就认为没有误差，其实那是经过了强大的数据修正)。所以通过geohash定位附近的人时，8位已经是极限了，定位系统的精度导致再高的精度已经没有了意义

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 lookup = new HashMap();

//初始化编码映射内容

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 getArroundGeoHash(double lat, double lon){

//Log.i("okunu", "getArroundGeoHash lat = " + lat + " lng = " + lon);

ArrayList 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

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

}

}