You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by kw...@apache.org on 2016/06/07 11:13:16 UTC
lucene-solr:branch_6x: LUCENE-7316: Use intersections in bounds
computations for GeoConvexPolygon and GeoConcavePolygon.
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 <Da...@gmail.com>
Authored: Tue Jun 7 07:10:38 2016 -0400
Committer: Karl Wright <Da...@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,