Created
June 5, 2019 06:08
-
-
Save paul-brebner/a67243859d2cf38bd9038a12a7b14762 to your computer and use it in GitHub Desktop.
Demonstration of 3D Geohash encoding, based on https://github.com/kungfoo/geohash-java/blob/master/src/main/java/ch/hsr/geohash/GeoHash.java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* 3D Geohash modified from https://github.com/kungfoo/geohash-java/blob/master/src/main/java/ch/hsr/geohash/GeoHash.java | |
* Paul Brebner, Instaclustr.com | |
* 5 June 2019 | |
* Just a demonstration of how altitude can be used to encode a 3D geohash, for use with Anomalia Machina blog series. | |
*/ | |
import java.io.Serializable; | |
import java.util.HashMap; | |
import java.util.Map; | |
public final class GeoHash3D implements Comparable<GeoHash3D>, Serializable { | |
private static final int MAX_BIT_PRECISION = 64; | |
private static final int MAX_CHARACTER_PRECISION = 12; | |
public static final long FIRST_BIT_FLAGGED = 0x8000000000000000l; | |
private static final char[] base32 = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'b', 'c', 'd', 'e', 'f', | |
'g', 'h', 'j', 'k', 'm', 'n', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' }; | |
private final static Map<Character, Integer> decodeMap = new HashMap<>(); | |
static { | |
int sz = base32.length; | |
for (int i = 0; i < sz; i++) { | |
decodeMap.put(base32[i], i); | |
} | |
} | |
protected long bits = 0; | |
protected byte significantBits = 0; | |
protected GeoHash3D() { | |
} | |
/** | |
* This method uses the given number of characters as the desired precision | |
* value. The hash can only be 64bits long, thus a maximum precision of 12 | |
* characters can be achieved. | |
*/ | |
public static GeoHash3D withCharacterPrecision(double latitude, double longitude, double altitude, int numberOfCharacters) { | |
if (numberOfCharacters > MAX_CHARACTER_PRECISION) { | |
throw new IllegalArgumentException("A geohash can only be " + MAX_CHARACTER_PRECISION + " character long."); | |
} | |
int desiredPrecision = (numberOfCharacters * 5 <= 60) ? numberOfCharacters * 5 : 60; | |
return new GeoHash3D(latitude, longitude, altitude, desiredPrecision); | |
} | |
/** | |
* This method uses the given number of characters as the desired precision | |
* value. The hash can only be 64bits long, thus a maximum precision of 12 | |
* characters can be achieved. | |
* Altitude is in units of km, - is below sea level, + is above sea level. | |
*/ | |
public static String geoHashStringWithCharacterPrecision(double latitude, double longitude, double altitude, int numberOfCharacters) { | |
GeoHash3D hash = withCharacterPrecision(latitude, longitude, altitude, numberOfCharacters); | |
return hash.toBase32(); | |
} | |
private GeoHash3D(double latitude, double longitude, double altitude, int desiredPrecision) { | |
desiredPrecision = Math.min(desiredPrecision, MAX_BIT_PRECISION); | |
int bit = 1; | |
double[] latitudeRange = { -90, 90 }; | |
double[] longitudeRange = { -180, 180 }; | |
// convert from km to degrees so altitude has the same range as latitude and longitude | |
// radius of the earth is only 6356km | |
// allowable altitude could be from -6356 to 35786km, sufficient range for altitudes from the centre of earth to geostationary orbit. | |
// this is a bit more than the range of longitude (which is 2 * 180 * 100km = 36,000km). Given that depths below 12.2km (deepest borehole) | |
// aren't practically useful, could limit to this giving very close to same range as longitude. | |
// Should check the altitude and throw exception if outside range. | |
double[] altitudeRange = {-13, 35786}; | |
while (significantBits < desiredPrecision) { | |
if (bit == 1) { | |
divideRangeEncode(longitude, longitudeRange); | |
} else if (bit == 2) | |
{ | |
divideRangeEncode(latitude, latitudeRange); | |
} | |
else | |
{ | |
divideRangeEncode(altitude, altitudeRange); | |
} | |
if (++bit > 3) bit = 1; | |
} | |
bits <<= (MAX_BIT_PRECISION - desiredPrecision); | |
} | |
public long ord() { | |
int insignificantBits = MAX_BIT_PRECISION - significantBits; | |
return bits >>> insignificantBits; | |
} | |
/** | |
* Returns the number of characters that represent this hash. | |
* | |
* @throws IllegalStateException | |
* when the hash cannot be encoded in base32, i.e. when the | |
* precision is not a multiple of 5. | |
*/ | |
public int getCharacterPrecision() { | |
if (significantBits % 5 != 0) { | |
throw new IllegalStateException( | |
"precision of GeoHash is not divisble by 5: " + this); | |
} | |
return significantBits / 5; | |
} | |
private void divideRangeEncode(double value, double[] range) { | |
double mid = (range[0] + range[1]) / 2; | |
if (value >= mid) { | |
addOnBitToEnd(); | |
range[0] = mid; | |
} else { | |
addOffBitToEnd(); | |
range[1] = mid; | |
} | |
} | |
/** | |
* how many significant bits are there in this {@link GeoHash3D}? | |
*/ | |
public int significantBits() { | |
return significantBits; | |
} | |
public long longValue() { | |
return bits; | |
} | |
/** | |
* get the base32 string for this {@link GeoHash3D}.<br> | |
* this method only makes sense, if this hash has a multiple of 5 | |
* significant bits. | |
* | |
* @throws IllegalStateException | |
* when the number of significant bits is not a multiple of 5. | |
*/ | |
public String toBase32() { | |
if (significantBits % 5 != 0) { | |
throw new IllegalStateException("Cannot convert a geohash to base32 if the precision is not a multiple of 5."); | |
} | |
StringBuilder buf = new StringBuilder(); | |
long firstFiveBitsMask = 0xf800000000000000l; | |
long bitsCopy = bits; | |
int partialChunks = (int) Math.ceil(((double) significantBits / 5)); | |
for (int i = 0; i < partialChunks; i++) { | |
int pointer = (int) ((bitsCopy & firstFiveBitsMask) >>> 59); | |
buf.append(base32[pointer]); | |
bitsCopy <<= 5; | |
} | |
return buf.toString(); | |
} | |
protected final void addOnBitToEnd() { | |
significantBits++; | |
bits <<= 1; | |
bits = bits | 0x1; | |
} | |
protected final void addOffBitToEnd() { | |
significantBits++; | |
bits <<= 1; | |
} | |
public String toBinaryString() { | |
StringBuilder bui = new StringBuilder(); | |
long bitsCopy = bits; | |
for (int i = 0; i < significantBits; i++) { | |
if ((bitsCopy & FIRST_BIT_FLAGGED) == FIRST_BIT_FLAGGED) { | |
bui.append('1'); | |
} else { | |
bui.append('0'); | |
} | |
bitsCopy <<= 1; | |
} | |
return bui.toString(); | |
} | |
@Override | |
public boolean equals(Object obj) { | |
if (obj == this) { | |
return true; | |
} | |
if (obj instanceof GeoHash3D) { | |
GeoHash3D other = (GeoHash3D) obj; | |
if (other.significantBits == significantBits && other.bits == bits) { | |
return true; | |
} | |
} | |
return false; | |
} | |
@Override | |
public int hashCode() { | |
int f = 17; | |
f = 31 * f + (int) (bits ^ (bits >>> 32)); | |
f = 31 * f + significantBits; | |
return f; | |
} | |
@Override | |
public int compareTo(GeoHash3D o) { | |
int bitsCmp = Long.compare(bits ^ FIRST_BIT_FLAGGED, o.bits ^ FIRST_BIT_FLAGGED); | |
if (bitsCmp != 0) { | |
return bitsCmp; | |
} else { | |
return Integer.compare(significantBits, o.significantBits); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment