[数学算法] 查找附近网点geohash算法及实现 （Java版本）

参考文档：

geohash有以下几个特点：

首先，geohash用一个字符串表示经度和纬度两个坐标。某些情况下无法在两列上同时应用索引 （例如MySQL 4之前的版本，Google App Engine的数据层等），利用geohash，只需在一列上应用索引即可。

其次，geohash表示的并不是一个点，而是一个矩形区域。比如编码wx4g0ec19，它表示的是一个矩形区域。 使用者可以发布地址编码，既能表明自己位于北海公园附近，又不至于暴露自己的精确坐标，有助于隐私保护。

第三，编码的前缀可以表示更大的区域。例如wx4g0ec1，它的前缀wx4g0e表示包含编码wx4g0ec1在内的更大范围。 这个特性可以用于附近地点搜索。首先根据用户当前坐标计算geohash（例如wx4g0ec1）然后取其前缀进行查询 （SELECT * FROM place WHERE geohash LIKE 'wx4g0e%'），即可查询附近的所有地点。

Geohash比直接用经纬度的高效很多。

Geohash算法实现（Java版本）

[java] view plain copy

 

1. package com.DistTest;  
2. import java.util.BitSet;  
3. import java.util.HashMap;  
4.   
5. public class Geohash {  
6.   
7.         private static int numbits = 6 * 5;  
8.         final static char[] digits = { '0', '1', '2', '3', '4', '5', '6', '7', '8',  
9.                         '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n', 'p',  
10.                         'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };  
11.          
12.         final static HashMap<Character, Integer> lookup = new HashMap<Character, Integer>();  
13.         static {  
14.                 int i = 0;  
15.                 for (char c : digits)  
16.                         lookup.put(c, i++);  
17.         }  
18.   
19.         public double[] decode(String geohash) {  
20.                 StringBuilder buffer = new StringBuilder();  
21.                 for (char c : geohash.toCharArray()) {  
22.   
23.                         int i = lookup.get(c) + 32;  
24.                         buffer.append( Integer.toString(i, 2).substring(1) );  
25.                 }  
26.                  
27.                 BitSet lonset = new BitSet();  
28.                 BitSet latset = new BitSet();  
29.                  
30.                 //even bits  
31.                 int j =0;  
32.                 for (int i=0; i< numbits*2;i+=2) {  
33.                         boolean isSet = false;  
34.                         if ( i < buffer.length() )  
35.                           isSet = buffer.charAt(i) == '1';  
36.                         lonset.set(j++, isSet);  
37.                 }  
38.                  
39.                 //odd bits  
40.                 j=0;  
41.                 for (int i=1; i< numbits*2;i+=2) {  
42.                         boolean isSet = false;  
43.                         if ( i < buffer.length() )  
44.                           isSet = buffer.charAt(i) == '1';  
45.                         latset.set(j++, isSet);  
46.                 }  
47.                //中国地理坐标：东经73°至东经135°，北纬4°至北纬53°  
48.                 double lon = decode(lonset, 70, 140);  
49.                 double lat = decode(latset, 0, 60);  
50.                  
51.                 return new double[] {lat, lon};          
52.         }  
53.          
54.         private double decode(BitSet bs, double floor, double ceiling) {  
55.                 double mid = 0;  
56.                 for (int i=0; i<bs.length(); i++) {  
57.                         mid = (floor + ceiling) / 2;  
58.                         if (bs.get(i))  
59.                                 floor = mid;  
60.                         else  
61.                                 ceiling = mid;  
62.                 }  
63.                 return mid;  
64.         }  
65.          
66.          
67.         public String encode(double lat, double lon) {  
68.                 BitSet latbits = getBits(lat, 0, 60);  
69.                 BitSet lonbits = getBits(lon, 70, 140);  
70.                 StringBuilder buffer = new StringBuilder();  
71.                 for (int i = 0; i < numbits; i++) {  
72.                         buffer.append( (lonbits.get(i))?'1':'0');  
73.                         buffer.append( (latbits.get(i))?'1':'0');  
74.                 }  
75.                 return base32(Long.parseLong(buffer.toString(), 2));  
76.         }  
77.   
78.         private BitSet getBits(double lat, double floor, double ceiling) {  
79.                 BitSet buffer = new BitSet(numbits);  
80.                 for (int i = 0; i < numbits; i++) {  
81.                         double mid = (floor + ceiling) / 2;  
82.                         if (lat >= mid) {  
83.                                 buffer.set(i);  
84.                                 floor = mid;  
85.                         } else {  
86.                                 ceiling = mid;  
87.                         }  
88.                 }  
89.                 return buffer;  
90.         }  
91.   
92.         public static String base32(long i) {  
93.                 char[] buf = new char[65];  
94.                 int charPos = 64;  
95.                 boolean negative = (i < 0);  
96.                 if (!negative)  
97.                         i = -i;  
98.                 while (i <= -32) {  
99.                         buf[charPos--] = digits[(int) (-(i % 32))];  
100.                         i /= 32;  
101.                 }  
102.                 buf[charPos] = digits[(int) (-i)];  
103.   
104.                 if (negative)  
105.                         buf[--charPos] = '-';  
106.                 return new String(buf, charPos, (65 - charPos));  
107.         }  
108.   
109. }  

球面距离公式：

[java] view plain copy

 

1. package com.DistTest;  
2. public class Test{   
3.     private static final  double EARTH_RADIUS = 6371000;//赤道半径(单位m)  
4.       
5.     /** 
6.      * 转化为弧度(rad) 
7.      * */  
8.     private static double rad(double d)  
9.     {  
10.        return d * Math.PI / 180.0;  
11.     }  
12.     /** 
13.      * 基于googleMap中的算法得到两经纬度之间的距离,计算精度与谷歌地图的距离精度差不多，相差范围在0.2米以下 
14.      * @param lon1 第一点的精度 
15.      * @param lat1 第一点的纬度 
16.      * @param lon2 第二点的精度 
17.      * @param lat3 第二点的纬度 
18.      * @return 返回的距离，单位m 
19.      * */  
20.     public static double GetDistance(double lon1,double lat1,double lon2, double lat2)  
21.     {  
22.        double radLat1 = rad(lat1);  
23.        double radLat2 = rad(lat2);  
24.        double a = radLat1 - radLat2;  
25.        double b = rad(lon1) - rad(lon2);  
26.        double s = 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)));  
27.        s = s * EARTH_RADIUS;  
28.        s = Math.round(s * 10000) / 10000;  
29.        return s;  
30.     }  
31.        
32.     public static void main(String []args){  
33.           double lon1=109.0145193757;    
34.           double lat1=34.236080797698;  
35.           double lon2=108.9644583556;  
36.           double lat2=34.286439088548;  
37.           double dist;  
38.           String geocode;  
39.             
40.           dist=Test.GetDistance(lon1, lat1, lon2, lat2);   
41.           System.out.println("两点相距：" + dist + " 米");  
42.             
43.             
44.           Geohash geohash = new Geohash();  
45.           geocode=geohash.encode(lat1, lon1);  
46.           System.out.println("当前位置编码：" + geocode);  
47.            
48.           geocode=geohash.encode(lat2, lon2);  
49.           System.out.println("远方位置编码：" + geocode);  
50.   
51.        }  
52.     //wqj7j37sfu03h2xb2q97  
53.     /* 
54. 永相逢超市 
55. 108.83457500177 
56. 34.256981052624 
57. wqj6us6cmkj5bbfj6qdg 
58. s6q08ubhhuq7 
59. */  
60. }  

