Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
GeoHash utilities in Java
/*
* Copyright (c) 2013 Mindoo GmbH
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package com.mindoo.utils;
import java.util.ArrayList;
import java.util.List;
import com.javadocmd.simplelatlng.LatLng;
import com.javadocmd.simplelatlng.LatLngTool;
import com.javadocmd.simplelatlng.LatLngTool.Bearing;
import com.javadocmd.simplelatlng.util.LengthUnit;
/**
* Class ported from JavaScript class <a href="https://github.com/davetroy/geohash-js/blob/master/geohash.js">geohash.js</a>
* (licensed under MIT license) with some additional helper methods for conversions.<br>
* <br>
* Uses utility classes and methods from project <a href="https://github.com/javadocmd/simplelatlng">SimpleLatLng</a>.
*
* @author Karsten Lehmann
*/
public class GeoHashUtils {
private static int[] BITS = new int[]{16, 8, 4, 2, 1};
public enum Dir {topleft, top, topright, left, right, bottomleft, bottom, bottomright};
public static Dir[] Corners=new Dir[] {Dir.topleft, Dir.topright, Dir.bottomleft, Dir.bottomright};
public static Dir[] Edged=new Dir[] {Dir.top, Dir.left, Dir.right, Dir.bottom};
public enum Type {odd, even};
private static String BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz";
private static final String NEIGHBORS_right_even="bc01fg45238967deuvhjyznpkmstqrwx";
private static final String NEIGHBORS_left_even="238967debc01fg45kmstqrwxuvhjyznp";
private static final String NEIGHBORS_top_even="p0r21436x8zb9dcf5h7kjnmqesgutwvy";
private static final String NEIGHBORS_bottom_even="14365h7k9dcfesgujnmqp0r2twvyx8zb";
private static final String NEIGHBORS_bottom_odd=NEIGHBORS_left_even;
private static final String NEIGHBORS_top_odd=NEIGHBORS_right_even;
private static final String NEIGHBORS_left_odd=NEIGHBORS_bottom_even;
private static final String NEIGHBORS_right_odd=NEIGHBORS_top_even;
private static String NEIGHBORS(Dir dir, Type type) {
switch (dir) {
case top:
switch (type) {
case even:
return NEIGHBORS_top_even;
case odd:
return NEIGHBORS_top_odd;
}
break;
case bottom:
switch (type) {
case even:
return NEIGHBORS_bottom_even;
case odd:
return NEIGHBORS_bottom_odd;
}
break;
case left:
switch (type) {
case even:
return NEIGHBORS_left_even;
case odd:
return NEIGHBORS_left_odd;
}
break;
case right:
switch (type) {
case even:
return NEIGHBORS_right_even;
case odd:
return NEIGHBORS_right_odd;
}
break;
default:
throw new IllegalArgumentException("Illegal combination of dir and type: dir="+dir+", type="+type);
}
throw new IllegalArgumentException("Illegal combination of dir and type: dir="+dir+", type="+type);
}
private static final String BORDERS_right_even="bcfguvyz";
private static final String BORDERS_left_even="0145hjnp";
private static final String BORDERS_top_even="prxz";
private static final String BORDERS_bottom_even="028b";
private static final String BORDERS_bottom_odd=BORDERS_left_even;
private static final String BORDERS_top_odd=BORDERS_right_even;
private static final String BORDERS_left_odd=BORDERS_bottom_even;
private static final String BORDERS_right_odd=BORDERS_top_even;
private static String BORDERS(Dir dir, Type type) {
switch (dir) {
case top:
switch (type) {
case even:
return BORDERS_top_even;
case odd:
return BORDERS_top_odd;
}
break;
case bottom:
switch (type) {
case even:
return BORDERS_bottom_even;
case odd:
return BORDERS_bottom_odd;
}
break;
case left:
switch (type) {
case even:
return BORDERS_left_even;
case odd:
return BORDERS_left_odd;
}
break;
case right:
switch (type) {
case even:
return BORDERS_right_even;
case odd:
return BORDERS_right_odd;
}
break;
default:
throw new IllegalArgumentException("Illegal combination of dir and type: dir="+dir+", type="+type);
}
throw new IllegalArgumentException("Illegal combination of dir and type: dir="+dir+", type="+type);
}
public static void refine_interval(double[] interval, int cd, int mask) {
/*
if (cd&mask)
interval[0] = (interval[0] + interval[1])/2;
else
interval[1] = (interval[0] + interval[1])/2;
*/
if ((cd&mask)!=0)
interval[0] = (interval[0] + interval[1])/2;
else
interval[1] = (interval[0] + interval[1])/2;
}
public static String calculateAdjacent(String srcHash, Dir dir) {
/*
srcHash = srcHash.toLowerCase();
var lastChr = srcHash.charAt(srcHash.length-1);
var type = (srcHash.length % 2) ? 'odd' : 'even';
var base = srcHash.substring(0,srcHash.length-1);
if (BORDERS[dir][type].indexOf(lastChr)!=-1)
base = calculateAdjacent(base, dir);
return base + BASE32[NEIGHBORS[dir][type].indexOf(lastChr)];
*/
srcHash=srcHash.toLowerCase();
char lastChr = srcHash.charAt(srcHash.length()-1);
Type type = ((srcHash.length()%2)!=0) ? Type.odd : Type.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 GeoHashPos decodeGeoHash(String geohash) {
/*
var is_even = 1;
var lat = []; var lon = [];
lat[0] = -90.0; lat[1] = 90.0;
lon[0] = -180.0; lon[1] = 180.0;
lat_err = 90.0; lon_err = 180.0;
for (i=0; i<geohash.length; i++) {
c = geohash[i];
cd = BASE32.indexOf(c);
for (j=0; j<5; j++) {
mask = BITS[j];
if (is_even) {
lon_err /= 2;
refine_interval(lon, cd, mask);
} else {
lat_err /= 2;
refine_interval(lat, cd, mask);
}
is_even = !is_even;
}
}
lat[2] = (lat[0] + lat[1])/2;
lon[2] = (lon[0] + lon[1])/2;
return { latitude: lat, longitude: lon};
*/
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<5; j++) {
int mask = BITS[j];
if (is_even) {
lon_err /= 2;
refine_interval(lon, cd, mask);
}
else {
lat_err /= 2;
refine_interval(lat, cd, mask);
}
is_even = ! is_even;
}
}
lat[2] = (lat[0] + lat[1])/2;
lon[2] = (lon[0] + lon[1])/2;
GeoHashPos pos=new GeoHashPos();
pos.latitude = lat;
pos.longitude = lon;
return pos;
}
private static class GeoHashPos {
public double[] latitude;
public double[] longitude;
}
public static String encodeGeoHash(double latitude, double longitude) {
/*
var is_even=1;
var i=0;
var lat = []; var lon = [];
var bit=0;
var ch=0;
var precision = 12;
geohash = "";
lat[0] = -90.0; lat[1] = 90.0;
lon[0] = -180.0; lon[1] = 180.0;
while (geohash.length < precision) {
if (is_even) {
mid = (lon[0] + lon[1]) / 2;
if (longitude > mid) {
ch |= BITS[bit];
lon[0] = mid;
} else
lon[1] = mid;
} else {
mid = (lat[0] + lat[1]) / 2;
if (latitude > mid) {
ch |= BITS[bit];
lat[0] = mid;
} else
lat[1] = mid;
}
is_even = !is_even;
if (bit < 4)
bit++;
else {
geohash += BASE32[ch];
bit = 0;
ch = 0;
}
}
return geohash;
*/
boolean is_even=true;
double[] lat = new double[2];
double[] lon = new double[2];
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;
if (longitude > mid) {
ch |= BITS[bit];
lon[0] = mid;
}
else {
lon[1] = mid;
}
}
else {
double mid = (lat[0] + lat[1]) / 2;
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;
}
/**
* Finds the geohashes within the area defined by the center point and the distance
*
* @param center coordinate of circle center point
* @param distance distance from circle center point to circle border
* @param unit unit for distance
* @param precision geohash precision between 1 and 12; small values result in less keys, but will most probably result in a lot more data entries to check for intersection; large values result in many keys and better accuracy, but looking up many keys in a database may take a lot longer
* @return hashes
*/
public static List<String> getHashesInArea(LatLng center, int distance, LengthUnit unit, int precision) {
if (precision < 1 || precision > 12)
throw new IllegalArgumentException("Precision must be between 1 and 12: "+precision);
LatLng rightBorder = LatLngTool.travel(center, Bearing.EAST, distance, unit);
LatLng leftBorder = LatLngTool.travel(center, Bearing.WEST, distance, unit);
LatLng topBorder = LatLngTool.travel(center, Bearing.NORTH, distance, unit);
LatLng bottomBorder = LatLngTool.travel(center, Bearing.SOUTH, distance, unit);
LatLng topLeft = new LatLng(topBorder.getLatitude(), leftBorder.getLongitude());
LatLng bottomRight = new LatLng(bottomBorder.getLatitude(), rightBorder.getLongitude());
List<String> keys = getHashesInArea(topLeft, bottomRight, precision);
return keys;
}
/**
* Finds the geohashes within the area defined by the top left and the bottom right points
*
* @param topLeft top left coordinates of a rectangle
* @param bottomRight bottom right coordinates of a rectangle
* @param precision geohash precision between 1 and 12; small values result in less keys, but will most probably result in a lot more data entries to check for intersection; large values result in many keys and better accuracy, but looking up many keys in a database may take a lot longer
* @return hashes
*/
public static List<String> getHashesInArea(LatLng topLeft, LatLng bottomRight, int precision) {
// System.out.println("topLeft="+topLeft.toString()+", bottomRight="+bottomRight.toString());
//latitude: y direction
//longitude: x direction
double latitudeTopLeft = topLeft.getLatitude();
double longitudeTopLeft = topLeft.getLongitude();
double latitudeBottomRight = bottomRight.getLatitude();
double longitudeBottomRight = bottomRight.getLongitude();
//sanity checks
if (latitudeTopLeft < latitudeBottomRight)
throw new IllegalArgumentException("latitudeTopLeft cannot be less than latitudeBottomRight");
if (longitudeTopLeft > longitudeBottomRight)
throw new IllegalArgumentException("longitudeTopLeft cannot be greater than longitudeBottomRight");
//compute the other coordinates
double latitudeTopRight = latitudeTopLeft;
double longitudeTopRight = longitudeBottomRight;
double latitudeBottomLeft = latitudeBottomRight;
double longitudeBottomLeft = longitudeTopLeft;
String topLeftHash = encodeGeoHash(latitudeTopLeft, longitudeTopLeft).substring(0,precision);
String topRightHash = encodeGeoHash(latitudeTopRight, longitudeTopRight).substring(0,precision);
String bottomLeftHash = encodeGeoHash(latitudeBottomLeft, longitudeBottomLeft).substring(0,precision);
String bottomRightHash = encodeGeoHash(latitudeBottomRight, longitudeBottomRight).substring(0,precision);
GeoHashBox topLeftBox = new GeoHashBox(topLeftHash);
if (!topLeftBox.contains(topLeft))
throw new IllegalArgumentException("topLeftBox must contain topLeft");
GeoHashBox bottomRightBox = new GeoHashBox(bottomRightHash);
if (!bottomRightBox.contains(bottomRight))
throw new IllegalArgumentException("bottomRightBox must contain bottomRight");
//compute the number of columns in our search area
int columns = 1;
String currHash=topLeftHash;
while (!currHash.equals(topRightHash)) {
String nextHash = calculateAdjacent(currHash, Dir.right);
columns++;
currHash = nextHash;
}
//compute the number of rows in our search area
int rows = 1;
currHash=topLeftHash;
while (!currHash.equals(bottomLeftHash)) {
rows++;
String nextHash = calculateAdjacent(currHash, Dir.bottom);
currHash = nextHash;
}
List<String> hashesInArea = new ArrayList<String>();
//now traverse the whole area and collect the hashes
String firstColHash=topLeftHash;
for (int y=0; y<rows; y++) {
//reset currHash to first column
currHash = firstColHash;
for (int x=0; x<columns; x++) {
hashesInArea.add(currHash);
currHash = calculateAdjacent(currHash, Dir.right);
}
//move to next row
firstColHash = calculateAdjacent(firstColHash, Dir.bottom);
}
return hashesInArea;
}
public static void main(String[] args) {
double latitude = 38.8970960;
double longitude = -77.0365450;
LatLng point=new LatLng(latitude, longitude);
/*
String simplelatlngHash=Geohasher.hash(point);
System.out.println("simplelatlngHash: "+simplelatlngHash);
String geohash = encodeGeoHash(latitude, longitude);
System.out.println("["+latitude+","+longitude+"] => "+geohash);
*/
/*
GeoHashBox centerBox=new GeoHashBox(geohash);
System.out.println("center: "+centerBox.getGeohash());
for (Dir dir : Dir.values()) {
GeoHashBox neighborBox=centerBox.getNeighbor(dir);
System.out.println(dir.toString()+": "+neighborBox.getGeohash());
}
*/
int maxHashes=10;
int distance=500;
LengthUnit unit=LengthUnit.METER;
long t0=System.currentTimeMillis();
List<String> hashes=getOptimalHashesInArea(point, distance, unit, maxHashes);
long t1=System.currentTimeMillis();
System.out.println("Computing hashes took "+(t1-t0)+"ms");
System.out.println("Highest precision for distance "+distance+" "+unit.toString()+" with less than "+maxHashes+" hashes is "+hashes.get(0).length()+" with "+hashes.size()+" hashes");
/*
List<String> hashesInArea=getHashesInArea(point, 100, LengthUnit.METER, 3);
System.out.println(Integer.toString(hashesInArea.size())+" hashesInArea found: "+hashesInArea);
*/
System.exit(0);
}
/**
* The method computes the geohashes for precisions between 1 and 12 and finds the
* highest precision where the number of hashes still lower than <i>maxHashes<i>.
*
* @param topLeft top left coordinates of a rectangle
* @param bottomRight bottom right coordinates of a rectangle
* @param maxHashes maximum of hashes to return, e.g. 5 to do max 5 hash prefix lookups
* @return hashes
*/
public static List<String> getOptimalHashesInArea(LatLng topLeft, LatLng bottomRight, int maxHashes) {
List<String> hashesInAreaForHighestPrecision=null;
for (int precision=1; precision<=12; precision++) {
List<String> hashesInArea=getHashesInArea(topLeft, bottomRight, precision);
if (hashesInArea.size() <= maxHashes) {
hashesInAreaForHighestPrecision=hashesInArea;
}
else
break;
}
return hashesInAreaForHighestPrecision;
}
/**
* The method computes the geohashes for precisions between 1 and 12 and finds the
* highest precision where the number of hashes still lower than <i>maxHashes<i>.
*
* @param center center point
* @param distance distance for search area
* @param unit unit for distance
* @param maxHashes maximum of hashes to return, e.g. 5 to do max 5 hash prefix lookups
* @return hashes
*/
public static List<String> getOptimalHashesInArea(LatLng center, int distance, LengthUnit unit, int maxHashes) {
List<String> hashesInAreaForHighestPrecision=null;
for (int precision=1; precision<=12; precision++) {
List<String> hashesInArea=getHashesInArea(center, distance, unit, precision);
if (hashesInArea.size() <= maxHashes) {
hashesInAreaForHighestPrecision=hashesInArea;
}
else
break;
}
return hashesInAreaForHighestPrecision;
}
public static class GeoHashBox {
private String m_geohash;
private GeoHashPos m_box;
private LatLng m_corners_topleft;
private LatLng m_corners_topright;
private LatLng m_corners_bottomright;
private LatLng m_corners_bottomleft;
private LatLng m_centerPoint;
private int m_selfPos;
private GeoHashBox m_neighbors_top;
private GeoHashBox m_neighbors_bottom;
private GeoHashBox m_neighbors_right;
private GeoHashBox m_neighbors_left;
private GeoHashBox m_neighbors_topleft;
private GeoHashBox m_neighbors_topright;
private GeoHashBox m_neighbors_bottomright;
private GeoHashBox m_neighbors_bottomleft;
public GeoHashBox(String geohash) {
this.m_geohash = geohash;
this.m_box = decodeGeoHash(geohash);
// m_corners_topleft = new LatLng(m_box.latitude[0], m_box.longitude[0]);
// m_corners_topright = new LatLng(m_box.latitude[1], m_box.longitude[0]);
// m_corners_bottomright = new LatLng(m_box.latitude[1], m_box.longitude[1]);
// m_corners_bottomleft = new LatLng(m_box.latitude[0], m_box.longitude[1]);
m_corners_topleft = new LatLng(m_box.latitude[1], m_box.longitude[0]);
m_corners_topright = new LatLng(m_box.latitude[1], m_box.longitude[1]);
m_corners_bottomright = new LatLng(m_box.latitude[0], m_box.longitude[1]);
m_corners_bottomleft = new LatLng(m_box.latitude[0], m_box.longitude[0]);
m_centerPoint = new LatLng((m_box.latitude[0] + m_box.latitude[1])/2, (m_box.longitude[0] + m_box.longitude[1])/2);
char lastChr = m_geohash.charAt(m_geohash.length()-1);
m_selfPos = BASE32.indexOf(lastChr);
}
public String toString() {
return "[topleft: "+m_corners_topleft+", topright: "+m_corners_topright+", bottomleft: "+m_corners_bottomleft+", bottomright: "+m_corners_bottomright+"]";
}
public String getGeohash() {
return m_geohash;
}
public LatLng getCenterPoint() {
return m_centerPoint;
}
public LatLng getCorner(Dir dir) {
switch (dir) {
case topleft:
return m_corners_topleft;
case topright:
return m_corners_topright;
case bottomleft:
return m_corners_bottomleft;
case bottomright:
return m_corners_bottomright;
default:
throw new IllegalArgumentException("Unsupported direction for this operation: "+dir);
}
}
public boolean contains(LatLng point) {
return getCorner(Dir.bottomleft).getLatitude() <= point.getLatitude() &&
point.getLatitude() <= getCorner(Dir.topleft).getLatitude() &&
getCorner(Dir.bottomleft).getLongitude() <= point.getLongitude() &&
point.getLongitude() <= getCorner(Dir.bottomright).getLongitude();
}
public GeoHashBox getNeighbor(Dir dir) {
switch (dir) {
case top:
if (m_neighbors_top==null) {
m_neighbors_top = new GeoHashBox(calculateAdjacent(m_geohash, Dir.top));
}
return m_neighbors_top;
case left:
if (m_neighbors_left==null) {
m_neighbors_left=new GeoHashBox(calculateAdjacent(m_geohash, Dir.left));
}
return m_neighbors_left;
case right:
if (m_neighbors_right==null) {
m_neighbors_right=new GeoHashBox(calculateAdjacent(m_geohash, Dir.right));
}
return m_neighbors_right;
case bottom:
if (m_neighbors_bottom==null) {
m_neighbors_bottom=new GeoHashBox(calculateAdjacent(m_geohash, Dir.bottom));
}
return m_neighbors_bottom;
case topleft:
if (m_neighbors_topleft==null) {
m_neighbors_topleft=new GeoHashBox(calculateAdjacent(getNeighbor(Dir.left).getGeohash(), Dir.top));
}
return m_neighbors_topleft;
case topright:
if (m_neighbors_topright==null) {
m_neighbors_topright=new GeoHashBox(calculateAdjacent(getNeighbor(Dir.right).getGeohash(), Dir.top));
}
return m_neighbors_topright;
case bottomleft:
if (m_neighbors_bottomleft==null) {
m_neighbors_bottomleft=new GeoHashBox(calculateAdjacent(getNeighbor(Dir.left).getGeohash(), Dir.bottom));
}
return m_neighbors_bottomleft;
case bottomright:
if (m_neighbors_bottomright==null) {
m_neighbors_bottomright=new GeoHashBox(calculateAdjacent(getNeighbor(Dir.right).getGeohash(), Dir.bottom));
}
return m_neighbors_bottomright;
default:
throw new IllegalArgumentException("Unsupported direction for this operation: "+dir);
}
}
}
/**
* Converts DMS format (degrees, minutes, seconds) like 25"40'25 format to decimal format
*
* @param degrees degrees
* @param minutes minutes
* @param seconds seconds
* @return decimal value
*/
public static double convertDMSToDecimalDegree(double degrees, double minutes, double seconds) {
return Math.signum(degrees) * (Math.abs(degrees) + (Math.abs(minutes)/60) + (Math.abs(seconds)/3600));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment