lucene-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From kwri...@apache.org
Subject lucene-solr:branch_6x: LUCENE-7316: Use intersections in bounds computations for GeoConvexPolygon and GeoConcavePolygon.
Date Tue, 07 Jun 2016 11:13:16 GMT
Repository: lucene-solr
Updated Branches:
  refs/heads/branch_6x d4ede8b2f -> 3ee694eb8


LUCENE-7316: Use intersections in bounds computations for GeoConvexPolygon and GeoConcavePolygon.


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

Branch: refs/heads/branch_6x
Commit: 3ee694eb866f0850ea70f16b3d5fb1464197738b
Parents: d4ede8b
Author: Karl Wright <DaddyWri@gmail.com>
Authored: Tue Jun 7 07:10:38 2016 -0400
Committer: Karl Wright <DaddyWri@gmail.com>
Committed: Tue Jun 7 07:12:05 2016 -0400

----------------------------------------------------------------------
 .../spatial3d/geom/GeoConcavePolygon.java       | 31 ++++++-
 .../lucene/spatial3d/geom/GeoConvexPolygon.java | 29 ++++++-
 .../lucene/spatial3d/geom/GeoPolygonTest.java   | 89 ++++++++++++++++++++
 3 files changed, 147 insertions(+), 2 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/3ee694eb/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 0d8f615..a133b3e 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,7 +50,11 @@ 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;