附近网点距离排序

[java] view plain copy

 

1. package com.DistTest;  
2.     
3. import java.sql.DriverManager;  
4. import java.sql.ResultSet;  
5. import java.sql.SQLException;  
6. import java.sql.Connection;  
7. import java.sql.Statement;  
8.    
9.    
10. public class sqlTest {  
11.       
12.     public static void main(String[] args) throws Exception {  
13.         Connection conn = null;  
14.         String sql;  
15.         String url = "jdbc:mysql://132.97.**.**/test?"  
16.                 + "user=***&password=****&useUnicode=true&characterEncoding=UTF8";  
17.    
18.         try {  
19.             Class.forName("com.mysql.jdbc.Driver");// 动态加载mysql驱动  
20.             // System.out.println("成功加载MySQL驱动程序");  
21.             // 一个Connection代表一个数据库连接  
22.             conn = DriverManager.getConnection(url);  
23.             // Statement里面带有很多方法，比如executeUpdate可以实现插入，更新和删除等  
24.             Statement stmt = conn.createStatement();  
25.             sql = "select * from retailersinfotable limit 1,10";  
26.             ResultSet rs = stmt.executeQuery(sql);// executeQuery会返回结果的集合，否则返回空值  
27.             double lon1=109.0145193757;    
28.             double lat1=34.236080797698;  
29.             System.out.println("当前位置：");  
30.             int i=0;  
31.             String[][] array = new String[10][3];  
32.             while (rs.next()){  
33.                     //从数据库取出地理坐标  
34.                     double lon2=Double.parseDouble(rs.getString("Longitude"));  
35.                     double lat2=Double.parseDouble(rs.getString("Latitude"));  
36.                       
37.                     //根据地理坐标，生成geohash编码  
38.                     Geohash geohash = new Geohash();  
39.                     String geocode=geohash.encode(lat2, lon2).substring(0, 9);  
40.                       
41.                     //计算两点间的距离  
42.                     int dist=(int) Test.GetDistance(lon1, lat1, lon2, lat2);   
43.                       
44.                     array[i][0]=String.valueOf(i);  
45.                     array[i][1]=geocode;  
46.                     array[i][2]=Integer.toString(dist);  
47.                       
48.                     i++;  
49.           
50.                 //  System.out.println(lon2+"---"+lat2+"---"+geocode+"---"+dist);     
51.                 }  
52.   
53.             array=sqlTest.getOrder(array); //二维数组排序  
54.             sqlTest.showArray(array);        //打印数组  
55.   
56.               
57.               
58.               
59.         } catch (SQLException e) {  
60.             System.out.println("MySQL操作错误");  
61.             e.printStackTrace();  
62.         } finally {  
63.             conn.close();  
64.         }  
65.    
66.     }  
67.     /* 
68.      * 二维数组排序，比较array[][2]的值，返回二维数组 
69.      * */  
70.     public static String[][] getOrder(String[][] array){  
71.         for (int j = 0; j < array.length ; j++) {  
72.             for (int bb = 0; bb < array.length - 1; bb++) {  
73.                 String[] ss;  
74.                 int a1=Integer.valueOf(array[bb][2]);  //转化成int型比较大小  
75.                 int a2=Integer.valueOf(array[bb+1][2]);  
76.                 if (a1>a2) {  
77.                     ss = array[bb];  
78.                     array[bb] = array[bb + 1];  
79.                     array[bb + 1] = ss;  
80.                       
81.                 }  
82.             }  
83.         }   
84.         return array;  
85.     }  
86.       
87.     /*打印数组*/  
88.     public static void showArray(String[][] array){  
89.           for(int a=0;a<array.length;a++){  
90.             for(int j=0;j<array[0].length;j++)  
91.                 System.out.print(array[a][j]+" ");  
92.             System.out.println();  
93.         }  
94.     }  
95.   
96. }