Faster GeoHashUtils
-------------------
Key: LUCENE-2965
URL: https://issues.apache.org/jira/browse/LUCENE-2965
Project: Lucene - Java
Issue Type: Improvement
Components: contrib/spatial
Affects Versions: 3.0.3, 3.0.2, 3.0.1, 3.0, 2.9.4, 2.9.2
Reporter: 朱文彬
I found the current implement of
org.apache.lucene.spatial.geohash.GeoHashUtils.encode and decode is slow and
this is my improvement (400% faster )
/**
* Encodes the given latitude and longitude into a geohash
*
* @param latitude Latitude to encode
* @param longitude Longitude to encode
* @return Geohash encoding of the longitude and latitude
*/
public static String encode(double latitude, double longitude) {
double latL = -90, latH = 90;
double lngL = -180, lngH = 180;
double mid;
// assert PRECISION % 2 == 0;
final char[] geohash = new char[PRECISION];
int len = 0;
int ch = 0;
while (len < PRECISION) {
if (longitude > (mid = (lngL + lngH) * 0.5)) {
ch |= 16;
lngL = mid;
} else
lngH = mid;
if (longitude > (mid = (lngL + lngH) * 0.5)) {
ch |= 4;
lngL = mid;
} else
lngH = mid;
if (longitude > (mid = (lngL + lngH) * 0.5)) {
ch |= 1;
lngL = mid;
} else {
lngH = mid;
}
if (latitude > (mid = (latL + latH) * 0.5)) {
ch |= 8;
latL = mid;
} else {
latH = mid;
}
if (latitude > (mid = (latL + latH) * 0.5)) {
ch |= 2;
latL = mid;
} else {
latH = mid;
}
geohash[len++] = BASE_32[ch];
ch = 0;
if (latitude > (mid = (latL + latH) * 0.5)) {
ch |= 16;
latL = mid;
} else
latH = mid;
if (longitude > (mid = (lngL + lngH) * 0.5)) {
ch |= 8;
lngL = mid;
} else
lngH = mid;
if (latitude > (mid = (latL + latH) * 0.5)) {
ch |= 4;
latL = mid;
} else
latH = mid;
if (longitude > (mid = (lngL + lngH) * 0.5)) {
ch |= 2;
lngL = mid;
} else
lngH = mid;
if (latitude > (mid = (latL + latH) * 0.5)) {
ch |= 1;
latL = mid;
} else
latH = mid;
geohash[len++] = BASE_32[ch];
ch = 0;
}
return new String(geohash);
}
/**
* Decodes the given geohash into a latitude and longitude
*
* @param geohash Geohash to deocde
* @return Array with the latitude at index 0, and longitude at index 1
*/
public static double[] decode(String geohash) {
double latL = -90.0, latH = 90.0;
double lngL = -180.0, lngH = 180.0;
double gap;
int len = geohash.length();
for (int i = 0; i < len; ) {
switch (geohash.charAt(i++)) {
case '0':
latH -= (latH - latL) * 0.75;
lngH -= (lngH - lngL) * 0.875;
break;
case '1':
latH -= (latH - latL) * 0.75;
gap = lngH - lngL;
lngL += gap * 0.125;
lngH -= gap * 0.75;
break;
case '2':
gap = latH - latL;
latL += gap * 0.25;
latH -= gap * 0.5;
lngH -= (lngH - lngL) * 0.875;
break;
case '3':
gap = latH - latL;
latL += gap * 0.25;
latH -= gap * 0.5;
gap = lngH - lngL;
lngL += gap * 0.125;
lngH -= gap * 0.75;
break;
case '4':
latH -= (latH - latL) * 0.75;
gap = lngH - lngL;
lngL += gap * 0.25;
lngH -= gap * 0.625;
break;
case '5':
latH -= (latH - latL) * 0.75;
gap = lngH - lngL;
lngL += gap * 0.375;
lngH -= gap * 0.5;
break;
case '6':
gap = latH - latL;
latL += gap * 0.25;
latH -= gap * 0.5;
gap = lngH - lngL;
lngL += gap * 0.25;
lngH -= gap * 0.625;
break;
case '7':
gap = latH - latL;
latL += gap * 0.25;
latH -= gap * 0.5;
gap = lngH - lngL;
lngL += gap * 0.375;
lngH -= gap * 0.5;
break;
case '8':
gap = latH - latL;
latL += gap * 0.5;
latH -= gap * 0.25;
lngH -= (lngH - lngL) * 0.875;
break;
case '9':
gap = latH - latL;
latL += gap * 0.5;
latH -= gap * 0.25;
gap = lngH - lngL;
lngL += gap * 0.125;
lngH -= gap * 0.75;
break;
case 'b':
latL += (latH - latL) * 0.75;
lngH -= (lngH - lngL) * 0.875;
break;
case 'c':
latL += (latH - latL) * 0.75;
gap = lngH - lngL;
lngL += gap * 0.125;
lngH -= gap * 0.75;
break;
case 'd':
gap = latH - latL;
latL += gap * 0.5;
latH -= gap * 0.25;
gap = lngH - lngL;
lngL += gap * 0.25;
lngH -= gap * 0.625;
break;
case 'e':
gap = latH - latL;
latL += gap * 0.5;
latH -= gap * 0.25;
gap = lngH - lngL;
lngL += gap * 0.375;
lngH -= gap * 0.5;
break;
case 'f':
latL += (latH - latL) * 0.75;
gap = lngH - lngL;
lngL += gap * 0.25;
lngH -= gap * 0.625;
break;
case 'g':
latL += (latH - latL) * 0.75;
gap = lngH - lngL;
lngL += gap * 0.375;
lngH -= gap * 0.5;
break;
case 'h':
latH -= (latH - latL) * 0.75;
gap = lngH - lngL;
lngL += gap * 0.5;
lngH -= gap * 0.375;
break;
case 'j':
latH -= (latH - latL) * 0.75;
gap = lngH - lngL;
lngL += gap * 0.625;
lngH -= gap * 0.25;
break;
case 'k':
gap = latH - latL;
latL += gap * 0.25;
latH -= gap * 0.5;
gap = lngH - lngL;
lngL += gap * 0.5;
lngH -= gap * 0.375;
break;
case 'm':
gap = latH - latL;
latL += gap * 0.25;
latH -= gap * 0.5;
gap = lngH - lngL;
lngL += gap * 0.625;
lngH -= gap * 0.25;
break;
case 'n':
latH -= (latH - latL) * 0.75;
gap = lngH - lngL;
lngL += gap * 0.75;
lngH -= gap * 0.125;
break;
case 'p':
latH -= (latH - latL) * 0.75;
lngL += (lngH - lngL) * 0.875;
break;
case 'q':
gap = latH - latL;
latL += gap * 0.25;
latH -= gap * 0.5;
gap = lngH - lngL;
lngL += gap * 0.75;
lngH -= gap * 0.125;
break;
case 'r':
gap = latH - latL;
latL += gap * 0.25;
latH -= gap * 0.5;
lngL += (lngH - lngL) * 0.875;
break;
case 's':
gap = latH - latL;
latL += gap * 0.5;
latH -= gap * 0.25;
gap = lngH - lngL;
lngL += gap * 0.5;
lngH -= gap * 0.375;
break;
case 't':
gap = latH - latL;
latL += gap * 0.5;
latH -= gap * 0.25;
gap = lngH - lngL;
lngL += gap * 0.625;
lngH -= gap * 0.25;
break;
case 'u':
latL += (latH - latL) * 0.75;
gap = lngH - lngL;
lngL += gap * 0.5;
lngH -= gap * 0.375;
break;
case 'v':
latL += (latH - latL) * 0.75;
gap = lngH - lngL;
lngL += gap * 0.625;
lngH -= gap * 0.25;
break;
case 'w':
gap = latH - latL;
latL += gap * 0.5;
latH -= gap * 0.25;
gap = lngH - lngL;
lngL += gap * 0.75;
lngH -= gap * 0.125;
break;
case 'x':
gap = latH - latL;
latL += gap * 0.5;
latH -= gap * 0.25;
lngL += (lngH - lngL) * 0.875;
break;
case 'y':
latL += (latH - latL) * 0.75;
gap = lngH - lngL;
lngL += gap * 0.75;
lngH -= gap * 0.125;
break;
case 'z':
latL += (latH - latL) * 0.75;
lngL += (lngH - lngL) * 0.875;
break;
}
switch (geohash.charAt(i++)) {
case '0':
latH -= (latH - latL) * 0.875;
lngH -= (lngH - lngL) * 0.75;
break;
case '1':
gap = latH - latL;
latL += gap * 0.125;
latH -= gap * 0.75;
lngH -= (lngH - lngL) * 0.75;
break;
case '2':
latH -= (latH - latL) * 0.875;
gap = lngH - lngL;
lngL += gap * 0.25;
lngH -= gap * 0.5;
break;
case '3':
gap = latH - latL;
latL += gap * 0.125;
latH -= gap * 0.75;
gap = lngH - lngL;
lngL += gap * 0.25;
lngH -= gap * 0.5;
break;
case '4':
gap = latH - latL;
latL += gap * 0.25;
latH -= gap * 0.625;
lngH -= (lngH - lngL) * 0.75;
break;
case '5':
gap = latH - latL;
latL += gap * 0.375;
latH -= gap * 0.5;
lngH -= (lngH - lngL) * 0.75;
break;
case '6':
gap = latH - latL;
latL += gap * 0.25;
latH -= gap * 0.625;
gap = lngH - lngL;
lngL += gap * 0.25;
lngH -= gap * 0.5;
break;
case '7':
gap = latH - latL;
latL += gap * 0.375;
latH -= gap * 0.5;
gap = lngH - lngL;
lngL += gap * 0.25;
lngH -= gap * 0.5;
break;
case '8':
latH -= (latH - latL) * 0.875;
gap = lngH - lngL;
lngL += gap * 0.5;
lngH -= gap * 0.25;
break;
case '9':
gap = latH - latL;
latL += gap * 0.125;
latH -= gap * 0.75;
gap = lngH - lngL;
lngL += gap * 0.5;
lngH -= gap * 0.25;
break;
case 'b':
latH -= (latH - latL) * 0.875;
lngL += (lngH - lngL) * 0.75;
break;
case 'c':
gap = latH - latL;
latL += gap * 0.125;
latH -= gap * 0.75;
lngL += (lngH - lngL) * 0.75;
break;
case 'd':
gap = latH - latL;
latL += gap * 0.25;
latH -= gap * 0.625;
gap = lngH - lngL;
lngL += gap * 0.5;
lngH -= gap * 0.25;
break;
case 'e':
gap = latH - latL;
latL += gap * 0.375;
latH -= gap * 0.5;
gap = lngH - lngL;
lngL += gap * 0.5;
lngH -= gap * 0.25;
break;
case 'f':
gap = latH - latL;
latL += gap * 0.25;
latH -= gap * 0.625;
lngL += (lngH - lngL) * 0.75;
break;
case 'g':
gap = latH - latL;
latL += gap * 0.375;
latH -= gap * 0.5;
lngL += (lngH - lngL) * 0.75;
break;
case 'h':
gap = latH - latL;
latL += gap * 0.5;
latH -= gap * 0.375;
lngH -= (lngH - lngL) * 0.75;
break;
case 'j':
gap = latH - latL;
latL += gap * 0.625;
latH -= gap * 0.25;
lngH -= (lngH - lngL) * 0.75;
break;
case 'k':
gap = latH - latL;
latL += gap * 0.5;
latH -= gap * 0.375;
gap = lngH - lngL;
lngL += gap * 0.25;
lngH -= gap * 0.5;
break;
case 'm':
gap = latH - latL;
latL += gap * 0.625;
latH -= gap * 0.25;
gap = lngH - lngL;
lngL += gap * 0.25;
lngH -= gap * 0.5;
break;
case 'n':
gap = latH - latL;
latL += gap * 0.75;
latH -= gap * 0.125;
lngH -= (lngH - lngL) * 0.75;
break;
case 'p':
latL += (latH - latL) * 0.875;
lngH -= (lngH - lngL) * 0.75;
break;
case 'q':
gap = latH - latL;
latL += gap * 0.75;
latH -= gap * 0.125;
gap = lngH - lngL;
lngL += gap * 0.25;
lngH -= gap * 0.5;
break;
case 'r':
latL += (latH - latL) * 0.875;
gap = lngH - lngL;
lngL += gap * 0.25;
lngH -= gap * 0.5;
break;
case 's':
gap = latH - latL;
latL += gap * 0.5;
latH -= gap * 0.375;
gap = lngH - lngL;
lngL += gap * 0.5;
lngH -= gap * 0.25;
break;
case 't':
gap = latH - latL;
latL += gap * 0.625;
latH -= gap * 0.25;
gap = lngH - lngL;
lngL += gap * 0.5;
lngH -= gap * 0.25;
break;
case 'u':
gap = latH - latL;
latL += gap * 0.5;
latH -= gap * 0.375;
lngL += (lngH - lngL) * 0.75;
break;
case 'v':
gap = latH - latL;
latL += gap * 0.625;
latH -= gap * 0.25;
lngL += (lngH - lngL) * 0.75;
break;
case 'w':
gap = latH - latL;
latL += gap * 0.75;
latH -= gap * 0.125;
gap = lngH - lngL;
lngL += gap * 0.5;
lngH -= gap * 0.25;
break;
case 'x':
latL += (latH - latL) * 0.875;
gap = lngH - lngL;
lngL += gap * 0.5;
lngH -= gap * 0.25;
break;
case 'y':
gap = latH - latL;
latL += gap * 0.75;
latH -= gap * 0.125;
lngL += (lngH - lngL) * 0.75;
break;
case 'z':
latL += (latH - latL) * 0.875;
lngL += (lngH - lngL) * 0.75;
break;
}
}
return new double[] { (latL + latH) / 2D, (lngL + lngH) / 2D };
}
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
