# 附近的人位置距离计算方法

## geohash的实现java版：

```  1 import java.util.BitSet;
2 import java.util.HashMap;
3 import java.util.Map;
4
5 import org.apache.commons.lang3.StringUtils;
6
7 public class Geohash {
8
9     private static int numbits = 6 * 5;
10     final static char[] digits = { '0', '1', '2', '3', '4', '5', '6', '7', '8',
11             '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n', 'p',
12             'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
13
14     final static HashMap<Character, Integer> lookup = new HashMap<Character, Integer>();
15     static {
16         int i = 0;
17         for (char c : digits)
18             lookup.put(c, i++);
19
20     }
21
22     public Geohash() {
23         setMap();
24     }
25
26     public double[] decode(String geohash) {
27         StringBuilder buffer = new StringBuilder();
28         for (char c : geohash.toCharArray()) {
29
30             int i = lookup.get(c) + 32;
31             buffer.append(Integer.toString(i, 2).substring(1));
32         }
33
34         BitSet lonset = new BitSet();
35         BitSet latset = new BitSet();
36
37         // even bits
38         int j = 0;
39         for (int i = 0; i < numbits * 2; i += 2) {
40             boolean isSet = false;
41             if (i < buffer.length())
42                 isSet = buffer.charAt(i) == '1';
43             lonset.set(j++, isSet);
44         }
45
46         // odd bits
47         j = 0;
48         for (int i = 1; i < numbits * 2; i += 2) {
49             boolean isSet = false;
50             if (i < buffer.length())
51                 isSet = buffer.charAt(i) == '1';
52             latset.set(j++, isSet);
53         }
54
55         double lon = decode(lonset, -180, 180);
56         double lat = decode(latset, -90, 90);
57
58         return new double[] { lat, lon };
59     }
60
61     private double decode(BitSet bs, double floor, double ceiling) {
62         double mid = 0;
63         for (int i = 0; i < bs.length(); i++) {
64             mid = (floor + ceiling) / 2;
65             if (bs.get(i))
66                 floor = mid;
67             else
68                 ceiling = mid;
69         }
70         return mid;
71     }
72
73     public String encode(String lat, String lon) {
74
75         return encode(Double.parseDouble(lat), Double.parseDouble(lon));
76
77     }
78
79     public String encode(double lat, double lon) {
80         BitSet latbits = getBits(lat, -90, 90);
81         BitSet lonbits = getBits(lon, -180, 180);
82         StringBuilder buffer = new StringBuilder();
83         for (int i = 0; i < numbits; i++) {
84             buffer.append((lonbits.get(i)) ? '1' : '0');
85             buffer.append((latbits.get(i)) ? '1' : '0');
86         }
87         return base32(Long.parseLong(buffer.toString(), 2));
88     }
89
90     private BitSet getBits(double lat, double floor, double ceiling) {
91         BitSet buffer = new BitSet(numbits);
92         for (int i = 0; i < numbits; i++) {
93             double mid = (floor + ceiling) / 2;
94             if (lat >= mid) {
95                 buffer.set(i);
96                 floor = mid;
97             } else {
98                 ceiling = mid;
99             }
100         }
101         return buffer;
102     }
103
104     public static String base32(long i) {
105         char[] buf = new char[65];
106         int charPos = 64;
107         boolean negative = (i < 0);
108         if (!negative)
109             i = -i;
110         while (i <= -32) {
111             buf[charPos--] = digits[(int) (-(i % 32))];
112             i /= 32;
113         }
114         buf[charPos] = digits[(int) (-i)];
115
116         if (negative)
117             buf[--charPos] = '-';
118         return new String(buf, charPos, (65 - charPos));
119     }
120
121     /*********************** 获取九个的矩形编码 ****************************************/
122     public static String BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz";
123     public static Map<String, String> BORDERS = new HashMap<String, String>();
124     public static Map<String, String> NEIGHBORS = new HashMap<String, String>();
125
126     public static void setMap() {
127         NEIGHBORS.put("right:even", "bc01fg45238967deuvhjyznpkmstqrwx");
128         NEIGHBORS.put("left:even", "238967debc01fg45kmstqrwxuvhjyznp");
129         NEIGHBORS.put("top:even", "p0r21436x8zb9dcf5h7kjnmqesgutwvy");
130         NEIGHBORS.put("bottom:even", "14365h7k9dcfesgujnmqp0r2twvyx8zb");
131
132         NEIGHBORS.put("right:odd", "p0r21436x8zb9dcf5h7kjnmqesgutwvy");
133         NEIGHBORS.put("left:odd", "14365h7k9dcfesgujnmqp0r2twvyx8zb");
134         NEIGHBORS.put("top:odd", "bc01fg45238967deuvhjyznpkmstqrwx");
135         NEIGHBORS.put("bottom:odd", "238967debc01fg45kmstqrwxuvhjyznp");
136
137         BORDERS.put("right:even", "bcfguvyz");
138         BORDERS.put("left:even", "0145hjnp");
139         BORDERS.put("top:even", "prxz");
140         BORDERS.put("bottom:even", "028b");
141
142         BORDERS.put("right:odd", "prxz");
143         BORDERS.put("left:odd", "028b");
144         BORDERS.put("top:odd", "bcfguvyz");
145         BORDERS.put("bottom:odd", "0145hjnp");
146
147     }
148
149     /**
150      * 获取九个点的矩形编码
151      *
152      * @param geohash
153      * @return
154      */
155     public String[] getGeoHashExpand(String geohash) {
156         try {
157             String geohashTop = calculateAdjacent(geohash, "top");
158             String geohashBottom = calculateAdjacent(geohash, "bottom");
159             String geohashRight = calculateAdjacent(geohash, "right");
160             String geohashLeft = calculateAdjacent(geohash, "left");
161             String geohashTopLeft = calculateAdjacent(geohashLeft, "top");
162             String geohashTopRight = calculateAdjacent(geohashRight, "top");
163             String geohashBottomRight = calculateAdjacent(geohashRight,
164                     "bottom");
165             String geohashBottomLeft = calculateAdjacent(geohashLeft, "bottom");
166             String[] expand = { geohash, geohashTop, geohashBottom,
167                     geohashRight, geohashLeft, geohashTopLeft, geohashTopRight,
168                     geohashBottomRight, geohashBottomLeft };
169             return expand;
170         } catch (Exception e) {
171             return null;
172         }
173     }
174
175     /**
176      * 分别计算每个点的矩形编码
177      *
178      * @param srcHash
179      * @param dir
180      * @return
181      */
182     public static String calculateAdjacent(String srcHash, String dir) {
183         srcHash = srcHash.toLowerCase();
184         char lastChr = srcHash.charAt(srcHash.length() - 1);
185         int a = srcHash.length() % 2;
186         String type = (a > 0) ? "odd" : "even";
187         String base = srcHash.substring(0, srcHash.length() - 1);
188         if (BORDERS.get(dir + ":" + type).indexOf(lastChr) != -1) {
189             base = calculateAdjacent(base, dir);
190         }
191         base = base
192                 + BASE32.toCharArray()[(NEIGHBORS.get(dir + ":" + type)
193                         .indexOf(lastChr))];
194         return base;
195     }
196
197     // @Deprecated
198     // public static void expandLngLat(String geohash, int len){
199     // boolean is_even = true;
200     // double[] lat = new double[3];
201     // double[] lon = new double[3];
202     // lat[0] = -90.0;
203     // lat[1] = 90.0;
204     // lon[0] = -180.0;
205     // lon[1] = 180.0;
206     // double lat_err = 90.0;
207     // double lon_err = 180.0;
208     // char[] geohashChar = geohash.toCharArray();
209     // // String[] BITS = {"16", "8", "4", "2", "1"};
210     // int[] BITS = {16, 8, 4, 2, 1};
211     // for (int i = 0; i < geohashChar.length; i++) {
212     // char c = geohashChar[i];
213     // int cd = BASE32.indexOf(c);
214     // for (int j = 0; j < 5; j++) {
215     // int mask = BITS[j];
216     // if (is_even) {
217     // lon_err /= 2;
218     // refine_interval(lon, cd, mask);
219     // } else {
220     // lat_err /= 2;
221     // refine_interval(lat, cd, mask);
222     // }
223     // is_even = !is_even;
224     // }
225     // }
226     // lat[2] = (lat[0] + lat[1])/2;
227     // //1:[38.8970947265625, 38.902587890625, 38.89984130859375]
228     // //1: 38.8970947265625, 38.902587890625, 38.89984130859375
229     // //2:[38.902587890625, 38.9080810546875, 38.90533447265625]
230     // //2: 38.902587890625, 38.9080810546875, 38.90533447265625
231     // lon[2] = (lon[0] + lon[1])/2;
232     // //1:[-77.047119140625, -77.0361328125, -77.0416259765625]
233     // //1: -77.047119140625, -77.0361328125, -77.0416259765625
234     // //2:[-77.047119140625, -77.0361328125, -77.0416259765625]
235     // //2: -77.047119140625, -77.0361328125, -77.0416259765625
236     //
237     // String topLeft = lat[0]+","+lon[0];
238     // String topRight = lat[0]+","+lon[1];
239     //
240     // String bottomleft = lat[1]+","+lon[0];
241     // String bottoomRight = lat[1]+","+lon[1];
242     // String centerPoint = (lat[0]+lat[1])/2+","+(lon[0]+lon[1])/2;
243     //
244     // String centerTop = lat[0]+","+(lon[0]+lon[1])/2;
245     // String centerBottom = lat[1]+","+(lon[0]+lon[1])/2;
246     //
247     // String centerLeft = (lat[0]+lat[1])/2+","+lon[0];
248     // String centerRight = (lat[0]+lat[1])/2+","+lon[1];
249     // // System.out.println("topLeft:["+topLeft+"] geoHash:"+g.encode(lat[0],
250     // lon[0]));
251     // // System.out.println("topRight:["+topRight+"] geoHash:"+g.encode(lat[0],
252     // lon[1]));
253     // //
254     // System.out.println("bottomleft:["+bottomleft+"] geoHash:"+g.encode(lat[1],
255     // lon[0]));
256     // //
257     // System.out.println("bottoomRight:["+bottoomRight+"] geoHash:"+g.encode(lat[1],
258     // lon[1]));
259     // //
260     // System.out.println("centerPoint:["+centerPoint+"] geoHash:"+g.encode((lat[0]+lat[1])/2,
261     // (lon[0]+lon[1])/2));
262     // //
263     // System.out.println("centerTop:["+centerTop+"] geoHash:"+g.encode(lat[0],
264     // (lon[0]+lon[1])/2));
265     // //
266     // System.out.println("centerBottom:["+centerBottom+"] geoHash:"+g.encode(lat[1],
267     // (lon[0]+lon[1])/2));
268     // //
269     // System.out.println("centerLeft:["+centerLeft+"] geoHash:"+g.encode((lat[0]+lat[1])/2,
270     // lon[0]));
271     // //
272     // System.out.println("centerRight:["+centerRight+"] geoHash:"+g.encode((lat[0]+lat[1])/2,
273     // lon[1]));
274     //
275     // }
276     //
277     // @Deprecated
278     // public static void refine_interval(double[] interval, int cd, int mask){
279     // if ((cd & mask)>0){
280     // interval[0] = (interval[0] + interval[1])/2;
281     // }else{
282     // interval[1] = (interval[0] + interval[1])/2;
283     // }
284     // }
285     //
286
287     // ****************************************************************************************************************
288
289     private static final double EARTH_RADIUS = 6371;// 赤道半径(单位m)
290
291     /**
293      * */
294     private static double rad(double d) {
295         return d * Math.PI / 180.0;
296     }
297
298     /**
300      *
301      * @param lon1
302      *            第一点的精度
303      * @param lat1
304      *            第一点的纬度
305      * @param lon2
306      *            第二点的精度
307      * @param lat2
308      *            第二点的纬度
309      * @return 返回的距离，单位m
310      * */
311     public  double getDistance(double lon1, double lat1, double lon2,
312             double lat2) {
315         double a = radLat1 - radLat2;
316         double b = rad(lon1) - rad(lon2);
317         double s = 2 * Math.asin(Math.sqrt(Math.pow(Math.sin(a / 2), 2)
319                 * Math.pow(Math.sin(b / 2), 2)));
320         s = s * EARTH_RADIUS;
321         s = Math.round(s * 1000)/1000.0;
322         return s;
323     }
324
325     /*
326      * 永相逢超市 108.83457500177 34.256981052624 wqj6us6cmkj5bbfj6qdg s6q08ubhhuq7
327      */
328     public static void main(String[] args) throws Exception {
329
330         // 东四站 灯市口站
331         double lon1 = 116.4174628300;
332         double lat1 = 39.9243669400;
333         double lon2 = 116.4177739600;
334         double lat2 = 39.9171260300;
335         double dist;
336         String geocode;
337
338         Geohash geohash = new Geohash();
339         dist = geohash.getDistance(lon1, lat1, lon2, lat2);
340         System.out.println("两点相距：" + dist + " km");
341
342         geocode = geohash.encode(lat1, lon1);
343         System.out.println("当前位置编码：" + geocode);
344         double[] decode = new Geohash().decode(geocode);
345         for (double d : decode) {
346             System.out.println(d);
347         }
348
349         geocode = geohash.encode(lat2, lon2);
350         System.out.println("远方位置编码：" + geocode);
351         decode = new Geohash().decode(geocode);
352         for (double d : decode) {
353             System.out.println(d);
354         }
355
356         /* 获取的geohash多少位，位数越长，精度越准 */
357         int geohashLen = 5;
358
359         /* 获取中心点的geohash */
360         String code = geohash.encode(lat1, lon1).substring(0, geohashLen);
361
362         /* 获取所有的矩形geohash， 一共是九个 ，包含中心点,打印顺序请参考图2 */
363         String[] result = geohash.getGeoHashExpand(code);
364         for (String string : result) {
365             System.out.println(string);
366         }
367
368     }
369
370 }```

