You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by th...@apache.org on 2016/04/14 01:21:42 UTC
[26/50] lucene-solr:jira/SOLR-8908: LUCENE-7203: Improve polygon
intersection detection using a small amount of upfront work.
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/aa4236a6
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/aa4236a6
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/aa4236a6
Branch: refs/heads/jira/SOLR-8908
Commit: aa4236a61299aff832b2bac70585cb480e3274e5
Parents: 61e3c40
Author: Karl Wright <Da...@gmail.com>
Authored: Tue Apr 12 06:03:04 2016 -0400
Committer: Karl Wright <Da...@gmail.com>
Committed: Tue Apr 12 06:03:04 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/aa4236a6/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/aa4236a6/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);
}
}