You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by kw...@apache.org on 2016/05/17 21:20:59 UTC
lucene-solr:master: LUCENE-7212: Add Geo3D sorted document fields.
Repository: lucene-solr
Updated Branches:
refs/heads/master d1202a8f8 -> 07af00d8e
LUCENE-7212: Add Geo3D sorted document fields.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/07af00d8
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/07af00d8
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/07af00d8
Branch: refs/heads/master
Commit: 07af00d8e7bc4ce2820973e2ab511bfe536654c6
Parents: d1202a8
Author: Karl Wright <Da...@gmail.com>
Authored: Tue May 17 17:20:39 2016 -0400
Committer: Karl Wright <Da...@gmail.com>
Committed: Tue May 17 17:20:39 2016 -0400
----------------------------------------------------------------------
.../lucene/spatial3d/Geo3DDocValuesField.java | 113 +++++++++--
.../org/apache/lucene/spatial3d/Geo3DPoint.java | 145 +-------------
.../spatial3d/Geo3DPointDistanceComparator.java | 166 ++++++++++++++++
.../lucene/spatial3d/Geo3DPointSortField.java | 96 ++++++++++
.../org/apache/lucene/spatial3d/Geo3DUtil.java | 191 +++++++++++++++++++
.../apache/lucene/spatial3d/TestGeo3DPoint.java | 2 +-
6 files changed, 559 insertions(+), 154 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/07af00d8/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DDocValuesField.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DDocValuesField.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DDocValuesField.java
index 703cc67..46dd777 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DDocValuesField.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DDocValuesField.java
@@ -25,6 +25,7 @@ import org.apache.lucene.document.FieldType;
import org.apache.lucene.spatial3d.geom.PlanetModel;
import org.apache.lucene.spatial3d.geom.GeoPoint;
+import org.apache.lucene.spatial3d.geom.GeoDistanceShape;
/**
* An per-document 3D location field.
@@ -54,15 +55,15 @@ public class Geo3DDocValuesField extends Field {
// 0x200000 = (maximum - minimum) * factor
// So, factor = 0x200000 / (maximum - minimum)
- private final double inverseMaximumValue = 1.0 / (double)(0x200000);
+ private final static double inverseMaximumValue = 1.0 / (double)(0x200000);
- private final double inverseXFactor = (PlanetModel.WGS84.getMaximumXValue() - PlanetModel.WGS84.getMinimumXValue()) * inverseMaximumValue;
- private final double inverseYFactor = (PlanetModel.WGS84.getMaximumYValue() - PlanetModel.WGS84.getMinimumYValue()) * inverseMaximumValue;
- private final double inverseZFactor = (PlanetModel.WGS84.getMaximumZValue() - PlanetModel.WGS84.getMinimumZValue()) * inverseMaximumValue;
+ private final static double inverseXFactor = (PlanetModel.WGS84.getMaximumXValue() - PlanetModel.WGS84.getMinimumXValue()) * inverseMaximumValue;
+ private final static double inverseYFactor = (PlanetModel.WGS84.getMaximumYValue() - PlanetModel.WGS84.getMinimumYValue()) * inverseMaximumValue;
+ private final static double inverseZFactor = (PlanetModel.WGS84.getMaximumZValue() - PlanetModel.WGS84.getMinimumZValue()) * inverseMaximumValue;
- private final double xFactor = 1.0 / inverseXFactor;
- private final double yFactor = 1.0 / inverseYFactor;
- private final double zFactor = 1.0 / inverseZFactor;
+ private final static double xFactor = 1.0 / inverseXFactor;
+ private final static double yFactor = 1.0 / inverseYFactor;
+ private final static double zFactor = 1.0 / inverseZFactor;
/**
* Type for a Geo3DDocValuesField
@@ -128,13 +129,47 @@ public class Geo3DDocValuesField extends Field {
);
}
+ /** Decode GeoPoint value from long docvalues value.
+ * @param docValue is the doc values value.
+ * @return the GeoPoint.
+ */
+ public static GeoPoint decodePoint(final long docValue) {
+ return new GeoPoint(decodeX(((int)(docValue >> 42)) & 0x1FFFFF),
+ decodeY(((int)(docValue >> 21)) & 0x1FFFFF),
+ decodeZ(((int)(docValue)) & 0x1FFFFF));
+ }
+
+ /** Decode X value from long docvalues value.
+ * @param docValue is the doc values value.
+ * @return the x value.
+ */
+ public static double decodeXValue(final long docValue) {
+ return decodeX(((int)(docValue >> 42)) & 0x1FFFFF);
+ }
+
+ /** Decode Y value from long docvalues value.
+ * @param docValue is the doc values value.
+ * @return the y value.
+ */
+ public static double decodeYValue(final long docValue) {
+ return decodeY(((int)(docValue >> 21)) & 0x1FFFFF);
+ }
+
+ /** Decode Z value from long docvalues value.
+ * @param docValue is the doc values value.
+ * @return the z value.
+ */
+ public static double decodeZValue(final long docValue) {
+ return decodeZ(((int)(docValue)) & 0x1FFFFF);
+ }
+
// For encoding/decoding, we generally want the following behavior:
// (1) If you encode the maximum value or the minimum value, the resulting int fits in 21 bits.
// (2) If you decode an encoded value, you get back the original value for both the minimum and maximum planet model values.
// (3) Rounding occurs such that a small delta from the minimum and maximum planet model values still returns the same
// values -- that is, these are in the center of the range of input values that should return the minimum or maximum when decoded
- private int encodeX(final double x) {
+ private static int encodeX(final double x) {
if (x > PlanetModel.WGS84.getMaximumXValue()) {
throw new IllegalArgumentException("x value exceeds WGS84 maximum");
} else if (x < PlanetModel.WGS84.getMinimumXValue()) {
@@ -143,11 +178,11 @@ public class Geo3DDocValuesField extends Field {
return (int)Math.floor((x - PlanetModel.WGS84.getMinimumXValue()) * xFactor + 0.5);
}
- private double decodeX(final int x) {
+ private static double decodeX(final int x) {
return x * inverseXFactor + PlanetModel.WGS84.getMinimumXValue();
}
- private int encodeY(final double y) {
+ private static int encodeY(final double y) {
if (y > PlanetModel.WGS84.getMaximumYValue()) {
throw new IllegalArgumentException("y value exceeds WGS84 maximum");
} else if (y < PlanetModel.WGS84.getMinimumYValue()) {
@@ -156,11 +191,11 @@ public class Geo3DDocValuesField extends Field {
return (int)Math.floor((y - PlanetModel.WGS84.getMinimumYValue()) * yFactor + 0.5);
}
- private double decodeY(final int y) {
+ private static double decodeY(final int y) {
return y * inverseYFactor + PlanetModel.WGS84.getMinimumYValue();
}
- private int encodeZ(final double z) {
+ private static int encodeZ(final double z) {
if (z > PlanetModel.WGS84.getMaximumZValue()) {
throw new IllegalArgumentException("z value exceeds WGS84 maximum");
} else if (z < PlanetModel.WGS84.getMinimumZValue()) {
@@ -169,7 +204,7 @@ public class Geo3DDocValuesField extends Field {
return (int)Math.floor((z - PlanetModel.WGS84.getMinimumZValue()) * zFactor + 0.5);
}
- private double decodeZ(final int z) {
+ private static double decodeZ(final int z) {
return z * inverseZFactor + PlanetModel.WGS84.getMinimumZValue();
}
@@ -193,14 +228,60 @@ public class Geo3DDocValuesField extends Field {
long currentValue = Long.valueOf((Long)fieldsData);
- result.append(decodeX(((int)(currentValue >> 42)) & 0x1FFFFF));
+ result.append(decodeXValue(currentValue));
result.append(',');
- result.append(decodeY(((int)(currentValue >> 21)) & 0x1FFFFF));
+ result.append(decodeYValue(currentValue));
result.append(',');
- result.append(decodeZ(((int)(currentValue)) & 0x1FFFFF));
+ result.append(decodeZValue(currentValue));
result.append('>');
return result.toString();
}
+ /**
+ * Creates a SortField for sorting by distance from a point.
+ * <p>
+ * This sort orders documents by ascending distance from the location. The value returned in {@link FieldDoc} for
+ * the hits contains a Double instance with the distance in meters.
+ * <p>
+ * If a document is missing the field, then by default it is treated as having {@link Double#POSITIVE_INFINITY} distance
+ * (missing values sort last).
+ * <p>
+ * If a document contains multiple values for the field, the <i>closest</i> distance to the location is used.
+ *
+ * @param field field name. must not be null.
+ * @param latitude latitude at the center: must be within standard +/-90 coordinate bounds.
+ * @param longitude longitude at the center: must be within standard +/-180 coordinate bounds.
+ * @param maxRadiusMeters is the maximum radius in meters.
+ * @return SortField ordering documents by distance
+ * @throws IllegalArgumentException if {@code field} is null or location has invalid coordinates.
+ */
+ public static SortField newDistanceSort(final String field, final double latitude, final double longitude, final double maxRadiusMeters) {
+ final GeoDistanceShape shape = Geo3DUtil.fromDistance(latitude, longitude, maxRadiusMeters);
+ return new Geo3DPointSortField(field, shape);
+ }
+
+ /**
+ * Creates a SortField for sorting by distance along a path.
+ * <p>
+ * This sort orders documents by ascending distance along the described path. The value returned in {@link FieldDoc} for
+ * the hits contains a Double instance with the distance in meters.
+ * <p>
+ * If a document is missing the field, then by default it is treated as having {@link Double#POSITIVE_INFINITY} distance
+ * (missing values sort last).
+ * <p>
+ * If a document contains multiple values for the field, the <i>closest</i> distance to the location is used.
+ *
+ * @param field field name. must not be null.
+ * @param pathLatitudes latitude values for points of the path: must be within standard +/-90 coordinate bounds.
+ * @param pathLongitudes longitude values for points of the path: must be within standard +/-180 coordinate bounds.
+ * @param pathWidthMeters width of the path in meters.
+ * @return SortField ordering documents by distance
+ * @throws IllegalArgumentException if {@code field} is null or location has invalid coordinates.
+ */
+ public static SortField newDistanceSort(final String field, final double[] pathLatitudes, final double[] pathLongitudes, final double pathWidthMeters) {
+ final GeoDistanceShape shape = Geo3DUtil.fromPath(pathLatitudes, pathLongitudes, pathWidthMeters);
+ return new Geo3DPointSortField(field, shape);
+ }
+
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/07af00d8/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPoint.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPoint.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPoint.java
index 42c513c..2ff1286 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPoint.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPoint.java
@@ -50,11 +50,6 @@ import org.apache.lucene.util.NumericUtils;
* @lucene.experimental */
public final class Geo3DPoint extends Field {
- /** How many radians are in one earth surface meter */
- public final static double RADIANS_PER_METER = 1.0 / PlanetModel.WGS84_MEAN;
- /** How many radians are in one degree */
- public final static double RADIANS_PER_DEGREE = Math.PI / 180.0;
-
/** Indexing {@link FieldType}. */
public static final FieldType TYPE = new FieldType();
static {
@@ -72,20 +67,10 @@ public final class Geo3DPoint extends Field {
GeoUtils.checkLatitude(latitude);
GeoUtils.checkLongitude(longitude);
// Translate latitude/longitude to x,y,z:
- final GeoPoint point = new GeoPoint(PlanetModel.WGS84, fromDegrees(latitude), fromDegrees(longitude));
+ final GeoPoint point = new GeoPoint(PlanetModel.WGS84, Geo3DUtil.fromDegrees(latitude), Geo3DUtil.fromDegrees(longitude));
fillFieldsData(point.x, point.y, point.z);
}
- /** Converts degress to radians */
- private static double fromDegrees(final double degrees) {
- return degrees * RADIANS_PER_DEGREE;
- }
-
- /** Converts earth-surface meters to radians */
- private static double fromMeters(final double meters) {
- return meters * RADIANS_PER_METER;
- }
-
/**
* Create a query for matching points within the specified distance of the supplied location.
* @param field field name. must not be null. Note that because
@@ -99,12 +84,10 @@ public final class Geo3DPoint extends Field {
* @throws IllegalArgumentException if {@code field} is null, location has invalid coordinates, or radius is invalid.
*/
public static Query newDistanceQuery(final String field, final double latitude, final double longitude, final double radiusMeters) {
- GeoUtils.checkLatitude(latitude);
- GeoUtils.checkLongitude(longitude);
- final GeoShape shape = GeoCircleFactory.makeGeoCircle(PlanetModel.WGS84, fromDegrees(latitude), fromDegrees(longitude), fromMeters(radiusMeters));
+ final GeoShape shape = Geo3DUtil.fromDistance(latitude, longitude, radiusMeters);
return newShapeQuery(field, shape);
}
-
+
/**
* Create a query for matching a box.
* <p>
@@ -118,12 +101,7 @@ public final class Geo3DPoint extends Field {
* @throws IllegalArgumentException if {@code field} is null, or the box has invalid coordinates.
*/
public static Query newBoxQuery(final String field, final double minLatitude, final double maxLatitude, final double minLongitude, final double maxLongitude) {
- GeoUtils.checkLatitude(minLatitude);
- GeoUtils.checkLongitude(minLongitude);
- GeoUtils.checkLatitude(maxLatitude);
- GeoUtils.checkLongitude(maxLongitude);
- final GeoShape shape = GeoBBoxFactory.makeGeoBBox(PlanetModel.WGS84,
- fromDegrees(maxLatitude), fromDegrees(minLatitude), fromDegrees(minLongitude), fromDegrees(maxLongitude));
+ final GeoShape shape = Geo3DUtil.fromBox(minLatitude, maxLatitude, minLongitude, maxLongitude);
return newShapeQuery(field, shape);
}
@@ -137,30 +115,7 @@ public final class Geo3DPoint extends Field {
* @return query matching points within this polygon
*/
public static Query newPolygonQuery(final String field, final Polygon... polygons) {
- //System.err.println("Creating polygon...");
- if (polygons.length < 1) {
- throw new IllegalArgumentException("need at least one polygon");
- }
- final GeoShape shape;
- if (polygons.length == 1) {
- final GeoShape component = fromPolygon(polygons[0]);
- if (component == null) {
- // Polygon is degenerate
- shape = new GeoCompositePolygon();
- } else {
- shape = component;
- }
- } else {
- final GeoCompositePolygon poly = new GeoCompositePolygon();
- for (final Polygon p : polygons) {
- final GeoPolygon component = fromPolygon(p);
- if (component != null) {
- poly.addShape(component);
- }
- }
- shape = poly;
- }
- //System.err.println("...done");
+ final GeoShape shape = Geo3DUtil.fromPolygon(polygons);
return newShapeQuery(field, shape);
}
@@ -177,7 +132,7 @@ public final class Geo3DPoint extends Field {
if (polygons.length < 1) {
throw new IllegalArgumentException("need at least one polygon");
}
- final GeoShape shape = fromLargePolygon(polygons);
+ final GeoShape shape = Geo3DUtil.fromLargePolygon(polygons);
return newShapeQuery(field, shape);
}
@@ -191,94 +146,10 @@ public final class Geo3DPoint extends Field {
* @return query matching points within this polygon
*/
public static Query newPathQuery(final String field, final double[] pathLatitudes, final double[] pathLongitudes, final double pathWidthMeters) {
- if (pathLatitudes.length != pathLongitudes.length) {
- throw new IllegalArgumentException("same number of latitudes and longitudes required");
- }
- final GeoPoint[] points = new GeoPoint[pathLatitudes.length];
- for (int i = 0; i < pathLatitudes.length; i++) {
- final double latitude = pathLatitudes[i];
- final double longitude = pathLongitudes[i];
- GeoUtils.checkLatitude(latitude);
- GeoUtils.checkLongitude(longitude);
- points[i] = new GeoPoint(PlanetModel.WGS84, fromDegrees(latitude), fromDegrees(longitude));
- }
- final GeoShape shape = GeoPathFactory.makeGeoPath(PlanetModel.WGS84, fromMeters(pathWidthMeters), points);
+ final GeoShape shape = Geo3DUtil.fromPath(pathLatitudes, pathLongitudes, pathWidthMeters);
return newShapeQuery(field, shape);
}
-
- /**
- * Convert a Polygon object to a large GeoPolygon.
- * @param polygons is the list of polygons to convert.
- * @return the large GeoPolygon.
- */
- private static GeoPolygon fromLargePolygon(final Polygon... polygons) {
- return GeoPolygonFactory.makeLargeGeoPolygon(PlanetModel.WGS84, convertToDescription(polygons));
- }
-
- /**
- * Convert a list of polygons to a list of polygon descriptions.
- * @param polygons is the list of polygons to convert.
- * @return the list of polygon descriptions.
- */
- private static List<GeoPolygonFactory.PolygonDescription> convertToDescription(final Polygon... polygons) {
- final List<GeoPolygonFactory.PolygonDescription> descriptions = new ArrayList<>(polygons.length);
- for (final Polygon polygon : polygons) {
- final Polygon[] theHoles = polygon.getHoles();
- final List<GeoPolygonFactory.PolygonDescription> holes = convertToDescription(theHoles);
-
- // Now do the polygon itself
- final double[] polyLats = polygon.getPolyLats();
- final double[] polyLons = polygon.getPolyLons();
-
- // I presume the arguments have already been checked
- final List<GeoPoint> points = new ArrayList<>(polyLats.length-1);
- // We skip the last point anyway because the API requires it to be repeated, and geo3d doesn't repeat it.
- for (int i = 0; i < polyLats.length - 1; i++) {
- final int index = polyLats.length - 2 - i;
- points.add(new GeoPoint(PlanetModel.WGS84, fromDegrees(polyLats[index]), fromDegrees(polyLons[index])));
- }
-
- descriptions.add(new GeoPolygonFactory.PolygonDescription(points, holes));
- }
- return descriptions;
- }
-
- /**
- * Convert a Polygon object into a GeoPolygon.
- * This method uses
- * @param polygon is the Polygon object.
- * @return the GeoPolygon.
- */
- private static GeoPolygon fromPolygon(final Polygon polygon) {
- // First, assemble the "holes". The geo3d convention is to use the same polygon sense on the inner ring as the
- // outer ring, so we process these recursively with reverseMe flipped.
- final Polygon[] theHoles = polygon.getHoles();
- final List<GeoPolygon> holeList = new ArrayList<>(theHoles.length);
- for (final Polygon hole : theHoles) {
- //System.out.println("Hole: "+hole);
- final GeoPolygon component = fromPolygon(hole);
- if (component != null) {
- holeList.add(component);
- }
- }
-
- // Now do the polygon itself
- final double[] polyLats = polygon.getPolyLats();
- final double[] polyLons = polygon.getPolyLons();
-
- // I presume the arguments have already been checked
- final List<GeoPoint> points = new ArrayList<>(polyLats.length-1);
- // We skip the last point anyway because the API requires it to be repeated, and geo3d doesn't repeat it.
- for (int i = 0; i < polyLats.length - 1; i++) {
- final int index = polyLats.length - 2 - i;
- points.add(new GeoPoint(PlanetModel.WGS84, fromDegrees(polyLats[index]), fromDegrees(polyLons[index])));
- }
- //System.err.println(" building polygon with "+points.size()+" points...");
- final GeoPolygon rval = GeoPolygonFactory.makeGeoPolygon(PlanetModel.WGS84, points, holeList);
- //System.err.println(" ...done");
- return rval;
- }
-
+
/**
* Creates a new Geo3DPoint field with the specified x,y,z.
*
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/07af00d8/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPointDistanceComparator.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPointDistanceComparator.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPointDistanceComparator.java
new file mode 100644
index 0000000..869e3a3
--- /dev/null
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPointDistanceComparator.java
@@ -0,0 +1,166 @@
+/*
+ * 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.spatial3d;
+
+import java.io.IOException;
+
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.FieldInfo;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedNumericDocValues;
+import org.apache.lucene.search.FieldComparator;
+import org.apache.lucene.search.LeafFieldComparator;
+import org.apache.lucene.search.Scorer;
+
+import org.apache.lucene.spatial3d.geom.GeoDistanceShape;
+import org.apache.lucene.spatial3d.geom.XYZBounds;
+import org.apache.lucene.spatial3d.geom.DistanceStyle;
+import org.apache.lucene.spatial3d.geom.PlanetModel;
+
+/**
+ * Compares documents by distance from an origin point, using a GeoDistanceShape to compute the distance
+ * <p>
+ * When the least competitive item on the priority queue changes (setBottom), we recompute
+ * a bounding box representing competitive distance to the top-N. Then in compareBottom, we can
+ * quickly reject hits based on bounding box alone without computing distance for every element.
+ */
+class Geo3DPointDistanceComparator extends FieldComparator<Double> implements LeafFieldComparator {
+ final String field;
+
+ final GeoDistanceShape distanceShape;
+
+ final double[] values;
+ double bottomDistance;
+ double topValue;
+ SortedNumericDocValues currentDocs;
+
+ XYZBounds priorityQueueBounds;
+
+ // the number of times setBottom has been called (adversary protection)
+ int setBottomCounter = 0;
+
+ public Geo3DPointDistanceComparator(String field, final GeoDistanceShape distanceShape, int numHits) {
+ this.field = field;
+ this.distanceShape = distanceShape;
+ this.values = new double[numHits];
+ }
+
+ @Override
+ public void setScorer(Scorer scorer) {}
+
+ @Override
+ public int compare(int slot1, int slot2) {
+ return Double.compare(values[slot1], values[slot2]);
+ }
+
+ @Override
+ public void setBottom(int slot) {
+ bottomDistance = values[slot];
+ // make bounding box(es) to exclude non-competitive hits, but start
+ // sampling if we get called way too much: don't make gobs of bounding
+ // boxes if comparator hits a worst case order (e.g. backwards distance order)
+ if (setBottomCounter < 1024 || (setBottomCounter & 0x3F) == 0x3F) {
+ // Update bounds
+ final XYZBounds bounds = new XYZBounds();
+ distanceShape.getDistanceBounds(bounds, DistanceStyle.ARC, bottomDistance);
+ priorityQueueBounds = bounds;
+ }
+ setBottomCounter++;
+ }
+
+ @Override
+ public void setTopValue(Double value) {
+ topValue = value.doubleValue();
+ }
+
+ @Override
+ public int compareBottom(int doc) throws IOException {
+ currentDocs.setDocument(doc);
+
+ int numValues = currentDocs.count();
+ if (numValues == 0) {
+ return Double.compare(bottomDistance, Double.POSITIVE_INFINITY);
+ }
+
+ int cmp = -1;
+ for (int i = 0; i < numValues; i++) {
+ long encoded = currentDocs.valueAt(i);
+
+ // Test against bounds.
+ // First we need to decode...
+ final double x = Geo3DDocValuesField.decodeXValue(encoded);
+ final double y = Geo3DDocValuesField.decodeYValue(encoded);
+ final double z = Geo3DDocValuesField.decodeZValue(encoded);
+
+ if (x > priorityQueueBounds.getMaximumX() ||
+ x < priorityQueueBounds.getMinimumX() ||
+ y > priorityQueueBounds.getMaximumY() ||
+ y < priorityQueueBounds.getMinimumY() ||
+ z > priorityQueueBounds.getMaximumZ() ||
+ z < priorityQueueBounds.getMinimumZ()) {
+ continue;
+ }
+
+ cmp = Math.max(cmp, Double.compare(bottomDistance, distanceShape.computeDistance(DistanceStyle.ARC, x, y, z)));
+ }
+ return cmp;
+ }
+
+ @Override
+ public void copy(int slot, int doc) throws IOException {
+ values[slot] = computeMinimumDistance(doc);
+ }
+
+ @Override
+ public LeafFieldComparator getLeafComparator(LeafReaderContext context) throws IOException {
+ LeafReader reader = context.reader();
+ FieldInfo info = reader.getFieldInfos().fieldInfo(field);
+ if (info != null) {
+ Geo3DDocValuesField.checkCompatible(info);
+ }
+ currentDocs = DocValues.getSortedNumeric(reader, field);
+ return this;
+ }
+
+ @Override
+ public Double value(int slot) {
+ // Return the arc distance
+ return Double.valueOf(values[slot] * PlanetModel.WGS84_MEAN);
+ }
+
+ @Override
+ public int compareTop(int doc) throws IOException {
+ return Double.compare(topValue, computeMinimumDistance(doc));
+ }
+
+ double computeMinimumDistance(final int doc) {
+ currentDocs.setDocument(doc);
+ double minValue = Double.POSITIVE_INFINITY;
+ final int numValues = currentDocs.count();
+ for (int i = 0; i < numValues; i++) {
+ final long encoded = currentDocs.valueAt(i);
+ final double distance = distanceShape.computeDistance(DistanceStyle.ARC,
+ Geo3DDocValuesField.decodeXValue(encoded),
+ Geo3DDocValuesField.decodeYValue(encoded),
+ Geo3DDocValuesField.decodeZValue(encoded));
+ minValue = Math.min(minValue, distance);
+ }
+ return minValue;
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/07af00d8/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPointSortField.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPointSortField.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPointSortField.java
new file mode 100644
index 0000000..4d6b417
--- /dev/null
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DPointSortField.java
@@ -0,0 +1,96 @@
+/*
+ * 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.spatial3d;
+
+import java.io.IOException;
+
+import org.apache.lucene.search.FieldComparator;
+import org.apache.lucene.search.SortField;
+
+import org.apache.lucene.spatial3d.geom.GeoDistanceShape;
+
+/**
+ * Sorts by distance from an origin location.
+ */
+final class Geo3DPointSortField extends SortField {
+ final GeoDistanceShape distanceShape;
+
+ Geo3DPointSortField(final String field, final GeoDistanceShape distanceShape) {
+ super(field, SortField.Type.CUSTOM);
+ if (field == null) {
+ throw new IllegalArgumentException("field must not be null");
+ }
+ if (distanceShape == null) {
+ throw new IllegalArgumentException("distanceShape must not be null");
+ }
+ this.distanceShape = distanceShape;
+ setMissingValue(Double.POSITIVE_INFINITY);
+ }
+
+ @Override
+ public FieldComparator<?> getComparator(int numHits, int sortPos) throws IOException {
+ return new Geo3DPointDistanceComparator(getField(), distanceShape, numHits);
+ }
+
+ @Override
+ public Double getMissingValue() {
+ return (Double) super.getMissingValue();
+ }
+
+ @Override
+ public void setMissingValue(Object missingValue) {
+ if (Double.valueOf(Double.POSITIVE_INFINITY).equals(missingValue) == false) {
+ throw new IllegalArgumentException("Missing value can only be Double.POSITIVE_INFINITY (missing values last), but got " + missingValue);
+ }
+ this.missingValue = missingValue;
+ }
+
+ @Override
+ public int hashCode() {
+ final int prime = 31;
+ int result = super.hashCode();
+ long temp;
+ temp = distanceShape.hashCode();
+ result = prime * result + (int) (temp ^ (temp >>> 32));
+ return result;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) return true;
+ if (!super.equals(obj)) return false;
+ if (getClass() != obj.getClass()) return false;
+ final Geo3DPointSortField other = (Geo3DPointSortField) obj;
+ return distanceShape.equals(other.distanceShape);
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder builder = new StringBuilder();
+ builder.append("<distanceShape:");
+ builder.append('"');
+ builder.append(getField());
+ builder.append('"');
+ builder.append(" shape=");
+ builder.append(distanceShape);
+ if (Double.POSITIVE_INFINITY != getMissingValue()) {
+ builder.append(" missingValue=" + getMissingValue());
+ }
+ builder.append('>');
+ return builder.toString();
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/07af00d8/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DUtil.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DUtil.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DUtil.java
index bfda66f..a413c06 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DUtil.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/Geo3DUtil.java
@@ -17,9 +17,30 @@
package org.apache.lucene.spatial3d;
import org.apache.lucene.spatial3d.geom.PlanetModel;
+import org.apache.lucene.spatial3d.geom.GeoPolygonFactory;
+import org.apache.lucene.spatial3d.geom.GeoPathFactory;
+import org.apache.lucene.spatial3d.geom.GeoCircleFactory;
+import org.apache.lucene.spatial3d.geom.GeoBBoxFactory;
+import org.apache.lucene.spatial3d.geom.GeoPath;
+import org.apache.lucene.spatial3d.geom.GeoPolygon;
+import org.apache.lucene.spatial3d.geom.GeoCircle;
+import org.apache.lucene.spatial3d.geom.GeoBBox;
+import org.apache.lucene.spatial3d.geom.GeoCompositePolygon;
+import org.apache.lucene.spatial3d.geom.GeoPoint;
+
+import org.apache.lucene.geo.Polygon;
+import org.apache.lucene.geo.GeoUtils;
+
+import java.util.List;
+import java.util.ArrayList;
class Geo3DUtil {
+ /** How many radians are in one earth surface meter */
+ final static double RADIANS_PER_METER = 1.0 / PlanetModel.WGS84_MEAN;
+ /** How many radians are in one degree */
+ final static double RADIANS_PER_DEGREE = Math.PI / 180.0;
+
private static final double MAX_VALUE = PlanetModel.WGS84.getMaximumMagnitude();
private static final int BITS = 32;
private static final double MUL = (0x1L<<BITS)/(2*MAX_VALUE);
@@ -65,4 +86,174 @@ class Geo3DUtil {
}
}
+ /** Converts degress to radians */
+ static double fromDegrees(final double degrees) {
+ return degrees * RADIANS_PER_DEGREE;
+ }
+
+ /** Converts earth-surface meters to radians */
+ static double fromMeters(final double meters) {
+ return meters * RADIANS_PER_METER;
+ }
+
+ /**
+ * Convert a set of Polygon objects into a GeoPolygon.
+ * @param polygons are the Polygon objects.
+ * @return the GeoPolygon.
+ */
+ static GeoPolygon fromPolygon(final Polygon... polygons) {
+ //System.err.println("Creating polygon...");
+ if (polygons.length < 1) {
+ throw new IllegalArgumentException("need at least one polygon");
+ }
+ final GeoPolygon shape;
+ if (polygons.length == 1) {
+ final GeoPolygon component = fromPolygon(polygons[0]);
+ if (component == null) {
+ // Polygon is degenerate
+ shape = new GeoCompositePolygon();
+ } else {
+ shape = component;
+ }
+ } else {
+ final GeoCompositePolygon poly = new GeoCompositePolygon();
+ for (final Polygon p : polygons) {
+ final GeoPolygon component = fromPolygon(p);
+ if (component != null) {
+ poly.addShape(component);
+ }
+ }
+ shape = poly;
+ }
+ return shape;
+ //System.err.println("...done");
+ }
+
+
+ /**
+ * Convert a Polygon object to a large GeoPolygon.
+ * @param polygons is the list of polygons to convert.
+ * @return the large GeoPolygon.
+ */
+ static GeoPolygon fromLargePolygon(final Polygon... polygons) {
+ return GeoPolygonFactory.makeLargeGeoPolygon(PlanetModel.WGS84, convertToDescription(polygons));
+ }
+
+ /**
+ * Convert input parameters to a path.
+ * @param pathLatitudes latitude values for points of the path: must be within standard +/-90 coordinate bounds.
+ * @param pathLongitudes longitude values for points of the path: must be within standard +/-180 coordinate bounds.
+ * @param pathWidthMeters width of the path in meters.
+ * @return the path.
+ */
+ static GeoPath fromPath(final double[] pathLatitudes, final double[] pathLongitudes, final double pathWidthMeters) {
+ if (pathLatitudes.length != pathLongitudes.length) {
+ throw new IllegalArgumentException("same number of latitudes and longitudes required");
+ }
+ final GeoPoint[] points = new GeoPoint[pathLatitudes.length];
+ for (int i = 0; i < pathLatitudes.length; i++) {
+ final double latitude = pathLatitudes[i];
+ final double longitude = pathLongitudes[i];
+ GeoUtils.checkLatitude(latitude);
+ GeoUtils.checkLongitude(longitude);
+ points[i] = new GeoPoint(PlanetModel.WGS84, fromDegrees(latitude), fromDegrees(longitude));
+ }
+ return GeoPathFactory.makeGeoPath(PlanetModel.WGS84, fromMeters(pathWidthMeters), points);
+ }
+
+ /**
+ * Convert input parameters to a circle.
+ * @param latitude latitude at the center: must be within standard +/-90 coordinate bounds.
+ * @param longitude longitude at the center: must be within standard +/-180 coordinate bounds.
+ * @param radiusMeters maximum distance from the center in meters: must be non-negative and finite.
+ * @return the circle.
+ */
+ static GeoCircle fromDistance(final double latitude, final double longitude, final double radiusMeters) {
+ GeoUtils.checkLatitude(latitude);
+ GeoUtils.checkLongitude(longitude);
+ return GeoCircleFactory.makeGeoCircle(PlanetModel.WGS84, fromDegrees(latitude), fromDegrees(longitude), fromMeters(radiusMeters));
+ }
+
+ /**
+ * Convert input parameters to a box.
+ * @param minLatitude latitude lower bound: must be within standard +/-90 coordinate bounds.
+ * @param maxLatitude latitude upper bound: must be within standard +/-90 coordinate bounds.
+ * @param minLongitude longitude lower bound: must be within standard +/-180 coordinate bounds.
+ * @param maxLongitude longitude upper bound: must be within standard +/-180 coordinate bounds.
+ * @return the box.
+ */
+ static GeoBBox fromBox(final double minLatitude, final double maxLatitude, final double minLongitude, final double maxLongitude) {
+ GeoUtils.checkLatitude(minLatitude);
+ GeoUtils.checkLongitude(minLongitude);
+ GeoUtils.checkLatitude(maxLatitude);
+ GeoUtils.checkLongitude(maxLongitude);
+ return GeoBBoxFactory.makeGeoBBox(PlanetModel.WGS84,
+ Geo3DUtil.fromDegrees(maxLatitude), Geo3DUtil.fromDegrees(minLatitude), Geo3DUtil.fromDegrees(minLongitude), Geo3DUtil.fromDegrees(maxLongitude));
+ }
+
+ /**
+ * Convert a Polygon object into a GeoPolygon.
+ * This method uses
+ * @param polygon is the Polygon object.
+ * @return the GeoPolygon.
+ */
+ private static GeoPolygon fromPolygon(final Polygon polygon) {
+ // First, assemble the "holes". The geo3d convention is to use the same polygon sense on the inner ring as the
+ // outer ring, so we process these recursively with reverseMe flipped.
+ final Polygon[] theHoles = polygon.getHoles();
+ final List<GeoPolygon> holeList = new ArrayList<>(theHoles.length);
+ for (final Polygon hole : theHoles) {
+ //System.out.println("Hole: "+hole);
+ final GeoPolygon component = fromPolygon(hole);
+ if (component != null) {
+ holeList.add(component);
+ }
+ }
+
+ // Now do the polygon itself
+ final double[] polyLats = polygon.getPolyLats();
+ final double[] polyLons = polygon.getPolyLons();
+
+ // I presume the arguments have already been checked
+ final List<GeoPoint> points = new ArrayList<>(polyLats.length-1);
+ // We skip the last point anyway because the API requires it to be repeated, and geo3d doesn't repeat it.
+ for (int i = 0; i < polyLats.length - 1; i++) {
+ final int index = polyLats.length - 2 - i;
+ points.add(new GeoPoint(PlanetModel.WGS84, fromDegrees(polyLats[index]), fromDegrees(polyLons[index])));
+ }
+ //System.err.println(" building polygon with "+points.size()+" points...");
+ final GeoPolygon rval = GeoPolygonFactory.makeGeoPolygon(PlanetModel.WGS84, points, holeList);
+ //System.err.println(" ...done");
+ return rval;
+ }
+
+ /**
+ * Convert a list of polygons to a list of polygon descriptions.
+ * @param polygons is the list of polygons to convert.
+ * @return the list of polygon descriptions.
+ */
+ private static List<GeoPolygonFactory.PolygonDescription> convertToDescription(final Polygon... polygons) {
+ final List<GeoPolygonFactory.PolygonDescription> descriptions = new ArrayList<>(polygons.length);
+ for (final Polygon polygon : polygons) {
+ final Polygon[] theHoles = polygon.getHoles();
+ final List<GeoPolygonFactory.PolygonDescription> holes = convertToDescription(theHoles);
+
+ // Now do the polygon itself
+ final double[] polyLats = polygon.getPolyLats();
+ final double[] polyLons = polygon.getPolyLons();
+
+ // I presume the arguments have already been checked
+ final List<GeoPoint> points = new ArrayList<>(polyLats.length-1);
+ // We skip the last point anyway because the API requires it to be repeated, and geo3d doesn't repeat it.
+ for (int i = 0; i < polyLats.length - 1; i++) {
+ final int index = polyLats.length - 2 - i;
+ points.add(new GeoPoint(PlanetModel.WGS84, fromDegrees(polyLats[index]), fromDegrees(polyLons[index])));
+ }
+
+ descriptions.add(new GeoPolygonFactory.PolygonDescription(points, holes));
+ }
+ return descriptions;
+ }
+
+
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/07af00d8/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java
index c2cb93b..3475b17 100644
--- a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java
+++ b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/TestGeo3DPoint.java
@@ -132,7 +132,7 @@ public class TestGeo3DPoint extends LuceneTestCase {
}
private static double toRadians(double degrees) {
- return degrees * Geo3DPoint.RADIANS_PER_DEGREE;
+ return degrees * Geo3DUtil.RADIANS_PER_DEGREE;
}
private static class Cell {