### 问题1：

计算的附近的概念不精准，仅仅只是一个区域，在边界问题上需要考虑。距离相近的在边界位置geohash显示却在两块区域。因此引入周围8个区域来精算中间一个区域的位置。这样做会把中间区域周围的包含，但最大范围无法估量。因为周围8块所代表的的精度算法，仅仅是该区域内的，而不是包含所有。就是说，假如中间区域精度1km以内，我需要将周围的区域加上才能把全部1km以内的位置包含。如下图所示：

记一个geohash的精度(区域的边长)为len,记最大距离为可以搜索到的最远的附近的位置，记最小距离为该距离内的所有位置必然包含在内。比如最小距离为d,则方圆为d的距离内的所有点都包含。

位于中心区域0110的人最大附近距离为：两个对角线b=2√2len。最小距离为：a=len

### 问题2：

距离需要进行2次计算。若有排序概念还需要排序。

### 我的抉择：

我选择了匹配前6位，测试距离大概1km以内。然后面临另一个问题：分页。

缺点：

finally：缓存边界

## 算法遗漏：

```1  SELECT id, lat, lon, geohash, updatetime FROM user_location
2 WHERE 1=1
3 and (
4 geohash like 'wx4g0t%' or  geohash like 'wx4g0w%' or  geohash like 'wx4g0s%'
5 or  geohash like 'wx4g0v%' or  geohash like 'wx4g0m%' or  geohash like 'wx4g0q%'
6 or  geohash like 'wx4g0y%' or  geohash like 'wx4g0u%' or  geohash like 'wx4g0k%')```

