lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From a.@apache.org
Subject [19/26] lucene-solr:jira/solr-12730: LUCENE-8554: Add new LatLonShapeLineQuery that queries indexed LatLonShape fields by arbitrary lines
Date Mon, 05 Nov 2018 18:56:37 GMT
LUCENE-8554: Add new LatLonShapeLineQuery that queries indexed LatLonShape fields by arbitrary lines


Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/0cbefe8b
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/0cbefe8b
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/0cbefe8b

Branch: refs/heads/jira/solr-12730
Commit: 0cbefe8b25044a0f565c8491bda86626f2eddf5e
Parents: 2b8f577
Author: Nicholas Knize <nknize@gmail.com>
Authored: Thu Nov 1 12:38:39 2018 -0500
Committer: Nicholas Knize <nknize@gmail.com>
Committed: Fri Nov 2 11:48:59 2018 -0500

----------------------------------------------------------------------
 lucene/CHANGES.txt                              |   3 +
 .../java/org/apache/lucene/geo/EdgeTree.java    | 426 +++++++++++++++++
 .../java/org/apache/lucene/geo/GeoUtils.java    |  14 +
 .../java/org/apache/lucene/geo/Polygon2D.java   | 478 +++----------------
 .../java/org/apache/lucene/geo/Rectangle.java   |   7 +
 .../org/apache/lucene/document/LatLonShape.java |   7 +
 .../document/LatLonShapeBoundingBoxQuery.java   |  62 ++-
 .../lucene/document/LatLonShapeLineQuery.java   | 138 ++++++
 .../document/LatLonShapePolygonQuery.java       |   2 +-
 .../lucene/document/LatLonShapeQuery.java       |   4 +-
 .../src/java/org/apache/lucene/geo/Line.java    |  10 +
 .../src/java/org/apache/lucene/geo/Line2D.java  |  40 ++
 .../document/BaseLatLonShapeTestCase.java       | 123 ++++-
 .../document/TestLatLonLineShapeQueries.java    |  48 +-
 .../document/TestLatLonPointShapeQueries.java   |  42 +-
 .../document/TestLatLonPolygonShapeQueries.java |  15 +-
 16 files changed, 974 insertions(+), 445 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/0cbefe8b/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index acf0dee..3461e57 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -241,6 +241,9 @@ New Features
   https://github.com/snowballstem/snowball/blob/master/algorithms/arabic.sbl 
   (Ryadh Dahimene via Jim Ferenczi)
 
