This is an automated email from the ASF dual-hosted git repository. erans pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/commons-geometry.git
commit 6b2951586a90b1405001c72462459b49d9ed17c9 Author: Matt Juntunen <matt.juntu...@hotmail.com> AuthorDate: Thu Jul 25 21:55:18 2019 -0400 GEOMETRY-59: adding Plane.fromPoints(Collection, DoublePrecisionContext) to help fix issues with computed Plane orientation --- .../commons/geometry/euclidean/threed/Plane.java | 100 ++++++- .../geometry/euclidean/threed/PolyhedronsSet.java | 20 +- .../geometry/euclidean/threed/PlaneTest.java | 286 ++++++++++++++++++++- .../euclidean/threed/PolyhedronsSetTest.java | 45 +++- 4 files changed, 436 insertions(+), 15 deletions(-) diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/Plane.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/Plane.java index f82ae52..0be47cd 100644 --- a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/Plane.java +++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/Plane.java @@ -16,8 +16,12 @@ */ package org.apache.commons.geometry.euclidean.threed; +import java.util.Arrays; +import java.util.Collection; +import java.util.Iterator; import java.util.Objects; +import org.apache.commons.geometry.core.exception.GeometryException; import org.apache.commons.geometry.core.exception.IllegalNormException; import org.apache.commons.geometry.core.partitioning.Embedding; import org.apache.commons.geometry.core.partitioning.Hyperplane; @@ -127,11 +131,103 @@ public final class Plane implements Hyperplane<Vector3D>, Embedding<Vector3D, Ve * @param p3 third point belonging to the plane * @param precision precision context used to compare floating point values * @return a new plane - * @throws IllegalNormException if the points do not constitute a plane + * @throws GeometryException if the points do not define a unique plane */ public static Plane fromPoints(final Vector3D p1, final Vector3D p2, final Vector3D p3, final DoublePrecisionContext precision) { - return Plane.fromPointAndPlaneVectors(p1, p1.vectorTo(p2), p1.vectorTo(p3), precision); + return Plane.fromPoints(Arrays.asList(p1, p2, p3), precision); + } + + /** Construct a plane from a collection of points lying on the plane. The plane orientation is + * determined by the overall orientation of the point sequence. For example, if the points wind + * around the z-axis in a counter-clockwise direction, then the plane normal will point up the + * +z axis. If the points wind in the opposite direction, then the plane normal will point down + * the -z axis. The {@code u} vector for the plane is set to the first non-zero vector between + * points in the sequence (ie, the first direction in the path). + * + * @param pts collection of sequenced points lying on the plane + * @param precision precision context used to compare floating point values + * @return a new plane containing the given points + * @throws IllegalArgumentException if the given collection does not contain at least 3 points + * @throws GeometryException if the points do not define a unique plane + */ + public static Plane fromPoints(final Collection<Vector3D> pts, final DoublePrecisionContext precision) { + + if (pts.size() < 3) { + throw new IllegalArgumentException("At least 3 points are required to define a plane; " + + "argument contains only " + pts.size() + "."); + } + + final Iterator<Vector3D> it = pts.iterator(); + + Vector3D startPt = it.next(); + + Vector3D u = null; + Vector3D w = null; + + Vector3D currentPt; + + Vector3D currentVector = null; + Vector3D prevVector = null; + + Vector3D cross = null; + double crossNorm; + double crossSumX = 0.0; + double crossSumY = 0.0; + double crossSumZ = 0.0; + + boolean nonPlanar = false; + + while (it.hasNext()) { + currentPt = it.next(); + currentVector = startPt.vectorTo(currentPt); + + if (!precision.eqZero(currentVector.norm())) { + + if (u == null) { + // save the first non-zero vector as our u vector + u = currentVector.normalize(); + } + if (prevVector != null) { + cross = prevVector.cross(currentVector); + + crossSumX += cross.getX(); + crossSumY += cross.getY(); + crossSumZ += cross.getZ(); + + crossNorm = cross.norm(); + + if (!precision.eqZero(crossNorm)) { + // the cross product has non-zero magnitude + if (w == null) { + // save the first non-zero cross product as our normal + w = cross.normalize(); + } + else if (!precision.eq(1.0, Math.abs(w.dot(cross) / crossNorm))) { + // if the normalized dot product is not either +1 or -1, then + // the points are not coplanar + nonPlanar = true; + break; + } + } + } + + prevVector = currentVector; + } + } + + if (u == null || w == null || nonPlanar) { + throw new GeometryException("Points do not define a plane: " + pts); + } + + if (w.dot(Vector3D.of(crossSumX, crossSumY, crossSumZ)) < 0) { + w = w.negate(); + } + + final Vector3D v = w.cross(u); + final double originOffset = -startPt.dot(w); + + return new Plane(u, v, w, originOffset, precision); } // This should be removed after GEOMETRY-32 is done. diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/PolyhedronsSet.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/PolyhedronsSet.java index 234f81d..995c9a9 100644 --- a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/PolyhedronsSet.java +++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/PolyhedronsSet.java @@ -214,26 +214,26 @@ public class PolyhedronsSet extends AbstractRegion<Vector3D, Vector2D> { } final List<SubHyperplane<Vector3D>> boundary = new ArrayList<>(); + final List<Vector3D> facetVertices = new ArrayList<>(); for (final int[] facet : facets) { - // define facet plane from the first 3 points - Plane plane = Plane.fromPoints(vertices.get(facet[0]), vertices.get(facet[1]), vertices.get(facet[2]), - precision); + for (int i=0; i<facet.length; ++i) { + facetVertices.add(vertices.get(facet[i])); + } + + Plane plane = Plane.fromPoints(facetVertices, precision); - // check all points are in the plane + // convert to subspace points final Vector2D[] two2Points = new Vector2D[facet.length]; - for (int i = 0 ; i < facet.length; ++i) { - final Vector3D v = vertices.get(facet[i]); - if (!plane.contains(v)) { - throw new IllegalArgumentException("Point " + v + " is out of plane"); - } - two2Points[i] = plane.toSubSpace(v); + for (int i=0 ; i<facet.length; ++i) { + two2Points[i] = plane.toSubSpace(facetVertices.get(i)); } // create the polygonal facet boundary.add(new SubPlane(plane, new PolygonsSet(precision, two2Points))); + facetVertices.clear(); } return boundary; diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/PlaneTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/PlaneTest.java index d250269..af76826 100644 --- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/PlaneTest.java +++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/PlaneTest.java @@ -16,9 +16,16 @@ */ package org.apache.commons.geometry.euclidean.threed; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.List; + +import org.apache.commons.geometry.core.GeometryTestUtils; +import org.apache.commons.geometry.core.exception.GeometryException; import org.apache.commons.geometry.core.exception.IllegalNormException; import org.apache.commons.geometry.core.precision.DoublePrecisionContext; import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext; +import org.apache.commons.geometry.euclidean.EuclideanTestUtils; import org.apache.commons.geometry.euclidean.threed.rotation.QuaternionRotation; import org.junit.Assert; import org.junit.Test; @@ -46,7 +53,7 @@ public class PlaneTest { Plane.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1), Vector3D.of(0, 0, 1), Vector3D.of(0, 0, -2), TEST_PRECISION); } - @Test(expected=IllegalNormException.class) + @Test(expected=GeometryException.class) public void testPointsDoNotConstituteAPlane() { Plane.fromPoints(Vector3D.of(0, 0, 1), Vector3D.of(0, 0, 1), Vector3D.of(0, 1, 0), TEST_PRECISION); } @@ -203,6 +210,246 @@ public class PlaneTest { } @Test + public void testFromPoints_collection_threePoints() { + // arrange + List<Vector3D> pts = Arrays.asList( + Vector3D.of(1, 1, 0), + Vector3D.of(1, 1, -1), + Vector3D.of(0, 1, 0) + ); + + // act + Plane plane = Plane.fromPoints(pts, TEST_PRECISION); + + // assert + checkPlane(plane, Vector3D.PLUS_Y, Vector3D.MINUS_Z, Vector3D.MINUS_X); + + Assert.assertTrue(plane.contains(pts.get(0))); + Assert.assertTrue(plane.contains(pts.get(1))); + Assert.assertTrue(plane.contains(pts.get(2))); + } + + @Test + public void testFromPoints_collection_someCollinearPoints() { + // arrange + List<Vector3D> pts = Arrays.asList( + Vector3D.of(1, 0, 2), + Vector3D.of(2, 0, 2), + Vector3D.of(3, 0, 2), + Vector3D.of(0, 1, 2) + ); + + // act + Plane plane = Plane.fromPoints(pts, TEST_PRECISION); + + // assert + checkPlane(plane, Vector3D.of(0, 0, 2), Vector3D.PLUS_X, Vector3D.PLUS_Y); + + Assert.assertTrue(plane.contains(pts.get(0))); + Assert.assertTrue(plane.contains(pts.get(1))); + Assert.assertTrue(plane.contains(pts.get(2))); + Assert.assertTrue(plane.contains(pts.get(3))); + } + + @Test + public void testFromPoints_collection_concaveWithCollinearAndDuplicatePoints() { + // arrange + List<Vector3D> pts = Arrays.asList( + Vector3D.of(1, 0, 1), + Vector3D.of(1, 0, 0.5), + + Vector3D.of(1, 0, 0), + Vector3D.of(1, 1, -1), + Vector3D.of(1, 2, 0), + Vector3D.of(1, 2, 1e-15), + Vector3D.of(1, 1, -0.5), + Vector3D.of(1, 1 + 1e-15, -0.5), + Vector3D.of(1 - 1e-15, 1, -0.5), + Vector3D.of(1, 0, 0), + + Vector3D.of(1, 0, 0.5), + Vector3D.of(1, 0, 1) + ); + + Vector3D origin = Vector3D.of(1, 0, 0); + + // act + checkPlane(Plane.fromPoints(pts, TEST_PRECISION), + origin, Vector3D.MINUS_Z, Vector3D.PLUS_Y); + checkPlane(Plane.fromPoints(rotate(pts, 1), TEST_PRECISION), + origin, Vector3D.MINUS_Z, Vector3D.PLUS_Y); + + checkPlane(Plane.fromPoints(rotate(pts, 2), TEST_PRECISION), + origin, Vector3D.normalize(0, 1, -1), Vector3D.normalize(0, 1, 1)); + + checkPlane(Plane.fromPoints(rotate(pts, 3), TEST_PRECISION), + origin, Vector3D.normalize(0, 1, 1), Vector3D.normalize(0, -1, 1)); + + checkPlane(Plane.fromPoints(rotate(pts, 4), TEST_PRECISION), + origin, Vector3D.normalize(0, -1, -0.5), Vector3D.normalize(0, 0.5, -1)); + checkPlane(Plane.fromPoints(rotate(pts, 5), TEST_PRECISION), + origin, Vector3D.normalize(0, -1, -0.5), Vector3D.normalize(0, 0.5, -1)); + + checkPlane(Plane.fromPoints(rotate(pts, 6), TEST_PRECISION), + origin, Vector3D.normalize(0, -1, 0.5), Vector3D.normalize(0, -0.5, -1)); + checkPlane(Plane.fromPoints(rotate(pts, 7), TEST_PRECISION), + origin, Vector3D.normalize(0, -1, 0.5), Vector3D.normalize(0, -0.5, -1)); + checkPlane(Plane.fromPoints(rotate(pts, 8), TEST_PRECISION), + origin, Vector3D.normalize(0, -1, 0.5), Vector3D.normalize(0, -0.5, -1)); + + checkPlane(Plane.fromPoints(rotate(pts, 9), TEST_PRECISION), + origin, Vector3D.PLUS_Z, Vector3D.MINUS_Y); + checkPlane(Plane.fromPoints(rotate(pts, 10), TEST_PRECISION), + origin, Vector3D.PLUS_Z, Vector3D.MINUS_Y); + + checkPlane(Plane.fromPoints(rotate(pts, 11), TEST_PRECISION), + origin, Vector3D.MINUS_Z, Vector3D.PLUS_Y); + } + + @Test + public void testFromPoints_collection_choosesBestOrientation() { + // act/assert + checkPlane(Plane.fromPoints(Arrays.asList( + Vector3D.of(1, 0, 2), + Vector3D.of(2, 0, 2), + Vector3D.of(3, 0, 2), + Vector3D.of(3.5, 1, 2) + ), TEST_PRECISION), Vector3D.of(0, 0, 2), Vector3D.PLUS_X, Vector3D.PLUS_Y); + + checkPlane(Plane.fromPoints(Arrays.asList( + Vector3D.of(1, 0, 2), + Vector3D.of(2, 0, 2), + Vector3D.of(3, 0, 2), + Vector3D.of(3.5, -1, 2) + ), TEST_PRECISION), Vector3D.of(0, 0, 2), Vector3D.PLUS_X, Vector3D.MINUS_Y); + + checkPlane(Plane.fromPoints(Arrays.asList( + Vector3D.of(1, 0, 2), + Vector3D.of(2, 0, 2), + Vector3D.of(3, 0, 2), + Vector3D.of(3.5, -1, 2), + Vector3D.of(4, 0, 2) + ), TEST_PRECISION), Vector3D.of(0, 0, 2), Vector3D.PLUS_X, Vector3D.PLUS_Y); + + checkPlane(Plane.fromPoints(Arrays.asList( + Vector3D.of(1, 0, 2), + Vector3D.of(2, 0, 2), + Vector3D.of(3, 0, 2), + Vector3D.of(3.5, 1, 2), + Vector3D.of(4, -1, 2) + ), TEST_PRECISION), Vector3D.of(0, 0, 2), Vector3D.PLUS_X, Vector3D.MINUS_Y); + + checkPlane(Plane.fromPoints(Arrays.asList( + Vector3D.of(0, 0, 2), + Vector3D.of(1, 0, 2), + Vector3D.of(1, 1, 2), + Vector3D.of(0, 1, 2), + Vector3D.of(0, 0, 2) + ), TEST_PRECISION), Vector3D.of(0, 0, 2), Vector3D.PLUS_X, Vector3D.PLUS_Y); + + checkPlane(Plane.fromPoints(Arrays.asList( + Vector3D.of(0, 0, 2), + Vector3D.of(0, 1, 2), + Vector3D.of(1, 1, 2), + Vector3D.of(1, 0, 2), + Vector3D.of(0, 0, 2) + ), TEST_PRECISION), Vector3D.of(0, 0, 2), Vector3D.PLUS_Y, Vector3D.PLUS_X); + + checkPlane(Plane.fromPoints(Arrays.asList( + Vector3D.of(0, 0, 2), + Vector3D.of(1, 0, 2), + Vector3D.of(2, 1, 2), + Vector3D.of(3, 0, 2), + Vector3D.of(2, 4, 2), + Vector3D.of(0, 0, 2) + ), TEST_PRECISION), Vector3D.of(0, 0, 2), Vector3D.PLUS_X, Vector3D.PLUS_Y); + + checkPlane(Plane.fromPoints(Arrays.asList( + Vector3D.of(0, 0, 2), + Vector3D.of(0, 1, 2), + Vector3D.of(2, 4, 2), + Vector3D.of(3, 0, 2), + Vector3D.of(2, 1, 2), + Vector3D.of(0, 0, 2) + ), TEST_PRECISION), Vector3D.of(0, 0, 2), Vector3D.PLUS_Y, Vector3D.PLUS_X); + } + + @Test + public void testFromPoints_collection_illegalArguments() { + // arrange + Vector3D a = Vector3D.ZERO; + Vector3D b = Vector3D.PLUS_X; + + // act/assert + GeometryTestUtils.assertThrows(() -> { + Plane.fromPoints(Arrays.asList(), TEST_PRECISION); + }, IllegalArgumentException.class); + + GeometryTestUtils.assertThrows(() -> { + Plane.fromPoints(Arrays.asList(a), TEST_PRECISION); + }, IllegalArgumentException.class); + + GeometryTestUtils.assertThrows(() -> { + Plane.fromPoints(Arrays.asList(a, b), TEST_PRECISION); + }, IllegalArgumentException.class); + } + + @Test + public void testFromPoints_collection_allPointsCollinear() { + // act/assert + GeometryTestUtils.assertThrows(() -> { + Plane.fromPoints(Arrays.asList( + Vector3D.ZERO, + Vector3D.PLUS_X, + Vector3D.of(2, 0, 0) + ), TEST_PRECISION); + }, GeometryException.class); + + GeometryTestUtils.assertThrows(() -> { + Plane.fromPoints(Arrays.asList( + Vector3D.ZERO, + Vector3D.PLUS_X, + Vector3D.of(2, 0, 0), + Vector3D.of(3, 0, 0) + ), TEST_PRECISION); + }, GeometryException.class); + } + + @Test + public void testFromPoints_collection_notEnoughUniquePoints() { + // act/assert + GeometryTestUtils.assertThrows(() -> { + Plane.fromPoints(Arrays.asList( + Vector3D.ZERO, + Vector3D.ZERO, + Vector3D.of(1e-12, 1e-12, 0), + Vector3D.PLUS_X + ), TEST_PRECISION); + }, GeometryException.class); + + GeometryTestUtils.assertThrows(() -> { + Plane.fromPoints(Arrays.asList( + Vector3D.ZERO, + Vector3D.of(1e-12, 0, 0), + Vector3D.ZERO + ), TEST_PRECISION); + }, GeometryException.class); + } + + @Test + public void testFromPoints_collection_pointsNotOnSamePlane() { + // act/assert + GeometryTestUtils.assertThrows(() -> { + Plane.fromPoints(Arrays.asList( + Vector3D.ZERO, + Vector3D.PLUS_X, + Vector3D.PLUS_Y, + Vector3D.PLUS_Z + ), TEST_PRECISION); + }, GeometryException.class); + } + + @Test public void testRotate() { Vector3D p1 = Vector3D.of(1.2, 3.4, -5.8); Vector3D p2 = Vector3D.of(3.4, -5.8, 1.2); @@ -304,4 +551,41 @@ public class PlaneTest { TEST_PRECISION))); } + private static void checkPlane(Plane plane, Vector3D origin, Vector3D u, Vector3D v) { + u = u.normalize(); + v = v.normalize(); + Vector3D w = u.cross(v); + + EuclideanTestUtils.assertCoordinatesEqual(origin, plane.getOrigin(), TEST_EPS); + Assert.assertTrue(plane.contains(origin)); + + EuclideanTestUtils.assertCoordinatesEqual(u, plane.getU(), TEST_EPS); + Assert.assertEquals(1.0, plane.getU().norm(), TEST_EPS); + + EuclideanTestUtils.assertCoordinatesEqual(v, plane.getV(), TEST_EPS); + Assert.assertEquals(1.0, plane.getV().norm(), TEST_EPS); + + EuclideanTestUtils.assertCoordinatesEqual(w, plane.getW(), TEST_EPS); + Assert.assertEquals(1.0, plane.getW().norm(), TEST_EPS); + + EuclideanTestUtils.assertCoordinatesEqual(w, plane.getNormal(), TEST_EPS); + Assert.assertEquals(1.0, plane.getNormal().norm(), TEST_EPS); + + double offset = plane.getOriginOffset(); + Assert.assertEquals(Vector3D.ZERO.distance(plane.getOrigin()), Math.abs(offset), TEST_EPS); + EuclideanTestUtils.assertCoordinatesEqual(origin, plane.getNormal().multiply(-offset), TEST_EPS); + } + + + private static <T> List<T> rotate(List<T> list, int shift) { + int size = list.size(); + + List<T> result = new ArrayList<>(size); + + for (int i=0; i<size; ++i) { + result.add(list.get((i + shift) % size)); + } + + return result; + } } diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/PolyhedronsSetTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/PolyhedronsSetTest.java index 093501e..fe38389 100644 --- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/PolyhedronsSetTest.java +++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/PolyhedronsSetTest.java @@ -799,6 +799,47 @@ public class PolyhedronsSetTest { Assert.assertEquals(22.0, polyhedron.getBoundarySize(), TEST_EPS); } + // GEOMETRY-59 + @Test + public void testCreateFromBRep_slightlyConcavePrism() { + // arrange + Vector3D vertices[] = { + Vector3D.of( 0, 0, 0 ), + Vector3D.of( 2, 1e-7, 0 ), + Vector3D.of( 4, 0, 0 ), + Vector3D.of( 2, 2, 0 ), + Vector3D.of( 0, 0, 2 ), + Vector3D.of( 2, 1e-7, 2 ), + Vector3D.of( 4, 0, 2 ), + Vector3D.of( 2, 2, 2 ) + }; + + int facets[][] = { + { 4, 5, 6, 7 }, + { 3, 2, 1, 0 }, + { 0, 1, 5, 4 }, + { 1, 2, 6, 5 }, + { 2, 3, 7, 6 }, + { 3, 0, 4, 7 } + }; + + // act + PolyhedronsSet prism = new PolyhedronsSet( + Arrays.asList(vertices), + Arrays.asList(facets), + TEST_PRECISION); + + + // assert + Assert.assertTrue(Double.isFinite(prism.getSize())); + + checkPoints(Region.Location.INSIDE, prism, Vector3D.of(2, 1, 1)); + checkPoints(Region.Location.OUTSIDE, prism, + Vector3D.of(2, 1, 3), Vector3D.of(2, 1, -3), + Vector3D.of(2, -1, 1), Vector3D.of(2, 3, 1), + Vector3D.of(-1, 1, 1), Vector3D.of(4, 1, 1)); + } + @Test public void testCreateFromBRep_verticesTooClose() throws IOException, ParseException { checkError("pentomino-N-too-close.ply", "Vertices are too close"); @@ -811,7 +852,7 @@ public class PolyhedronsSetTest { @Test public void testCreateFromBRep_nonPlanar() throws IOException, ParseException { - checkError("pentomino-N-out-of-plane.ply", "out of plane"); + checkError("pentomino-N-out-of-plane.ply", "do not define a plane"); } @Test @@ -842,7 +883,7 @@ public class PolyhedronsSetTest { try { new PolyhedronsSet(vertices, facets, TEST_PRECISION); Assert.fail("an exception should have been thrown"); - } catch (IllegalArgumentException e) { + } catch (RuntimeException e) { String actual = e.getMessage(); Assert.assertTrue("Expected string to contain \"" + expected + "\" but was \"" + actual + "\"", actual.contains(expected));