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/01/31 13:22:57 UTC
lucene-solr:branch_7x: LUCENE-8141: Do a better job of making sure
polygon points are not coplanar. Committed on behalf of Ignacio Vera.
Repository: lucene-solr
Updated Branches:
refs/heads/branch_7x 32ca9cf4d -> 505f7b9d5
LUCENE-8141: Do a better job of making sure polygon points are not coplanar. Committed on behalf of Ignacio Vera.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/505f7b9d
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/505f7b9d
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/505f7b9d
Branch: refs/heads/branch_7x
Commit: 505f7b9d56abed389f20d97a16bc5462603b95a3
Parents: 32ca9cf
Author: Karl Wright <Da...@gmail.com>
Authored: Wed Jan 31 08:20:58 2018 -0500
Committer: Karl Wright <Da...@gmail.com>
Committed: Wed Jan 31 08:22:50 2018 -0500
----------------------------------------------------------------------
.../spatial3d/geom/GeoPolygonFactory.java | 209 ++++++-------------
.../lucene/spatial3d/geom/GeoPolygonTest.java | 30 ++-
2 files changed, 95 insertions(+), 144 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/505f7b9d/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 d272c86..5de93fe 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
@@ -18,6 +18,7 @@ package org.apache.lucene.spatial3d.geom;
import java.util.ArrayList;
import java.util.BitSet;
+import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.Iterator;
@@ -443,18 +444,13 @@ public class GeoPolygonFactory {
*/
static List<GeoPoint> filterEdges(final List<GeoPoint> noIdenticalPoints, final double leniencyValue) {
- // Now, do the depth-first search needed to find a path that has no coplanarities in it.
- // This is, unfortunately, not easy, because coplanarity is not transitive as you walk around the polygon.
- // If point C is not coplanar with edge A-B, there is no guarantee that A is not coplanar with B-C.
- // But we have to produce a polygon that is safe no matter which way it is looked at.
- // The approach I'm taking therefore is to do a depth-first search until we find a valid polygon.
- // This algorithmically awful in the worst case, but luckily we can presume that real-life data
- // does not require more than a couple of iterations.
+ // Now, do the search needed to find a path that has no coplanarities in it.
+ // It is important to check coplanarities using the points that are further away so the
+ // plane is more precise.
for (int i = 0; i < noIdenticalPoints.size(); i++) {
- final SafePath startPath = new SafePath(null, noIdenticalPoints.get(i), i, null);
- // Search, with this as the start path.
- final SafePath resultPath = findSafePath(startPath, noIdenticalPoints, getLegalIndex(i+1, noIdenticalPoints.size()), i, leniencyValue);
+ //Search starting for current index.
+ final SafePath resultPath = findSafePath(noIdenticalPoints, i, leniencyValue);
if (resultPath != null && resultPath.previous != null) {
// Read out result, maintaining ordering
final List<GeoPoint> rval = new ArrayList<>(noIdenticalPoints.size());
@@ -465,134 +461,67 @@ public class GeoPolygonFactory {
// No path found. This means that everything was coplanar.
return null;
}
-
- /** Recursive depth-first path search. In order to find a valid path, we must consider all possible legal extensions of
- * the current path. We discard any path that produces illegalities (meaning anything that would allow any coplanarity
- * to continue to exist no matter from which direction one looks at it), and take the first legal path we find.
- * @param currentPath is the current path (not null).
- * @param points is the raw list of points under consideration.
- * @param pointIndex is the index of the point that represents the next possible point for consideration for path
- * extension.
- * @param startPointIndex is index of the point that starts the current path, so that we can know when we are done.
- * @param leniencyValue is the maximum allowed distance of a point being skipped from the revised polygon. Pass zero if
- * no leniency desired.
- * @return null if there was no safe path found, or the safe path if one was discovered.
+
+ /** Iterative path search through ordered list of points. The method merges together
+ * all consecutive coplanar points and builds the plane using the first and the last point.
+ * It does not converge if the starting point is coplanar with the last and next point of the path.
+ *
+ * @param points is the ordered raw list of points under consideration.
+ * @param startIndex is index of the point that starts the current path, so that we can know when we are done.
+ * @param leniencyValue is the allowed distance of a point from the plane to be considered coplanar.
+ * @return null if the starting point is coplanar with the last and next point of the path.
*/
- private static SafePath findSafePath(final SafePath currentPath, final List<GeoPoint> points, final int pointIndex,
- final int startPointIndex, final double leniencyValue) {
- //System.err.println("extending path...");
-
- // Loop across all possible path extensions, and consider each in turn
- int considerPointIndex = pointIndex;
- while (true) {
- // Check if the extension of currentPath to considerPointIndex is workable
- final GeoPoint considerStartPoint = currentPath.lastPoint;
- final GeoPoint considerEndPoint = points.get(considerPointIndex);
- final int nextPointIndex = getLegalIndex(considerPointIndex + 1, points.size());
- if (!considerStartPoint.isNumericallyIdentical(considerEndPoint)) {
- // Create a plane including these two
- final Plane considerPlane = new Plane(considerStartPoint, considerEndPoint);
-
- boolean isChoiceLegal = true;
+ private static SafePath findSafePath(final List<GeoPoint> points, final int startIndex, final double leniencyValue) {
+ SafePath safePath = null;
+ for (int i = startIndex; i < startIndex + points.size(); i++) {
+ //get start point, always the same for an iteration
+ final int startPointIndex = getLegalIndex(i -1, points.size());
+ final GeoPoint startPoint = points.get(startPointIndex);
+ //get end point, can be coplanar and therefore change
+ int endPointIndex = getLegalIndex(i, points.size());
+ GeoPoint endPoint = points.get(endPointIndex);
- //System.err.println(" considering "+considerStartPoint+" to "+considerEndPoint);
- if (isChoiceLegal) {
- // Consider the previous plane/point
- if (currentPath.lastPlane != null) {
- if (currentPath.lastPlane.evaluateIsZero(considerEndPoint)) {
- //System.err.println(" coplanar with last plane");
- // no good
- isChoiceLegal = false;
- } else if (considerPlane.evaluateIsZero(currentPath.previous.lastPoint)) {
- //System.err.println(" last point coplanar with this plane");
- isChoiceLegal = false;
- } else {
- // To guarantee that no planes we build are coplanar with edge points, we need to verify everything back from
- // considerEndPoint back to the start of the path. We build the edge from considerEndPoint back to each
- // of the SafePath points already determined. Then, we need to look at all triangles that include that edge and
- // the SafePath points in between. If all of those triangles are legal, we can be assured that adding the current
- // proposed point is safe to do.
- // This is, of course, a lot of work -- specifically, it's O(n^2) for each point in the path, which leads to an O(n^3)
- // evaluation time overall!!
- // The only alternative is to understand the cases under which these triangles would be introduced, and tailor the
- // cleaning to catch those cases only. Still need to figure that out. The case that blows up is when *all* the points
- // for a triangle are coplanar, so theoretically we don't even need to generate the triangle at all(!)
- //
- // Build a plane that represents the third edge in this triangle, to guarantee that we can compose
- // the polygon from triangles
- final Plane thirdPlane = new Plane(currentPath.previous.lastPoint, considerEndPoint);
- if (thirdPlane.evaluateIsZero(considerStartPoint)) {
- isChoiceLegal = false;
- }
- }
- }
- }
-
- if (isChoiceLegal && considerPointIndex == startPointIndex) {
- // Verify that the first plane (already recorded) works together with the last plane
- final SafePath firstPlaneEndpoint = currentPath.findFirstEndpoint();
- if (firstPlaneEndpoint == null) {
- //System.err.println(" path not long enough");
- isChoiceLegal = false;
- } else {
- if (firstPlaneEndpoint.lastPlane.evaluateIsZero(considerStartPoint)) {
- //System.err.println(" last point is coplanar with start plane");
- isChoiceLegal = false;
- } else if (considerPlane.evaluateIsZero(firstPlaneEndpoint.lastPoint)) {
- //System.err.println(" first point is coplanar with last plane");
- isChoiceLegal = false;
- } else {
- // Build a plane that represents the third edge in this triangle, to guarantee that we can compose
- // the polygon from triangles
- final Plane thirdPlane = new Plane(considerStartPoint, firstPlaneEndpoint.lastPoint);
- if (thirdPlane.evaluateIsZero(considerEndPoint)) {
- isChoiceLegal = false;
- }
- }
- }
+ if (startPoint.isNumericallyIdentical(endPoint)) {
+ //go to next if identical
+ continue;
+ }
+ //Check if nextPoints are co-planar, if so advance to next point.
+ //if we go over the start index then we have no succeed.
+ while (true) {
+ int nextPointIndex = getLegalIndex(endPointIndex + 1, points.size());
+ final GeoPoint nextPoint = points.get(nextPointIndex);
+ if (startPoint.isNumericallyIdentical(nextPoint)) {
+ //all coplanar
+ return null;
}
-
- if (isChoiceLegal) {
- // All points between the start and end, if any, must be on the plane.
- int checkIndex = getLegalIndex(currentPath.lastPointIndex + 1, points.size());
- while (checkIndex != considerPointIndex) {
- if (Math.abs(considerPlane.evaluate(points.get(checkIndex))) >= Vector.MINIMUM_RESOLUTION + leniencyValue) {
- // This possibility is no good. But does it say anything about other possibilities? I think
- // it may mean we don't have to consider any further extensions. I can't prove this, but
- // it makes this algorithm complete in not an insane period of time at least...
- //System.err.println(" interior point not coplanar with trial plane");
- //isChoiceLegal = false;
- //break;
- return null;
- }
- checkIndex = getLegalIndex(checkIndex + 1, points.size());
- }
+ Plane nextPlane = new Plane(startPoint, nextPoint);
+ if (Math.abs(nextPlane.evaluate(endPoint)) > Vector.MINIMUM_RESOLUTION + leniencyValue) {
+ //no coplanar.
+ break;
}
-
- if (isChoiceLegal) {
- // Extend the path and call ourselves recursively.
- if (considerPointIndex == startPointIndex) {
- // Current path has been validated; return it
- return currentPath;
- }
- //System.err.println(" adding to path: "+considerEndPoint+"; "+considerPlane);
- final SafePath newPath = new SafePath(currentPath, considerEndPoint, considerPointIndex, considerPlane);
- final SafePath result = findSafePath(newPath, points, nextPointIndex, startPointIndex, leniencyValue);
- if (result != null) {
- return result;
- }
+ if (endPointIndex == startIndex) {
+ //we are over the path, we fail.
+ return null;
}
-
+ //advance
+ endPointIndex = nextPointIndex;
+ endPoint = nextPoint;
+ i++;
}
-
- if (considerPointIndex == startPointIndex) {
+
+ if (safePath != null && endPointIndex == startIndex) {
+ //We are already at the start, current point is coplanar with
+ //start point, no need to add this node.
break;
}
- considerPointIndex = nextPointIndex;
+ //Create node and move to next one
+ Plane currentPlane = new Plane(startPoint, endPoint);
+ safePath = new SafePath(safePath, endPoint, endPointIndex, currentPlane);
}
- return null;
+ return safePath;
}
-
+
+
/** Pick a random pole that has a good chance of being inside the polygon described by the points.
* @param generator is the random number generator to use.
* @param planetModel is the planet model to use.
@@ -1722,25 +1651,19 @@ public class GeoPolygonFactory {
this.lastPlane = lastPlane;
this.previous = previous;
}
-
- /** Find the first endpoint */
- public SafePath findFirstEndpoint() {
- if (previous == null) {
- return null;
- }
- if (previous.previous == null) {
- return this;
- }
- return previous.findFirstEndpoint();
- }
-
+
/** Fill in a list, in order, of safe points.
*/
public void fillInList(final List<GeoPoint> pointList) {
- if (previous != null) {
- previous.fillInList(pointList);
+ //we don't use recursion because it can be problematic
+ //for polygons with many points.
+ SafePath safePath = this;
+ while (safePath.previous != null) {
+ pointList.add(safePath.lastPoint);
+ safePath = safePath.previous;
}
- pointList.add(lastPoint);
+ pointList.add(safePath.lastPoint);
+ Collections.reverse(pointList);
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/505f7b9d/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 6291057..a17b57c 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
@@ -91,7 +91,22 @@ public class GeoPolygonTest {
}
}
-
+
+ @Test
+ public void testPolygonPointFiltering2() {
+ //all coplanar
+ GeoPoint point1 = new GeoPoint(PlanetModel.SPHERE, 1.1264101919629863, -0.9108307879480759);
+ GeoPoint point2 = new GeoPoint(PlanetModel.SPHERE, 1.1264147298190414, -0.9108309624810013);
+ GeoPoint point3 = new GeoPoint(PlanetModel.SPHERE, 1.1264056541069312, -0.9108306134151508);
+ final List<GeoPoint> originalPoints = new ArrayList<>();
+ originalPoints.add(point1);
+ originalPoints.add(point2);
+ originalPoints.add(point3);
+ final List<GeoPoint> filteredPoints = GeoPolygonFactory.filterEdges(GeoPolygonFactory.filterPoints(originalPoints), 0.0);
+ assertEquals(null, filteredPoints);
+ }
+
+
@Test
public void testPolygonClockwise() {
GeoPolygon c;
@@ -1050,5 +1065,18 @@ shape:
}
}
+ @Test
+ public void testLUCENE8140() throws Exception {
+ //POINT(15.426026 68.35078) is coplanar
+ //"POLYGON((15.426411 68.35069,15.4261 68.35078,15.426026 68.35078,15.425868 68.35078,15.425745 68.350746,15.426411 68.35069))";
+ List<GeoPoint> points = new ArrayList<>();
+ points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(68.35069), Geo3DUtil.fromDegrees(15.426411)));
+ points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(68.35078), Geo3DUtil.fromDegrees(15.4261)));
+ points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(68.35078), Geo3DUtil.fromDegrees(15.426026)));
+ points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(68.35078), Geo3DUtil.fromDegrees(15.425868)));
+ points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(68.350746), Geo3DUtil.fromDegrees(15.426411)));
+ assertTrue(GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, points) != null);
+ }
+
}