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/02/10 12:55:20 UTC
lucene-solr:branch_7x: LUCENE-8157: Do a better job of handling
coplanar points in polygon construction. Thanks to Ignacio Vera for his help
on this code.
Repository: lucene-solr
Updated Branches:
refs/heads/branch_7x 09de0da79 -> 98337f9af
LUCENE-8157: Do a better job of handling coplanar points in polygon construction. Thanks to Ignacio Vera for his help on this code.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/98337f9a
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/98337f9a
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/98337f9a
Branch: refs/heads/branch_7x
Commit: 98337f9af5075cc60ddcdd0e1751e9c7ab7d8895
Parents: 09de0da
Author: Karl Wright <Da...@gmail.com>
Authored: Sat Feb 10 07:53:36 2018 -0500
Committer: Karl Wright <Da...@gmail.com>
Committed: Sat Feb 10 07:55:11 2018 -0500
----------------------------------------------------------------------
.../spatial3d/geom/GeoPolygonFactory.java | 60 ++++------------
.../org/apache/lucene/spatial3d/geom/Plane.java | 15 ++++
.../apache/lucene/spatial3d/geom/Vector.java | 73 ++++++++++++++++++++
.../spatial3d/geom/RandomGeoPolygonTest.java | 71 +++++++++++++++++++
4 files changed, 174 insertions(+), 45 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/98337f9a/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 5de93fe..8105b80 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
@@ -494,8 +494,7 @@ public class GeoPolygonFactory {
//all coplanar
return null;
}
- Plane nextPlane = new Plane(startPoint, nextPoint);
- if (Math.abs(nextPlane.evaluate(endPoint)) > Vector.MINIMUM_RESOLUTION + leniencyValue) {
+ if (!Plane.arePointsCoplanar(startPoint, endPoint, nextPoint)) {
//no coplanar.
break;
}
@@ -521,7 +520,6 @@ public class GeoPolygonFactory {
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.
@@ -1079,12 +1077,19 @@ public class GeoPolygonFactory {
break;
}
final Edge newLastEdge = edgeBuffer.getNext(lastEdge);
+ if (Plane.arePointsCoplanar(lastEdge.startPoint, lastEdge.endPoint, newLastEdge.endPoint)) {
+ break;
+ }
if (isWithin(newLastEdge.endPoint, includedEdges)) {
//System.out.println(" maybe can extend to next edge");
// Found a candidate for extension. But do some other checks first. Basically, we need to know if we construct a polygon
// here will overlap with other remaining points?
final SidedPlane returnBoundary;
if (firstEdge.startPoint != newLastEdge.endPoint) {
+ if (Plane.arePointsCoplanar(firstEdge.endPoint, firstEdge.startPoint, newLastEdge.endPoint) ||
+ Plane.arePointsCoplanar(firstEdge.startPoint, newLastEdge.endPoint, newLastEdge.startPoint)) {
+ break;
+ }
returnBoundary = new SidedPlane(firstEdge.endPoint, firstEdge.startPoint, newLastEdge.endPoint);
} else {
returnBoundary = null;
@@ -1135,12 +1140,19 @@ public class GeoPolygonFactory {
break;
}
final Edge newFirstEdge = edgeBuffer.getPrevious(firstEdge);
+ if (Plane.arePointsCoplanar(newFirstEdge.startPoint, newFirstEdge.endPoint, firstEdge.endPoint)) {
+ break;
+ }
if (isWithin(newFirstEdge.startPoint, includedEdges)) {
//System.out.println(" maybe can extend to previous edge");
// Found a candidate for extension. But do some other checks first. Basically, we need to know if we construct a polygon
// here will overlap with other remaining points?
final SidedPlane returnBoundary;
if (newFirstEdge.startPoint != lastEdge.endPoint) {
+ if(Plane.arePointsCoplanar(lastEdge.startPoint, lastEdge.endPoint, newFirstEdge.startPoint) ||
+ Plane.arePointsCoplanar(lastEdge.endPoint, newFirstEdge.startPoint, newFirstEdge.endPoint)) {
+ break;
+ }
returnBoundary = new SidedPlane(lastEdge.startPoint, lastEdge.endPoint, newFirstEdge.startPoint);
} else {
returnBoundary = null;
@@ -1225,27 +1237,6 @@ public class GeoPolygonFactory {
edge = edgeBuffer.getNext(edge);
}
returnIsInternal = lastEdge.isInternal;
-
- // Look for coplanarity; abort if so
- for (int i = 0; i < points.size(); i++) {
- final GeoPoint start = points.get(i);
- final GeoPoint end = points.get(getLegalIndex(i + 1, points.size()));
- // We have to find the next point that is not on the plane between start and end.
- // If there is no such point, it's an error.
- final Plane planeToFind = new Plane(start, end);
- int endPointIndex = -1;
- for (int j = 0; j < points.size(); j++) {
- final int index = getLegalIndex(j + i + 2, points.size());
- if (!planeToFind.evaluateIsZero(points.get(index))) {
- endPointIndex = index;
- break;
- }
- }
- if (endPointIndex == -1) {
- return false;
- }
- }
-
edgeBuffer.clear();
} else {
// Build the return edge (internal, of course)
@@ -1270,27 +1261,6 @@ public class GeoPolygonFactory {
}
edge = edgeBuffer.getNext(edge);
}
-
- // Look for coplanarity; abort if so
- for (int i = 0; i < points.size(); i++) {
- final GeoPoint start = points.get(i);
- final GeoPoint end = points.get(getLegalIndex(i + 1, points.size()));
- // We have to find the next point that is not on the plane between start and end.
- // If there is no such point, it's an error.
- final Plane planeToFind = new Plane(start, end);
- int endPointIndex = -1;
- for (int j = 0; j < points.size(); j++) {
- final int index = getLegalIndex(j + i + 2, points.size());
- if (!planeToFind.evaluateIsZero(points.get(index))) {
- endPointIndex = index;
- break;
- }
- }
- if (endPointIndex == -1) {
- return false;
- }
- }
-
// Modify the edge buffer
edgeBuffer.replace(edges, returnEdge);
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/98337f9a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Plane.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Plane.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Plane.java
index c72c8c6..e40fb27 100755
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Plane.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Plane.java
@@ -666,6 +666,21 @@ public class Plane extends Vector {
}
return findCrossings(planetModel, q, bounds, NO_BOUNDS);
}
+
+ /**
+ * Checks if three points are coplanar in any of the three planes they can describe.
+ * The planes are all assumed to go through the origin.
+ *
+ * @param A The first point.
+ * @param B The second point.
+ * @param C The third point
+ * @return true if provided points are coplanar in any of the three planes they can describe.
+ */
+ public static boolean arePointsCoplanar(final GeoPoint A, final GeoPoint B, final GeoPoint C) {
+ return Vector.crossProductEvaluateIsZero(A, B, C) ||
+ Vector.crossProductEvaluateIsZero(A, C, B) ||
+ Vector.crossProductEvaluateIsZero(B, C, A);
+ }
/**
* Find the intersection points between two planes, given a set of bounds.
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/98337f9a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Vector.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Vector.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Vector.java
index 454439b..f901d29 100755
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Vector.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/Vector.java
@@ -181,6 +181,79 @@ public class Vector {
}
/**
+ * Evaluate the cross product of two vectors against a point.
+ * If the dot product of the resultant vector resolves to "zero", then
+ * return true.
+ * @param A is the first vector to use for the cross product.
+ * @param B is the second vector to use for the cross product.
+ * @param point is the point to evaluate.
+ * @return true if we get a zero dot product.
+ */
+ public static boolean crossProductEvaluateIsZero(final Vector A, final Vector B, final Vector point) {
+ // Include Gram-Schmidt in-line so we avoid creating objects unnecessarily
+ // Compute the naive perpendicular
+ final double thisX = A.y * B.z - A.z * B.y;
+ final double thisY = A.z * B.x - A.x * B.z;
+ final double thisZ = A.x * B.y - A.y * B.x;
+
+ final double magnitude = magnitude(thisX, thisY, thisZ);
+ if (magnitude < MINIMUM_RESOLUTION) {
+ return true;
+ }
+
+ final double inverseMagnitude = 1.0/magnitude;
+
+ double normalizeX = thisX * inverseMagnitude;
+ double normalizeY = thisY * inverseMagnitude;
+ double normalizeZ = thisZ * inverseMagnitude;
+ // For a plane to work, the dot product between the normal vector
+ // and the points needs to be less than the minimum resolution.
+ // This is sometimes not true for points that are very close. Therefore
+ // we need to adjust
+ int i = 0;
+ while (true) {
+ final double currentDotProdA = A.x * normalizeX + A.y * normalizeY + A.z * normalizeZ;
+ final double currentDotProdB = B.x * normalizeX + B.y * normalizeY + B.z * normalizeZ;
+ if (Math.abs(currentDotProdA) < MINIMUM_RESOLUTION && Math.abs(currentDotProdB) < MINIMUM_RESOLUTION) {
+ break;
+ }
+ // Converge on the one that has largest dot product
+ final double currentVectorX;
+ final double currentVectorY;
+ final double currentVectorZ;
+ final double currentDotProd;
+ if (Math.abs(currentDotProdA) > Math.abs(currentDotProdB)) {
+ currentVectorX = A.x;
+ currentVectorY = A.y;
+ currentVectorZ = A.z;
+ currentDotProd = currentDotProdA;
+ } else {
+ currentVectorX = B.x;
+ currentVectorY = B.y;
+ currentVectorZ = B.z;
+ currentDotProd = currentDotProdB;
+ }
+
+ // Adjust
+ normalizeX = normalizeX - currentDotProd * currentVectorX;
+ normalizeY = normalizeY - currentDotProd * currentVectorY;
+ normalizeZ = normalizeZ - currentDotProd * currentVectorZ;
+ // Normalize
+ final double correctedMagnitude = magnitude(normalizeX, normalizeY, normalizeZ);
+ final double inverseCorrectedMagnitude = 1.0 / correctedMagnitude;
+ normalizeX = normalizeX * inverseCorrectedMagnitude;
+ normalizeY = normalizeY * inverseCorrectedMagnitude;
+ normalizeZ = normalizeZ * inverseCorrectedMagnitude;
+ //This is probably not needed as the method seems to converge
+ //quite quickly. But it is safer to have a way out.
+ if (i++ > 10) {
+ throw new IllegalArgumentException("Plane could not be constructed! Could not find a normal vector.");
+ }
+ }
+ return Math.abs(normalizeX * point.x + normalizeY * point.y + normalizeZ * point.z) < MINIMUM_RESOLUTION;
+ }
+
+ /**
* Do a dot product.
*
* @param v is the vector to multiply.
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/98337f9a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/RandomGeoPolygonTest.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/RandomGeoPolygonTest.java b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/RandomGeoPolygonTest.java
new file mode 100644
index 0000000..b286fbb
--- /dev/null
+++ b/lucene/spatial3d/src/test/org/apache/lucene/spatial3d/geom/RandomGeoPolygonTest.java
@@ -0,0 +1,71 @@
+package org.apache.lucene.spatial3d.geom;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import com.carrotsearch.randomizedtesting.annotations.Repeat;
+import org.junit.Test;
+
+/**
+ * Random test for polygons.
+ */
+public class RandomGeoPolygonTest extends RandomGeo3dShapeGenerator {
+
+ @Test
+ @Repeat(iterations = 10)
+ public void testRandomLUCENE8157() {
+ final PlanetModel planetModel = randomPlanetModel();
+ final GeoPoint startPoint = randomGeoPoint(planetModel);
+ double d = random().nextDouble();
+ final double distanceSmall = d * 1e-9 + Vector.MINIMUM_ANGULAR_RESOLUTION;
+ final double distanceBig = d * 1e-7 + Vector.MINIMUM_ANGULAR_RESOLUTION ;
+ final double bearing = random().nextDouble() * Math.PI;
+ GeoPoint point1 = planetModel.surfacePointOnBearing(startPoint, distanceSmall, bearing*1.001);
+ GeoPoint point2 = planetModel.surfacePointOnBearing(startPoint, distanceBig, bearing);
+ GeoPoint point3 = planetModel.surfacePointOnBearing(startPoint, distanceBig, bearing - 0.5 * Math.PI);
+ List<GeoPoint> points = new ArrayList<>();
+ points.add(startPoint);
+ points.add(point1);
+ points.add(point2);
+ points.add(point3);
+ try {
+ GeoPolygon polygon = GeoPolygonFactory.makeGeoPolygon(planetModel, points);
+ assertTrue(polygon != null);
+ }
+ catch(Exception e) {
+ fail(points.toString());
+ }
+ }
+
+ public void testLUCENE8157() {
+ GeoPoint point1 = new GeoPoint(PlanetModel.SPHERE, 0.281855362988772, -0.7816673189809037);
+ GeoPoint point2 = new GeoPoint(PlanetModel.SPHERE, 0.28185536309057774, -0.7816673188511931);
+ GeoPoint point3 = new GeoPoint(PlanetModel.SPHERE, 0.28186535556824205, -0.7816546103463846);
+ GeoPoint point4 = new GeoPoint(PlanetModel.SPHERE, 0.28186757010406716, -0.7816777221140381);
+ List<GeoPoint> points = new ArrayList<>();
+ points.add(point1);
+ points.add(point2);
+ points.add(point3);
+ points.add(point4);
+ try {
+ GeoPolygon polygon = GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, points);
+ }
+ catch(Exception e) {
+ fail(points.toString());
+ }
+ }
+
+ @Test
+ public void testCoplanarityTilePolygon() {
+ //POLYGON((-90.55764 -0.34907,-90.55751 -0.34868,-90.55777 -0.34842,-90.55815 -0.34766,-90.55943 -0.34842, -90.55918 -0.34842,-90.55764 -0.34907))
+ List<GeoPoint> points = new ArrayList<>();
+ points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-0.34907), Geo3DUtil.fromDegrees(-90.55764)));
+ points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-0.34868), Geo3DUtil.fromDegrees(-90.55751)));
+ points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-0.34842), Geo3DUtil.fromDegrees(-90.55777)));
+ points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-0.34766), Geo3DUtil.fromDegrees(-90.55815)));
+ points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-0.34842), Geo3DUtil.fromDegrees(-90.55943)));
+ points.add(new GeoPoint(PlanetModel.SPHERE, Geo3DUtil.fromDegrees(-0.34842), Geo3DUtil.fromDegrees(-90.55918)));
+ GeoCompositePolygon polygon = (GeoCompositePolygon)GeoPolygonFactory.makeGeoPolygon(PlanetModel.SPHERE, points);
+ assertTrue(polygon.size() == 3);
+ }
+}