+
   /**
    * Create a concave polygon from a list of points.  The first point must be on the
    * external edge.
@@ -210,6 +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);
     for (int edgeIndex = 0; edgeIndex < edges.length; edgeIndex++) {
       final SidedPlane edge = edges[edgeIndex];
       final SidedPlane invertedEdge = invertedEdges[edgeIndex];
@@ -218,10 +224,29 @@ 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--;
       }
       eitherBounds.put(edge, new EitherBound(invertedEdges[legalIndex(bound1Index)], invertedEdges[legalIndex(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);
+      }
     }
 
     // Pick an edge point arbitrarily from the outer polygon.  Glom this together with all
edge points from
@@ -403,6 +428,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);
+      }
     }
     
   }

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/3ee694eb/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 2ed516a..860eb26 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,6 +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;
   
   /**
    * Create a convex polygon from a list of points.  The first point must be on the
@@ -206,6 +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);
     for (int edgeIndex = 0; edgeIndex < edges.length; edgeIndex++) {
       final SidedPlane edge = edges[edgeIndex];
       int bound1Index = legalIndex(edgeIndex+1);
@@ -213,10 +219,27 @@ 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--;
       }
       eitherBounds.put(edge, new EitherBound(edges[legalIndex(bound1Index)], edges[legalIndex(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);
+      }
     }
     
     // Pick an edge point arbitrarily from the outer polygon.  Glom this together with all
edge points from
@@ -383,7 +406,7 @@ class GeoConvexPolygon extends GeoBasePolygon {
       bounds.addPoint(planetModel.MAX_Y_POLE);
     }
 
-    // Add all the points
+    // Add all the points and the intersections
     for (final GeoPoint point : points) {
       bounds.addPoint(point);
     }
@@ -391,6 +414,10 @@ 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);
+      }
     }
     
   }

http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/3ee694eb/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 f030896..6aec9b3 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
@@ -662,6 +662,95 @@ shape:
   }
   
   @Test
+  public void testPolygonFactoryCase5() {
+    /*
+   [junit4]   1> points=[[lat=0.0425265613312593, lon=0.0([X=1.0002076326868337, Y=0.0,
Z=0.042561051669501374])], 
+    [lat=0.8894380320379947, lon=-2.8993466885897496([X=-0.6109015457368775, Y=-0.1509528453728308,
Z=0.7760109675775679])], 
+    [lat=-0.8298163536994994, lon=-0.1462586594666574([X=0.6673285226073522, Y=-0.09830454048435874,
Z=-0.7372817203741138])], 
+    [lat=0.0, lon=-1.7156310907312492E-12([X=1.0011188539924791, Y=-1.7175506314267352E-12,
Z=0.0])], 
+    [lat=-0.7766317703682181, lon=3.141592653589793([X=-0.7128972529667801, Y=8.730473389667082E-17,
Z=-0.7005064828988063])]]
+
+   {[GeoConvexPolygon: {planetmodel=PlanetModel.WGS84, points=
+   [[lat=0.0425265613312593, lon=0.0([X=1.0002076326868337, Y=0.0, Z=0.042561051669501374])],

+   [lat=0.8894380320379947, lon=-2.8993466885897496([X=-0.6109015457368775, Y=-0.1509528453728308,
Z=0.7760109675775679])], 
+   [lat=-0.8298163536994994, lon=-0.1462586594666574([X=0.6673285226073522, Y=-0.09830454048435874,
Z=-0.7372817203741138])], 
+   [lat=0.0, lon=-1.7156310907312492E-12([X=1.0011188539924791, Y=-1.7175506314267352E-12,
Z=0.0])]], internalEdges={3}}, 
+   GeoConvexPolygon: {planetmodel=PlanetModel.WGS84, points=
+   [[lat=0.0425265613312593, lon=0.0([X=1.0002076326868337, Y=0.0, Z=0.042561051669501374])],

+   [lat=0.0, lon=-1.7156310907312492E-12([X=1.0011188539924791, Y=-1.7175506314267352E-12,
Z=0.0])], 
+   [lat=-0.7766317703682181, lon=3.141592653589793([X=-0.7128972529667801, Y=8.730473389667082E-17,
Z=-0.7005064828988063])]], internalEdges={0}}]}
+    */
+    final GeoPoint p1 = new GeoPoint(PlanetModel.WGS84, 0.0425265613312593, 0.0);
+    final GeoPoint p2 = new GeoPoint(PlanetModel.WGS84, 0.8894380320379947, -2.8993466885897496);
+    final GeoPoint p3 = new GeoPoint(PlanetModel.WGS84, -0.8298163536994994, -0.1462586594666574);
+    final GeoPoint p4 = new GeoPoint(PlanetModel.WGS84, 0.0, -1.7156310907312492E-12);
+    final GeoPoint p5 = new GeoPoint(PlanetModel.WGS84, -0.7766317703682181, 3.141592653589793);
+
+    final List<GeoPoint> polyList = new ArrayList<>();
+    polyList.add(p1);
+    polyList.add(p2);
+    polyList.add(p3);
+    polyList.add(p4);
+    polyList.add(p5);
+    
+    GeoPolygon p = GeoPolygonFactory.makeGeoPolygon(PlanetModel.WGS84, polyList);
+    System.out.println("p = "+p);
+
+    XYZBounds bounds = new XYZBounds();
+    p.getBounds(bounds);
+    XYZSolid solid = XYZSolidFactory.makeXYZSolid(PlanetModel.WGS84, bounds.getMinimumX(),
bounds.getMaximumX(),
+      bounds.getMinimumY(), bounds.getMaximumY(),
+      bounds.getMinimumZ(), bounds.getMaximumZ());
+
+    //final List<GeoPoint> p1List = new ArrayList<>();
+    //p1List.add(p1);
+    //p1List.add(p2);
+    //p1List.add(p3);
+    //p1List.add(p4);
+    //final BitSet p1Internal = new BitSet();
+    //final GeoConvexPolygon poly1 = new GeoConvexPolygon(PlanetModel.WGS84, p1List, p1Internal,
false);
+    
+    /*
+    final List<GeoPoint> p2List = new ArrayList<>();
+    p2List.add(p1);
+    p2List.add(p4);
+    p2List.add(p5);
+    final BitSet p2Internal = new BitSet();
+    final GeoConvexPolygon poly2 = new GeoConvexPolygon(PlanetModel.WGS84, p2List, p2Internal,
false);
+    */
+    
+    //XYZBounds bounds1 = new XYZBounds();
+    //poly1.getBounds(bounds1);
+    //XYZSolid solid1 = XYZSolidFactory.makeXYZSolid(PlanetModel.WGS84, bounds1.getMinimumX(),
bounds1.getMaximumX(),
+    //  bounds1.getMinimumY(), bounds1.getMaximumY(),
+    //  bounds1.getMinimumZ(), bounds1.getMaximumZ());
+    
+    /*
+    XYZBounds bounds2 = new XYZBounds();
+    poly2.getBounds(bounds2);
+    XYZSolid solid2 = XYZSolidFactory.makeXYZSolid(PlanetModel.WGS84, bounds2.getMinimumX(),
bounds2.getMaximumX(),
+      bounds2.getMinimumY(), bounds2.getMaximumY(),
+      bounds2.getMinimumZ(), bounds2.getMaximumZ());
+    */
+    
+    final GeoPoint point = new GeoPoint(PlanetModel.WGS84, -0.41518838180529244, 3.141592653589793);
+    final GeoPoint encodedPoint = new GeoPoint(-0.9155623168963972, 2.3309121299774915E-10,
-0.40359240449795253);
+    System.out.println("point = "+point);
+    System.out.println("encodedPoint = "+encodedPoint);
+    
+    assertTrue(p.isWithin(point));
+    assertTrue(solid.isWithin(point));
+    
+    //System.out.println("bounds1 = "+bounds1);
+    //System.out.println("bounds2 = "+bounds2);
+    //assertTrue(poly1.isWithin(point));
+    //assertTrue(poly2.isWithin(point));
+    //assertTrue(solid2.isWithin(point));
+    
+    //assertTrue(poly2.isWithin(encodedPoint));
+  }
+  
+  @Test
   public void testLargePolygonFailureCase1() {
     /*
    [junit4]    >   shape=GeoComplexPolygon: {planetmodel=PlanetModel.WGS84, number of
shapes=1, address=65f193fc, 


Mime
View raw message