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/04/17 14:15:15 UTC
[2/2] lucene-solr:branch_6x: LUCENE-7226: Clean polygon data,
where feasible.
LUCENE-7226: Clean polygon data, where feasible.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/6f960ca4
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/6f960ca4
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/6f960ca4
Branch: refs/heads/branch_6x
Commit: 6f960ca4aa25d331484da3ee9b7f42a24b61ce67
Parents: 4abba2d
Author: Karl Wright <Da...@gmail.com>
Authored: Sun Apr 17 08:12:51 2016 -0400
Committer: Karl Wright <Da...@gmail.com>
Committed: Sun Apr 17 08:12:51 2016 -0400
----------------------------------------------------------------------
.../spatial3d/geom/GeoPolygonFactory.java | 105 ++++++++++++++++++-
.../apache/lucene/spatial3d/geom/Vector.java | 16 ++-
.../lucene/spatial3d/geom/GeoPolygonTest.java | 64 +++++++++++
3 files changed, 178 insertions(+), 7 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6f960ca4/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 6bf8766..f6c0803 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
@@ -139,24 +139,26 @@ public class GeoPolygonFactory {
final List<GeoPolygon> holes,
final GeoPoint testPoint,
final boolean testPointInside) {
+ // First, exercise a sanity filter on the provided pointList, and remove identical points, linear points, and backtracks
+ final List<GeoPoint> filteredPointList = filterPoints(pointList);
// We will be trying twice to find the right GeoPolygon, using alternate siding choices for the first polygon
// side. While this looks like it might be 2x as expensive as it could be, there's really no other choice I can
// find.
- final SidedPlane initialPlane = new SidedPlane(testPoint, pointList.get(0), pointList.get(1));
+ final SidedPlane initialPlane = new SidedPlane(testPoint, filteredPointList.get(0), filteredPointList.get(1));
// We don't know if this is the correct siding choice. We will only know as we build the complex polygon.
// So we need to be prepared to try both possibilities.
GeoCompositePolygon rval = new GeoCompositePolygon();
- if (buildPolygonShape(rval, planetModel, pointList, new BitSet(), 0, 1, initialPlane, holes, testPoint) == false) {
+ if (buildPolygonShape(rval, planetModel, filteredPointList, new BitSet(), 0, 1, initialPlane, holes, testPoint) == false) {
// The testPoint was within the shape. Was that intended?
if (testPointInside) {
// Yes: build it for real
rval = new GeoCompositePolygon();
- buildPolygonShape(rval, planetModel, pointList, new BitSet(), 0, 1, initialPlane, holes, null);
+ buildPolygonShape(rval, planetModel, filteredPointList, new BitSet(), 0, 1, initialPlane, holes, null);
return rval;
}
// No: do the complement and return that.
rval = new GeoCompositePolygon();
- buildPolygonShape(rval, planetModel, pointList, new BitSet(), 0, 1, new SidedPlane(initialPlane), holes, null);
+ buildPolygonShape(rval, planetModel, filteredPointList, new BitSet(), 0, 1, new SidedPlane(initialPlane), holes, null);
return rval;
} else {
// The testPoint was outside the shape. Was that intended?
@@ -166,11 +168,104 @@ public class GeoPolygonFactory {
}
// No: return the complement
rval = new GeoCompositePolygon();
- buildPolygonShape(rval, planetModel, pointList, new BitSet(), 0, 1, new SidedPlane(initialPlane), holes, null);
+ buildPolygonShape(rval, planetModel, filteredPointList, new BitSet(), 0, 1, new SidedPlane(initialPlane), holes, null);
return rval;
}
}
+ /** Filter duplicate points and coplanar points.
+ */
+ static List<GeoPoint> filterPoints(final List<GeoPoint> input) {
+
+ final List<GeoPoint> noIdenticalPoints = new ArrayList<>(input.size());
+
+ // Backtrack to find something different from the first point
+ int startIndex = -1;
+ final GeoPoint comparePoint = input.get(0);
+ for (int i = 0; i < input.size()-1; i++) {
+ final GeoPoint thePoint = input.get(getLegalIndex(- i - 1, input.size()));
+ if (!thePoint.isNumericallyIdentical(comparePoint)) {
+ startIndex = getLegalIndex(-i, input.size());
+ break;
+ }
+ }
+ if (startIndex == -1) {
+ throw new IllegalArgumentException("polygon is degenerate: all points are identical");
+ }
+
+ // Now we can start the process of walking around, removing duplicate points.
+ int currentIndex = startIndex;
+ while (true) {
+ final GeoPoint currentPoint = input.get(currentIndex);
+ noIdenticalPoints.add(currentPoint);
+ while (true) {
+ currentIndex = getLegalIndex(currentIndex + 1, input.size());
+ if (currentIndex == startIndex) {
+ break;
+ }
+ final GeoPoint nextNonIdenticalPoint = input.get(currentIndex);
+ if (!nextNonIdenticalPoint.isNumericallyIdentical(currentPoint)) {
+ break;
+ }
+ }
+ if (currentIndex == startIndex) {
+ break;
+ }
+ }
+
+ if (noIdenticalPoints.size() < 3) {
+ throw new IllegalArgumentException("polygon has fewer than three non-identical points");
+ }
+
+ // Next step: remove coplanar points and backtracks. For this, we use a strategy that is similar but we assess whether the points
+ // are on the same plane, taking the first and last points on the same plane only.
+
+ final List<GeoPoint> nonCoplanarPoints = new ArrayList<>(noIdenticalPoints.size());
+
+ int startPlaneIndex = -1;
+ final Plane comparePlane = new Plane(noIdenticalPoints.get(0), noIdenticalPoints.get(1));
+ for (int i = 0; i < noIdenticalPoints.size()-1; i++) {
+ final GeoPoint thePoint = noIdenticalPoints.get(getLegalIndex(- i - 1, noIdenticalPoints.size()));
+ if (!comparePlane.evaluateIsZero(thePoint)) {
+ startPlaneIndex = getLegalIndex(-i, noIdenticalPoints.size());
+ break;
+ }
+ }
+ if (startPlaneIndex == -1) {
+ throw new IllegalArgumentException("polygon is degenerate: all points are coplanar");
+ }
+
+ // Now we can start the process of walking around, removing duplicate points.
+ int currentPlaneIndex = startPlaneIndex;
+ while (true) {
+ final GeoPoint currentPoint = noIdenticalPoints.get(currentPlaneIndex);
+ nonCoplanarPoints.add(currentPoint);
+ int nextPlaneIndex = getLegalIndex(currentPlaneIndex + 1, noIdenticalPoints.size());
+ if (nextPlaneIndex == startPlaneIndex) {
+ break;
+ }
+ final Plane testPlane = new Plane(currentPoint, noIdenticalPoints.get(nextPlaneIndex));
+ while (true) {
+ currentPlaneIndex = nextPlaneIndex;
+ if (currentPlaneIndex == startPlaneIndex) {
+ break;
+ }
+ // Check if the next point is off plane
+ nextPlaneIndex = getLegalIndex(currentPlaneIndex + 1, noIdenticalPoints.size());
+ final GeoPoint nextNonCoplanarPoint = noIdenticalPoints.get(nextPlaneIndex);
+ if (!testPlane.evaluateIsZero(nextNonCoplanarPoint)) {
+ // We will want to add the point at currentPlaneIndex to the list (last on of the series)
+ break;
+ }
+ }
+ if (currentPlaneIndex == startPlaneIndex) {
+ break;
+ }
+ }
+
+ return nonCoplanarPoints;
+ }
+
/** The maximum distance from the close point to the trial pole: 2 degrees */
private final static double MAX_POLE_DISTANCE = Math.PI * 2.0 / 180.0;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6f960ca4/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 3a1b233..3cf60c3 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
@@ -328,6 +328,18 @@ public class Vector {
return magnitude(x,y,z);
}
+ /**
+ * Compute whether two vectors are numerically identical.
+ * @param other is the other vector.
+ * @return true if they are numerically identical.
+ */
+ public boolean isNumericallyIdentical(final Vector other) {
+ final double thisX = y * other.z - z * other.y;
+ final double thisY = z * other.x - x * other.z;
+ final double thisZ = x * other.y - y * other.x;
+ return thisX * thisX + thisY * thisY + thisZ * thisZ < MINIMUM_RESOLUTION_SQUARED;
+ }
+
/** Compute the desired magnitude of a unit vector projected to a given
* planet model.
* @param planetModel is the planet model.
@@ -336,7 +348,7 @@ public class Vector {
* @param z is the unit vector z value.
* @return a magnitude value for that (x,y,z) that projects the vector onto the specified ellipsoid.
*/
- protected static double computeDesiredEllipsoidMagnitude(final PlanetModel planetModel, final double x, final double y, final double z) {
+ static double computeDesiredEllipsoidMagnitude(final PlanetModel planetModel, final double x, final double y, final double z) {
return 1.0 / Math.sqrt(x*x*planetModel.inverseAbSquared + y*y*planetModel.inverseAbSquared + z*z*planetModel.inverseCSquared);
}
@@ -346,7 +358,7 @@ public class Vector {
* @param z is the unit vector z value.
* @return a magnitude value for that z value that projects the vector onto the specified ellipsoid.
*/
- protected static double computeDesiredEllipsoidMagnitude(final PlanetModel planetModel, final double z) {
+ static double computeDesiredEllipsoidMagnitude(final PlanetModel planetModel, final double z) {
return 1.0 / Math.sqrt((1.0-z*z)*planetModel.inverseAbSquared + z*z*planetModel.inverseCSquared);
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/6f960ca4/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 e721299..5bb7a11 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
@@ -30,6 +30,70 @@ import static org.junit.Assert.assertTrue;
public class GeoPolygonTest {
@Test
+ public void testPolygonPointFiltering() {
+ final GeoPoint point1 = new GeoPoint(PlanetModel.WGS84, 1.0, 2.0);
+ final GeoPoint point2 = new GeoPoint(PlanetModel.WGS84, 0.5, 2.5);
+ final GeoPoint point3 = new GeoPoint(PlanetModel.WGS84, 0.0, 0.0);
+ final GeoPoint point4 = new GeoPoint(PlanetModel.WGS84, Math.PI * 0.5, 0.0);
+ final GeoPoint point5 = new GeoPoint(PlanetModel.WGS84, 1.0, 0.0);
+
+ // First: duplicate points in the middle
+ {
+ final List<GeoPoint> originalPoints = new ArrayList<>();
+ originalPoints.add(point1);
+ originalPoints.add(point2);
+ originalPoints.add(point2);
+ originalPoints.add(point3);
+ final List<GeoPoint> filteredPoints =GeoPolygonFactory.filterPoints(originalPoints);
+ assertEquals(3, filteredPoints.size());
+ assertEquals(point1, filteredPoints.get(0));
+ assertEquals(point2, filteredPoints.get(1));
+ assertEquals(point3, filteredPoints.get(2));
+ }
+ // Next, duplicate points at the beginning
+ {
+ final List<GeoPoint> originalPoints = new ArrayList<>();
+ originalPoints.add(point2);
+ originalPoints.add(point1);
+ originalPoints.add(point3);
+ originalPoints.add(point2);
+ final List<GeoPoint> filteredPoints =GeoPolygonFactory.filterPoints(originalPoints);
+ assertEquals(3, filteredPoints.size());
+ assertEquals(point2, filteredPoints.get(0));
+ assertEquals(point1, filteredPoints.get(1));
+ assertEquals(point3, filteredPoints.get(2));
+ }
+
+ // Coplanar point removal
+ {
+ final List<GeoPoint> originalPoints = new ArrayList<>();
+ originalPoints.add(point1);
+ originalPoints.add(point3);
+ originalPoints.add(point4);
+ originalPoints.add(point5);
+ final List<GeoPoint> filteredPoints =GeoPolygonFactory.filterPoints(originalPoints);
+ assertEquals(3, filteredPoints.size());
+ assertEquals(point1, filteredPoints.get(0));
+ assertEquals(point3, filteredPoints.get(1));
+ assertEquals(point5, filteredPoints.get(2));
+ }
+ // Over the boundary
+ {
+ final List<GeoPoint> originalPoints = new ArrayList<>();
+ originalPoints.add(point5);
+ originalPoints.add(point1);
+ originalPoints.add(point3);
+ originalPoints.add(point4);
+ final List<GeoPoint> filteredPoints =GeoPolygonFactory.filterPoints(originalPoints);
+ assertEquals(3, filteredPoints.size());
+ assertEquals(point5, filteredPoints.get(0));
+ assertEquals(point1, filteredPoints.get(1));
+ assertEquals(point3, filteredPoints.get(2));
+ }
+
+ }
+
+ @Test
public void testPolygonClockwise() {
GeoPolygon c;
GeoPoint gp;