GeoHash utilities in Java

GeoHashUtils.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));
	}
}