``` 1 SELECT id, lat, lon, geohash, updatetime FROM user_location
2 WHERE 1=1
3 and (
4 geohash like 'wx4g0%' or  geohash like 'wx4g2%' or  geohash like 'wx4fb%'
5 or  geohash like 'wx4g1%' or  geohash like 'wx4ep%' or  geohash like 'wx4er%'
6 or  geohash like 'wx4g3%' or  geohash like 'wx4fc%' or  geohash like 'wx4dz%')
7 and(
8 geohash not like 'wx4g0t%' or  geohash not like 'wx4g0w%' or  geohash not like 'wx4g0s%'
9 or  geohash not like 'wx4g0v%' or  geohash not like 'wx4g0m%' or  geohash not like 'wx4g0q%'
10 or  geohash not like 'wx4g0y%' or  geohash not like 'wx4g0u%' or  geohash not like 'wx4g0k%'
11 )```

298 篇文章56 人订阅

0 条评论

## 相关文章

852

### Python学习笔记（1）：列表元组结构

Python的列表元组功能强大，令人印象深刻。一是非常灵活，二是便于集体操作。特别是以元组作为列表项的结构，和数据访问的结果能够对应起来，和习惯的二维表理解上也...

2066

813

2934

### Python中被忽略的else

else, 我们再熟悉不过了。对于一个python程序员来说，else往往都是配合if来使用的，像这样：

1132

3396

3234

1162

3508

36914