+* LUCENE-8554: Add new LatLonShapeLineQuery that queries indexed LatLonShape fields
+  by arbitrary lines. (Nick Knize)
+
 Improvements:
 
 * LUCENE-8521: Change LatLonShape encoding to 7 dimensions instead of 6; where the

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/0cbefe8b/lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java b/lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java
new file mode 100644
index 0000000..d954f88
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/geo/EdgeTree.java
@@ -0,0 +1,426 @@
+/*
+ * 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.geo;
+
+import java.util.Arrays;
+import java.util.Comparator;
+
+import org.apache.lucene.index.PointValues.Relation;
+import org.apache.lucene.util.ArrayUtil;
+
+import static org.apache.lucene.geo.GeoUtils.lineCrossesLine;
+import static org.apache.lucene.geo.GeoUtils.orient;
+
+/**
+ * 2D line/polygon geometry implementation represented as a balanced interval tree of edges.
+ * <p>
+ * Construction takes {@code O(n log n)} time for sorting and tree construction.
+ * {@link #relate relate()} are {@code O(n)}, but for most
+ * practical lines and polygons are much faster than brute force.
+ * @lucene.internal
+ */
+public abstract class EdgeTree {
+  /** minimum latitude of this geometry's bounding box area */
+  public final double minLat;
+  /** maximum latitude of this geometry's bounding box area */
+  public final double maxLat;
+  /** minimum longitude of this geometry's bounding box area */
+  public final double minLon;
+  /** maximum longitude of this geometry's bounding box area */
+  public final double maxLon;
+
+  // each component is a node in an augmented 2d kd-tree: we alternate splitting between latitude/longitude,
+  // and pull up max values for both dimensions to each parent node (regardless of split).
+
+  /** maximum latitude of this component or any of its children */
+  protected double maxY;
+  /** maximum longitude of this component or any of its children */
+  protected double maxX;
+  /** which dimension was this node split on */
+  // TODO: its implicit based on level, but boolean keeps code simple
+  protected boolean splitX;
+
+  // child components, or null
+  protected EdgeTree left;
+  protected EdgeTree right;
+
+  /** root node of edge tree */
+  protected final Edge tree;
+
+  protected EdgeTree(final double minLat, final double maxLat, final double minLon, final double maxLon, double[] lats, double[] lons) {
+    this.minLat = minLat;
+    this.maxLat = maxLat;
+    this.minLon = minLon;
+    this.maxLon = maxLon;
+    this.maxY = maxLat;
+    this.maxX = maxLon;
+
+    // create interval tree of edges
+    this.tree = createTree(lats, lons);
+  }
+
+  /** Returns relation to the provided triangle */
+  public Relation relateTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
+    // compute bounding box of triangle
+    double minLat = StrictMath.min(StrictMath.min(ay, by), cy);
+    double minLon = StrictMath.min(StrictMath.min(ax, bx), cx);
+    double maxLat = StrictMath.max(StrictMath.max(ay, by), cy);
+    double maxLon = StrictMath.max(StrictMath.max(ax, bx), cx);
+    if (minLat <= maxY && minLon <= maxX) {
+      Relation relation = internalComponentRelateTriangle(ax, ay, bx, by, cx, cy);
+      if (relation != Relation.CELL_OUTSIDE_QUERY) {
+        return relation;
+      }
+      if (left != null) {
+        relation = left.relateTriangle(ax, ay, bx, by, cx, cy);
+        if (relation != Relation.CELL_OUTSIDE_QUERY) {
+          return relation;
+        }
+      }
+      if (right != null && ((splitX == false && maxLat >= this.minLat) || (splitX && maxLon >= this.minLon))) {
+        relation = right.relateTriangle(ax, ay, bx, by, cx, cy);
+        if (relation != Relation.CELL_OUTSIDE_QUERY) {
+          return relation;
+        }
+      }
+    }
+    return Relation.CELL_OUTSIDE_QUERY;
+  }
+
+  /** Returns relation to the provided rectangle */
+  public Relation relate(double minLat, double maxLat, double minLon, double maxLon) {
+    if (minLat <= maxY && minLon <= maxX) {
+      Relation relation = internalComponentRelate(minLat, maxLat, minLon, maxLon);
+      if (relation != Relation.CELL_OUTSIDE_QUERY) {
+        return relation;
+      }
+      if (left != null) {
+        relation = left.relate(minLat, maxLat, minLon, maxLon);
+        if (relation != Relation.CELL_OUTSIDE_QUERY) {
+          return relation;
+        }
+      }
+      if (right != null && ((splitX == false && maxLat >= this.minLat) || (splitX && maxLon >= this.minLon))) {
+        relation = right.relate(minLat, maxLat, minLon, maxLon);
+        if (relation != Relation.CELL_OUTSIDE_QUERY) {
+          return relation;
+        }
+      }
+    }
+    return Relation.CELL_OUTSIDE_QUERY;
+  }
+
+  protected Relation componentRelate(double minLat, double maxLat, double minLon, double maxLon) {
+    return null;
+  }
+  protected Relation componentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
+    return null;
+  }
+
+  private Relation internalComponentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
+    // compute bounding box of triangle
+    double minLat = StrictMath.min(StrictMath.min(ay, by), cy);
+    double minLon = StrictMath.min(StrictMath.min(ax, bx), cx);
+    double maxLat = StrictMath.max(StrictMath.max(ay, by), cy);
+    double maxLon = StrictMath.max(StrictMath.max(ax, bx), cx);
+    if (maxLon < this.minLon || minLon > this.maxLon || maxLat < this.minLat || minLat > this.maxLat) {
+      return Relation.CELL_OUTSIDE_QUERY;
+    }
+
+    Relation shapeRelation = componentRelateTriangle(ax, ay, bx, by, cx, cy);
+    if (shapeRelation != null) {
+      return shapeRelation;
+    }
+
+    // we cross
+    if (tree.crossesTriangle(ax, ay, bx, by, cx, cy)) {
+      return Relation.CELL_CROSSES_QUERY;
+    }
+    return Relation.CELL_OUTSIDE_QUERY;
+  }
+
+
+  /** Returns relation to the provided rectangle for this component */
+  protected Relation internalComponentRelate(double minLat, double maxLat, double minLon, double maxLon) {
+    // if the bounding boxes are disjoint then the shape does not cross
+    if (maxLon < this.minLon || minLon > this.maxLon || maxLat < this.minLat || minLat > this.maxLat) {
+      return Relation.CELL_OUTSIDE_QUERY;
+    }
+    // if the rectangle fully encloses us, we cross.
+    if (minLat <= this.minLat && maxLat >= this.maxLat && minLon <= this.minLon && maxLon >= this.maxLon) {
+      return Relation.CELL_CROSSES_QUERY;
+    }
+
+    Relation shapeRelation = componentRelate(minLat, maxLat, minLon, maxLon);
+    if (shapeRelation != null) {
+      return shapeRelation;
+    }
+
+    // we cross
+    if (tree.crosses(minLat, maxLat, minLon, maxLon)) {
+      return Relation.CELL_CROSSES_QUERY;
+    }
+
+    return Relation.CELL_OUTSIDE_QUERY;
+  }
+
+  /** Creates tree from sorted components (with range low and high inclusive) */
+  protected static EdgeTree createTree(EdgeTree components[], int low, int high, boolean splitX) {
+    if (low > high) {
+      return null;
+    }
+    final int mid = (low + high) >>> 1;
+    if (low < high) {
+      Comparator<EdgeTree> comparator;
+      if (splitX) {
+        comparator = (left, right) -> {
+          int ret = Double.compare(left.minLon, right.minLon);
+          if (ret == 0) {
+            ret = Double.compare(left.maxX, right.maxX);
+          }
+          return ret;
+        };
+      } else {
+        comparator = (left, right) -> {
+          int ret = Double.compare(left.minLat, right.minLat);
+          if (ret == 0) {
+            ret = Double.compare(left.maxY, right.maxY);
+          }
+          return ret;
+        };
+      }
+      ArrayUtil.select(components, low, high + 1, mid, comparator);
+    }
+    // add midpoint
+    EdgeTree newNode = components[mid];
+    newNode.splitX = splitX;
+    // add children
+    newNode.left = createTree(components, low, mid - 1, !splitX);
+    newNode.right = createTree(components, mid + 1, high, !splitX);
+    // pull up max values to this node
+    if (newNode.left != null) {
+      newNode.maxX = Math.max(newNode.maxX, newNode.left.maxX);
+      newNode.maxY = Math.max(newNode.maxY, newNode.left.maxY);
+    }
+    if (newNode.right != null) {
+      newNode.maxX = Math.max(newNode.maxX, newNode.right.maxX);
+      newNode.maxY = Math.max(newNode.maxY, newNode.right.maxY);
+    }
+    return newNode;
+  }
+
+  /**
+   * Internal tree node: represents geometry edge from lat1,lon1 to lat2,lon2.
+   * The sort value is {@code low}, which is the minimum latitude of the edge.
+   * {@code max} stores the maximum latitude of this edge or any children.
+   */
+  static class Edge {
+    // lat-lon pair (in original order) of the two vertices
+    final double lat1, lat2;
+    final double lon1, lon2;
+    /** min of this edge */
+    final double low;
+    /** max latitude of this edge or any children */
+    double max;
+
+    /** left child edge, or null */
+    Edge left;
+    /** right child edge, or null */
+    Edge right;
+
+    Edge(double lat1, double lon1, double lat2, double lon2, double low, double max) {
+      this.lat1 = lat1;
+      this.lon1 = lon1;
+      this.lat2 = lat2;
+      this.lon2 = lon2;
+      this.low = low;
+      this.max = max;
+    }
+
+    /** Returns true if the triangle crosses any edge in this edge subtree */
+    boolean crossesTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
+      // compute bounding box of triangle
+      double minLat = StrictMath.min(StrictMath.min(ay, by), cy);
+      double minLon = StrictMath.min(StrictMath.min(ax, bx), cx);
+      double maxLat = StrictMath.max(StrictMath.max(ay, by), cy);
+      double maxLon = StrictMath.max(StrictMath.max(ax, bx), cx);
+
+      if (minLat <= max) {
+        double dy = lat1;
+        double ey = lat2;
+        double dx = lon1;
+        double ex = lon2;
+
+        // optimization: see if the rectangle is outside of the "bounding box" of the polyline at all
+        // if not, don't waste our time trying more complicated stuff
+        boolean outside = (dy < minLat && ey < minLat) ||
+            (dy > maxLat && ey > maxLat) ||
+            (dx < minLon && ex < minLon) ||
+            (dx > maxLon && ex > maxLon);
+
+        if (outside == false) {
+          // does triangle's first edge intersect polyline?
+          // ax, ay -> bx, by
+          if (lineCrossesLine(ax, ay, bx, by, dx, dy, ex, ey)) {
+            return true;
+          }
+
+          // does triangle's second edge intersect polyline?
+          // bx, by -> cx, cy
+          if (lineCrossesLine(bx, by, cx, cy, dx, dy, ex, ey)) {
+            return true;
+          }
+
+          // does triangle's third edge intersect polyline?
+          // cx, cy -> ax, ay
+          if (lineCrossesLine(cx, cy, ax, ay, dx, dy, ex, ey)) {
+            return true;
+          }
+        }
+
+        if (left != null) {
+          if (left.crossesTriangle(ax, ay, bx, by, cx, cy)) {
+            return true;
+          }
+        }
+
+        if (right != null && maxLat >= low) {
+          if (right.crossesTriangle(ax, ay, bx, by, cx, cy)) {
+            return true;
+          }
+        }
+      }
+      return false;
+    }
+
+    /** Returns true if the box crosses any edge in this edge subtree */
+    boolean crosses(double minLat, double maxLat, double minLon, double maxLon) {
+      // we just have to cross one edge to answer the question, so we descend the tree and return when we do.
+      if (minLat <= max) {
+        // we compute line intersections of every polygon edge with every box line.
+        // if we find one, return true.
+        // for each box line (AB):
+        //   for each poly line (CD):
+        //     intersects = orient(C,D,A) * orient(C,D,B) <= 0 && orient(A,B,C) * orient(A,B,D) <= 0
+        double cy = lat1;
+        double dy = lat2;
+        double cx = lon1;
+        double dx = lon2;
+
+        // optimization: see if the rectangle is outside of the "bounding box" of the polyline at all
+        // if not, don't waste our time trying more complicated stuff
+        boolean outside = (cy < minLat && dy < minLat) ||
+            (cy > maxLat && dy > maxLat) ||
+            (cx < minLon && dx < minLon) ||
+            (cx > maxLon && dx > maxLon);
+        // optimization: see if either end of the line segment is contained by the rectangle
+        if (Rectangle.containsPoint(cy, cx, minLat, maxLat, minLon, maxLon)
+            || Rectangle.containsPoint(dy, dx, minLat, maxLat, minLon, maxLon)) {
+          return true;
+        }
+
+        if (outside == false) {
+          // does box's top edge intersect polyline?
+          // ax = minLon, bx = maxLon, ay = maxLat, by = maxLat
+          if (orient(cx, cy, dx, dy, minLon, maxLat) * orient(cx, cy, dx, dy, maxLon, maxLat) <= 0 &&
+              orient(minLon, maxLat, maxLon, maxLat, cx, cy) * orient(minLon, maxLat, maxLon, maxLat, dx, dy) <= 0) {
+            return true;
+          }
+
+          // does box's right edge intersect polyline?
+          // ax = maxLon, bx = maxLon, ay = maxLat, by = minLat
+          if (orient(cx, cy, dx, dy, maxLon, maxLat) * orient(cx, cy, dx, dy, maxLon, minLat) <= 0 &&
+              orient(maxLon, maxLat, maxLon, minLat, cx, cy) * orient(maxLon, maxLat, maxLon, minLat, dx, dy) <= 0) {
+            return true;
+          }
+
+          // does box's bottom edge intersect polyline?
+          // ax = maxLon, bx = minLon, ay = minLat, by = minLat
+          if (orient(cx, cy, dx, dy, maxLon, minLat) * orient(cx, cy, dx, dy, minLon, minLat) <= 0 &&
+              orient(maxLon, minLat, minLon, minLat, cx, cy) * orient(maxLon, minLat, minLon, minLat, dx, dy) <= 0) {
+            return true;
+          }
+
+          // does box's left edge intersect polyline?
+          // ax = minLon, bx = minLon, ay = minLat, by = maxLat
+          if (orient(cx, cy, dx, dy, minLon, minLat) * orient(cx, cy, dx, dy, minLon, maxLat) <= 0 &&
+              orient(minLon, minLat, minLon, maxLat, cx, cy) * orient(minLon, minLat, minLon, maxLat, dx, dy) <= 0) {
+            return true;
+          }
+        }
+
+        if (left != null) {
+          if (left.crosses(minLat, maxLat, minLon, maxLon)) {
+            return true;
+          }
+        }
+
+        if (right != null && maxLat >= low) {
+          if (right.crosses(minLat, maxLat, minLon, maxLon)) {
+            return true;
+          }
+        }
+      }
+      return false;
+    }
+  }
+
+  /**
+   * Creates an edge interval tree from a set of geometry vertices.
+   * @return root node of the tree.
+   */
+  private static Edge createTree(double[] lats, double[] lons) {
+    Edge edges[] = new Edge[lats.length - 1];
+    for (int i = 1; i < lats.length; i++) {
+      double lat1 = lats[i-1];
+      double lon1 = lons[i-1];
+      double lat2 = lats[i];
+      double lon2 = lons[i];
+      edges[i - 1] = new Edge(lat1, lon1, lat2, lon2, Math.min(lat1, lat2), Math.max(lat1, lat2));
+    }
+    // sort the edges then build a balanced tree from them
+    Arrays.sort(edges, (left, right) -> {
+      int ret = Double.compare(left.low, right.low);
+      if (ret == 0) {
+        ret = Double.compare(left.max, right.max);
+      }
+      return ret;
+    });
+    return createTree(edges, 0, edges.length - 1);
+  }
+
+  /** Creates tree from sorted edges (with range low and high inclusive) */
+  private static Edge createTree(Edge edges[], int low, int high) {
+    if (low > high) {
+      return null;
+    }
+    // add midpoint
+    int mid = (low + high) >>> 1;
+    Edge newNode = edges[mid];
+    // add children
+    newNode.left = createTree(edges, low, mid - 1);
+    newNode.right = createTree(edges, mid + 1, high);
+    // pull up max values to this node
+    if (newNode.left != null) {
+      newNode.max = Math.max(newNode.max, newNode.left.max);
+    }
+    if (newNode.right != null) {
+      newNode.max = Math.max(newNode.max, newNode.right.max);
+    }
+    return newNode;
+  }
+}

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/0cbefe8b/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java b/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
index 468de93..0c73032 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/GeoUtils.java
@@ -194,6 +194,20 @@ public final class GeoUtils {
     }
   }
 
