守望者--AIR技术交流

 找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

搜索
热搜: ANE FlasCC 炼金术
查看: 515|回复: 0

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

[复制链接]
  • TA的每日心情
    擦汗
    2017-11-3 12:47
  • 签到天数: 441 天

    [LV.9]以坛为家II

    1741

    主题

    2093

    帖子

    13万

    积分

    超级版主

    Rank: 18Rank: 18Rank: 18Rank: 18Rank: 18

    威望
    517
    贡献
    24
    金币
    51073
    钢镚
    1421

    开源英雄守望者

    发表于 2016-9-13 16:00:20 | 显示全部楼层 |阅读模式

    参考文档:

    http://blog.csdn.net/wangxiafghj/article/details/9014363geohash  算法原理及实现方式
    http://blog.charlee.li/geohash-intro/  geohash:用字符串实现附近地点搜索
    http://blog.sina.com.cn/s/blog_7c05385f0101eofb.html    查找附近点--Geohash方案讨论
    http://www.wubiao.info/372        查找附近的xxx 球面距离以及Geohash方案探讨
    http://en.wikipedia.org/wiki/Haversine_formula       Haversine formula球面距离公式
    http://www.codecodex.com/wiki/Calculate_Distance_Between_Two_Points_on_a_Globe   球面距离公式代码实现
    http://developer.baidu.com/map/jsdemo.htm#a6_1   球面距离公式验证  
    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 plain copy
     在CODE上查看代码片派生到我的代码片
    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, 70140);  
    49.                 double lat = decode(latset, 060);  
    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, 060);  
    69.                 BitSet lonbits = getBits(lon, 70140);  
    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
     在CODE上查看代码片派生到我的代码片
    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
     在CODE上查看代码片派生到我的代码片
    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(09);  
    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://blog.csdn.net/sunrise_2013/article/details/42024813

    守望者AIR技术交流社区(www.airmyth.com)
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    
    关闭

    站长推荐上一条 /4 下一条

    QQ|手机版|Archiver|网站地图|小黑屋|守望者 ( 京ICP备14061876号

    GMT+8, 2017-12-14 04:42 , Processed in 1.343750 second(s), 35 queries .

    守望者AIR

    守望者AIR技术交流社区

    本站成立于 2014年12月31日

    快速回复 返回顶部 返回列表