首页 > 代码库 > 查找最近距离geohash算法(增加周边邻近编号)
查找最近距离geohash算法(增加周边邻近编号)
接着上一篇文章:查找附近网点geohash算法及实现 (Java版本) http://blog.csdn.net/sunrise_2013/article/details/42024813
参考文档:
http://www.slideshare.net/sandeepbhaskar2/geohash 介绍geohash原理及例子
http://geohash.gofreerange.com/ 演示实例
http://geohash.gofreerange.com/ 周边8格子实例
由于存在部分网点丢失的情况,为了解决边缘问题,需要计算这个块周围的八个格子,补充代码,实现周边8个编码的最近编码。
根据一个geohash值 获取周围8个geohash值的代码。
例如在方格4的左下部分的点和大方格1的右下部分的点离的很近,可是它们的geohash值一定是相差的相当远,因为头一次的分块就相差太大了,很多时候我们对geohash的值进行简单的排序比较,结果貌似真的能够找出相近的点,并且似乎还是按照距离的远近排列的,可是实际上会有一些点被漏掉了。
上述这个问题,可以通过搜索一个格子,周围八个格子的数据,统一获取后再进行过滤。这样就在编码层次解决了这个问题。
主要代码:
<span style="font-family: Arial, Helvetica, sans-serif;">public static String[] getGeoHashExpand(String geohash) {</span></span>
try { String geohashTop = calculateAdjacent(geohash, TOP); String geohashBottom = calculateAdjacent(geohash, BOTTOM); String geohashRight = calculateAdjacent(geohash, RIGHT); String geohashLeft = calculateAdjacent(geohash, LEFT); String geohashTopLeft = calculateAdjacent(geohashLeft, TOP); String geohashTopRight = calculateAdjacent(geohashRight, TOP); String geohashBottomRight = calculateAdjacent(geohashRight, BOTTOM); String geohashBottomLeft = calculateAdjacent(geohashLeft, BOTTOM); String[] expand = { geohash, geohashTop, geohashBottom, geohashRight, geohashLeft, geohashTopLeft, geohashTopRight, geohashBottomRight, geohashBottomLeft }; return expand; } catch (Exception e) { //logger.error("GeoHash Error",e); return null; } }
</pre><pre code_snippet_id="571887" snippet_file_name="blog_20150105_5_8338259" name="code" class="java">
public static String calculateAdjacent(String srcHash, int dir) { srcHash = srcHash.toLowerCase(); char lastChr = srcHash.charAt(srcHash.length() - 1); int type = (srcHash.length() % 2) == 1 ? ODD : EVEN; String base = srcHash.substring(0, srcHash.length() - 1); if (BORDERS[dir][type].indexOf(lastChr) != -1) { base = calculateAdjacent(base, dir); } return base + BASE32.charAt(NEIGHBORS[dir][type].indexOf(lastChr)); }
全部代码实例:
Geohase.java
package com.DistTest; //Geohash.java //Geohash library for Java //ported from David Troy's Geohash library for Javascript //- http://github.com/davetroy/geohash-js/tree/master //(c) 2008 David Troy //(c) 2008 Tom Carden //Distributed under the MIT License public class Geohash { public static int BITS[] = { 16, 8, 4, 2, 1 }; public static String BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"; public static int RIGHT = 0; public static int LEFT = 1; public static int TOP = 2; public static int BOTTOM = 3; public static int EVEN = 0; public static int ODD = 1; public static String[][] NEIGHBORS; public static String[][] BORDERS; static { NEIGHBORS = new String[4][2]; BORDERS = new String[4][2]; NEIGHBORS[BOTTOM][EVEN] = "bc01fg45238967deuvhjyznpkmstqrwx"; NEIGHBORS[TOP][EVEN] = "238967debc01fg45kmstqrwxuvhjyznp"; NEIGHBORS[LEFT][EVEN] = "p0r21436x8zb9dcf5h7kjnmqesgutwvy"; NEIGHBORS[RIGHT][EVEN] = "14365h7k9dcfesgujnmqp0r2twvyx8zb"; BORDERS[BOTTOM][EVEN] = "bcfguvyz"; BORDERS[TOP][EVEN] = "0145hjnp"; BORDERS[LEFT][EVEN] = "prxz"; BORDERS[RIGHT][EVEN] = "028b"; NEIGHBORS[BOTTOM][ODD] = NEIGHBORS[LEFT][EVEN]; NEIGHBORS[TOP][ODD] = NEIGHBORS[RIGHT][EVEN]; NEIGHBORS[LEFT][ODD] = NEIGHBORS[BOTTOM][EVEN]; NEIGHBORS[RIGHT][ODD] = NEIGHBORS[TOP][EVEN]; BORDERS[BOTTOM][ODD] = BORDERS[LEFT][EVEN]; BORDERS[TOP][ODD] = BORDERS[RIGHT][EVEN]; BORDERS[LEFT][ODD] = BORDERS[BOTTOM][EVEN]; BORDERS[RIGHT][ODD] = BORDERS[TOP][EVEN]; } private static void refine_interval(double[] interval, int cd, int mask) { if ((cd & mask) > 0) { interval[0] = (interval[0] + interval[1]) / 2.0; } else { interval[1] = (interval[0] + interval[1]) / 2.0; } } public static String calculateAdjacent(String srcHash, int dir) { srcHash = srcHash.toLowerCase(); char lastChr = srcHash.charAt(srcHash.length() - 1); int type = (srcHash.length() % 2) == 1 ? ODD : EVEN; String base = srcHash.substring(0, srcHash.length() - 1); if (BORDERS[dir][type].indexOf(lastChr) != -1) { base = calculateAdjacent(base, dir); } return base + BASE32.charAt(NEIGHBORS[dir][type].indexOf(lastChr)); } public static String[] getGeoHashExpand(String geohash) { try { String geohashTop = calculateAdjacent(geohash, TOP); String geohashBottom = calculateAdjacent(geohash, BOTTOM); String geohashRight = calculateAdjacent(geohash, RIGHT); String geohashLeft = calculateAdjacent(geohash, LEFT); String geohashTopLeft = calculateAdjacent(geohashLeft, TOP); String geohashTopRight = calculateAdjacent(geohashRight, TOP); String geohashBottomRight = calculateAdjacent(geohashRight, BOTTOM); String geohashBottomLeft = calculateAdjacent(geohashLeft, BOTTOM); String[] expand = { geohash, geohashTop, geohashBottom, geohashRight, geohashLeft, geohashTopLeft, geohashTopRight, geohashBottomRight, geohashBottomLeft }; return expand; } catch (Exception e) { //logger.error("GeoHash Error",e); return null; } } public static double[][] decode(String geohash) { boolean is_even = true; double[] lat = new double[3]; double[] lon = new double[3]; lat[0] = -90.0; lat[1] = 90.0; lon[0] = -180.0; lon[1] = 180.0; double lat_err = 90.0; double lon_err = 180.0; for (int i = 0; i < geohash.length(); i++) { char c = geohash.charAt(i); int cd = BASE32.indexOf(c); for (int j = 0; j < BITS.length; j++) { int mask = BITS[j]; if (is_even) { lon_err /= 2.0; refine_interval(lon, cd, mask); } else { lat_err /= 2.0; refine_interval(lat, cd, mask); } is_even = !is_even; } } lat[2] = (lat[0] + lat[1]) / 2.0; lon[2] = (lon[0] + lon[1]) / 2.0; return new double[][] { lat, lon }; } public static String encode(double latitude, double longitude) { boolean is_even = true; int i = 0; double lat[] = new double[3]; double lon[] = new double[3]; int bit = 0; int ch = 0; int precision = 12; String geohash = ""; lat[0] = -90.0; lat[1] = 90.0; lon[0] = -180.0; lon[1] = 180.0; while (geohash.length() < precision) { if (is_even) { double mid = (lon[0] + lon[1]) / 2.0; if (longitude > mid) { ch |= BITS[bit]; lon[0] = mid; } else { lon[1] = mid; } } else { double mid = (lat[0] + lat[1]) / 2.0; if (latitude > mid) { ch |= BITS[bit]; lat[0] = mid; } else { lat[1] = mid; } } is_even = !is_even; if (bit < 4) { bit++; } else { geohash += BASE32.charAt(ch); bit = 0; ch = 0; } } return geohash; } }
测试实例:
package com.DistTest; import java.sql.DriverManager; import java.sql.ResultSet; import java.sql.SQLException; import java.sql.Connection; import java.sql.Statement; public class sqlTest { public static void main(String[] args) throws Exception { Connection conn = null; String sql; String sql1; String url = "jdbc:mysql://132.97.194.62/test?" + "user=root&password=sheng&useUnicode=true&characterEncoding=UTF8"; try { Class.forName("com.mysql.jdbc.Driver");// 动态加载mysql驱动 // System.out.println("成功加载MySQL驱动程序"); // 一个Connection代表一个数据库连接 conn = DriverManager.getConnection(url); // Statement里面带有很多方法,比如executeUpdate可以实现插入,更新和删除等 Statement stmt = conn.createStatement(); double lon1=109.0145193757; double lat1=34.236080797698; //根据地理坐标,生成geohash编码 // Geohash ghash = new Geohash(); // String gcode=Geohash.encode(lat1, lon1).substring(0, 4); String gcode="wqj6z"; String[] neargcode=Geohash.getGeoHashExpand(gcode); for(int i=0;i<neargcode.length;i++) { System.out.println(neargcode[i]); } sql = "select * from retailersinfotable where geohash like " + "'"+neargcode[0]+"%' or '"+neargcode[1]+"%' or '"+neargcode[2]+"%' " + "or '"+neargcode[3]+"%' or '"+neargcode[4]+"%' or '"+neargcode[5]+"%' " + "or '"+neargcode[6]+"%' or '"+neargcode[7]+"%' or '"+neargcode[8]+"%'"; System.out.println(sql); ResultSet rs = stmt.executeQuery(sql);// executeQuery会返回结果的集合,否则返回空值 rs.last(); int rowCount = rs.getRow(); //获得ResultSet的总行数 System.out.println(rowCount); rs.beforeFirst(); System.out.println("当前位置:经度"+lon1+" 维度:"+lat1); int i=0; String[][] array = new String[rowCount][3]; while (rs.next()){ //从数据库取出地理坐标 double lon2=Double.parseDouble(rs.getString("Longitude")); double lat2=Double.parseDouble(rs.getString("Latitude")); //根据地理坐标,生成geohash编码 Geohash geohash = new Geohash(); String geocode=geohash.encode(lat2, lon2).substring(0, 9); //计算两点间的距离 int dist=(int) Test.GetDistance(lon1, lat1, lon2, lat2); array[i][0]=String.valueOf(i); array[i][1]=geocode; array[i][2]=Integer.toString(dist); i++; // System.out.println(lon2+"---"+lat2+"---"+geocode+"---"+dist); } array=sqlTest.getOrder(array); //二维数组排序 sqlTest.showArray(array); //打印数组 } catch (SQLException e) { System.out.println("MySQL操作错误"); e.printStackTrace(); } finally { conn.close(); } } /* * 二维数组排序,比较array[][2]的值,返回二维数组 * */ public static String[][] getOrder(String[][] array){ for (int j = 0; j < array.length ; j++) { for (int bb = 0; bb < array.length - 1; bb++) { String[] ss; int a1=Integer.valueOf(array[bb][2]); //转化成int型比较大小 int a2=Integer.valueOf(array[bb+1][2]); if (a1>a2) { ss = array[bb]; array[bb] = array[bb + 1]; array[bb + 1] = ss; } } } return array; } /*打印数组*/ public static void showArray(String[][] array){ for(int a=0;a<array.length;a++){ for(int j=0;j<array[0].length;j++) System.out.print(array[a][j]+" "); System.out.println(); } } /* public static void main(String[] args) { String aaa="wxsfdf"; Geohash geohash = new Geohash(); String[] str = geohash.getGeoHashExpand(aaa); for(int i=0;i<str.length;i++) { System.out.println(str[i]); } }*/ }
查找最近距离geohash算法(增加周边邻近编号)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。