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 2018/03/25 16:22:21 UTC
lucene-solr:branch_6x: LUCENE-8220: Add general makeGeoPolygon
variant that decides the best technology for you.
Repository: lucene-solr
Updated Branches:
refs/heads/branch_6x 81ac4d28f -> a13befe75
LUCENE-8220: Add general makeGeoPolygon variant that decides the best technology for you.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/a13befe7
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/a13befe7
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/a13befe7
Branch: refs/heads/branch_6x
Commit: a13befe7580c93b8721a4680b8208de3b8c49d5e
Parents: 81ac4d2
Author: Karl Wright <Da...@gmail.com>
Authored: Sun Mar 25 12:20:41 2018 -0400
Committer: Karl Wright <Da...@gmail.com>
Committed: Sun Mar 25 12:22:15 2018 -0400
----------------------------------------------------------------------
.../spatial3d/geom/GeoPolygonFactory.java | 219 ++++++++++++++-----
.../lucene/spatial3d/geom/GeoPolygonTest.java | 61 ++++--
2 files changed, 206 insertions(+), 74 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/a13befe7/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPolygonFactory.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPolygonFactory.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPolygonFactory.java
index 9478388..d8938dc 100755
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPolygonFactory.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPolygonFactory.java
@@ -36,20 +36,8 @@ public class GeoPolygonFactory {
private GeoPolygonFactory() {
}
- /** Create a GeoPolygon using the specified points and holes, using order to determine
- * siding of the polygon. Much like ESRI, this method uses clockwise to indicate the space
- * on the same side of the shape as being inside, and counter-clockwise to indicate the
- * space on the opposite side as being inside.
- * @param pointList is a list of the GeoPoints to build an arbitrary polygon out of. If points go
- * clockwise from a given pole, then that pole should be within the polygon. If points go
- * counter-clockwise, then that pole should be outside the polygon.
- * @return a GeoPolygon corresponding to what was specified.
- */
- public static GeoPolygon makeGeoPolygon(final PlanetModel planetModel,
- final List<GeoPoint> pointList) {
- return makeGeoPolygon(planetModel, pointList, null);
- }
-
+ private static final int SMALL_POLYGON_CUTOFF_EDGES = 100;
+
/** Create a GeoConcavePolygon using the specified points. The polygon must have
* a maximum extent larger than PI. The siding of the polygon is chosen so that any
* adjacent point to a segment provides an exterior measurement and therefore,
@@ -78,24 +66,6 @@ public class GeoPolygonFactory {
return new GeoConvexPolygon(planetModel, pointList);
}
- /** Create a GeoPolygon using the specified points and holes, using order to determine
- * siding of the polygon. Much like ESRI, this method uses clockwise to indicate the space
- * on the same side of the shape as being inside, and counter-clockwise to indicate the
- * space on the opposite side as being inside.
- * @param pointList is a list of the GeoPoints to build an arbitrary polygon out of. If points go
- * clockwise from a given pole, then that pole should be within the polygon. If points go
- * counter-clockwise, then that pole should be outside the polygon.
- * @param holes is a list of polygons representing "holes" in the outside polygon. Holes describe the area outside
- * each hole as being "in set". Null == none.
- * @return a GeoPolygon corresponding to what was specified, or null if a valid polygon cannot be generated
- * from this input.
- */
- public static GeoPolygon makeGeoPolygon(final PlanetModel planetModel,
- final List<GeoPoint> pointList,
- final List<GeoPolygon> holes) {
- return makeGeoPolygon(planetModel, pointList, holes, 0.0);
- }
-
/** Create a GeoConcavePolygon using the specified points and holes. The polygon must have
* a maximum extent larger than PI. The siding of the polygon is chosen so that any adjacent
@@ -130,7 +100,164 @@ public class GeoPolygonFactory {
final List<GeoPolygon> holes) {
return new GeoConvexPolygon(planetModel,pointList, holes);
}
-
+
+ /** Use this class to specify a polygon with associated holes.
+ */
+ public static class PolygonDescription {
+ /** The list of points */
+ public final List<? extends GeoPoint> points;
+ /** The list of holes */
+ public final List<? extends PolygonDescription> holes;
+
+ /** Instantiate the polygon description.
+ * @param points is the list of points.
+ */
+ public PolygonDescription(final List<? extends GeoPoint> points) {
+ this(points, new ArrayList<>());
+ }
+
+ /** Instantiate the polygon description.
+ * @param points is the list of points.
+ * @param holes is the list of holes.
+ */
+ public PolygonDescription(final List<? extends GeoPoint> points, final List<? extends PolygonDescription> holes) {
+ this.points = points;
+ this.holes = holes;
+ }
+
+ }
+
+ /** Create a GeoPolygon using the specified points and holes, using order to determine
+ * siding of the polygon. Much like ESRI, this method uses clockwise to indicate the space
+ * on the same side of the shape as being inside, and counter-clockwise to indicate the
+ * space on the opposite side as being inside.
+ * @param description describes the polygon and its associated holes. If points go
+ * clockwise from a given pole, then that pole should be within the polygon. If points go
+ * counter-clockwise, then that pole should be outside the polygon.
+ * @return a GeoPolygon corresponding to what was specified, or null if a valid polygon cannot be generated
+ * from this input.
+ */
+ public static GeoPolygon makeGeoPolygon(final PlanetModel planetModel,
+ final PolygonDescription description) {
+ return makeGeoPolygon(planetModel, description, 0.0);
+ }
+
+ /** Create a GeoPolygon using the specified points and holes, using order to determine
+ * siding of the polygon. Much like ESRI, this method uses clockwise to indicate the space
+ * on the same side of the shape as being inside, and counter-clockwise to indicate the
+ * space on the opposite side as being inside.
+ * @param description describes the polygon and its associated holes. If points go
+ * clockwise from a given pole, then that pole should be within the polygon. If points go
+ * counter-clockwise, then that pole should be outside the polygon.
+ * @param leniencyValue is the maximum distance (in units) that a point can be from the plane and still be considered as
+ * belonging to the plane. Any value greater than zero may cause some of the provided points that are in fact outside
+ * the strict definition of co-planarity, but are within this distance, to be discarded for the purposes of creating a
+ * "safe" polygon.
+ * @return a GeoPolygon corresponding to what was specified, or null if a valid polygon cannot be generated
+ * from this input.
+ */
+ public static GeoPolygon makeGeoPolygon(final PlanetModel planetModel,
+ final PolygonDescription description,
+ final double leniencyValue) {
+
+ // First, convert the holes to polygons in their own right.
+ final List<GeoPolygon> holes;
+ if (description.holes != null && description.holes.size() > 0) {
+ holes = new ArrayList<>(description.holes.size());
+ for (final PolygonDescription holeDescription : description.holes) {
+ final GeoPolygon gp = makeGeoPolygon(planetModel, holeDescription, leniencyValue);
+ if (gp == null) {
+ return null;
+ }
+ holes.add(gp);
+ }
+ } else {
+ holes = null;
+ }
+
+ // First, exercise a sanity filter on the provided pointList, and remove identical points, linear points, and backtracks
+ //System.err.println(" filtering "+pointList.size()+" points...");
+ //final long startTime = System.currentTimeMillis();
+ final List<GeoPoint> firstFilteredPointList = filterPoints(description.points);
+ if (firstFilteredPointList == null) {
+ return null;
+ }
+ final List<GeoPoint> filteredPointList = filterEdges(firstFilteredPointList, leniencyValue);
+ //System.err.println(" ...done in "+(System.currentTimeMillis()-startTime)+"ms ("+((filteredPointList==null)?"degenerate":(filteredPointList.size()+" points"))+")");
+ if (filteredPointList == null) {
+ return null;
+ }
+
+ if (filteredPointList.size() <= SMALL_POLYGON_CUTOFF_EDGES) {
+ try {
+ //First approximation to find a point
+ final GeoPoint centerOfMass = getCenterOfMass(planetModel, filteredPointList);
+ final Boolean isCenterOfMassInside = isInsidePolygon(centerOfMass, filteredPointList);
+ if (isCenterOfMassInside != null) {
+ return generateGeoPolygon(planetModel, filteredPointList, holes, centerOfMass, isCenterOfMassInside);
+ }
+
+ //System.err.println("points="+pointList);
+ // Create a random number generator. Effectively this furnishes us with a repeatable sequence
+ // of points to use for poles.
+ final Random generator = new Random(1234);
+ for (int counter = 0; counter < 1000000; counter++) {
+ //counter++;
+ // Pick the next random pole
+ final GeoPoint pole = pickPole(generator, planetModel, filteredPointList);
+ // Is it inside or outside?
+ final Boolean isPoleInside = isInsidePolygon(pole, filteredPointList);
+ if (isPoleInside != null) {
+ // Legal pole
+ //System.out.println("Took "+counter+" iterations to find pole");
+ //System.out.println("Pole = "+pole+"; isInside="+isPoleInside+"; pointList = "+pointList);
+ return generateGeoPolygon(planetModel, filteredPointList, holes, pole, isPoleInside);
+ }
+ // If pole choice was illegal, try another one
+ }
+ throw new IllegalArgumentException("cannot find a point that is inside the polygon "+filteredPointList);
+ } catch (TileException e) {
+ // Couldn't tile the polygon; use GeoComplexPolygon instead, if we can.
+ }
+ }
+ // Fallback: create large geo polygon, using complex polygon logic.
+ final List<PolygonDescription> pd = new ArrayList<>(1);
+ pd.add(description);
+ return makeLargeGeoPolygon(planetModel, pd);
+ }
+
+ /** Create a GeoPolygon using the specified points and holes, using order to determine
+ * siding of the polygon. Much like ESRI, this method uses clockwise to indicate the space
+ * on the same side of the shape as being inside, and counter-clockwise to indicate the
+ * space on the opposite side as being inside.
+ * @param pointList is a list of the GeoPoints to build an arbitrary polygon out of. If points go
+ * clockwise from a given pole, then that pole should be within the polygon. If points go
+ * counter-clockwise, then that pole should be outside the polygon.
+ * @return a GeoPolygon corresponding to what was specified.
+ */
+ public static GeoPolygon makeGeoPolygon(final PlanetModel planetModel,
+ final List<GeoPoint> pointList) {
+ return makeGeoPolygon(planetModel, pointList, null);
+ }
+
+ /** Create a GeoPolygon using the specified points and holes, using order to determine
+ * siding of the polygon. Much like ESRI, this method uses clockwise to indicate the space
+ * on the same side of the shape as being inside, and counter-clockwise to indicate the
+ * space on the opposite side as being inside.
+ * @param pointList is a list of the GeoPoints to build an arbitrary polygon out of. If points go
+ * clockwise from a given pole, then that pole should be within the polygon. If points go
+ * counter-clockwise, then that pole should be outside the polygon.
+ * @param holes is a list of polygons representing "holes" in the outside polygon. Holes describe the area outside
+ * each hole as being "in set". Null == none.
+ * @return a GeoPolygon corresponding to what was specified, or null if a valid polygon cannot be generated
+ * from this input.
+ */
+ public static GeoPolygon makeGeoPolygon(final PlanetModel planetModel,
+ final List<GeoPoint> pointList,
+ final List<GeoPolygon> holes) {
+ return makeGeoPolygon(planetModel, pointList, holes, 0.0);
+ }
+
/** Create a GeoPolygon using the specified points and holes, using order to determine
* siding of the polygon. Much like ESRI, this method uses clockwise to indicate the space
* on the same side of the shape as being inside, and counter-clockwise to indicate the
@@ -220,32 +347,6 @@ public class GeoPolygonFactory {
return planetModel.createSurfacePoint(x, y, z);
}
- /** Use this class to specify a polygon with associated holes.
- */
- public static class PolygonDescription {
- /** The list of points */
- public final List<? extends GeoPoint> points;
- /** The list of holes */
- public final List<? extends PolygonDescription> holes;
-
- /** Instantiate the polygon description.
- * @param points is the list of points.
- */
- public PolygonDescription(final List<? extends GeoPoint> points) {
- this(points, new ArrayList<>());
- }
-
- /** Instantiate the polygon description.
- * @param points is the list of points.
- * @param holes is the list of holes.
- */
- public PolygonDescription(final List<? extends GeoPoint> points, final List<? extends PolygonDescription> holes) {
- this.points = points;
- this.holes = holes;
- }
-
- }
-
/** Create a large GeoPolygon. This is one which has more than 100 sides and/or may have resolution problems
* with very closely spaced points, which often occurs when the polygon was constructed to approximate curves. No tiling
* is done, and intersections and membership are optimized for having large numbers of sides.
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/a13befe7/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 fdc9c6d..9d2aa1e 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
@@ -121,7 +121,8 @@ public class GeoPolygonTest {
points.add(new GeoPoint(PlanetModel.SPHERE, 0.1, -0.5));
points.add(new GeoPoint(PlanetModel.SPHERE, 0.0, -0.4));
- c = GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, points);
+ GeoPolygonFactory.PolygonDescription pd = new GeoPolygonFactory.PolygonDescription(points);
+ c = GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, pd);
//System.out.println(c);
// Middle point should NOT be within!!
@@ -129,7 +130,7 @@ public class GeoPolygonTest {
assertTrue(!c.isWithin(gp));
shapes = new ArrayList<>();
- shapes.add(new GeoPolygonFactory.PolygonDescription(points));
+ shapes.add(pd);
c = GeoPolygonFactory.makeLargeGeoPolygon(PlanetModel.SPHERE, shapes);
assertTrue(!c.isWithin(gp));
@@ -141,7 +142,8 @@ public class GeoPolygonTest {
points.add(new GeoPoint(PlanetModel.SPHERE, 0.0, -0.6));
points.add(new GeoPoint(PlanetModel.SPHERE, -0.1, -0.5));
- c = GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, points);
+ pd = new GeoPolygonFactory.PolygonDescription(points);
+ c = GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, pd);
//System.out.println(c);
// Middle point should be within!!
@@ -149,7 +151,7 @@ public class GeoPolygonTest {
assertTrue(c.isWithin(gp));
shapes = new ArrayList<>();
- shapes.add(new GeoPolygonFactory.PolygonDescription(points));
+ shapes.add(pd);
c = GeoPolygonFactory.makeLargeGeoPolygon(PlanetModel.SPHERE, shapes);
assertTrue(c.isWithin(gp));
@@ -170,7 +172,9 @@ public class GeoPolygonTest {
points.add(new GeoPoint(PlanetModel.SPHERE, 0.0, -0.6));
points.add(new GeoPoint(PlanetModel.SPHERE, -0.1, -0.5));
- c = GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, points);
+ GeoPolygonFactory.PolygonDescription pd = new GeoPolygonFactory.PolygonDescription(points);
+
+ c = GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, pd);
xyzBounds = new XYZBounds();
c.getBounds(xyzBounds);
@@ -180,7 +184,7 @@ public class GeoPolygonTest {
assertEquals(GeoArea.DISJOINT, xyzSolid.getRelationship(c));
shapes = new ArrayList<>();
- shapes.add(new GeoPolygonFactory.PolygonDescription(points));
+ shapes.add(pd);
c = GeoPolygonFactory.makeLargeGeoPolygon(PlanetModel.SPHERE, shapes);
@@ -242,9 +246,10 @@ public class GeoPolygonTest {
gp = new GeoPoint(PlanetModel.SPHERE, 0.0, Math.PI);
assertFalse(c.isWithin(gp));
+ GeoPolygonFactory.PolygonDescription pd = new GeoPolygonFactory.PolygonDescription(points);
// Now, same thing for large polygon
shapes = new ArrayList<>();
- shapes.add(new GeoPolygonFactory.PolygonDescription(points));
+ shapes.add(pd);
c = GeoPolygonFactory.makeLargeGeoPolygon(PlanetModel.SPHERE, shapes);
@@ -286,7 +291,8 @@ public class GeoPolygonTest {
points.add(new GeoPoint(PlanetModel.SPHERE, -0.1, -0.7));
points.add(new GeoPoint(PlanetModel.SPHERE, -0.01, -0.6));
points.add(new GeoPoint(PlanetModel.SPHERE, -0.1, -0.5));
-
+
+ pd = new GeoPolygonFactory.PolygonDescription(points);
/*
System.out.println("Points: ");
for (GeoPoint p : points) {
@@ -294,7 +300,7 @@ public class GeoPolygonTest {
}
*/
- c = GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, points);
+ c = GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, pd);
// Sample some points within
gp = new GeoPoint(PlanetModel.SPHERE, 0.0, -0.5);
assertTrue(c.isWithin(gp));
@@ -325,7 +331,7 @@ public class GeoPolygonTest {
// Now, same thing for large polygon
shapes = new ArrayList<>();
- shapes.add(new GeoPolygonFactory.PolygonDescription(points));
+ shapes.add(pd);
c = GeoPolygonFactory.makeLargeGeoPolygon(PlanetModel.SPHERE, shapes);
// Sample some points within
@@ -996,7 +1002,7 @@ shape:
}
@Test
- public void testConcavePolygonWithHole() {
+ public void testPolygonWithHole() {
ArrayList<GeoPoint> points = new ArrayList<>();
points.add(new GeoPoint(PlanetModel.SPHERE, -1.1, -1.5));
points.add(new GeoPoint(PlanetModel.SPHERE, 1.0, -1.6));
@@ -1007,11 +1013,36 @@ shape:
hole_points.add(new GeoPoint(PlanetModel.SPHERE, 0.0, -0.6));
hole_points.add(new GeoPoint(PlanetModel.SPHERE, 0.1, -0.5));
hole_points.add(new GeoPoint(PlanetModel.SPHERE, 0.0, -0.4));
- GeoPolygon hole = GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE,hole_points);
+
+ GeoPolygonFactory.PolygonDescription holeDescription = new GeoPolygonFactory.PolygonDescription(hole_points);
+ List<GeoPolygonFactory.PolygonDescription> holes = new ArrayList<>(1);
+ holes.add(holeDescription);
+ GeoPolygonFactory.PolygonDescription polygonDescription = new GeoPolygonFactory.PolygonDescription(points, holes);
+
+ // Create two polygons -- one simple, the other complex. Both have holes. Compare their behavior.
+ GeoPolygon holeSimplePolygon = GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE,polygonDescription);
+ List<GeoPolygonFactory.PolygonDescription> polys = new ArrayList<>(1);
+ polys.add(polygonDescription);
+ GeoPolygon holeComplexPolygon = GeoPolygonFactory.makeLargeGeoPolygon(PlanetModel.SPHERE,polys);
+
+ // Sample some nearby points outside
+ GeoPoint gp;
+ gp = new GeoPoint(PlanetModel.SPHERE, 0.0, -0.65);
+ assertEquals(holeSimplePolygon.isWithin(gp), holeComplexPolygon.isWithin(gp));
+ gp = new GeoPoint(PlanetModel.SPHERE, 0.0, -0.35);
+ assertEquals(holeSimplePolygon.isWithin(gp), holeComplexPolygon.isWithin(gp));
+ gp = new GeoPoint(PlanetModel.SPHERE, -0.15, -0.5);
+ assertEquals(holeSimplePolygon.isWithin(gp), holeComplexPolygon.isWithin(gp));
+ gp = new GeoPoint(PlanetModel.SPHERE, 0.15, -0.5);
+ assertEquals(holeSimplePolygon.isWithin(gp), holeComplexPolygon.isWithin(gp));
+ // Random points outside
+ gp = new GeoPoint(PlanetModel.SPHERE, 0.0, 0.0);
+ assertEquals(holeSimplePolygon.isWithin(gp), holeComplexPolygon.isWithin(gp));
+ gp = new GeoPoint(PlanetModel.SPHERE, Math.PI * 0.5, 0.0);
+ assertEquals(holeSimplePolygon.isWithin(gp), holeComplexPolygon.isWithin(gp));
+ gp = new GeoPoint(PlanetModel.SPHERE, 0.0, Math.PI);
+ assertEquals(holeSimplePolygon.isWithin(gp), holeComplexPolygon.isWithin(gp));
- GeoPolygon polygon = ((GeoCompositePolygon)GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, points,Collections.singletonList(hole))).getShape(0);
- GeoPolygon polygon2 = GeoPolygonFactory.makeGeoConcavePolygon(PlanetModel.SPHERE,points,Collections.singletonList(hole));
- assertEquals(polygon,polygon2);
}
@Test