lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From 朱文彬 (JIRA) <j...@apache.org>
Subject [jira] Created: (LUCENE-2965) Faster GeoHashUtils
Date Fri, 11 Mar 2011 13:57:00 GMT
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-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


Mime
View raw message