lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kwri...@apache.org
Subject [1/3] lucene-solr:branch_6x: LUCENE-7203: Improve polygon intersection detection using a small amount of upfront work.
Date Tue, 12 Apr 2016 10:09:10 GMT
Repository: lucene-solr
Updated Branches:
  refs/heads/branch_6x 39d74d86c -> 882901dcf


LUCENE-7203: Improve polygon intersection detection using a small amount of upfront work.


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

Branch: refs/heads/branch_6x
Commit: e4b26922ab9c9af8e190a75df0f0a69f15672622
Parents: ace13b5
Author: Karl Wright <DaddyWri@gmail.com>
Authored: Tue Apr 12 06:03:04 2016 -0400
Committer: Karl Wright <DaddyWri@gmail.com>
Committed: Tue Apr 12 06:06:55 2016 -0400

----------------------------------------------------------------------
 .../spatial3d/geom/GeoConcavePolygon.java       | 39 ++++++++++---------
 .../lucene/spatial3d/geom/GeoConvexPolygon.java | 40 +++++++++++---------
 2 files changed, 44 insertions(+), 35 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e4b26922/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConcavePolygon.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConcavePolygon.java
b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConcavePolygon.java
index 8c6f757..518df33 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConcavePolygon.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConcavePolygon.java
@@ -224,7 +224,17 @@ class GeoConcavePolygon extends GeoBasePolygon {
     // For each edge, create a bounds object.
     eitherBounds = new HashMap<>(edges.length);
     for (int edgeIndex = 0; edgeIndex < edges.length; edgeIndex++) {
-      eitherBounds.put(edges[edgeIndex], new EitherBound(invertedEdges[edgeIndex]));
+      final SidedPlane edge = edges[edgeIndex];
+      final SidedPlane invertedEdge = invertedEdges[edgeIndex];
+      int bound1Index = legalIndex(edgeIndex+1);
+      while (invertedEdges[legalIndex(bound1Index)].isNumericallyIdentical(invertedEdge))
{
+        bound1Index++;
+      }
+      int bound2Index = legalIndex(edgeIndex-1);
+      while (invertedEdges[legalIndex(bound2Index)].isNumericallyIdentical(invertedEdge))
{
+        bound2Index--;
+      }
+      eitherBounds.put(edge, new EitherBound(invertedEdges[legalIndex(bound1Index)], invertedEdges[legalIndex(bound2Index)]));
     }
 
     // Pick an edge point arbitrarily
@@ -238,6 +248,9 @@ class GeoConcavePolygon extends GeoBasePolygon {
   protected int legalIndex(int index) {
     while (index >= points.size())
       index -= points.size();
+    while (index < 0) {
+      index += points.size();
+    }
     return index;
   }
 
@@ -297,37 +310,29 @@ class GeoConcavePolygon extends GeoBasePolygon {
     return false;
   }
 
-  /** A membership implementation representing polygon edges that all must apply.
+  /** A membership implementation representing polygon edges that must apply.
    */
   protected class EitherBound implements Membership {
     
-    protected final SidedPlane exception;
+    protected final SidedPlane sideBound1;
+    protected final SidedPlane sideBound2;
     
     /** Constructor.
       * @param exception is the one plane to exclude from the check.
       */
-    public EitherBound(final SidedPlane exception) {
-      this.exception = exception;
+    public EitherBound(final SidedPlane sideBound1, final SidedPlane sideBound2) {
+      this.sideBound1 = sideBound1;
+      this.sideBound2 = sideBound2;
     }
 
     @Override
     public boolean isWithin(final Vector v) {
-      for (final SidedPlane edge : invertedEdges) {
-        if (edge != exception && !edge.isWithin(v)) {
-          return false;
-        }
-      }
-      return true;
+      return sideBound1.isWithin(v) && sideBound2.isWithin(v);
     }
 
     @Override
     public boolean isWithin(final double x, final double y, final double z) {
-      for (final SidedPlane edge : invertedEdges) {
-        if (edge != exception && !edge.isWithin(x, y, z)) {
-          return false;
-        }
-      }
-      return true;
+      return sideBound1.isWithin(x,y,z) && sideBound2.isWithin(x,y,z);
     }
   }
 

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e4b26922/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConvexPolygon.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConvexPolygon.java
b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConvexPolygon.java
index b631b55..4cc8177 100755
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConvexPolygon.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoConvexPolygon.java
@@ -219,8 +219,17 @@ class GeoConvexPolygon extends GeoBasePolygon {
     
     // For each edge, create a bounds object.
     eitherBounds = new HashMap<>(edges.length);
-    for (final SidedPlane edge : edges) {
-      eitherBounds.put(edge, new EitherBound(edge));
+    for (int edgeIndex = 0; edgeIndex < edges.length; edgeIndex++) {
+      final SidedPlane edge = edges[edgeIndex];
+      int bound1Index = legalIndex(edgeIndex+1);
+      while (edges[legalIndex(bound1Index)].isNumericallyIdentical(edge)) {
+        bound1Index++;
+      }
+      int bound2Index = legalIndex(edgeIndex-1);
+      while (edges[legalIndex(bound2Index)].isNumericallyIdentical(edge)) {
+        bound2Index--;
+      }
+      eitherBounds.put(edge, new EitherBound(edges[legalIndex(bound1Index)], edges[legalIndex(bound2Index)]));
     }
     
     // Pick an edge point arbitrarily
@@ -234,6 +243,9 @@ class GeoConvexPolygon extends GeoBasePolygon {
   protected int legalIndex(int index) {
     while (index >= points.size())
       index -= points.size();
+    while (index < 0) {
+      index += points.size();
+    }
     return index;
   }
 
@@ -284,37 +296,29 @@ class GeoConvexPolygon extends GeoBasePolygon {
     return false;
   }
 
-  /** A membership implementation representing polygon edges that all must apply.
+  /** A membership implementation representing polygon edges that must apply.
    */
   protected class EitherBound implements Membership {
     
-    protected final SidedPlane exception;
+    protected final SidedPlane sideBound1;
+    protected final SidedPlane sideBound2;
     
     /** Constructor.
       * @param exception is the one plane to exclude from the check.
       */
-    public EitherBound(final SidedPlane exception) {
-      this.exception = exception;
+    public EitherBound(final SidedPlane sideBound1, final SidedPlane sideBound2) {
+      this.sideBound1 = sideBound1;
+      this.sideBound2 = sideBound2;
     }
 
     @Override
     public boolean isWithin(final Vector v) {
-      for (final SidedPlane edge : edges) {
-        if (edge != exception && !edge.isWithin(v)) {
-          return false;
-        }
-      }
-      return true;
+      return sideBound1.isWithin(v) && sideBound2.isWithin(v);
     }
 
     @Override
     public boolean isWithin(final double x, final double y, final double z) {
-      for (final SidedPlane edge : edges) {
-        if (edge != exception && !edge.isWithin(x, y, z)) {
-          return false;
-        }
-      }
-      return true;
+      return sideBound1.isWithin(x,y,z) && sideBound2.isWithin(x,y,z);
     }
   }
 


Mime
View raw message