+  /** uses orient method to compute whether two line segments cross */
+  public static boolean lineCrossesLine(double a1x, double a1y, double b1x, double b1y, double a2x, double a2y, double b2x, double b2y) {
+    // shortcut: either "line" is actually a point
+    if ((a1x == b1x && a1y == b1y) || (a2x == b2x && a2y == b2y)) {
+      return false;
+    }
+
+    if (orient(a2x, a2y, b2x, b2y, a1x, a1y) * orient(a2x, a2y, b2x, b2y, b1x, b1y) <= 0 &&
+        orient(a1x, a1y, b1x, b1y, a2x, a2y) * orient(a1x, a1y, b1x, b1y, b2x, b2y) <= 0) {
+      return true;
+    }
+    return false;
+  }
+
   /**
    * used to define the orientation of 3 points
    * -1 = Clockwise

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/0cbefe8b/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java b/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
index 64a3784..fee23d0 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Polygon2D.java
@@ -16,72 +16,29 @@
  */
 package org.apache.lucene.geo;
 
-import java.util.Arrays;
-import java.util.Comparator;
-
 import org.apache.lucene.index.PointValues.Relation;
-import org.apache.lucene.util.ArrayUtil;
-
-import static org.apache.lucene.geo.GeoUtils.orient;
 
 /**
  * 2D polygon implementation represented as a balanced interval tree of edges.
  * <p>
- * Construction takes {@code O(n log n)} time for sorting and tree construction.
- * {@link #contains contains()} and {@link #relate relate()} are {@code O(n)}, but for most 
- * practical polygons are much faster than brute force.
- * <p>
  * Loosely based on the algorithm described in <a href="http://www-ma2.upc.es/geoc/Schirra-pointPolygon.pdf">
  * http://www-ma2.upc.es/geoc/Schirra-pointPolygon.pdf</a>.
  * @lucene.internal
  */
 // Both Polygon.contains() and Polygon.crossesSlowly() loop all edges, and first check that the edge is within a range.
