lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From no...@apache.org
Subject [10/50] [abbrv] lucene-solr:apiv2: LUCENE-7424: GeoPolygon computation of intersection bounds was incorrect.
Date Wed, 07 Sep 2016 09:56:58 GMT
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 <DaddyWri@gmail.com>
Authored: Thu Aug 25 18:09:50 2016 -0400
Committer: Karl Wright <DaddyWri@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));
+  }
   
 }


Mime
View raw message