查找附近网点geohash算法及实现

川长思鸟来 2022-08-07 09:55 229阅读 0赞

查找附近网点geohash算法及实现  
   
2014-12-19 11:40:01  [www.hackbase.com][]  来源：互联网  
   
参考文档：[http://blog.csdn.net/wangxiafghj/article/details/9014363geohash][http_blog.csdn.net_wangxiafghj_article_details_9014363geohash] 算法原理及实现方式[http://blog.charlee.li/geohash-intro/][http_blog.charlee.li_geohash-intro] geohash：用字符串实现附近地点搜索[http://blog.sina.com.cn/s/blog][http_blog.sina.com.cn_s_blog] ...

参考文档：

[http://blog.csdn.net/wangxiafghj/article/details/9014363geohash][http_blog.csdn.net_wangxiafghj_article_details_9014363geohash]  算法原理及实现方式  
[http://blog.charlee.li/geohash-intro/][http_blog.charlee.li_geohash-intro]  geohash：用字符串实现附近地点搜索  
[http://blog.sina.com.cn/s/blog\_7c05385f0101eofb.html][http_blog.sina.com.cn_s_blog_7c05385f0101eofb.html]    查找附近点--Geohash方案讨论  
[http://www.wubiao.info/372][http_www.wubiao.info_372]        查找附近的xxx 球面距离以及Geohash方案探讨  
[http://en.wikipedia.org/wiki/Haversine\_formula][http_en.wikipedia.org_wiki_Haversine_formula]       Haversine formula球面距离公式  
[http://www.codecodex.com/wiki/Calculate\_Distance\_Between\_Two\_Points\_on\_a\_Globe][http_www.codecodex.com_wiki_Calculate_Distance_Between_Two_Points_on_a_Globe]   球面距离公式代码实现  
[http://developer.baidu.com/map/jsdemo.htm\#a6\_1][http_developer.baidu.com_map_jsdemo.htm_a6_1]   球面距离公式验证   
[http://www.wubiao.info/470][http_www.wubiao.info_470]     Mysql or Mongodb LBS快速实现方案

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 plaincopy在CODE上查看代码片派生到我的代码片  
01.package com.DistTest;   
02.import java.util.BitSet;   
03.import java.util.HashMap;   
04.   
05.public class Geohash \{   
06.   
07.        private static int numbits = 6 \* 5;   
08.        final static char\[\] digits = \{ '0', '1', '2', '3', '4', '5', '6', '7', '8',   
09.                        '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 plaincopy在CODE上查看代码片派生到我的代码片  
01.package com.DistTest;   
02.public class Test\{    
03.    private static final  double EARTH\_RADIUS = 6371000;//赤道半径(单位m)   
04.       
05.    /\*\*  
06.     \* 转化为弧度(rad)  
07.     \* \*/   
08.    private static double rad(double d)   
09.    \{   
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 plaincopy在CODE上查看代码片派生到我的代码片  
01.package com.DistTest;   
02.     
03.import java.sql.DriverManager;   
04.import java.sql.ResultSet;   
05.import java.sql.SQLException;   
06.import java.sql.Connection;   
07.import java.sql.Statement;   
08.    
09.    
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.\}

免责声明：本文仅代表作者个人观点，与本站无关。其原创性以及文中陈

本篇文章来源于 黑基网-中国最大的网络安全站点 原文链接：[http://www.hackbase.com/tech/2014-12-19/70144.html][http_www.hackbase.com_tech_2014-12-19_70144.html]

[www.hackbase.com]: http://www.hackbase.com
[http_blog.csdn.net_wangxiafghj_article_details_9014363geohash]: http://blog.csdn.net/wangxiafghj/article/details/9014363geohash
[http_blog.charlee.li_geohash-intro]: http://blog.charlee.li/geohash-intro/
[http_blog.sina.com.cn_s_blog]: http://blog.sina.com.cn/s/blog
[http_blog.sina.com.cn_s_blog_7c05385f0101eofb.html]: http://blog.sina.com.cn/s/blog_7c05385f0101eofb.html
[http_www.wubiao.info_372]: http://www.wubiao.info/372
[http_en.wikipedia.org_wiki_Haversine_formula]: http://en.wikipedia.org/wiki/Haversine_formula
[http_www.codecodex.com_wiki_Calculate_Distance_Between_Two_Points_on_a_Globe]: http://www.codecodex.com/wiki/Calculate_Distance_Between_Two_Points_on_a_Globe
[http_developer.baidu.com_map_jsdemo.htm_a6_1]: http://developer.baidu.com/map/jsdemo.htm#a6_1
[http_www.wubiao.info_470]: http://www.wubiao.info/470
[http_www.hackbase.com_tech_2014-12-19_70144.html]: http://www.hackbase.com/tech/2014-12-19/70144.html