-// we just organize the edges to do the same computations on the same subset of edges more efficiently. 
-public final class Polygon2D {
-  /** minimum latitude of this polygon's bounding box area */
-  public final double minLat;
-  /** maximum latitude of this polygon's bounding box area */
-  public final double maxLat;
-  /** minimum longitude of this polygon's bounding box area */
-  public final double minLon;
-  /** maximum longitude of this polygon's bounding box area */
-  public final double maxLon;
-  
+// we just organize the edges to do the same computations on the same subset of edges more efficiently.
+public final class Polygon2D extends EdgeTree {
   // each component/hole is a node in an augmented 2d kd-tree: we alternate splitting between latitude/longitude,
   // and pull up max values for both dimensions to each parent node (regardless of split).
-
-  /** maximum latitude of this component or any of its children */
-  private double maxY;
-  /** maximum longitude of this component or any of its children */
-  private double maxX;
-  /** which dimension was this node split on */
-  // TODO: its implicit based on level, but boolean keeps code simple
-  private boolean splitX;
-
-  // child components, or null
-  private Polygon2D left;
-  private Polygon2D right;
-  
   /** tree of holes, or null */
   private final Polygon2D holes;
-  
-  /** root node of edge tree */
-  private final Edge tree;
 
   private Polygon2D(Polygon polygon, Polygon2D holes) {
+    super(polygon.minLat, polygon.maxLat, polygon.minLon, polygon.maxLon, polygon.getPolyLats(), polygon.getPolyLons());
     this.holes = holes;
-    this.minLat = polygon.minLat;
-    this.maxLat = polygon.maxLat;
-    this.minLon = polygon.minLon;
-    this.maxLon = polygon.maxLon;
-    this.maxY = maxLat;
-    this.maxX = maxLon;
-    
-    // create interval tree of edges
-    this.tree = createTree(polygon.getPolyLats(), polygon.getPolyLons());
   }
 
-  /** 
+  /**
    * Returns true if the point is contained within this polygon.
    * <p>
    * See <a href="https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html">
@@ -93,96 +50,36 @@ public final class Polygon2D {
         return true;
       }
       if (left != null) {
-        if (left.contains(latitude, longitude)) {
+        if (((Polygon2D)left).contains(latitude, longitude)) {
           return true;
         }
       }
       if (right != null && ((splitX == false && latitude >= minLat) || (splitX && longitude >= minLon))) {
-        if (right.contains(latitude, longitude)) {
+        if (((Polygon2D)right).contains(latitude, longitude)) {
           return true;
         }
       }
     }
     return false;
   }
-  
+
   /** Returns true if the point is contained within this polygon component. */
   private boolean componentContains(double latitude, double longitude) {
     // check bounding box
     if (latitude < minLat || latitude > maxLat || longitude < minLon || longitude > maxLon) {
       return false;
     }
-    
-    if (tree.contains(latitude, longitude)) {
+    if (contains(tree, latitude, longitude)) {
       if (holes != null && holes.contains(latitude, longitude)) {
         return false;
       }
       return true;
     }
-    
     return false;
   }
 
-  /** Returns relation to the provided triangle */
-  public Relation relateTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
-    // compute bounding box of triangle
-    double minLat = StrictMath.min(StrictMath.min(ay, by), cy);
-    double minLon = StrictMath.min(StrictMath.min(ax, bx), cx);
-    double maxLat = StrictMath.max(StrictMath.max(ay, by), cy);
-    double maxLon = StrictMath.max(StrictMath.max(ax, bx), cx);
-    if (minLat <= maxY && minLon <= maxX) {
-      Relation relation = componentRelateTriangle(ax, ay, bx, by, cx, cy);
-      if (relation != Relation.CELL_OUTSIDE_QUERY) {
-        return relation;
-      }
-      if (left != null) {
-        relation = left.relateTriangle(ax, ay, bx, by, cx, cy);
-        if (relation != Relation.CELL_OUTSIDE_QUERY) {
-          return relation;
-        }
-      }
-      if (right != null && ((splitX == false && maxLat >= this.minLat) || (splitX && maxLon >= this.minLon))) {
-        relation = right.relateTriangle(ax, ay, bx, by, cx, cy);
-        if (relation != Relation.CELL_OUTSIDE_QUERY) {
-          return relation;
-        }
-      }
-    }
-    return Relation.CELL_OUTSIDE_QUERY;
-  }
-
-  /** Returns relation to the provided rectangle */
-  public Relation relate(double minLat, double maxLat, double minLon, double maxLon) {
-    if (minLat <= maxY && minLon <= maxX) {
-      Relation relation = componentRelate(minLat, maxLat, minLon, maxLon);
-      if (relation != Relation.CELL_OUTSIDE_QUERY) {
-        return relation;
-      }
-      if (left != null) {
-        relation = left.relate(minLat, maxLat, minLon, maxLon);
-        if (relation != Relation.CELL_OUTSIDE_QUERY) {
-          return relation;
-        }
-      }
-      if (right != null && ((splitX == false && maxLat >= this.minLat) || (splitX && maxLon >= this.minLon))) {
-        relation = right.relate(minLat, maxLat, minLon, maxLon);
-        if (relation != Relation.CELL_OUTSIDE_QUERY) {
-          return relation;
-        }
-      }
-    }
-    return Relation.CELL_OUTSIDE_QUERY;
-  }
-
-  private Relation componentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
-    // compute bounding box of triangle
-    double minLat = StrictMath.min(StrictMath.min(ay, by), cy);
-    double minLon = StrictMath.min(StrictMath.min(ax, bx), cx);
-    double maxLat = StrictMath.max(StrictMath.max(ay, by), cy);
-    double maxLon = StrictMath.max(StrictMath.max(ax, bx), cx);
-    if (maxLon < this.minLon || minLon > this.maxLon || maxLat < this.minLat || minLat > this.maxLat) {
-      return Relation.CELL_OUTSIDE_QUERY;
-    }
+  @Override
+  protected Relation componentRelateTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
     // check any holes
     if (holes != null) {
       Relation holeRelation = holes.relateTriangle(ax, ay, bx, by, cx, cy);
@@ -202,24 +99,12 @@ public final class Polygon2D {
     } else if (numCorners > 0) {
       return Relation.CELL_CROSSES_QUERY;
     }
-
-    // we cross
-    if (tree.crossesTriangle(ax, ay, bx, by, cx, cy)) {
-      return Relation.CELL_CROSSES_QUERY;
-    }
-    return Relation.CELL_OUTSIDE_QUERY;
+    return null;
   }
 
   /** Returns relation to the provided rectangle for this component */
-  private Relation componentRelate(double minLat, double maxLat, double minLon, double maxLon) {
-    // if the bounding boxes are disjoint then the shape does not cross
-    if (maxLon < this.minLon || minLon > this.maxLon || maxLat < this.minLat || minLat > this.maxLat) {
-      return Relation.CELL_OUTSIDE_QUERY;
-    }
-    // if the rectangle fully encloses us, we cross.
-    if (minLat <= this.minLat && maxLat >= this.maxLat && minLon <= this.minLon && maxLon >= this.maxLon) {
-      return Relation.CELL_CROSSES_QUERY;
-    }
+  @Override
+  protected Relation componentRelate(double minLat, double maxLat, double minLon, double maxLon) {
     // check any holes
     if (holes != null) {
       Relation holeRelation = holes.relate(minLat, maxLat, minLon, maxLon);
@@ -239,13 +124,7 @@ public final class Polygon2D {
     } else if (numCorners > 0) {
       return Relation.CELL_CROSSES_QUERY;
     }
-    
-    // we cross
-    if (tree.crosses(minLat, maxLat, minLon, maxLon)) {
-      return Relation.CELL_CROSSES_QUERY;
-    }
-    
-    return Relation.CELL_OUTSIDE_QUERY;
+    return null;
   }
 
   private int numberOfTriangleCorners(double ax, double ay, double bx, double by, double cx, double cy) {
@@ -288,52 +167,7 @@ public final class Polygon2D {
     }
     return containsCount;
   }
-  
-  /** Creates tree from sorted components (with range low and high inclusive) */
-  private static Polygon2D createTree(Polygon2D components[], int low, int high, boolean splitX) {
-    if (low > high) {
-      return null;
-    }
-    final int mid = (low + high) >>> 1;
-    if (low < high) {
-      Comparator<Polygon2D> comparator;
-      if (splitX) {
-        comparator = (left, right) -> {
-          int ret = Double.compare(left.minLon, right.minLon);
-          if (ret == 0) {
-            ret = Double.compare(left.maxX, right.maxX);
-          }
-          return ret;
-        };
-      } else {
-        comparator = (left, right) -> {
-          int ret = Double.compare(left.minLat, right.minLat);
-          if (ret == 0) {
-            ret = Double.compare(left.maxY, right.maxY);
-          }
-          return ret;
-        };
-      }
-      ArrayUtil.select(components, low, high + 1, mid, comparator);
-    }
-    // add midpoint
-    Polygon2D newNode = components[mid];
-    newNode.splitX = splitX;
-    // add children
-    newNode.left = createTree(components, low, mid - 1, !splitX);
-    newNode.right = createTree(components, mid + 1, high, !splitX);
-    // pull up max values to this node
-    if (newNode.left != null) {
-      newNode.maxX = Math.max(newNode.maxX, newNode.left.maxX);
-      newNode.maxY = Math.max(newNode.maxY, newNode.left.maxY);
-    }
-    if (newNode.right != null) {
-      newNode.maxX = Math.max(newNode.maxX, newNode.right.maxX);
-      newNode.maxY = Math.max(newNode.maxY, newNode.right.maxY);
-    }
-    return newNode;
-  }
-  
+
   /** Builds a Polygon2D from multipolygon */
   public static Polygon2D create(Polygon... polygons) {
     Polygon2D components[] = new Polygon2D[polygons.length];
@@ -346,253 +180,55 @@ public final class Polygon2D {
       }
       components[i] = new Polygon2D(gon, holes);
     }
-    return createTree(components, 0, components.length - 1, false);
+    return (Polygon2D)createTree(components, 0, components.length - 1, false);
   }
 
-  /** 
-   * Internal tree node: represents polygon edge from lat1,lon1 to lat2,lon2.
-   * The sort value is {@code low}, which is the minimum latitude of the edge.
-   * {@code max} stores the maximum latitude of this edge or any children.
+  /**
+   * Returns true if the point crosses this edge subtree an odd number of times
+   * <p>
+   * See <a href="https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html">
+   * https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html</a> for more information.
    */
-  static final class Edge {
-    // lat-lon pair (in original order) of the two vertices
-    final double lat1, lat2;
-    final double lon1, lon2;
-    /** min of this edge */
-    final double low;
-    /** max latitude of this edge or any children */
-    double max;
-    
-    /** left child edge, or null */
-    Edge left;
-    /** right child edge, or null */
-    Edge right;
-
-    Edge(double lat1, double lon1, double lat2, double lon2, double low, double max) {
-      this.lat1 = lat1;
-      this.lon1 = lon1;
-      this.lat2 = lat2;
-      this.lon2 = lon2;
-      this.low = low;
-      this.max = max;
-    }
-    
-    /** 
-     * Returns true if the point crosses this edge subtree an odd number of times
-     * <p>
-     * See <a href="https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html">
-     * https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html</a> for more information.
-     */
-    // ported to java from https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html
-    // original code under the BSD license (https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html#License%20to%20Use)
-    //
-    // Copyright (c) 1970-2003, Wm. Randolph Franklin
-    //
-    // Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated 
-    // documentation files (the "Software"), to deal in the Software without restriction, including without limitation 
-    // the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and 
-    // to permit persons to whom the Software is furnished to do so, subject to the following conditions:
-    //
-    // 1. Redistributions of source code must retain the above copyright 
-    //    notice, this list of conditions and the following disclaimers.
-    // 2. Redistributions in binary form must reproduce the above copyright 
-    //    notice in the documentation and/or other materials provided with 
-    //    the distribution.
-    // 3. The name of W. Randolph Franklin may not be used to endorse or 
-    //    promote products derived from this Software without specific 
-    //    prior written permission. 
-    //
-    // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED 
-    // TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 
-    // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF 
-    // CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 
-    // IN THE SOFTWARE. 
-    boolean contains(double latitude, double longitude) {
-      // crossings algorithm is an odd-even algorithm, so we descend the tree xor'ing results along our path
-      boolean res = false;
-      if (latitude <= max) {
-        if (lat1 > latitude != lat2 > latitude) {
-          if (longitude < (lon1 - lon2) * (latitude - lat2) / (lat1 - lat2) + lon2) {
-            res = true;
-          }
-        }
-        if (left != null) {
-          res ^= left.contains(latitude, longitude);
-        }
-        if (right != null && latitude >= low) {
-          res ^= right.contains(latitude, longitude);
+  // ported to java from https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html
+  // original code under the BSD license (https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html#License%20to%20Use)
+  //
+  // Copyright (c) 1970-2003, Wm. Randolph Franklin
+  //
+  // Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated
+  // documentation files (the "Software"), to deal in the Software without restriction, including without limitation
+  // the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and
+  // to permit persons to whom the Software is furnished to do so, subject to the following conditions:
+  //
+  // 1. Redistributions of source code must retain the above copyright
+  //    notice, this list of conditions and the following disclaimers.
+  // 2. Redistributions in binary form must reproduce the above copyright
+  //    notice in the documentation and/or other materials provided with
+  //    the distribution.
+  // 3. The name of W. Randolph Franklin may not be used to endorse or
+  //    promote products derived from this Software without specific
+  //    prior written permission.
+  //
+  // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
+  // TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+  // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
+  // CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+  // IN THE SOFTWARE.
+  private static boolean contains(Edge tree, double latitude, double longitude) {
+    // crossings algorithm is an odd-even algorithm, so we descend the tree xor'ing results along our path
+    boolean res = false;
+    if (latitude <= tree.max) {
+      if (tree.lat1 > latitude != tree.lat2 > latitude) {
+        if (longitude < (tree.lon1 - tree.lon2) * (latitude - tree.lat2) / (tree.lat1 - tree.lat2) + tree.lon2) {
+          res = true;
         }
       }
-      return res;
-    }
-
-    /** Returns true if the triangle crosses any edge in this edge subtree */
-    boolean crossesTriangle(double ax, double ay, double bx, double by, double cx, double cy) {
-      // compute bounding box of triangle
-      double minLat = StrictMath.min(StrictMath.min(ay, by), cy);
-      double minLon = StrictMath.min(StrictMath.min(ax, bx), cx);
-      double maxLat = StrictMath.max(StrictMath.max(ay, by), cy);
-      double maxLon = StrictMath.max(StrictMath.max(ax, bx), cx);
-
-      if (minLat <= max) {
-        double dy = lat1;
-        double ey = lat2;
-        double dx = lon1;
-        double ex = lon2;
-
-        // optimization: see if the rectangle is outside of the "bounding box" of the polyline at all
-        // if not, don't waste our time trying more complicated stuff
-        boolean outside = (dy < minLat && ey < minLat) ||
-            (dy > maxLat && ey > maxLat) ||
-            (dx < minLon && ex < minLon) ||
-            (dx > maxLon && ex > maxLon);
-
-        if (outside == false) {
-          // does triangle's first edge intersect polyline?
-          // ax, ay -> bx, by
-          if (orient(dx, dy, ex, ey, ax, ay) * orient(dx, dy, ex, ey, bx, by) <= 0 &&
-              orient(ax, ay, bx, by, dx, dy) * orient(ax, ay, bx, by, ex, ey) <= 0) {
-            return true;
-          }
-
-          // does triangle's second edge intersect polyline?
-          // bx, by -> cx, cy
-          if (orient(dx, dy, ex, ey, bx, by) * orient(dx, dy, ex, ey, cx, cy) <= 0 &&
-              orient(bx, by, cx, cy, dx, dy) * orient(bx, by, cx, cy, ex, ey) <= 0) {
-            return true;
-          }
-
-          // does triangle's third edge intersect polyline?
-          // cx, cy -> ax, ay
-          if (orient(dx, dy, ex, ey, cx, cy) * orient(dx, dy, ex, ey, ax, ay) <= 0 &&
-              orient(cx, cy, ax, ay, dx, dy) * orient(cx, cy, ax, ay, ex, ey) <= 0) {
-            return true;
-          }
-        }
-
-        if (left != null) {
-          if (left.crossesTriangle(ax, ay, bx, by, cx, cy)) {
-            return true;
-          }
-        }
-
-        if (right != null && maxLat >= low) {
-          if (right.crossesTriangle(ax, ay, bx, by, cx, cy)) {
-            return true;
-          }
-        }
+      if (tree.left != null) {
+        res ^= contains(tree.left, latitude, longitude);
       }
-      return false;
-    }
-
-    /** Returns true if the box crosses any edge in this edge subtree */
-    boolean crosses(double minLat, double maxLat, double minLon, double maxLon) {
-      // we just have to cross one edge to answer the question, so we descend the tree and return when we do.
-      if (minLat <= max) {
-        // we compute line intersections of every polygon edge with every box line.
-        // if we find one, return true.
-        // for each box line (AB):
-        //   for each poly line (CD):
-        //     intersects = orient(C,D,A) * orient(C,D,B) <= 0 && orient(A,B,C) * orient(A,B,D) <= 0
-        double cy = lat1;
-        double dy = lat2;
-        double cx = lon1;
-        double dx = lon2;
-        
-        // optimization: see if the rectangle is outside of the "bounding box" of the polyline at all
-        // if not, don't waste our time trying more complicated stuff
-        boolean outside = (cy < minLat && dy < minLat) ||
-                          (cy > maxLat && dy > maxLat) ||
-                          (cx < minLon && dx < minLon) ||
-                          (cx > maxLon && dx > maxLon);
-        if (outside == false) {
-          // does box's top edge intersect polyline?
-          // ax = minLon, bx = maxLon, ay = maxLat, by = maxLat
-          if (orient(cx, cy, dx, dy, minLon, maxLat) * orient(cx, cy, dx, dy, maxLon, maxLat) <= 0 &&
-              orient(minLon, maxLat, maxLon, maxLat, cx, cy) * orient(minLon, maxLat, maxLon, maxLat, dx, dy) <= 0) {
-            return true;
-          }
-
-          // does box's right edge intersect polyline?
-          // ax = maxLon, bx = maxLon, ay = maxLat, by = minLat
-          if (orient(cx, cy, dx, dy, maxLon, maxLat) * orient(cx, cy, dx, dy, maxLon, minLat) <= 0 &&
-              orient(maxLon, maxLat, maxLon, minLat, cx, cy) * orient(maxLon, maxLat, maxLon, minLat, dx, dy) <= 0) {
-            return true;
-          }
-
-          // does box's bottom edge intersect polyline?
-          // ax = maxLon, bx = minLon, ay = minLat, by = minLat
-          if (orient(cx, cy, dx, dy, maxLon, minLat) * orient(cx, cy, dx, dy, minLon, minLat) <= 0 &&
-              orient(maxLon, minLat, minLon, minLat, cx, cy) * orient(maxLon, minLat, minLon, minLat, dx, dy) <= 0) {
-            return true;
-          }
-
-          // does box's left edge intersect polyline?
-          // ax = minLon, bx = minLon, ay = minLat, by = maxLat
-          if (orient(cx, cy, dx, dy, minLon, minLat) * orient(cx, cy, dx, dy, minLon, maxLat) <= 0 &&
-              orient(minLon, minLat, minLon, maxLat, cx, cy) * orient(minLon, minLat, minLon, maxLat, dx, dy) <= 0) {
-            return true;
-          }
-        }
-        
-        if (left != null) {
-          if (left.crosses(minLat, maxLat, minLon, maxLon)) {
-            return true;
-          }
-        }
-        
-        if (right != null && maxLat >= low) {
-          if (right.crosses(minLat, maxLat, minLon, maxLon)) {
-            return true;
-          }
-        }
+      if (tree.right != null && latitude >= tree.low) {
+        res ^= contains(tree.right, latitude, longitude);
       }
-      return false;
-    }
-  }
-
-  /** 
-   * Creates an edge interval tree from a set of polygon vertices.
-   * @return root node of the tree.
-   */
-  private static Edge createTree(double polyLats[], double polyLons[]) {
-    Edge edges[] = new Edge[polyLats.length - 1];
-    for (int i = 1; i < polyLats.length; i++) {
-      double lat1 = polyLats[i-1];
-      double lon1 = polyLons[i-1];
-      double lat2 = polyLats[i];
-      double lon2 = polyLons[i];
-      edges[i - 1] = new Edge(lat1, lon1, lat2, lon2, Math.min(lat1, lat2), Math.max(lat1, lat2));
-    }
-    // sort the edges then build a balanced tree from them
-    Arrays.sort(edges, (left, right) -> {
-      int ret = Double.compare(left.low, right.low);
-      if (ret == 0) {
-        ret = Double.compare(left.max, right.max);
-      }
-      return ret;
-    });
-    return createTree(edges, 0, edges.length - 1);
-  }
-
-  /** Creates tree from sorted edges (with range low and high inclusive) */
-  private static Edge createTree(Edge edges[], int low, int high) {
-    if (low > high) {
-      return null;
-    }
-    // add midpoint
-    int mid = (low + high) >>> 1;
-    Edge newNode = edges[mid];
-    // add children
-    newNode.left = createTree(edges, low, mid - 1);
-    newNode.right = createTree(edges, mid + 1, high);
-    // pull up max values to this node
-    if (newNode.left != null) {
-      newNode.max = Math.max(newNode.max, newNode.left.max);
-    }
-    if (newNode.right != null) {
-      newNode.max = Math.max(newNode.max, newNode.right.max);
     }
-    return newNode;
+    return res;
   }
 }

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/0cbefe8b/lucene/core/src/java/org/apache/lucene/geo/Rectangle.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/geo/Rectangle.java b/lucene/core/src/java/org/apache/lucene/geo/Rectangle.java
index a8200c6..45d437d 100644
--- a/lucene/core/src/java/org/apache/lucene/geo/Rectangle.java
+++ b/lucene/core/src/java/org/apache/lucene/geo/Rectangle.java
@@ -87,6 +87,13 @@ public class Rectangle {
     return maxLon < minLon;
   }
 
+  /** returns true if rectangle (defined by minLat, maxLat, minLon, maxLon) contains the lat lon point */
+  public static boolean containsPoint(final double lat, final double lon,
+                                      final double minLat, final double maxLat,
+                                      final double minLon, final double maxLon) {
+    return lat >= minLat && lat <= maxLat && lon >= minLon && lon <= maxLon;
+  }
+
   /** Compute Bounding Box for a circle using WGS-84 parameters */
   public static Rectangle fromPointDistance(final double centerLat, final double centerLon, final double radiusMeters) {
     checkLatitude(centerLat);

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/0cbefe8b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShape.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShape.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShape.java
index 99d7c08..580d574 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShape.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShape.java
@@ -124,6 +124,13 @@ public class LatLonShape {
     return new LatLonShapeBoundingBoxQuery(field, queryRelation, minLatitude, maxLatitude, minLongitude, maxLongitude);
   }
 
+  /** create a query to find all polygons that intersect a provided linestring (or array of linestrings)
+   *  note: does not support dateline crossing
+   **/
+  public static Query newLineQuery(String field, QueryRelation queryRelation, Line... lines) {
+    return new LatLonShapeLineQuery(field, queryRelation, lines);
+  }
+
   /** create a query to find all polygons that intersect a provided polygon (or array of polygons)
    *  note: does not support dateline crossing
    **/

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/0cbefe8b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
index cb8f9a1..d1c3e14 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeBoundingBoxQuery.java
@@ -18,7 +18,7 @@ package org.apache.lucene.document;
 
 import java.util.Arrays;
 
-import org.apache.lucene.geo.Polygon;
+import org.apache.lucene.geo.Rectangle;
 import org.apache.lucene.geo.Tessellator;
 import org.apache.lucene.index.PointValues.Relation;
 import org.apache.lucene.util.FutureArrays;
@@ -37,7 +37,7 @@ import static org.apache.lucene.geo.GeoUtils.orient;
  * Finds all previously indexed shapes that intersect the specified bounding box.
  *
  * <p>The field must be indexed using
- * {@link org.apache.lucene.document.LatLonShape#createIndexableFields(String, Polygon)} added per document.
+ * {@link org.apache.lucene.document.LatLonShape#createIndexableFields} added per document.
  *
  *  @lucene.experimental
  **/
@@ -99,25 +99,36 @@ final class LatLonShapeBoundingBoxQuery extends LatLonShapeQuery {
     int cY = (int)(c & 0x00000000FFFFFFFFL);
 
     if (queryRelation == LatLonShape.QueryRelation.WITHIN) {
-      return queryContains(aX, aY) && queryContains(bX, bY) && queryContains(cX, cY);
+      return bboxContainsTriangle(aX, aY, bX, bY, cX, cY, minX, maxX, minY, maxY);
     }
     return queryMatches(aX, aY, bX, bY, cX, cY);
   }
 
-  private boolean queryContains(int x, int y) {
+  /** static utility method to check if a bounding box contains a point */
+  private static boolean bboxContainsPoint(int x, int y, int minX, int maxX, int minY, int maxY) {
     return (x < minX || x > maxX || y < minY || y > maxY) == false;
   }
 
-  private boolean queryContains(int ax, int ay, int bx, int by, int cx, int cy) {
-    return queryContains(ax, ay) || queryContains(bx, by) || queryContains(cx, cy);
+  /** static utility method to check if a bounding box contains a triangle */
+  private static boolean bboxContainsTriangle(int ax, int ay, int bx, int by, int cx, int cy,
+                                              int minX, int maxX, int minY, int maxY) {
+    return bboxContainsPoint(ax, ay, minX, maxX, minY, maxY)
+        && bboxContainsPoint(bx, by, minX, maxX, minY, maxY)
+        && bboxContainsPoint(cx, cy, minX, maxX, minY, maxY);
+  }
+
+  /** instance method to check if query box contains point */
+  private boolean queryContainsPoint(int x, int y) {
+    return bboxContainsPoint(x, y, this.minX, this.maxX, this.minY, this.maxY);
   }
 
   protected boolean queryMatches(int aX, int aY, int bX, int bY, int cX, int cY) {
     // 1. query contains any triangle points
-    if (queryContains(aX, aY, bX, bY, cX, cY)) {
+    if (queryContainsPoint(aX, aY) || queryContainsPoint(bX, bY) || queryContainsPoint(cX, cY)) {
       return true;
     }
 
+    // compute bounding box of triangle
     int tMinX = StrictMath.min(StrictMath.min(aX, bX), cX);
     int tMaxX = StrictMath.max(StrictMath.max(aX, bX), cX);
     int tMinY = StrictMath.min(StrictMath.min(aY, bY), cY);
@@ -139,7 +150,6 @@ final class LatLonShapeBoundingBoxQuery extends LatLonShapeQuery {
       return true;
     }
 
-
     // 4. last ditch effort: check crossings
     if (queryIntersects(aX, aY, bX, bY, cX, cY)) {
       return true;
@@ -148,7 +158,30 @@ final class LatLonShapeBoundingBoxQuery extends LatLonShapeQuery {
   }
 
   /** returns true if the edge (defined by (ax, ay) (bx, by)) intersects the query */
-  private boolean edgeIntersectsQuery(double ax, double ay, double bx, double by) {
+  private static boolean edgeIntersectsBox(int ax, int ay, int bx, int by,
+                                           int minX, int maxX, int minY, int maxY) {
+    // shortcut: if edge is a point (occurs w/ Line shapes); simply check bbox w/ point
+    if (ax == bx && ay == by) {
+      return Rectangle.containsPoint(ay, ax, minY, maxY, minX, maxX);
+    }
+
+    // shortcut: check if either of the end points fall inside the box
+    if (bboxContainsPoint(ax, ay, minX, maxX, minY, maxY)
+        || bboxContainsPoint(bx, by, minX, maxX, minY, maxY)) {
+      return true;
+    }
+
+    // shortcut: check bboxes of edges are disjoint
+    if (boxesAreDisjoint(Math.min(ax, bx), Math.max(ax, bx), Math.min(ay, by), Math.max(ay, by),
+        minX, maxX, minY, maxY)) {
+      return false;
+    }
+
+    // shortcut: edge is a point
+    if (ax == bx && ay == by) {
+      return false;
+    }
+
     // top
     if (orient(ax, ay, bx, by, minX, maxY) * orient(ax, ay, bx, by, maxX, maxY) <= 0 &&
         orient(minX, maxY, maxX, maxY, ax, ay) * orient(minX, maxY, maxX, maxY, bx, by) <= 0) {
@@ -175,6 +208,11 @@ final class LatLonShapeBoundingBoxQuery extends LatLonShapeQuery {
     return false;
   }
 
+  /** returns true if the edge (defined by (ax, ay) (bx, by)) intersects the query */
+  private boolean edgeIntersectsQuery(int ax, int ay, int bx, int by) {
+    return edgeIntersectsBox(ax, ay, bx, by, this.minX, this.maxX, this.minY, this.maxY);
+  }
+
   /** returns true if the query intersects the provided triangle (in encoded space) */
   private boolean queryIntersects(int ax, int ay, int bx, int by, int cx, int cy) {
     // check each edge of the triangle against the query
@@ -186,6 +224,12 @@ final class LatLonShapeBoundingBoxQuery extends LatLonShapeQuery {
     return false;
   }
 
+  /** utility method to check if two boxes are disjoint */
+  public static boolean boxesAreDisjoint(final int aMinX, final int aMaxX, final int aMinY, final int aMaxY,
+                                          final int bMinX, final int bMaxX, final int bMinY, final int bMaxY) {
+    return (aMaxX < bMinX || aMinX > bMaxX || aMaxY < bMinY || aMinY > bMaxY);
+  }
+
   @Override
   public boolean equals(Object o) {
     return sameClassAs(o) && equalsTo(getClass().cast(o));

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/0cbefe8b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeLineQuery.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeLineQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeLineQuery.java
new file mode 100644
index 0000000..e49b4ec
--- /dev/null
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeLineQuery.java
@@ -0,0 +1,138 @@
+/*
+ * 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.document;
+
+import java.util.Arrays;
+
+import org.apache.lucene.document.LatLonShape.QueryRelation;
+import org.apache.lucene.geo.GeoEncodingUtils;
+import org.apache.lucene.geo.Line;
+import org.apache.lucene.geo.Line2D;
+import org.apache.lucene.index.PointValues.Relation;
+import org.apache.lucene.util.NumericUtils;
+
+/**
+ * Finds all previously indexed shapes that intersect the specified arbitrary {@code Line}.
+ * <p>
+ * Note:
+ * <ul>
+ *    <li>{@code QueryRelation.WITHIN} queries are not yet supported</li>
+ *    <li>Dateline crossing is not yet supported</li>
+ * </ul>
+ * <p>
+ * todo:
+ * <ul>
+ *   <li>Add distance support for buffered queries</li>
+ * </ul>
+ * <p>The field must be indexed using
+ * {@link org.apache.lucene.document.LatLonShape#createIndexableFields} added per document.
+ *
+ *  @lucene.experimental
+ **/
+final class LatLonShapeLineQuery extends LatLonShapeQuery {
+  final Line[] lines;
+  final private Line2D line2D;
+
+  public LatLonShapeLineQuery(String field, QueryRelation queryRelation, Line... lines) {
+    super(field, queryRelation);
+    /** line queries do not support within relations, only intersects and disjoint */
+    if (queryRelation == QueryRelation.WITHIN) {
+      throw new IllegalArgumentException("LatLonShapeLineQuery does not support " + QueryRelation.WITHIN + " queries");
+    }
+
+    if (lines == null) {
+      throw new IllegalArgumentException("lines must not be null");
+    }
+    if (lines.length == 0) {
+      throw new IllegalArgumentException("lines must not be empty");
+    }
+    for (int i = 0; i < lines.length; ++i) {
+      if (lines[i] == null) {
+        throw new IllegalArgumentException("line[" + i + "] must not be null");
+      } else if (lines[i].minLon > lines[i].maxLon) {
+        throw new IllegalArgumentException("LatLonShapeLineQuery does not currently support querying across dateline.");
+      }
+    }
+    this.lines = lines.clone();
+    this.line2D = Line2D.create(lines);
+  }
+
+  @Override
+  protected Relation relateRangeBBoxToQuery(int minXOffset, int minYOffset, byte[] minTriangle,
+                                                        int maxXOffset, int maxYOffset, byte[] maxTriangle) {
+    double minLat = GeoEncodingUtils.decodeLatitude(LatLonShape.decodeTriangleBoxVal(minTriangle, minYOffset));
+    double minLon = GeoEncodingUtils.decodeLongitude(LatLonShape.decodeTriangleBoxVal(minTriangle, minXOffset));
+    double maxLat = GeoEncodingUtils.decodeLatitude(LatLonShape.decodeTriangleBoxVal(maxTriangle, maxYOffset));
+    double maxLon = GeoEncodingUtils.decodeLongitude(LatLonShape.decodeTriangleBoxVal(maxTriangle, maxXOffset));
+
+    // check internal node against query
+    return line2D.relate(minLat, maxLat, minLon, maxLon);
+  }
+
+  @Override
+  protected boolean queryMatches(byte[] t) {
+    long a = NumericUtils.sortableBytesToLong(t, 4 * LatLonShape.BYTES);
+    long b = NumericUtils.sortableBytesToLong(t, 5 * LatLonShape.BYTES);
+    long c = NumericUtils.sortableBytesToLong(t, 6 * LatLonShape.BYTES);
+
+    int aX = (int)((a >>> 32) & 0x00000000FFFFFFFFL);
+    int bX = (int)((b >>> 32) & 0x00000000FFFFFFFFL);
+    int cX = (int)((c >>> 32) & 0x00000000FFFFFFFFL);
+    int aY = (int)(a & 0x00000000FFFFFFFFL);
+    int bY = (int)(b & 0x00000000FFFFFFFFL);
+    int cY = (int)(c & 0x00000000FFFFFFFFL);
+
+    double alat = GeoEncodingUtils.decodeLatitude(aY);
+    double alon = GeoEncodingUtils.decodeLongitude(aX);
+    double blat = GeoEncodingUtils.decodeLatitude(bY);
+    double blon = GeoEncodingUtils.decodeLongitude(bX);
+    double clat = GeoEncodingUtils.decodeLatitude(cY);
+    double clon = GeoEncodingUtils.decodeLongitude(cX);
+
+    if (queryRelation == LatLonShape.QueryRelation.WITHIN) {
+      return line2D.relateTriangle(alon, alat, blon, blat, clon, clat) == Relation.CELL_INSIDE_QUERY;
+    }
+    // INTERSECTS
+    return line2D.relateTriangle(alon, alat, blon, blat, clon, clat) != Relation.CELL_OUTSIDE_QUERY;
+  }
+
+  @Override
+  public String toString(String field) {
+    final StringBuilder sb = new StringBuilder();
+    sb.append(getClass().getSimpleName());
+    sb.append(':');
+    if (this.field.equals(field) == false) {
+      sb.append(" field=");
+      sb.append(this.field);
+      sb.append(':');
+    }
+    sb.append("Line(" + lines[0].toGeoJSON() + ")");
+    return sb.toString();
+  }
+
+  @Override
+  protected boolean equalsTo(Object o) {
+    return super.equalsTo(o) && Arrays.equals(lines, ((LatLonShapeLineQuery)o).lines);
+  }
+
+  @Override
+  public int hashCode() {
+    int hash = super.hashCode();
+    hash = 31 * hash + Arrays.hashCode(lines);
+    return hash;
+  }
+}

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/0cbefe8b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapePolygonQuery.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapePolygonQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapePolygonQuery.java
index a587112..2b342a8 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapePolygonQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapePolygonQuery.java
@@ -29,7 +29,7 @@ import org.apache.lucene.util.NumericUtils;
  * Finds all previously indexed shapes that intersect the specified arbitrary.
  *
  * <p>The field must be indexed using
- * {@link org.apache.lucene.document.LatLonShape#createIndexableFields(String, Polygon)} added per document.
+ * {@link org.apache.lucene.document.LatLonShape#createIndexableFields} added per document.
  *
  *  @lucene.experimental
  **/

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/0cbefe8b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeQuery.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeQuery.java b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeQuery.java
index be6b758..454b2b8 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeQuery.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/LatLonShapeQuery.java
@@ -271,8 +271,8 @@ abstract class LatLonShapeQuery extends Query {
     return Relation.CELL_CROSSES_QUERY;
   }
 
-  /** utility class for implementing constant score logic specifig to INTERSECT, WITHIN, and DISJOINT */
-  protected static abstract class RelationScorerSupplier extends ScorerSupplier {
+  /** utility class for implementing constant score logic specific to INTERSECT, WITHIN, and DISJOINT */
+  private static abstract class RelationScorerSupplier extends ScorerSupplier {
     PointValues values;
     IntersectVisitor visitor;
     long cost = -1;

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/0cbefe8b/lucene/sandbox/src/java/org/apache/lucene/geo/Line.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/geo/Line.java b/lucene/sandbox/src/java/org/apache/lucene/geo/Line.java
index c7e626d..489e5cf 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/geo/Line.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/Line.java
@@ -98,6 +98,16 @@ public class Line {
     return lons[vertex];
   }
 
+  /** Returns a copy of the internal latitude array */
+  public double[] getLats() {
+    return lats.clone();
+  }
+
+  /** Returns a copy of the internal longitude array */
+  public double[] getLons() {
+    return lons.clone();
+  }
+
   @Override
   public boolean equals(Object o) {
     if (this == o) return true;

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/0cbefe8b/lucene/sandbox/src/java/org/apache/lucene/geo/Line2D.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/geo/Line2D.java b/lucene/sandbox/src/java/org/apache/lucene/geo/Line2D.java
new file mode 100644
index 0000000..0f9441f
--- /dev/null
+++ b/lucene/sandbox/src/java/org/apache/lucene/geo/Line2D.java
@@ -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.geo;
+
+/**
+ * 2D line implementation represented as a balanced interval tree of edges.
+ * <p>
+ * Line {@code Line2D} Construction takes {@code O(n log n)} time for sorting and tree construction.
+ * {@link #relate relate()} are {@code O(n)}, but for most practical lines are much faster than brute force.
+ * @lucene.internal
+ */
+public final class Line2D extends EdgeTree {
+
+  private Line2D(Line line) {
+    super(line.minLat, line.maxLat, line.minLon, line.maxLon, line.getLats(), line.getLons());
+  }
+
+  /** create a Line2D edge tree from provided array of Linestrings */
+  public static Line2D create(Line... lines) {
+    Line2D components[] = new Line2D[lines.length];
+    for (int i = 0; i < components.length; ++i) {
+      components[i] = new Line2D(lines[i]);
+    }
+    return (Line2D)createTree(components, 0, components.length - 1, false);
+  }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/0cbefe8b/lucene/sandbox/src/test/org/apache/lucene/document/BaseLatLonShapeTestCase.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/BaseLatLonShapeTestCase.java b/lucene/sandbox/src/test/org/apache/lucene/document/BaseLatLonShapeTestCase.java
index 35f980d..106446e 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/BaseLatLonShapeTestCase.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/BaseLatLonShapeTestCase.java
@@ -25,6 +25,7 @@ import com.carrotsearch.randomizedtesting.generators.RandomPicks;
 import org.apache.lucene.document.LatLonShape.QueryRelation;
 import org.apache.lucene.geo.GeoTestUtil;
 import org.apache.lucene.geo.Line;
+import org.apache.lucene.geo.Line2D;
 import org.apache.lucene.geo.Polygon;
 import org.apache.lucene.geo.Polygon2D;
 import org.apache.lucene.geo.Rectangle;
@@ -65,6 +66,7 @@ public abstract class BaseLatLonShapeTestCase extends LuceneTestCase {
 
   /** name of the LatLonShape indexed field */
   protected static final String FIELD_NAME = "shape";
+  private static final QueryRelation[] POINT_LINE_RELATIONS = {QueryRelation.INTERSECTS, QueryRelation.DISJOINT};
 
   protected abstract ShapeType getShapeType();
 
@@ -114,6 +116,26 @@ public abstract class BaseLatLonShapeTestCase extends LuceneTestCase {
     return new Line(lats, lons);
   }
 
+  /** use {@link GeoTestUtil#nextPolygon()} to create a random line; TODO: move to GeoTestUtil */
+  public Line nextLine() {
+    Polygon poly = GeoTestUtil.nextPolygon();
+    double[] lats = new double[poly.numPoints() - 1];
+    double[] lons = new double[lats.length];
+    System.arraycopy(poly.getPolyLats(), 0, lats, 0, lats.length);
+    System.arraycopy(poly.getPolyLons(), 0, lons, 0, lons.length);
+
+    return new Line(lats, lons);
+  }
+
+  /**
+   * return a semi-random line used for queries
+   *
+   * note: shapes parameter may be used to ensure some queries intersect indexed shapes
+   **/
+  protected Line randomQueryLine(Object... shapes) {
+    return nextLine();
+  }
+
   /** creates the array of LatLonShape.Triangle values that are used to index the shape */
   protected abstract Field[] createIndexableFields(String field, Object shape);
 
@@ -130,6 +152,11 @@ public abstract class BaseLatLonShapeTestCase extends LuceneTestCase {
     return LatLonShape.newBoxQuery(field, queryRelation, minLat, maxLat, minLon, maxLon);
   }
 
+  /** factory method to create a new line query */
+  protected Query newLineQuery(String field, QueryRelation queryRelation, Line... lines) {
+    return LatLonShape.newLineQuery(field, queryRelation, lines);
+  }
+
   /** factory method to create a new polygon query */
   protected Query newPolygonQuery(String field, QueryRelation queryRelation, Polygon... polygons) {
     return LatLonShape.newPolygonQuery(field, queryRelation, polygons);
@@ -209,7 +236,9 @@ public abstract class BaseLatLonShapeTestCase extends LuceneTestCase {
 
     // test random bbox queries
     verifyRandomBBoxQueries(reader, shapes);
-    // test random polygon queires
+    // test random line queries
+    verifyRandomLineQueries(reader, shapes);
+    // test random polygon queries
     verifyRandomPolygonQueries(reader, shapes);
 
     IOUtils.close(w, reader, dir);
@@ -269,7 +298,7 @@ public abstract class BaseLatLonShapeTestCase extends LuceneTestCase {
       Query query = newRectQuery(FIELD_NAME, queryRelation, rect.minLat, rect.maxLat, rect.minLon, rect.maxLon);
 
       if (VERBOSE) {
-        System.out.println("  query=" + query);
+        System.out.println("  query=" + query + ", relation=" + queryRelation);
       }
 
       final FixedBitSet hits = new FixedBitSet(maxDoc);
@@ -337,6 +366,93 @@ public abstract class BaseLatLonShapeTestCase extends LuceneTestCase {
     }
   }
 
+  /** test random generated lines */
+  protected void verifyRandomLineQueries(IndexReader reader, Object... shapes) throws Exception {
+    IndexSearcher s = newSearcher(reader);
+
+    final int iters = atLeast(75);
+
+    Bits liveDocs = MultiBits.getLiveDocs(s.getIndexReader());
+    int maxDoc = s.getIndexReader().maxDoc();
+
+    for (int iter = 0; iter < iters; ++iter) {
+      if (VERBOSE) {
+        System.out.println("\nTEST: iter=" + (iter + 1) + " of " + iters + " s=" + s);
+      }
+
+      // line
+      Line queryLine = randomQueryLine(shapes);
+      Line2D queryLine2D = Line2D.create(queryLine);
+      QueryRelation queryRelation = RandomPicks.randomFrom(random(), POINT_LINE_RELATIONS);
+      Query query = newLineQuery(FIELD_NAME, queryRelation, queryLine);
+
+      if (VERBOSE) {
+        System.out.println("  query=" + query + ", relation=" + queryRelation);
+      }
+
+      final FixedBitSet hits = new FixedBitSet(maxDoc);
+      s.search(query, new SimpleCollector() {
+
+        private int docBase;
+
+        @Override
+        public ScoreMode scoreMode() {
+          return ScoreMode.COMPLETE_NO_SCORES;
+        }
+
+        @Override
+        protected void doSetNextReader(LeafReaderContext context) throws IOException {
+          docBase = context.docBase;
+        }
+
+        @Override
+        public void collect(int doc) throws IOException {
+          hits.set(docBase+doc);
+        }
+      });
+
+      boolean fail = false;
+      NumericDocValues docIDToID = MultiDocValues.getNumericValues(reader, "id");
+      for (int docID = 0; docID < maxDoc; ++docID) {
+        assertEquals(docID, docIDToID.nextDoc());
+        int id = (int) docIDToID.longValue();
+        boolean expected;
+        if (liveDocs != null && liveDocs.get(docID) == false) {
+          // document is deleted
+          expected = false;
+        } else if (shapes[id] == null) {
+          expected = false;
+        } else {
+          expected = getValidator(queryRelation).testLineQuery(queryLine2D, shapes[id]);
+        }
+
+        if (hits.get(docID) != expected) {
+          StringBuilder b = new StringBuilder();
+
+          if (expected) {
+            b.append("FAIL: id=" + id + " should match but did not\n");
+          } else {
+            b.append("FAIL: id=" + id + " should not match but did\n");
+          }
+          b.append("  relation=" + queryRelation + "\n");
+          b.append("  query=" + query + " docID=" + docID + "\n");
+          b.append("  shape=" + shapes[id] + "\n");
+          b.append("  deleted?=" + (liveDocs != null && liveDocs.get(docID) == false));
+          b.append("  queryPolygon=" + queryLine.toGeoJSON());
+          if (true) {
+            fail("wrong hit (first of possibly more):\n\n" + b);
+          } else {
+            System.out.println(b.toString());
+            fail = true;
+          }
+        }
+      }
+      if (fail) {
+        fail("some hits were wrong");
+      }
+    }
+  }
+
   /** test random generated polygons */
   protected void verifyRandomPolygonQueries(IndexReader reader, Object... shapes) throws Exception {
     IndexSearcher s = newSearcher(reader);
@@ -358,7 +474,7 @@ public abstract class BaseLatLonShapeTestCase extends LuceneTestCase {
       Query query = newPolygonQuery(FIELD_NAME, queryRelation, queryPolygon);
 
       if (VERBOSE) {
-        System.out.println("  query=" + query);
+        System.out.println("  query=" + query + ", relation=" + queryRelation);
       }
 
       final FixedBitSet hits = new FixedBitSet(maxDoc);
@@ -500,6 +616,7 @@ public abstract class BaseLatLonShapeTestCase extends LuceneTestCase {
   protected abstract class Validator {
     protected QueryRelation queryRelation = QueryRelation.INTERSECTS;
     public abstract boolean testBBoxQuery(double minLat, double maxLat, double minLon, double maxLon, Object shape);
+    public abstract boolean testLineQuery(Line2D line2d, Object shape);
     public abstract boolean testPolygonQuery(Polygon2D poly2d, Object shape);
 
     public void setRelation(QueryRelation relation) {

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/0cbefe8b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonLineShapeQueries.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonLineShapeQueries.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonLineShapeQueries.java
index 9a91232..5c83448 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonLineShapeQueries.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonLineShapeQueries.java
@@ -16,9 +16,12 @@
  */
 package org.apache.lucene.document;
 
+import com.carrotsearch.randomizedtesting.generators.RandomNumbers;
 import org.apache.lucene.document.LatLonShape.QueryRelation;
+import org.apache.lucene.geo.EdgeTree;
+import org.apache.lucene.geo.GeoTestUtil;
 import org.apache.lucene.geo.Line;
-import org.apache.lucene.geo.Polygon;
+import org.apache.lucene.geo.Line2D;
 import org.apache.lucene.geo.Polygon2D;
 import org.apache.lucene.index.PointValues.Relation;
 
@@ -33,6 +36,32 @@ public class TestLatLonLineShapeQueries extends BaseLatLonShapeTestCase {
   }
 
   @Override
+  protected Line randomQueryLine(Object... shapes) {
+    if (random().nextInt(100) == 42) {
+      // we want to ensure some cross, so randomly generate lines that share vertices with the indexed point set
+      int maxBound = (int)Math.floor(shapes.length * 0.1d);
+      if (maxBound < 2) {
+        maxBound = shapes.length;
+      }
+      double[] lats = new double[RandomNumbers.randomIntBetween(random(), 2, maxBound)];
+      double[] lons = new double[lats.length];
+      for (int i = 0, j = 0; j < lats.length && i < shapes.length; ++i, ++j) {
+        Line l = (Line) (shapes[i]);
+        if (random().nextBoolean() && l != null) {
+          int v = random().nextInt(l.numPoints() - 1);
+          lats[j] = l.getLat(v);
+          lons[j] = l.getLon(v);
+        } else {
+          lats[j] = GeoTestUtil.nextLatitude();
+          lons[j] = GeoTestUtil.nextLongitude();
+        }
+      }
+      return new Line(lats, lons);
+    }
+    return nextLine();
+  }
+
+  @Override
   protected Field[] createIndexableFields(String field, Object line) {
     return LatLonShape.createIndexableFields(field, (Line)line);
   }
@@ -54,9 +83,18 @@ public class TestLatLonLineShapeQueries extends BaseLatLonShapeTestCase {
       }
 
       // to keep it simple we convert the bbox into a polygon and use poly2d
-      Polygon2D p = Polygon2D.create(new Polygon[] {new Polygon(new double[] {minLat, minLat, maxLat, maxLat, minLat},
-          new double[] {minLon, maxLon, maxLon, minLon, minLon})});
-      return testLine(p, l);
+      Line2D line = Line2D.create(quantizeLine(l));
+      Relation r = line.relate(minLat, maxLat, minLon, maxLon);
+
+      if (queryRelation == QueryRelation.DISJOINT) {
+        return r == Relation.CELL_OUTSIDE_QUERY;
+      }
+      return r != Relation.CELL_OUTSIDE_QUERY;
+    }
+
+    @Override
+    public boolean testLineQuery(Line2D line2d, Object shape) {
+      return testLine(line2d, (Line) shape);
     }
 
     @Override
@@ -64,7 +102,7 @@ public class TestLatLonLineShapeQueries extends BaseLatLonShapeTestCase {
       return testLine(poly2d, (Line) shape);
     }
 
-    private boolean testLine(Polygon2D queryPoly, Line line) {
+    private boolean testLine(EdgeTree queryPoly, Line line) {
       double ax, ay, bx, by, temp;
       Relation r;
       for (int i = 0, j = 1; j < line.numPoints(); ++i, ++j) {

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/0cbefe8b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointShapeQueries.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointShapeQueries.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointShapeQueries.java
index 00bb8d4..3f3c30d 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointShapeQueries.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPointShapeQueries.java
@@ -16,7 +16,12 @@
  */
 package org.apache.lucene.document;
 
+import com.carrotsearch.randomizedtesting.generators.RandomNumbers;
 import org.apache.lucene.document.LatLonShape.QueryRelation;
+import org.apache.lucene.geo.EdgeTree;
+import org.apache.lucene.geo.GeoTestUtil;
+import org.apache.lucene.geo.Line;
+import org.apache.lucene.geo.Line2D;
 import org.apache.lucene.geo.Polygon2D;
 import org.apache.lucene.index.PointValues.Relation;
 
@@ -36,6 +41,31 @@ public class TestLatLonPointShapeQueries extends BaseLatLonShapeTestCase {
   }
 
   @Override
+  protected Line randomQueryLine(Object... shapes) {
+    if (random().nextInt(100) == 42) {
+      // we want to ensure some cross, so randomly generate lines that share vertices with the indexed point set
+      int maxBound = (int)Math.floor(shapes.length * 0.1d);
+      if (maxBound < 2) {
+        maxBound = shapes.length;
+      }
+      double[] lats = new double[RandomNumbers.randomIntBetween(random(), 2, maxBound)];
+      double[] lons = new double[lats.length];
+      for (int i = 0, j = 0; j < lats.length && i < shapes.length; ++i, ++j) {
+        Point p = (Point) (shapes[i]);
+        if (random().nextBoolean() && p != null) {
+          lats[j] = p.lat;
+          lons[j] = p.lon;
+        } else {
+          lats[j] = GeoTestUtil.nextLatitude();
+          lons[j] = GeoTestUtil.nextLongitude();
+        }
+      }
+      return new Line(lats, lons);
+    }
+    return nextLine();
+  }
+
+  @Override
   protected Field[] createIndexableFields(String field, Object point) {
     Point p = (Point)point;
     return LatLonShape.createIndexableFields(field, p.lat, p.lon);
@@ -61,12 +91,20 @@ public class TestLatLonPointShapeQueries extends BaseLatLonShapeTestCase {
     }
 
     @Override
+    public boolean testLineQuery(Line2D line2d, Object shape) {
+      return testPoint(line2d, (Point) shape);
+    }
+
+    @Override
     public boolean testPolygonQuery(Polygon2D poly2d, Object shape) {
-      Point p = (Point) shape;
+      return testPoint(poly2d, (Point) shape);
+    }
+
+    private boolean testPoint(EdgeTree tree, Point p) {
       double lat = decodeLatitude(encodeLatitude(p.lat));
       double lon = decodeLongitude(encodeLongitude(p.lon));
       // for consistency w/ the query we test the point as a triangle
-      Relation r = poly2d.relateTriangle(lon, lat, lon, lat, lon, lat);
+      Relation r = tree.relateTriangle(lon, lat, lon, lat, lon, lat);
       if (queryRelation == QueryRelation.WITHIN) {
         return r == Relation.CELL_INSIDE_QUERY;
       } else if (queryRelation == QueryRelation.DISJOINT) {

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/0cbefe8b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPolygonShapeQueries.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPolygonShapeQueries.java b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPolygonShapeQueries.java
index 03837a0..3a82dd0 100644
--- a/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPolygonShapeQueries.java
+++ b/lucene/sandbox/src/test/org/apache/lucene/document/TestLatLonPolygonShapeQueries.java
@@ -19,6 +19,8 @@ package org.apache.lucene.document;
 import java.util.List;
 
 import org.apache.lucene.document.LatLonShape.QueryRelation;
+import org.apache.lucene.geo.EdgeTree;
+import org.apache.lucene.geo.Line2D;
 import org.apache.lucene.geo.Polygon;
 import org.apache.lucene.geo.Polygon2D;
 import org.apache.lucene.geo.Tessellator;
@@ -79,11 +81,20 @@ public class TestLatLonPolygonShapeQueries extends BaseLatLonShapeTestCase {
     }
 
     @Override
+    public boolean testLineQuery(Line2D query, Object shape) {
+      return testPolygon(query, (Polygon) shape);
+    }
+
+    @Override
     public boolean testPolygonQuery(Polygon2D query, Object shape) {
-      List<Tessellator.Triangle> tessellation = Tessellator.tessellate((Polygon) shape);
+      return testPolygon(query, (Polygon) shape);
+    }
+
+    private boolean testPolygon(EdgeTree tree, Polygon shape) {
+      List<Tessellator.Triangle> tessellation = Tessellator.tessellate(shape);
       for (Tessellator.Triangle t : tessellation) {
         // we quantize the triangle for consistency with the index
-        Relation r = query.relateTriangle(quantizeLon(t.getLon(0)), quantizeLat(t.getLat(0)),
+        Relation r = tree.relateTriangle(quantizeLon(t.getLon(0)), quantizeLat(t.getLat(0)),
             quantizeLon(t.getLon(1)), quantizeLat(t.getLat(1)),
             quantizeLon(t.getLon(2)), quantizeLat(t.getLat(2)));
         if (queryRelation == QueryRelation.DISJOINT) {


Mime
View raw message