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 {