You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by no...@apache.org on 2016/09/07 09:56:58 UTC
[10/50] [abbrv] lucene-solr:apiv2: LUCENE-7424: GeoPolygon
computation of intersection bounds was incorrect.
LUCENE-7424: GeoPolygon computation of intersection bounds was incorrect.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/884aa160
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/884aa160
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/884aa160
Branch: refs/heads/apiv2
Commit: 884aa1609a72e273307a93a6a07f181eab25faad
Parents: e325973
Author: Karl Wright <Da...@gmail.com>
Authored: Thu Aug 25 18:09:50 2016 -0400
Committer: Karl Wright <Da...@gmail.com>
Committed: Thu Aug 25 18:09:50 2016 -0400
----------------------------------------------------------------------
.../spatial3d/geom/GeoConcavePolygon.java | 51 ++++++++------------
.../lucene/spatial3d/geom/GeoConvexPolygon.java | 47 ++++++++----------
.../lucene/spatial3d/geom/GeoPolygonTest.java | 39 +++++++++++++++
3 files changed, 79 insertions(+), 58 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/884aa160/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 1abc06c..e2a4c1e 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
@@ -50,10 +50,10 @@ class GeoConcavePolygon extends GeoBasePolygon {
protected boolean isDone = false;
/** A bounds object for each sided plane */
protected Map<SidedPlane, Membership> eitherBounds = null;
- /** Edge plane for one side of intersection */
- protected Map<SidedPlane, Plane> edgePlanes = null;
- /** Intersection bounds */
- protected Map<SidedPlane, Membership> intersectionBounds = null;
+ /** Map from edge to its previous non-coplanar brother */
+ protected Map<SidedPlane, SidedPlane> prevBrotherMap = null;
+ /** Map from edge to its next non-coplanar brother */
+ protected Map<SidedPlane, SidedPlane> nextBrotherMap = null;
/**
* Create a concave polygon from a list of points. The first point must be on the
@@ -214,8 +214,8 @@ class GeoConcavePolygon extends GeoBasePolygon {
// For each edge, create a bounds object.
eitherBounds = new HashMap<>(edges.length);
- intersectionBounds = new HashMap<>(edges.length);
- edgePlanes = new HashMap<>(edges.length);
+ prevBrotherMap = new HashMap<>(edges.length);
+ nextBrotherMap = new HashMap<>(edges.length);
for (int edgeIndex = 0; edgeIndex < edges.length; edgeIndex++) {
final SidedPlane edge = edges[edgeIndex];
final SidedPlane invertedEdge = invertedEdges[edgeIndex];
@@ -224,16 +224,6 @@ class GeoConcavePolygon extends GeoBasePolygon {
bound1Index++;
}
int bound2Index = legalIndex(edgeIndex-1);
- int otherIndex = bound2Index;
- final SidedPlane otherEdge;
- final SidedPlane otherInvertedEdge;
- if (invertedEdges[legalIndex(otherIndex)].isNumericallyIdentical(invertedEdge)) {
- otherInvertedEdge = null;
- otherEdge = null;
- } else {
- otherInvertedEdge = invertedEdges[legalIndex(otherIndex)];
- otherEdge = edges[legalIndex(otherIndex)];
- }
while (invertedEdges[legalIndex(bound2Index)].isNumericallyIdentical(invertedEdge)) {
bound2Index--;
}
@@ -252,15 +242,10 @@ class GeoConcavePolygon extends GeoBasePolygon {
}
}
eitherBounds.put(edge, new EitherBound(invertedEdges[bound1Index], invertedEdges[bound2Index]));
- // For intersections, we look at the point at the intersection between the previous edge and this one. We need to locate the
- // Intersection bounds needs to look even further forwards/backwards
- if (otherInvertedEdge != null) {
- while (invertedEdges[legalIndex(otherIndex)].isNumericallyIdentical(otherInvertedEdge)) {
- otherIndex--;
- }
- intersectionBounds.put(edge, new EitherBound(invertedEdges[legalIndex(otherIndex)], invertedEdges[legalIndex(bound2Index)]));
- edgePlanes.put(edge, otherEdge);
- }
+ // When we are done with this cycle, we'll need to build the intersection bound for each edge and its brother.
+ // For now, keep track of the relationships.
+ nextBrotherMap.put(invertedEdge, invertedEdges[bound1Index]);
+ prevBrotherMap.put(invertedEdge, invertedEdges[bound2Index]);
}
// Pick an edge point arbitrarily from the outer polygon. Glom this together with all edge points from
@@ -383,7 +368,7 @@ class GeoConcavePolygon extends GeoBasePolygon {
/** A membership implementation representing polygon edges that must apply.
*/
- protected class EitherBound implements Membership {
+ protected static class EitherBound implements Membership {
protected final SidedPlane sideBound1;
protected final SidedPlane sideBound2;
@@ -406,6 +391,12 @@ class GeoConcavePolygon extends GeoBasePolygon {
public boolean isWithin(final double x, final double y, final double z) {
return sideBound1.isWithin(x,y,z) && sideBound2.isWithin(x,y,z);
}
+
+ @Override
+ public String toString() {
+ return "(" + sideBound1 + "," + sideBound2 + ")";
+ }
+
}
@Override
@@ -442,10 +433,10 @@ class GeoConcavePolygon extends GeoBasePolygon {
// Add planes with membership.
for (final SidedPlane edge : edges) {
bounds.addPlane(planetModel, edge, eitherBounds.get(edge));
- final Membership m = intersectionBounds.get(edge);
- if (m != null) {
- bounds.addIntersection(planetModel, edgePlanes.get(edge), edge, m);
- }
+ }
+ for (final SidedPlane invertedEdge : invertedEdges) {
+ final SidedPlane nextEdge = nextBrotherMap.get(invertedEdge);
+ bounds.addIntersection(planetModel, invertedEdge, nextEdge, prevBrotherMap.get(invertedEdge), nextBrotherMap.get(nextEdge));
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/884aa160/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 dbf8f9f..6bd0aad 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
@@ -48,10 +48,10 @@ class GeoConvexPolygon extends GeoBasePolygon {
protected boolean isDone = false;
/** A bounds object for each sided plane */
protected Map<SidedPlane, Membership> eitherBounds = null;
- /** Edge plane for one side of intersection */
- protected Map<SidedPlane, Plane> edgePlanes = null;
- /** Intersection bounds */
- protected Map<SidedPlane, Membership> intersectionBounds = null;
+ /** Map from edge to its previous non-coplanar brother */
+ protected Map<SidedPlane, SidedPlane> prevBrotherMap = null;
+ /** Map from edge to its next non-coplanar brother */
+ protected Map<SidedPlane, SidedPlane> nextBrotherMap = null;
/**
* Create a convex polygon from a list of points. The first point must be on the
@@ -210,8 +210,8 @@ class GeoConvexPolygon extends GeoBasePolygon {
// For each edge, create a bounds object.
eitherBounds = new HashMap<>(edges.length);
- intersectionBounds = new HashMap<>(edges.length);
- edgePlanes = new HashMap<>(edges.length);
+ prevBrotherMap = new HashMap<>(edges.length);
+ nextBrotherMap = new HashMap<>(edges.length);
for (int edgeIndex = 0; edgeIndex < edges.length; edgeIndex++) {
final SidedPlane edge = edges[edgeIndex];
int bound1Index = legalIndex(edgeIndex+1);
@@ -219,13 +219,6 @@ class GeoConvexPolygon extends GeoBasePolygon {
bound1Index++;
}
int bound2Index = legalIndex(edgeIndex-1);
- int otherIndex = bound2Index;
- final SidedPlane otherEdge;
- if (edges[legalIndex(otherIndex)].isNumericallyIdentical(edge)) {
- otherEdge = null;
- } else {
- otherEdge = edges[legalIndex(otherIndex)];
- }
// Look for bound2
while (edges[legalIndex(bound2Index)].isNumericallyIdentical(edge)) {
bound2Index--;
@@ -245,17 +238,12 @@ class GeoConvexPolygon extends GeoBasePolygon {
}
}
eitherBounds.put(edge, new EitherBound(edges[bound1Index], edges[bound2Index]));
- // For intersections, we look at the point at the intersection between the previous edge and this one. We need to locate the
- // Intersection bounds needs to look even further forwards/backwards
- if (otherEdge != null) {
- while (edges[legalIndex(otherIndex)].isNumericallyIdentical(otherEdge)) {
- otherIndex--;
- }
- intersectionBounds.put(edge, new EitherBound(edges[legalIndex(otherIndex)], edges[legalIndex(bound2Index)]));
- edgePlanes.put(edge, otherEdge);
- }
+ // When we are done with this cycle, we'll need to build the intersection bound for each edge and its brother.
+ // For now, keep track of the relationships.
+ nextBrotherMap.put(edge, edges[bound1Index]);
+ prevBrotherMap.put(edge, edges[bound2Index]);
}
-
+
// Pick an edge point arbitrarily from the outer polygon. Glom this together with all edge points from
// inner polygons.
int edgePointCount = 1;
@@ -370,7 +358,7 @@ class GeoConvexPolygon extends GeoBasePolygon {
/** A membership implementation representing polygon edges that must apply.
*/
- protected class EitherBound implements Membership {
+ protected static class EitherBound implements Membership {
protected final SidedPlane sideBound1;
protected final SidedPlane sideBound2;
@@ -393,6 +381,11 @@ class GeoConvexPolygon extends GeoBasePolygon {
public boolean isWithin(final double x, final double y, final double z) {
return sideBound1.isWithin(x,y,z) && sideBound2.isWithin(x,y,z);
}
+
+ @Override
+ public String toString() {
+ return "(" + sideBound1 + "," + sideBound2 + ")";
+ }
}
@@ -428,10 +421,8 @@ class GeoConvexPolygon extends GeoBasePolygon {
// Add planes with membership.
for (final SidedPlane edge : edges) {
bounds.addPlane(planetModel, edge, eitherBounds.get(edge));
- final Membership m = intersectionBounds.get(edge);
- if (m != null) {
- bounds.addIntersection(planetModel, edgePlanes.get(edge), edge, m);
- }
+ final SidedPlane nextEdge = nextBrotherMap.get(edge);
+ bounds.addIntersection(planetModel, edge, nextEdge, prevBrotherMap.get(edge), nextBrotherMap.get(nextEdge));
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/884aa160/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java
index 6745060..8527e99 100755
--- a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java
+++ b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/GeoPolygonTest.java
@@ -927,5 +927,44 @@ shape:
assertTrue(!result);
}
+
+ @Test
+ public void testPolygonFailureCase2() {
+ /*
+ [junit4] 1> shape=GeoCompositeMembershipShape: {[GeoConvexPolygon: {planetmodel=PlanetModel.WGS84, points=[
+ [lat=1.079437865394857, lon=-1.720224083538152E-11([X=0.47111944719262044, Y=-8.104310192839264E-12, Z=0.8803759987367299])],
+ [lat=-1.5707963267948966, lon=0.017453291479645996([X=6.108601474971234E-17, Y=1.066260290095308E-18, Z=-0.997762292022105])],
+ [lat=0.017453291479645996, lon=2.4457272005608357E-47([X=1.0009653513901666, Y=2.448088186713865E-47, Z=0.01747191415779267])]], internalEdges={2}},
+ GeoConvexPolygon: {planetmodel=PlanetModel.WGS84, points=[
+ [lat=1.079437865394857, lon=-1.720224083538152E-11([X=0.47111944719262044, Y=-8.104310192839264E-12, Z=0.8803759987367299])],
+ [lat=0.017453291479645996, lon=2.4457272005608357E-47([X=1.0009653513901666, Y=2.448088186713865E-47, Z=0.01747191415779267])],
+ [lat=0.0884233366943164, lon=0.4323234231678824([X=0.9054355304510789, Y=0.4178006803188124, Z=0.08840463683725623])]], internalEdges={0}}]}
+ */
+ final List<GeoPoint> poly1List = new ArrayList<>();
+ poly1List.add(new GeoPoint(PlanetModel.WGS84, 1.079437865394857, -1.720224083538152E-11));
+ poly1List.add(new GeoPoint(PlanetModel.WGS84, -1.5707963267948966, 0.017453291479645996));
+ poly1List.add(new GeoPoint(PlanetModel.WGS84, 0.017453291479645996, 2.4457272005608357E-47));
+
+ final GeoConvexPolygon poly1 = new GeoConvexPolygon(PlanetModel.WGS84, poly1List);
+
+ /*
+ [junit4] 1> unquantized=[lat=-1.5316724989005415, lon=3.141592653589793([X=-0.03902652216795768, Y=4.779370545484258E-18, Z=-0.9970038705813589])]
+ [junit4] 1> quantized=[X=-0.03902652216283731, Y=2.3309121299774915E-10, Z=-0.9970038706538652]
+ */
+
+ final GeoPoint point = new GeoPoint(PlanetModel.WGS84, -1.5316724989005415, 3.141592653589793);
+
+ assertTrue(poly1.isWithin(point));
+
+ final XYZBounds actualBounds1 = new XYZBounds();
+ poly1.getBounds(actualBounds1);
+
+ final XYZSolid solid = XYZSolidFactory.makeXYZSolid(PlanetModel.WGS84,
+ actualBounds1.getMinimumX(), actualBounds1.getMaximumX(),
+ actualBounds1.getMinimumY(), actualBounds1.getMaximumY(),
+ actualBounds1.getMinimumZ(), actualBounds1.getMaximumZ());
+
+ assertTrue(solid.isWithin(point));
+ }
}