You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by ds...@apache.org on 2012/02/20 23:45:37 UTC
svn commit: r1291499 [2/12] - in
/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene:
./ src/ src/main/ src/main/java/ src/main/java/org/
src/main/java/org/apache/ src/main/java/org/apache/lucene/
src/main/java/org/apache/lucene/s...
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/distance/DistanceUtils.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/distance/DistanceUtils.java?rev=1291499&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/distance/DistanceUtils.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/distance/DistanceUtils.java Mon Feb 20 22:45:32 2012
@@ -0,0 +1,427 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.lucene.spatial.base.distance;
+
+import org.apache.lucene.spatial.base.context.SpatialContext;
+import org.apache.lucene.spatial.base.shape.Rectangle;
+
+import static java.lang.Math.toRadians;
+
+/**
+ * Various distance calculations and constants.
+ * Originally from Lucene 3x's old spatial module. It has been modified here.
+ */
+public class DistanceUtils {
+
+ //pre-compute some angles that are commonly used
+ public static final double DEG_45_AS_RADS = Math.PI / 4.0;
+ public static final double SIN_45_AS_RADS = Math.sin(DEG_45_AS_RADS);
+ public static final double DEG_90_AS_RADS = Math.PI / 2;
+ public static final double DEG_180_AS_RADS = Math.PI;
+ public static final double DEG_225_AS_RADS = 5 * DEG_45_AS_RADS;
+ public static final double DEG_270_AS_RADS = 3 * DEG_90_AS_RADS;
+
+
+ public static final double KM_TO_MILES = 0.621371192;
+ public static final double MILES_TO_KM = 1 / KM_TO_MILES;//1.609
+
+ /**
+ * The International Union of Geodesy and Geophysics says the Earth's mean radius in KM is:
+ *
+ * [1] http://en.wikipedia.org/wiki/Earth_radius
+ */
+ public static final double EARTH_MEAN_RADIUS_KM = 6371.0087714;
+ public static final double EARTH_EQUATORIAL_RADIUS_KM = 6378.1370;
+
+ public static final double EARTH_MEAN_RADIUS_MI = EARTH_MEAN_RADIUS_KM * KM_TO_MILES;
+ public static final double EARTH_EQUATORIAL_RADIUS_MI = EARTH_EQUATORIAL_RADIUS_KM * KM_TO_MILES;
+
+ /**
+ * Calculate the p-norm (i.e. length) between two vectors
+ *
+ * @param vec1 The first vector
+ * @param vec2 The second vector
+ * @param power The power (2 for cartesian distance, 1 for manhattan, etc.)
+ * @return The length.
+ * <p/>
+ * See http://en.wikipedia.org/wiki/Lp_space
+ * @see #vectorDistance(double[], double[], double, double)
+ */
+ public static double vectorDistance(double[] vec1, double[] vec2, double power) {
+ return vectorDistance(vec1, vec2, power, 1.0 / power);
+ }
+
+ /**
+ * Calculate the p-norm (i.e. length) between two vectors
+ *
+ * @param vec1 The first vector
+ * @param vec2 The second vector
+ * @param power The power (2 for cartesian distance, 1 for manhattan, etc.)
+ * @param oneOverPower If you've precalculated oneOverPower and cached it, use this method to save one division operation over {@link #vectorDistance(double[], double[], double)}.
+ * @return The length.
+ */
+ public static double vectorDistance(double[] vec1, double[] vec2, double power, double oneOverPower) {
+ double result = 0;
+
+ if (power == 0) {
+ for (int i = 0; i < vec1.length; i++) {
+ result += vec1[i] - vec2[i] == 0 ? 0 : 1;
+ }
+
+ } else if (power == 1.0) {
+ for (int i = 0; i < vec1.length; i++) {
+ result += vec1[i] - vec2[i];
+ }
+ } else if (power == 2.0) {
+ result = Math.sqrt(distSquaredCartesian(vec1, vec2));
+ } else if (power == Integer.MAX_VALUE || Double.isInfinite(power)) {//infinite norm?
+ for (int i = 0; i < vec1.length; i++) {
+ result = Math.max(result, Math.max(vec1[i], vec2[i]));
+ }
+ } else {
+ for (int i = 0; i < vec1.length; i++) {
+ result += Math.pow(vec1[i] - vec2[i], power);
+ }
+ result = Math.pow(result, oneOverPower);
+ }
+ return result;
+ }
+
+ /**
+ * Return the coordinates of a vector that is the corner of a box (upper right or lower left), assuming a Rectangular
+ * coordinate system. Note, this does not apply for points on a sphere or ellipse (although it could be used as an approximation).
+ *
+ * @param center The center point
+ * @param result Holds the result, potentially resizing if needed.
+ * @param distance The d from the center to the corner
+ * @param upperRight If true, return the coords for the upper right corner, else return the lower left.
+ * @return The point, either the upperLeft or the lower right
+ */
+ public static double[] vectorBoxCorner(double[] center, double[] result, double distance, boolean upperRight) {
+ if (result == null || result.length != center.length) {
+ result = new double[center.length];
+ }
+ if (upperRight == false) {
+ distance = -distance;
+ }
+ //We don't care about the power here,
+ // b/c we are always in a rectangular coordinate system, so any norm can be used by
+ //using the definition of sine
+ distance = SIN_45_AS_RADS * distance; // sin(Pi/4) == (2^0.5)/2 == opp/hyp == opp/distance, solve for opp, similarly for cosine
+ for (int i = 0; i < center.length; i++) {
+ result[i] = center[i] + distance;
+ }
+ return result;
+ }
+
+ /**
+ * Given a start point (startLat, startLon) and a bearing on a sphere of radius <i>sphereRadius</i>, return the destination point.
+ *
+ *
+ * @param startLat The starting point latitude, in radians
+ * @param startLon The starting point longitude, in radians
+ * @param distanceRAD The distance to travel along the bearing in radians.
+ * @param bearingRAD The bearing, in radians. North is a 0, moving clockwise till radians(360).
+ * @param result A preallocated array to hold the results. If null, a new one is constructed.
+ * @return The destination point, in radians. First entry is latitude, second is longitude
+ */
+ public static double[] pointOnBearingRAD(double startLat, double startLon, double distanceRAD, double bearingRAD, double[] result) {
+ /*
+ lat2 = asin(sin(lat1)*cos(d/R) + cos(lat1)*sin(d/R)*cos(θ))
+ lon2 = lon1 + atan2(sin(θ)*sin(d/R)*cos(lat1), cos(d/R)âsin(lat1)*sin(lat2))
+
+ */
+ double cosAngDist = Math.cos(distanceRAD);
+ double cosStartLat = Math.cos(startLat);
+ double sinAngDist = Math.sin(distanceRAD);
+ double sinStartLat = Math.sin(startLat);
+ double lat2 = Math.asin(sinStartLat * cosAngDist +
+ cosStartLat * sinAngDist * Math.cos(bearingRAD));
+
+ double lon2 = startLon + Math.atan2(Math.sin(bearingRAD) * sinAngDist * cosStartLat,
+ cosAngDist - sinStartLat * Math.sin(lat2));
+
+ /*lat2 = (lat2*180)/Math.PI;
+ lon2 = (lon2*180)/Math.PI;*/
+ //From Lucene. Move back to Lucene when synced
+ // normalize lon first
+ if (result == null || result.length != 2){
+ result = new double[2];
+ }
+ result[0] = lat2;
+ result[1] = lon2;
+ normLngRAD(result);
+
+ // normalize lat - could flip poles
+ normLatRAD(result);
+ return result;
+ }
+
+ /**
+ * @param latLng The lat/lon, in radians. lat in position 0, lon in position 1
+ */
+ public static void normLatRAD(double[] latLng) {
+
+ if (latLng[0] > DEG_90_AS_RADS) {
+ latLng[0] = DEG_90_AS_RADS - (latLng[0] - DEG_90_AS_RADS);
+ if (latLng[1] < 0) {
+ latLng[1] = latLng[1] + DEG_180_AS_RADS;
+ } else {
+ latLng[1] = latLng[1] - DEG_180_AS_RADS;
+ }
+ } else if (latLng[0] < -DEG_90_AS_RADS) {
+ latLng[0] = -DEG_90_AS_RADS - (latLng[0] + DEG_90_AS_RADS);
+ if (latLng[1] < 0) {
+ latLng[1] = latLng[1] + DEG_180_AS_RADS;
+ } else {
+ latLng[1] = latLng[1] - DEG_180_AS_RADS;
+ }
+ }
+
+ }
+
+ /**
+ * Returns a normalized Lng rectangle shape for the bounding box
+ *
+ * @param latLng The lat/lon, in radians, lat in position 0, lon in position 1
+ */
+ @Deprecated
+ public static void normLngRAD(double[] latLng) {
+ if (latLng[1] > DEG_180_AS_RADS) {
+ latLng[1] = -1.0 * (DEG_180_AS_RADS - (latLng[1] - DEG_180_AS_RADS));
+ } else if (latLng[1] < -DEG_180_AS_RADS) {
+ latLng[1] = (latLng[1] + DEG_180_AS_RADS) + DEG_180_AS_RADS;
+ }
+ }
+
+ /**
+ * Puts in range -180 <= lon_deg < +180.
+ */
+ public static double normLonDEG(double lon_deg) {
+ if (lon_deg >= -180 && lon_deg < 180)
+ return lon_deg;//common case, and avoids slight double precision shifting
+ double off = (lon_deg + 180) % 360;
+ return off < 0 ? 180 + off : -180 + off;
+ }
+
+ /**
+ * Puts in range -90 <= lat_deg <= 90.
+ */
+ public static double normLatDEG(double lat_deg) {
+ if (lat_deg >= -90 && lat_deg <= 90)
+ return lat_deg;//common case, and avoids slight double precision shifting
+ double off = Math.abs((lat_deg + 90) % 360);
+ return (off <= 180 ? off : 360-off) - 90;
+ }
+
+ public static Rectangle calcBoxByDistFromPtDEG(double lat, double lon, double distance, SpatialContext ctx) {
+ //See http://janmatuschek.de/LatitudeLongitudeBoundingCoordinates Section 3.1, 3.2 and 3.3
+
+ double radius = ctx.getUnits().earthRadius();
+ double dist_rad = distance / radius;
+ double dist_deg = Math.toDegrees(dist_rad);
+
+ if (dist_deg == 0)
+ return ctx.makeRect(lon,lon,lat,lat);
+
+ if (dist_deg >= 180)//distance is >= opposite side of the globe
+ return ctx.getWorldBounds();
+
+ //--calc latitude bounds
+ double latN_deg = lat + dist_deg;
+ double latS_deg = lat - dist_deg;
+
+ if (latN_deg >= 90 || latS_deg <= -90) {//touches either pole
+ //we have special logic for longitude
+ double lonW_deg = -180, lonE_deg = 180;//world wrap: 360 deg
+ if (latN_deg <= 90 && latS_deg >= -90) {//doesn't pass either pole: 180 deg
+ lonW_deg = lon -90;
+ lonE_deg = lon +90;
+ }
+ if (latN_deg > 90)
+ latN_deg = 90;
+ if (latS_deg < -90)
+ latS_deg = -90;
+
+ return ctx.makeRect(lonW_deg, lonE_deg, latS_deg, latN_deg);
+ } else {
+ //--calc longitude bounds
+ double lon_delta_deg = calcBoxByDistFromPtVertAxisOffsetDEG(lat, lon, distance, radius);
+
+ double lonW_deg = lon -lon_delta_deg;
+ double lonE_deg = lon +lon_delta_deg;
+
+ return ctx.makeRect(lonW_deg, lonE_deg, latS_deg, latN_deg);//ctx will normalize longitude
+ }
+ }
+
+ public static double calcBoxByDistFromPtVertAxisOffsetDEG(double lat, double lon, double distance, double radius) {
+ //http://gis.stackexchange.com/questions/19221/find-tangent-point-on-circle-furthest-east-or-west
+ if (distance == 0)
+ return 0;
+ double lat_rad = toRadians(lat);
+ double dist_rad = distance / radius;
+ double result_rad = Math.asin(Math.sin(dist_rad) / Math.cos(lat_rad));
+
+ if (!Double.isNaN(result_rad))
+ return Math.toDegrees(result_rad);
+ return 90;
+ }
+
+ public static double calcBoxByDistFromPtHorizAxisDEG(double lat, double lon, double distance, double radius) {
+ //http://gis.stackexchange.com/questions/19221/find-tangent-point-on-circle-furthest-east-or-west
+ if (distance == 0)
+ return lat;
+ double lat_rad = toRadians(lat);
+ double dist_rad = distance / radius;
+ double result_rad = Math.asin( Math.sin(lat_rad) / Math.cos(dist_rad));
+ if (!Double.isNaN(result_rad))
+ return Math.toDegrees(result_rad);
+ //TODO should we use use ctx.getBoundaryNudgeDegrees() offsets here or let caller?
+ if (lat > 0)
+ return 90;
+ if (lat < 0)
+ return -90;
+ return lat;
+ }
+
+ /**
+ * The square of the cartesian Distance. Not really a distance, but useful if all that matters is
+ * comparing the result to another one.
+ *
+ * @param vec1 The first point
+ * @param vec2 The second point
+ * @return The squared cartesian distance
+ */
+ public static double distSquaredCartesian(double[] vec1, double[] vec2) {
+ double result = 0;
+ for (int i = 0; i < vec1.length; i++) {
+ double v = vec1[i] - vec2[i];
+ result += v * v;
+ }
+ return result;
+ }
+
+ /**
+ *
+ * @param lat1 The y coordinate of the first point, in radians
+ * @param lon1 The x coordinate of the first point, in radians
+ * @param lat2 The y coordinate of the second point, in radians
+ * @param lon2 The x coordinate of the second point, in radians
+ * @return The distance between the two points, as determined by the Haversine formula, in radians.
+ */
+ public static double distHaversineRAD(double lat1, double lon1, double lat2, double lon2) {
+ //TODO investigate slightly different formula using asin() and min() http://www.movable-type.co.uk/scripts/gis-faq-5.1.html
+
+ // Check for same position
+ if (lat1 == lat2 && lon1 == lon2)
+ return 0.0;
+ double hsinX = Math.sin((lon1 - lon2) * 0.5);
+ double hsinY = Math.sin((lat1 - lat2) * 0.5);
+ double h = hsinY * hsinY +
+ (Math.cos(lat1) * Math.cos(lat2) * hsinX * hsinX);
+ return 2 * Math.atan2(Math.sqrt(h), Math.sqrt(1 - h));
+ }
+
+ /**
+ * Calculates the distance between two lat/lng's using the Law of Cosines. Due to numeric conditioning
+ * errors, it is not as accurate as the Haversine formula for small distances. But with
+ * double precision, it isn't that bad -- <a href="http://www.movable-type.co.uk/scripts/latlong.html">
+ * allegedly 1 meter</a>.
+ * <p/>
+ * See <a href="http://gis.stackexchange.com/questions/4906/why-is-law-of-cosines-more-preferable-than-haversine-when-calculating-distance-b">
+ * Why is law of cosines more preferable than haversine when calculating distance between two latitude-longitude points?</a>
+ * <p/>
+ * The arguments and return value are in radians.
+ */
+ public static double distLawOfCosinesRAD(double lat1, double lon1, double lat2, double lon2) {
+ //TODO validate formula
+
+ //(MIGRATED FROM org.apache.lucene.spatial.geometry.LatLng.arcDistance())
+ // Imported from mq java client. Variable references changed to match.
+
+ // Check for same position
+ if (lat1 == lat2 && lon1 == lon2)
+ return 0.0;
+
+ // Get the m_dLongitude difference. Don't need to worry about
+ // crossing 180 since cos(x) = cos(-x)
+ double dLon = lon2 - lon1;
+
+ double a = DEG_90_AS_RADS - lat1;
+ double c = DEG_90_AS_RADS - lat2;
+ double cosB = (Math.cos(a) * Math.cos(c))
+ + (Math.sin(a) * Math.sin(c) * Math.cos(dLon));
+
+ // Find angle subtended (with some bounds checking) in radians
+ if (cosB < -1.0)
+ return Math.PI;
+ else if (cosB >= 1.0)
+ return 0;
+ else
+ return Math.acos(cosB);
+ }
+
+ /**
+ * Calculates the great circle distance using the Vincenty Formula, simplified for a spherical model. This formula
+ * is accurate for any pair of points. The equation
+ * was taken from <a href="http://en.wikipedia.org/wiki/Great-circle_distance">Wikipedia</a>.
+ * <p/>
+ * The arguments are in radians, and the result is in radians.
+ */
+ public static double distVincentyRAD(double lat1, double lon1, double lat2, double lon2) {
+ // Check for same position
+ if (lat1 == lat2 && lon1 == lon2)
+ return 0.0;
+
+ double cosLat1 = Math.cos(lat1);
+ double cosLat2 = Math.cos(lat2);
+ double sinLat1 = Math.sin(lat1);
+ double sinLat2 = Math.sin(lat2);
+ double dLon = lon2 - lon1;
+ double cosDLon = Math.cos(dLon);
+ double sinDLon = Math.sin(dLon);
+
+ double a = cosLat2 * sinDLon;
+ double b = cosLat1*sinLat2 - sinLat1*cosLat2*cosDLon;
+ double c = sinLat1*sinLat2 + cosLat1*cosLat2*cosDLon;
+
+ return Math.atan2(Math.sqrt(a*a+b*b),c);
+ }
+
+ /**
+ * Converts a distance in the units of the radius to degrees (360 degrees are in a circle). A spherical
+ * earth model is assumed.
+ */
+ public static double dist2Degrees(double dist, double radius) {
+ return Math.toDegrees(dist2Radians(dist, radius));
+ }
+
+ /**
+ * Converts a distance in the units of the radius to radians (multiples of the radius). A spherical
+ * earth model is assumed.
+ */
+ public static double dist2Radians(double dist, double radius) {
+ return dist / radius;
+ }
+
+ public static double radians2Dist(double radians, double radius) {
+ return radians * radius;
+ }
+
+}
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/distance/GeodesicSphereDistCalc.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/distance/GeodesicSphereDistCalc.java?rev=1291499&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/distance/GeodesicSphereDistCalc.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/distance/GeodesicSphereDistCalc.java Mon Feb 20 22:45:32 2012
@@ -0,0 +1,133 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.lucene.spatial.base.distance;
+
+import org.apache.lucene.spatial.base.context.SpatialContext;
+import org.apache.lucene.spatial.base.shape.Point;
+import org.apache.lucene.spatial.base.shape.Rectangle;
+
+import static java.lang.Math.toRadians;
+
+/**
+ * A base class for a Distance Calculator that assumes a spherical earth model.
+ * @author dsmiley
+ */
+public abstract class GeodesicSphereDistCalc extends AbstractDistanceCalculator {
+ protected final double radius;
+
+ public GeodesicSphereDistCalc(double radius) {
+ this.radius = radius;
+ }
+
+ @Override
+ public double distanceToDegrees(double distance) {
+ return DistanceUtils.dist2Degrees(distance, radius);
+ }
+
+ @Override
+ public double degreesToDistance(double degrees) {
+ return DistanceUtils.radians2Dist(toRadians(degrees), radius);
+ }
+
+ @Override
+ public Point pointOnBearing(Point from, double dist, double bearingDEG, SpatialContext ctx) {
+ //TODO avoid unnecessary double[] intermediate object
+ if (dist == 0)
+ return from;
+ double[] latLon = DistanceUtils.pointOnBearingRAD(
+ toRadians(from.getY()), toRadians(from.getX()),
+ DistanceUtils.dist2Radians(dist,ctx.getUnits().earthRadius()),
+ toRadians(bearingDEG), null);
+ return ctx.makePoint(Math.toDegrees(latLon[1]), Math.toDegrees(latLon[0]));
+ }
+
+ @Override
+ public Rectangle calcBoxByDistFromPt(Point from, double distance, SpatialContext ctx) {
+ assert radius == ctx.getUnits().earthRadius();
+ if (distance == 0)
+ return from.getBoundingBox();
+ return DistanceUtils.calcBoxByDistFromPtDEG(from.getY(), from.getX(), distance, ctx);
+ }
+
+ @Override
+ public double calcBoxByDistFromPtHorizAxis(Point from, double distance, SpatialContext ctx) {
+ return DistanceUtils.calcBoxByDistFromPtHorizAxisDEG(from.getY(), from.getX(), distance, radius);
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) return true;
+ if (o == null || getClass() != o.getClass()) return false;
+
+ GeodesicSphereDistCalc that = (GeodesicSphereDistCalc) o;
+
+ if (Double.compare(that.radius, radius) != 0) return false;
+
+ return true;
+ }
+
+ @Override
+ public int hashCode() {
+ long temp = radius != +0.0d ? Double.doubleToLongBits(radius) : 0L;
+ return (int) (temp ^ (temp >>> 32));
+ }
+
+ @Override
+ public final double distance(Point from, double toX, double toY) {
+ return distanceLatLonRAD(toRadians(from.getY()), toRadians(from.getX()), toRadians(toY), toRadians(toX)) * radius;
+ }
+
+ protected abstract double distanceLatLonRAD(double lat1, double lon1, double lat2, double lon2);
+
+ public static class Haversine extends GeodesicSphereDistCalc {
+
+ public Haversine(double radius) {
+ super(radius);
+ }
+
+ @Override
+ protected double distanceLatLonRAD(double lat1, double lon1, double lat2, double lon2) {
+ return DistanceUtils.distHaversineRAD(lat1,lon1,lat2,lon2);
+ }
+
+ }
+
+ public static class LawOfCosines extends GeodesicSphereDistCalc {
+
+ public LawOfCosines(double radius) {
+ super(radius);
+ }
+
+ @Override
+ protected double distanceLatLonRAD(double lat1, double lon1, double lat2, double lon2) {
+ return DistanceUtils.distLawOfCosinesRAD(lat1, lon1, lat2, lon2);
+ }
+
+ }
+
+ public static class Vincenty extends GeodesicSphereDistCalc {
+ public Vincenty(double radius) {
+ super(radius);
+ }
+
+ @Override
+ protected double distanceLatLonRAD(double lat1, double lon1, double lat2, double lon2) {
+ return DistanceUtils.distVincentyRAD(lat1, lon1, lat2, lon2);
+ }
+ }
+}
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/distance/package-info.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/distance/package-info.java?rev=1291499&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/distance/package-info.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/distance/package-info.java Mon Feb 20 22:45:32 2012
@@ -0,0 +1,22 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.
+ */
+
+/**
+ * Ways to calculate distance
+ */
+package org.apache.lucene.spatial.base.distance;
+
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/exception/InvalidShapeException.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/exception/InvalidShapeException.java?rev=1291499&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/exception/InvalidShapeException.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/exception/InvalidShapeException.java Mon Feb 20 22:45:32 2012
@@ -0,0 +1,29 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.lucene.spatial.base.exception;
+
+public class InvalidShapeException extends RuntimeException {
+
+ public InvalidShapeException(String reason, Throwable cause) {
+ super(reason, cause);
+ }
+
+ public InvalidShapeException(String reason) {
+ super(reason);
+ }
+}
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/exception/InvalidSpatialArgument.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/exception/InvalidSpatialArgument.java?rev=1291499&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/exception/InvalidSpatialArgument.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/exception/InvalidSpatialArgument.java Mon Feb 20 22:45:32 2012
@@ -0,0 +1,29 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.lucene.spatial.base.exception;
+
+public class InvalidSpatialArgument extends RuntimeException {
+
+ public InvalidSpatialArgument(String reason, Throwable cause) {
+ super(reason, cause);
+ }
+
+ public InvalidSpatialArgument(String reason) {
+ super(reason);
+ }
+}
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/exception/UnsupportedSpatialOperation.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/exception/UnsupportedSpatialOperation.java?rev=1291499&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/exception/UnsupportedSpatialOperation.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/exception/UnsupportedSpatialOperation.java Mon Feb 20 22:45:32 2012
@@ -0,0 +1,27 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.lucene.spatial.base.exception;
+
+import org.apache.lucene.spatial.base.query.SpatialOperation;
+
+public class UnsupportedSpatialOperation extends UnsupportedOperationException {
+
+ public UnsupportedSpatialOperation(SpatialOperation op) {
+ super(op.getName());
+ }
+}
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/io/LineReader.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/io/LineReader.java?rev=1291499&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/io/LineReader.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/io/LineReader.java Mon Feb 20 22:45:32 2012
@@ -0,0 +1,113 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.lucene.spatial.base.io;
+
+import java.io.BufferedReader;
+import java.io.File;
+import java.io.FileInputStream;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.InputStreamReader;
+import java.io.Reader;
+import java.util.Iterator;
+
+public abstract class LineReader<T> implements Iterator<T> {
+
+ private int count = 0;
+ private int lineNumber = 0;
+ private BufferedReader reader;
+ private String nextLine;
+
+ public abstract T parseLine( String line );
+
+ protected void readComment( String line ) {
+
+ }
+
+ public LineReader(InputStream in) throws IOException {
+ reader = new BufferedReader(
+ new InputStreamReader( in, "UTF-8" ) );
+ next();
+ }
+
+ public LineReader(Reader r) throws IOException {
+ if (r instanceof BufferedReader) {
+ reader = (BufferedReader) r;
+ } else {
+ reader = new BufferedReader(r);
+ }
+ next();
+ }
+
+ public LineReader(File f) throws IOException {
+ reader = new BufferedReader(new InputStreamReader(new FileInputStream(f), "UTF-8"));
+ next();
+ }
+
+ @Override
+ public boolean hasNext() {
+ return nextLine != null;
+ }
+
+ @Override
+ public T next() {
+ T val = null;
+ if (nextLine != null) {
+ val = parseLine(nextLine);
+ count++;
+ }
+
+ if (reader != null) {
+ try {
+ while( reader != null ) {
+ nextLine = reader.readLine();
+ lineNumber++;
+ if (nextLine == null ) {
+ reader.close();
+ reader = null;
+ }
+ else if( nextLine.startsWith( "#" ) ) {
+ readComment( nextLine );
+ }
+ else {
+ nextLine = nextLine.trim();
+ if( nextLine.length() > 0 ) {
+ break;
+ }
+ }
+ }
+ } catch (IOException ioe) {
+ throw new RuntimeException("IOException thrown while reading/closing reader", ioe);
+ }
+ }
+ return val;
+ }
+
+ @Override
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+
+ public int getLineNumber() {
+ return lineNumber;
+ }
+
+ public int getCount() {
+ return count;
+ }
+}
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/io/geonames/Geoname.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/io/geonames/Geoname.java?rev=1291499&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/io/geonames/Geoname.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/io/geonames/Geoname.java Mon Feb 20 22:45:32 2012
@@ -0,0 +1,73 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.lucene.spatial.base.io.geonames;
+
+import java.sql.Date;
+
+public class Geoname {
+ public int id;
+ public String name; // name of geographical point (utf8) varchar(200)
+ public String nameASCII; // name of geographical point in plain ascii characters, varchar(200)
+ public String[] alternateNames; // alternatenames, comma separated varchar(5000)
+ public double latitude;
+ public double longitude;
+ public char featureClass;
+ public String featureCode; // 10
+ public String countryCode; // 2
+ public String[] countryCode2; // alternate country codes, comma separated, ISO-3166 2-letter country code, 60 characters
+ public String adminCode1; // fipscode (subject to change to iso code), see exceptions below, see file admin1Codes.txt for display names of this code; varchar(20)
+ public String adminCode2; // code for the second administrative division, a county in the US, see file admin2Codes.txt; varchar(80)
+ public String adminCode3; // code for third level administrative division, varchar(20)
+ public String adminCode4; // code for fourth level administrative division, varchar(20)
+ public Long population;
+ public Integer elevation; // in meters, integer
+ public Integer gtopo30; // average elevation of 30'x30' (ca 900mx900m) area in meters, integer
+ public String timezone;
+ public Date modified; // date of last modification in yyyy-MM-dd format
+
+ public Geoname(String line) {
+ String[] vals = line.split("\t");
+ id = Integer.parseInt(vals[0]);
+ name = vals[1];
+ nameASCII = vals[2];
+ alternateNames = vals[3].split(",");
+ latitude = Double.parseDouble(vals[4]);
+ longitude = Double.parseDouble(vals[5]);
+ featureClass = vals[6].length() > 0 ? vals[6].charAt(0) : 'S';
+ featureCode = vals[7];
+ countryCode = vals[8];
+ countryCode2 = vals[9].split(",");
+ adminCode1 = vals[10];
+ adminCode2 = vals[11];
+ adminCode3 = vals[12];
+ adminCode4 = vals[13];
+ if (vals[14].length() > 0) {
+ population = Long.decode(vals[14]);
+ }
+ if (vals[15].length() > 0) {
+ elevation = Integer.decode(vals[15]);
+ }
+ if (vals[16].length() > 0) {
+ gtopo30 = Integer.decode(vals[16]);
+ }
+ timezone = vals[17];
+ if (vals[18].length() > 0) {
+ modified = Date.valueOf(vals[18]);
+ }
+ }
+}
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/io/geonames/GeonamesReader.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/io/geonames/GeonamesReader.java?rev=1291499&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/io/geonames/GeonamesReader.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/io/geonames/GeonamesReader.java Mon Feb 20 22:45:32 2012
@@ -0,0 +1,40 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.lucene.spatial.base.io.geonames;
+
+import java.io.File;
+import java.io.IOException;
+import java.io.Reader;
+
+import org.apache.lucene.spatial.base.io.LineReader;
+
+public class GeonamesReader extends LineReader<Geoname> {
+
+ public GeonamesReader(Reader r) throws IOException {
+ super( r );
+ }
+
+ public GeonamesReader(File f) throws IOException {
+ super( f );
+ }
+
+ @Override
+ public Geoname parseLine(String line) {
+ return new Geoname( line );
+ }
+}
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/io/sample/SampleData.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/io/sample/SampleData.java?rev=1291499&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/io/sample/SampleData.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/io/sample/SampleData.java Mon Feb 20 22:45:32 2012
@@ -0,0 +1,41 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.lucene.spatial.base.io.sample;
+
+import java.util.Comparator;
+
+
+public class SampleData {
+ public String id;
+ public String name;
+ public String shape;
+
+ public SampleData(String line) {
+ String[] vals = line.split("\t");
+ id = vals[0];
+ name = vals[1];
+ shape = vals[2];
+ }
+
+ public static Comparator<SampleData> NAME_ORDER = new Comparator<SampleData>() {
+ @Override
+ public int compare(SampleData o1, SampleData o2) {
+ return o1.name.compareTo( o2.name );
+ }
+ };
+}
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/io/sample/SampleDataReader.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/io/sample/SampleDataReader.java?rev=1291499&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/io/sample/SampleDataReader.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/io/sample/SampleDataReader.java Mon Feb 20 22:45:32 2012
@@ -0,0 +1,45 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.lucene.spatial.base.io.sample;
+
+import java.io.File;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.Reader;
+
+import org.apache.lucene.spatial.base.io.LineReader;
+
+public class SampleDataReader extends LineReader<SampleData> {
+
+ public SampleDataReader(InputStream r) throws IOException {
+ super( r );
+ }
+
+ public SampleDataReader(Reader r) throws IOException {
+ super( r );
+ }
+
+ public SampleDataReader(File f) throws IOException {
+ super( f );
+ }
+
+ @Override
+ public SampleData parseLine(String line) {
+ return new SampleData( line );
+ }
+}
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/package-info.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/package-info.java?rev=1291499&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/package-info.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/package-info.java Mon Feb 20 22:45:32 2012
@@ -0,0 +1,23 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.
+ */
+
+/**
+ * This package is spatal stuff without any lucene dependencies
+ * Things implemented in this package could be calculated on the client side
+ */
+package org.apache.lucene.spatial.base;
+
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/Node.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/Node.java?rev=1291499&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/Node.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/Node.java Mon Feb 20 22:45:32 2012
@@ -0,0 +1,215 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.lucene.spatial.base.prefix;
+
+import org.apache.lucene.spatial.base.shape.SpatialRelation;
+import org.apache.lucene.spatial.base.shape.Point;
+import org.apache.lucene.spatial.base.shape.Shape;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
+
+/**
+ * Represents a grid cell. These are not necessarily threadsafe, although new Cell("") (world cell) must be.
+ */
+public abstract class Node implements Comparable<Node> {
+ public static final byte LEAF_BYTE = '+';//NOTE: must sort before letters & numbers
+
+ /*
+ Holds a byte[] and/or String representation of the cell. Both are lazy constructed from the other.
+ Neither contains the trailing leaf byte.
+ */
+ private byte[] bytes;
+ private int b_off;
+ private int b_len;
+
+ private String token;//this is the only part of equality
+
+ protected SpatialRelation shapeRel;//set in getSubCells(filter), and via setLeaf().
+ private SpatialPrefixTree spatialPrefixTree;
+
+ protected Node(SpatialPrefixTree spatialPrefixTree, String token) {
+ this.spatialPrefixTree = spatialPrefixTree;
+ this.token = token;
+ if (token.length() > 0 && token.charAt(token.length() - 1) == (char) LEAF_BYTE) {
+ this.token = token.substring(0, token.length() - 1);
+ setLeaf();
+ }
+
+ if (getLevel() == 0)
+ getShape();//ensure any lazy instantiation completes to make this threadsafe
+ }
+
+ protected Node(SpatialPrefixTree spatialPrefixTree, byte[] bytes, int off, int len) {
+ this.spatialPrefixTree = spatialPrefixTree;
+ this.bytes = bytes;
+ this.b_off = off;
+ this.b_len = len;
+ b_fixLeaf();
+ }
+
+ public void reset(byte[] bytes, int off, int len) {
+ assert getLevel() != 0;
+ token = null;
+ shapeRel = null;
+ this.bytes = bytes;
+ this.b_off = off;
+ this.b_len = len;
+ b_fixLeaf();
+ }
+
+ private void b_fixLeaf() {
+ if (bytes[b_off + b_len - 1] == LEAF_BYTE) {
+ b_len--;
+ setLeaf();
+ } else if (getLevel() == spatialPrefixTree.getMaxLevels()) {
+ setLeaf();
+ }
+ }
+
+ public SpatialRelation getShapeRel() {
+ return shapeRel;
+ }
+
+ public boolean isLeaf() {
+ return shapeRel == SpatialRelation.WITHIN;
+ }
+
+ public void setLeaf() {
+ assert getLevel() != 0;
+ shapeRel = SpatialRelation.WITHIN;
+ }
+
+ /**
+ * Note: doesn't contain a trailing leaf byte.
+ */
+ public String getTokenString() {
+ if (token == null) {
+ token = new String(bytes, b_off, b_len, SpatialPrefixTree.UTF8);
+ }
+ return token;
+ }
+
+ /**
+ * Note: doesn't contain a trailing leaf byte.
+ */
+ public byte[] getTokenBytes() {
+ if (bytes != null) {
+ if (b_off != 0 || b_len != bytes.length) {
+ throw new IllegalStateException("Not supported if byte[] needs to be recreated.");
+ }
+ } else {
+ bytes = token.getBytes(SpatialPrefixTree.UTF8);
+ b_off = 0;
+ b_len = bytes.length;
+ }
+ return bytes;
+ }
+
+ public int getLevel() {
+ return token != null ? token.length() : b_len;
+ }
+
+ //TODO add getParent() and update some algorithms to use this?
+ //public Cell getParent();
+
+ /**
+ * Like {@link #getSubCells()} but with the results filtered by a shape. If that shape is a {@link org.apache.lucene.spatial.base.shape.Point} then it
+ * must call {@link #getSubCell(org.apache.lucene.spatial.base.shape.Point)};
+ * Precondition: Never called when getLevel() == maxLevel.
+ *
+ * @param shapeFilter an optional filter for the returned cells.
+ * @return A set of cells (no dups), sorted. Not Modifiable.
+ */
+ public Collection<Node> getSubCells(Shape shapeFilter) {
+ //Note: Higher-performing subclasses might override to consider the shape filter to generate fewer cells.
+ if (shapeFilter instanceof Point) {
+ return Collections.singleton(getSubCell((Point) shapeFilter));
+ }
+ Collection<Node> cells = getSubCells();
+
+ if (shapeFilter == null) {
+ return cells;
+ }
+ List<Node> copy = new ArrayList<Node>(cells.size());//copy since cells contractually isn't modifiable
+ for (Node cell : cells) {
+ SpatialRelation rel = cell.getShape().relate(shapeFilter, spatialPrefixTree.ctx);
+ if (rel == SpatialRelation.DISJOINT)
+ continue;
+ cell.shapeRel = rel;
+ copy.add(cell);
+ }
+ cells = copy;
+ return cells;
+ }
+
+ /**
+ * Performant implementations are expected to implement this efficiently by considering the current
+ * cell's boundary.
+ * Precondition: Never called when getLevel() == maxLevel.
+ * Precondition: this.getShape().relate(p) != DISJOINT.
+ *
+ * @param p
+ * @return
+ */
+ public abstract Node getSubCell(Point p);
+
+ //TODO Cell getSubCell(byte b)
+
+ /**
+ * Gets the cells at the next grid cell level that cover this cell.
+ * Precondition: Never called when getLevel() == maxLevel.
+ *
+ * @return A set of cells (no dups), sorted. Not Modifiable.
+ */
+ protected abstract Collection<Node> getSubCells();
+
+ /**
+ * {@link #getSubCells()}.size() -- usually a constant. Should be >=2
+ */
+ public abstract int getSubCellsSize();
+
+ public abstract Shape getShape();
+
+ public Point getCenter() {
+ return getShape().getCenter();
+ }
+
+ @Override
+ public int compareTo(Node o) {
+ return getTokenString().compareTo(o.getTokenString());
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ return !(obj == null || !(obj instanceof Node)) && getTokenString().equals(((Node) obj).getTokenString());
+ }
+
+ @Override
+ public int hashCode() {
+ return getTokenString().hashCode();
+ }
+
+ @Override
+ public String toString() {
+ return getTokenString() + (isLeaf() ? (char) LEAF_BYTE : "");
+ }
+
+}
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/SpatialPrefixTree.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/SpatialPrefixTree.java?rev=1291499&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/SpatialPrefixTree.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/SpatialPrefixTree.java Mon Feb 20 22:45:32 2012
@@ -0,0 +1,246 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.lucene.spatial.base.prefix;
+
+import org.apache.lucene.spatial.base.context.SpatialContext;
+import org.apache.lucene.spatial.base.shape.Point;
+import org.apache.lucene.spatial.base.shape.Shape;
+
+import java.nio.charset.Charset;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
+
+/**
+ * A Spatial Prefix Tree, or Trie, which decomposes shapes into prefixed strings at variable lengths corresponding to
+ * variable precision. Each string corresponds to a spatial region.
+ *
+ * Implementations of this class should be thread-safe and immutable once initialized.
+ */
+public abstract class SpatialPrefixTree {
+
+ protected static final Charset UTF8 = Charset.forName("UTF-8");
+
+ protected final int maxLevels;
+
+ protected final SpatialContext ctx;
+
+ public SpatialPrefixTree(SpatialContext ctx, int maxLevels) {
+ assert maxLevels > 0;
+ this.ctx = ctx;
+ this.maxLevels = maxLevels;
+ }
+
+ public SpatialContext getSpatialContext() {
+ return ctx;
+ }
+
+ public int getMaxLevels() {
+ return maxLevels;
+ }
+
+ @Override
+ public String toString() {
+ return getClass().getSimpleName() + "(maxLevels:" + maxLevels + ",ctx:" + ctx + ")";
+ }
+
+ /**
+ * See {@link org.apache.lucene.spatial.base.query.SpatialArgs#getDistPrecision()}.
+ * A grid level looked up via {@link #getLevelForDistance(double)} is returned.
+ *
+ * @param shape
+ * @param precision 0-0.5
+ * @return 1-maxLevels
+ */
+ public int getMaxLevelForPrecision(Shape shape, double precision) {
+ if (precision < 0 || precision > 0.5) {
+ throw new IllegalArgumentException("Precision " + precision + " must be between [0-0.5]");
+ }
+ if (precision == 0 || shape instanceof Point) {
+ return maxLevels;
+ }
+ double bboxArea = shape.getBoundingBox().getArea();
+ if (bboxArea == 0) {
+ return maxLevels;
+ }
+ double avgSideLenFromCenter = Math.sqrt(bboxArea) / 2;
+ return getLevelForDistance(avgSideLenFromCenter * precision);
+ }
+
+ /**
+ * Returns the level of the smallest grid size with a side length that is greater or equal to the provided
+ * distance.
+ *
+ * @param dist >= 0
+ * @return level [1-maxLevels]
+ */
+ public abstract int getLevelForDistance(double dist);
+
+ //TODO double getDistanceForLevel(int level)
+
+ private transient Node worldNode;//cached
+
+ /**
+ * Returns the level 0 cell which encompasses all spatial data. Equivalent to {@link #getNode(String)} with "".
+ * This cell is threadsafe, just like a spatial prefix grid is, although cells aren't
+ * generally threadsafe.
+ * TODO rename to getTopCell or is this fine?
+ */
+ public Node getWorldNode() {
+ if (worldNode == null) {
+ worldNode = getNode("");
+ }
+ return worldNode;
+ }
+
+ /**
+ * The cell for the specified token. The empty string should be equal to {@link #getWorldNode()}.
+ * Precondition: Never called when token length > maxLevel.
+ */
+ public abstract Node getNode(String token);
+
+ public abstract Node getNode(byte[] bytes, int offset, int len);
+
+ public final Node getNode(byte[] bytes, int offset, int len, Node target) {
+ if (target == null) {
+ return getNode(bytes, offset, len);
+ }
+
+ target.reset(bytes, offset, len);
+ return target;
+ }
+
+ protected Node getNode(Point p, int level) {
+ return getNodes(p, level, false).get(0);
+ }
+
+ /**
+ * Gets the intersecting & including cells for the specified shape, without exceeding detail level.
+ * The result is a set of cells (no dups), sorted. Unmodifiable.
+ * <p/>
+ * This implementation checks if shape is a Point and if so uses an implementation that
+ * recursively calls {@link Node#getSubCell(org.apache.lucene.spatial.base.shape.Point)}. Cell subclasses
+ * ideally implement that method with a quick implementation, otherwise, subclasses should
+ * override this method to invoke {@link #getNodesAltPoint(org.apache.lucene.spatial.base.shape.Point, int, boolean)}.
+ * TODO consider another approach returning an iterator -- won't build up all cells in memory.
+ */
+ public List<Node> getNodes(Shape shape, int detailLevel, boolean inclParents) {
+ if (detailLevel > maxLevels) {
+ throw new IllegalArgumentException("detailLevel > maxLevels");
+ }
+
+ List<Node> cells;
+ if (shape instanceof Point) {
+ //optimized point algorithm
+ final int initialCapacity = inclParents ? 1 + detailLevel : 1;
+ cells = new ArrayList<Node>(initialCapacity);
+ recursiveGetNodes(getWorldNode(), (Point) shape, detailLevel, true, cells);
+ assert cells.size() == initialCapacity;
+ } else {
+ cells = new ArrayList<Node>(inclParents ? 1024 : 512);
+ recursiveGetNodes(getWorldNode(), shape, detailLevel, inclParents, cells);
+ }
+ if (inclParents) {
+ Node c = cells.remove(0);//remove getWorldNode()
+ assert c.getLevel() == 0;
+ }
+ return cells;
+ }
+
+ private void recursiveGetNodes(Node node, Shape shape, int detailLevel, boolean inclParents,
+ Collection<Node> result) {
+ if (node.isLeaf()) {//cell is within shape
+ result.add(node);
+ return;
+ }
+ final Collection<Node> subCells = node.getSubCells(shape);
+ if (node.getLevel() == detailLevel - 1) {
+ if (subCells.size() < node.getSubCellsSize()) {
+ if (inclParents)
+ result.add(node);
+ for (Node subCell : subCells) {
+ subCell.setLeaf();
+ }
+ result.addAll(subCells);
+ } else {//a bottom level (i.e. detail level) optimization where all boxes intersect, so use parent cell.
+ node.setLeaf();
+ result.add(node);
+ }
+ } else {
+ if (inclParents) {
+ result.add(node);
+ }
+ for (Node subCell : subCells) {
+ recursiveGetNodes(subCell, shape, detailLevel, inclParents, result);//tail call
+ }
+ }
+ }
+
+ private void recursiveGetNodes(Node node, Point point, int detailLevel, boolean inclParents,
+ Collection<Node> result) {
+ if (inclParents) {
+ result.add(node);
+ }
+ final Node pCell = node.getSubCell(point);
+ if (node.getLevel() == detailLevel - 1) {
+ pCell.setLeaf();
+ result.add(pCell);
+ } else {
+ recursiveGetNodes(pCell, point, detailLevel, inclParents, result);//tail call
+ }
+ }
+
+ /**
+ * Subclasses might override {@link #getNodes(org.apache.lucene.spatial.base.shape.Shape, int, boolean)}
+ * and check if the argument is a shape and if so, delegate
+ * to this implementation, which calls {@link #getNode(org.apache.lucene.spatial.base.shape.Point, int)} and
+ * then calls {@link #getNode(String)} repeatedly if inclParents is true.
+ */
+ protected final List<Node> getNodesAltPoint(Point p, int detailLevel, boolean inclParents) {
+ Node cell = getNode(p, detailLevel);
+ if (!inclParents) {
+ return Collections.singletonList(cell);
+ }
+
+ String endToken = cell.getTokenString();
+ assert endToken.length() == detailLevel;
+ List<Node> cells = new ArrayList<Node>(detailLevel);
+ for (int i = 1; i < detailLevel; i++) {
+ cells.add(getNode(endToken.substring(0, i)));
+ }
+ cells.add(cell);
+ return cells;
+ }
+
+ /**
+ * Will add the trailing leaf byte for leaves. This isn't particularly efficient.
+ */
+ public static List<String> nodesToTokenStrings(Collection<Node> nodes) {
+ List<String> tokens = new ArrayList<String>((nodes.size()));
+ for (Node node : nodes) {
+ final String token = node.getTokenString();
+ if (node.isLeaf()) {
+ tokens.add(token + (char) Node.LEAF_BYTE);
+ } else {
+ tokens.add(token);
+ }
+ }
+ return tokens;
+ }
+}
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/SpatialPrefixTreeFactory.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/SpatialPrefixTreeFactory.java?rev=1291499&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/SpatialPrefixTreeFactory.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/SpatialPrefixTreeFactory.java Mon Feb 20 22:45:32 2012
@@ -0,0 +1,95 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.lucene.spatial.base.prefix;
+
+import org.apache.lucene.spatial.base.context.SpatialContext;
+import org.apache.lucene.spatial.base.distance.DistanceUnits;
+import org.apache.lucene.spatial.base.distance.DistanceUtils;
+import org.apache.lucene.spatial.base.prefix.geohash.GeohashPrefixTree;
+import org.apache.lucene.spatial.base.prefix.quad.QuadPrefixTree;
+
+import java.util.Map;
+
+/**
+ * @author dsmiley
+ */
+public abstract class SpatialPrefixTreeFactory {
+
+ private static final double DEFAULT_GEO_MAX_DETAIL_KM = 0.001;//1m
+
+ protected Map<String, String> args;
+ protected SpatialContext ctx;
+ protected Integer maxLevels;
+
+ /**
+ * The factory is looked up via "prefixTree" in args, expecting "geohash" or "quad".
+ * If its neither of these, then "geohash" is chosen for a geo context, otherwise "quad" is chosen.
+ */
+ public static SpatialPrefixTree makeSPT(Map<String,String> args, ClassLoader classLoader, SpatialContext ctx) {
+ SpatialPrefixTreeFactory instance;
+ String cname = args.get("prefixTree");
+ if (cname == null)
+ cname = ctx.isGeo() ? "geohash" : "quad";
+ if ("geohash".equalsIgnoreCase(cname))
+ instance = new GeohashPrefixTree.Factory();
+ else if ("quad".equalsIgnoreCase(cname))
+ instance = new QuadPrefixTree.Factory();
+ else {
+ try {
+ Class c = classLoader.loadClass(cname);
+ instance = (SpatialPrefixTreeFactory) c.newInstance();
+ } catch (Exception e) {
+ throw new RuntimeException(e);
+ }
+ }
+ instance.init(args,ctx);
+ return instance.newSPT();
+ }
+
+ protected void init(Map<String, String> args, SpatialContext ctx) {
+ this.args = args;
+ this.ctx = ctx;
+ initMaxLevels();
+ }
+
+ protected void initMaxLevels() {
+ String mlStr = args.get("maxLevels");
+ if (mlStr != null) {
+ maxLevels = Integer.valueOf(mlStr);
+ return;
+ }
+
+ double degrees;
+ String maxDetailDistStr = args.get("maxDetailDist");
+ if (maxDetailDistStr == null) {
+ if (!ctx.isGeo()) {
+ return;//let default to max
+ }
+ degrees = DistanceUtils.dist2Degrees(DEFAULT_GEO_MAX_DETAIL_KM, DistanceUnits.KILOMETERS.earthRadius());
+ } else {
+ degrees = DistanceUtils.dist2Degrees(Double.parseDouble(maxDetailDistStr), ctx.getUnits().earthRadius());
+ }
+ maxLevels = getLevelForDistance(degrees) + 1;//returns 1 greater
+ }
+
+ /** Calls {@link SpatialPrefixTree#getLevelForDistance(double)}. */
+ protected abstract int getLevelForDistance(double degrees);
+
+ protected abstract SpatialPrefixTree newSPT();
+
+}
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/geohash/GeohashPrefixTree.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/geohash/GeohashPrefixTree.java?rev=1291499&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/geohash/GeohashPrefixTree.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/geohash/GeohashPrefixTree.java Mon Feb 20 22:45:32 2012
@@ -0,0 +1,150 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.lucene.spatial.base.prefix.geohash;
+
+import org.apache.lucene.spatial.base.context.SpatialContext;
+import org.apache.lucene.spatial.base.prefix.Node;
+import org.apache.lucene.spatial.base.prefix.SpatialPrefixTree;
+import org.apache.lucene.spatial.base.prefix.SpatialPrefixTreeFactory;
+import org.apache.lucene.spatial.base.shape.Point;
+import org.apache.lucene.spatial.base.shape.Rectangle;
+import org.apache.lucene.spatial.base.shape.Shape;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+
+/**
+ * A SpatialPrefixGrid based on Geohashes. Uses {@link GeohashUtils} to do all the geohash work.
+ */
+public class GeohashPrefixTree extends SpatialPrefixTree {
+
+ public static class Factory extends SpatialPrefixTreeFactory {
+
+ @Override
+ protected int getLevelForDistance(double degrees) {
+ GeohashPrefixTree grid = new GeohashPrefixTree(ctx, GeohashPrefixTree.getMaxLevelsPossible());
+ return grid.getLevelForDistance(degrees) + 1;//returns 1 greater
+ }
+
+ @Override
+ protected SpatialPrefixTree newSPT() {
+ return new GeohashPrefixTree(ctx,
+ maxLevels != null ? maxLevels : GeohashPrefixTree.getMaxLevelsPossible());
+ }
+ }
+
+ public GeohashPrefixTree(SpatialContext ctx, int maxLevels) {
+ super(ctx, maxLevels);
+ Rectangle bounds = ctx.getWorldBounds();
+ if (bounds.getMinX() != -180)
+ throw new IllegalArgumentException("Geohash only supports lat-lon world bounds. Got "+bounds);
+ int MAXP = getMaxLevelsPossible();
+ if (maxLevels <= 0 || maxLevels > MAXP)
+ throw new IllegalArgumentException("maxLen must be [1-"+MAXP+"] but got "+ maxLevels);
+ }
+
+ /** Any more than this and there's no point (double lat & lon are the same). */
+ public static int getMaxLevelsPossible() {
+ return GeohashUtils.MAX_PRECISION;
+ }
+
+ @Override
+ public int getLevelForDistance(double dist) {
+ final int level = GeohashUtils.lookupHashLenForWidthHeight(dist, dist);
+ return Math.max(Math.min(level, maxLevels), 1);
+ }
+
+ @Override
+ public Node getNode(Point p, int level) {
+ return new GhCell(GeohashUtils.encodeLatLon(p.getY(), p.getX(), level));//args are lat,lon (y,x)
+ }
+
+ @Override
+ public Node getNode(String token) {
+ return new GhCell(token);
+ }
+
+ @Override
+ public Node getNode(byte[] bytes, int offset, int len) {
+ return new GhCell(bytes, offset, len);
+ }
+
+ @Override
+ public List<Node> getNodes(Shape shape, int detailLevel, boolean inclParents) {
+ return shape instanceof Point ? super.getNodesAltPoint((Point) shape, detailLevel, inclParents) :
+ super.getNodes(shape, detailLevel, inclParents);
+ }
+
+ class GhCell extends Node {
+ GhCell(String token) {
+ super(GeohashPrefixTree.this, token);
+ }
+
+ GhCell(byte[] bytes, int off, int len) {
+ super(GeohashPrefixTree.this, bytes, off, len);
+ }
+
+ @Override
+ public void reset(byte[] bytes, int off, int len) {
+ super.reset(bytes, off, len);
+ shape = null;
+ }
+
+ @Override
+ public Collection<Node> getSubCells() {
+ String[] hashes = GeohashUtils.getSubGeohashes(getGeohash());//sorted
+ List<Node> cells = new ArrayList<Node>(hashes.length);
+ for (String hash : hashes) {
+ cells.add(new GhCell(hash));
+ }
+ return cells;
+ }
+
+ @Override
+ public int getSubCellsSize() {
+ return 32;//8x4
+ }
+
+ @Override
+ public Node getSubCell(Point p) {
+ return GeohashPrefixTree.this.getNode(p,getLevel()+1);//not performant!
+ }
+
+ private Shape shape;//cache
+
+ @Override
+ public Shape getShape() {
+ if (shape == null) {
+ shape = GeohashUtils.decodeBoundary(getGeohash(), ctx);
+ }
+ return shape;
+ }
+
+ @Override
+ public Point getCenter() {
+ return GeohashUtils.decode(getGeohash(), ctx);
+ }
+
+ private String getGeohash() {
+ return getTokenString();
+ }
+
+ }//class GhCell
+
+}
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/geohash/GeohashUtils.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/geohash/GeohashUtils.java?rev=1291499&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/geohash/GeohashUtils.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/geohash/GeohashUtils.java Mon Feb 20 22:45:32 2012
@@ -0,0 +1,196 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.lucene.spatial.base.prefix.geohash;
+
+import org.apache.lucene.spatial.base.context.SpatialContext;
+import org.apache.lucene.spatial.base.shape.Rectangle;
+import org.apache.lucene.spatial.base.shape.Point;
+
+import java.util.Arrays;
+
+/**
+ * Utilities for encoding and decoding geohashes. Based on
+ * <a href="http://en.wikipedia.org/wiki/Geohash">http://en.wikipedia.org/wiki/Geohash</a>.
+ */
+public class GeohashUtils {
+
+ private static final char[] BASE_32 = {'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'};//note: this is sorted
+
+ private static final int[] BASE_32_IDX;//sparse array of indexes from '0' to 'z'
+
+ public static final int MAX_PRECISION = 24;//DWS: I forget what level results in needless more precision but it's about this
+ private static final int[] BITS = {16, 8, 4, 2, 1};
+
+ static {
+ BASE_32_IDX = new int[BASE_32[BASE_32.length-1] - BASE_32[0] + 1];
+ assert BASE_32_IDX.length < 100;//reasonable length
+ Arrays.fill(BASE_32_IDX,-500);
+ for (int i = 0; i < BASE_32.length; i++) {
+ BASE_32_IDX[BASE_32[i] - BASE_32[0]] = i;
+ }
+ }
+
+ private GeohashUtils() {
+ }
+
+ /**
+ * 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 encodeLatLon(double latitude, double longitude) {
+ return encodeLatLon(latitude, longitude, 12);
+ }
+
+ public static String encodeLatLon(double latitude, double longitude, int precision) {
+ double[] latInterval = {-90.0, 90.0};
+ double[] lngInterval = {-180.0, 180.0};
+
+ final StringBuilder geohash = new StringBuilder(precision);
+ boolean isEven = true;
+
+ int bit = 0;
+ int ch = 0;
+
+ while (geohash.length() < precision) {
+ double mid = 0.0;
+ if (isEven) {
+ mid = (lngInterval[0] + lngInterval[1]) / 2D;
+ if (longitude > mid) {
+ ch |= BITS[bit];
+ lngInterval[0] = mid;
+ } else {
+ lngInterval[1] = mid;
+ }
+ } else {
+ mid = (latInterval[0] + latInterval[1]) / 2D;
+ if (latitude > mid) {
+ ch |= BITS[bit];
+ latInterval[0] = mid;
+ } else {
+ latInterval[1] = mid;
+ }
+ }
+
+ isEven = !isEven;
+
+ if (bit < 4) {
+ bit++;
+ } else {
+ geohash.append(BASE_32[ch]);
+ bit = 0;
+ ch = 0;
+ }
+ }
+
+ return geohash.toString();
+ }
+
+ /**
+ * 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 Point decode(String geohash, SpatialContext ctx) {
+ Rectangle rect = decodeBoundary(geohash,ctx);
+ double latitude = (rect.getMinY() + rect.getMaxY()) / 2D;
+ double longitude = (rect.getMinX() + rect.getMaxX()) / 2D;
+ return ctx.makePoint(longitude,latitude);
+ }
+
+ /** Returns min-max lat, min-max lon. */
+ public static Rectangle decodeBoundary(String geohash, SpatialContext ctx) {
+ double minY = -90, maxY = 90, minX = -180, maxX = 180;
+ boolean isEven = true;
+
+ for (int i = 0; i < geohash.length(); i++) {
+ char c = geohash.charAt(i);
+ if (c >= 'A' && c <= 'Z')
+ c -= ('A' - 'a');
+ final int cd = BASE_32_IDX[c - BASE_32[0]];//TODO check successful?
+
+ for (int mask : BITS) {
+ if (isEven) {
+ if ((cd & mask) != 0) {
+ minX = (minX + maxX) / 2D;
+ } else {
+ maxX = (minX + maxX) / 2D;
+ }
+ } else {
+ if ((cd & mask) != 0) {
+ minY = (minY + maxY) / 2D;
+ } else {
+ maxY = (minY + maxY) / 2D;
+ }
+ }
+ isEven = !isEven;
+ }
+
+ }
+ return ctx.makeRect(minX, maxX, minY, maxY);
+ }
+
+ /** Array of geohashes 1 level below the baseGeohash. Sorted. */
+ public static String[] getSubGeohashes(String baseGeohash) {
+ String[] hashes = new String[BASE_32.length];
+ for (int i = 0; i < BASE_32.length; i++) {//note: already sorted
+ char c = BASE_32[i];
+ hashes[i] = baseGeohash+c;
+ }
+ return hashes;
+ }
+
+ public static double[] lookupDegreesSizeForHashLen(int hashLen) {
+ return new double[]{hashLenToLatHeight[hashLen], hashLenToLonWidth[hashLen]};
+ }
+
+ /**
+ * Return the longest geohash length that will have a width & height >= specified arguments.
+ */
+ public static int lookupHashLenForWidthHeight(double width, double height) {
+ //loop through hash length arrays from beginning till we find one.
+ for(int len = 1; len <= MAX_PRECISION; len++) {
+ double latHeight = hashLenToLatHeight[len];
+ double lonWidth = hashLenToLonWidth[len];
+ if (latHeight < height || lonWidth < width)
+ return len-1;//previous length is big enough to encompass specified width & height
+ }
+ return MAX_PRECISION;
+ }
+
+ /** See the table at http://en.wikipedia.org/wiki/Geohash */
+ private static final double[] hashLenToLatHeight, hashLenToLonWidth;
+ static {
+ hashLenToLatHeight = new double[MAX_PRECISION +1];
+ hashLenToLonWidth = new double[MAX_PRECISION +1];
+ hashLenToLatHeight[0] = 90*2;
+ hashLenToLonWidth[0] = 180*2;
+ boolean even = false;
+ for(int i = 1; i <= MAX_PRECISION; i++) {
+ hashLenToLatHeight[i] = hashLenToLatHeight[i-1]/(even?8:4);
+ hashLenToLonWidth[i] = hashLenToLonWidth[i-1]/(even?4:8);
+ even = ! even;
+ }
+ }
+
+}
Added: lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/package-info.java
URL: http://svn.apache.org/viewvc/lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/package-info.java?rev=1291499&view=auto
==============================================================================
--- lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/package-info.java (added)
+++ lucene/dev/branches/lucene3795_lsp_spatial_module/modules/spatial-lucene/src/main/java/org/apache/lucene/spatial/base/prefix/package-info.java Mon Feb 20 22:45:32 2012
@@ -0,0 +1,28 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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.
+ */
+
+/**
+ * The Spatial Prefix package supports spatial indexing by index-time tokens
+ * where adding characters to a string gives greater resolution.
+ *
+ * Potential Implementations include:
+ * * http://en.wikipedia.org/wiki/Quadtree
+ * * http://en.wikipedia.org/wiki/Geohash
+ * * http://healpix.jpl.nasa.gov/
+ */
+package org.apache.lucene.spatial.base.prefix;
+