You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ma...@apache.org on 2020/03/24 03:15:30 UTC
[commons-geometry] branch master updated: GEOMETRY-91: updating
AbstractConvexHyperplaneBoundedRegion split logic to handle split
inconsistency edge cases
This is an automated email from the ASF dual-hosted git repository.
mattjuntunen pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-geometry.git
The following commit(s) were added to refs/heads/master by this push:
new 5599138 GEOMETRY-91: updating AbstractConvexHyperplaneBoundedRegion split logic to handle split inconsistency edge cases
5599138 is described below
commit 55991385c303a63bea1a02760516ff369f33eaa2
Author: Matt Juntunen <ma...@hotmail.com>
AuthorDate: Mon Mar 23 22:59:04 2020 -0400
GEOMETRY-91: updating AbstractConvexHyperplaneBoundedRegion split logic to handle split inconsistency edge cases
---
.../AbstractConvexHyperplaneBoundedRegion.java | 68 +++++++++++++++++-----
.../AbstractConvexHyperplaneBoundedRegionTest.java | 57 ++++++++++++++++++
2 files changed, 112 insertions(+), 13 deletions(-)
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/AbstractConvexHyperplaneBoundedRegion.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/AbstractConvexHyperplaneBoundedRegion.java
index 00fa774..82c8bec 100644
--- a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/AbstractConvexHyperplaneBoundedRegion.java
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/AbstractConvexHyperplaneBoundedRegion.java
@@ -236,20 +236,11 @@ public abstract class AbstractConvexHyperplaneBoundedRegion<P extends Point<P>,
if (trimmedSplitter == null) {
// The splitter lies entirely outside of the region; we need
// to determine whether we lie on the plus or minus side of the splitter.
- // We can use the first boundary to determine this. If the boundary is entirely
- // on the minus side of the splitter or lies directly on the splitter and has
- // the same orientation, then the area lies on the minus side of the splitter.
- // Otherwise, it lies on the plus side.
- final ConvexSubHyperplane<P> testSegment = boundaries.get(0);
- final SplitLocation testLocation = testSegment.split(splitter).getLocation();
-
- if (SplitLocation.MINUS == testLocation ||
- (SplitLocation.NEITHER == testLocation &&
- splitter.similarOrientation(testSegment.getHyperplane()))) {
- return new Split<>(thisInstance, null);
- }
- return new Split<>(null, thisInstance);
+ final SplitLocation regionLoc = determineRegionPlusMinusLocation(splitter);
+ return regionLoc == SplitLocation.MINUS ?
+ new Split<>(thisInstance, null) :
+ new Split<>(null, thisInstance);
}
final List<S> minusBoundaries = new ArrayList<>();
@@ -264,6 +255,57 @@ public abstract class AbstractConvexHyperplaneBoundedRegion<P extends Point<P>,
}
}
+ /** Determine whether the region lies on the plus or minus side of the given splitter. It is assumed
+ * that (1) the region is not full, and (2) the given splitter does not pass through the region.
+ *
+ * <p>In theory, this is a very simple operation: one need only test a single region boundary
+ * to see if it lies on the plus or minus side of the splitter. In practice, however, accumulated
+ * floating point errors can cause discrepancies between the splitting operations, causing
+ * boundaries to be classified as lying on both sides of the splitter when they should only lie on one.
+ * Therefore, this method examines as many boundaries as needed in order to determine the best response.
+ * The algorithm proceeds as follows:
+ * <ol>
+ * <li>If any boundary lies completely on the minus or plus side of the splitter, then
+ * {@link SplitLocation#MINUS MINUS} or {@link SplitLocation#PLUS PLUS} is returned, respectively.</li>
+ * <li>If any boundary is coincident with the splitter ({@link SplitLocation#NEITHER NEITHER}), then
+ * {@link SplitLocation#MINUS MINUS} is returned if the boundary hyperplane has the same orientation
+ * as the splitter, otherwise {@link SplitLocation#PLUS PLUS}.</li>
+ * <li>If no boundaries match the above conditions, then the sizes of the split boundaries are compared. If
+ * the sum of the sizes of the boundaries on the minus side is greater than the sum of the sizes of
+ * the boundaries on the plus size, then {@link SplitLocation#MINUS MINUS} is returned. Otherwise,
+ * {@link SplitLocation#PLUS PLUS} is returned.
+ * </ol>
+ * @param splitter splitter to classify the region against; the splitter is assumed to lie
+ * completely outside of the region
+ * @return {@link SplitLocation#MINUS} if the region lies on the minus side of the splitter and
+ * {@link SplitLocation#PLUS} if the region lies on the plus side of the splitter
+ */
+ private SplitLocation determineRegionPlusMinusLocation(final Hyperplane<P> splitter) {
+ double minusSize = 0;
+ double plusSize = 0;
+
+ Split<? extends ConvexSubHyperplane<P>> split;
+ SplitLocation loc;
+
+ for (final S boundary : boundaries) {
+ split = boundary.split(splitter);
+ loc = split.getLocation();
+
+ if (loc == SplitLocation.MINUS || loc == SplitLocation.PLUS) {
+ return loc;
+ } else if (loc == SplitLocation.NEITHER) {
+ return splitter.similarOrientation(boundary.getHyperplane()) ?
+ SplitLocation.MINUS :
+ SplitLocation.PLUS;
+ } else {
+ minusSize += split.getMinus().getSize();
+ plusSize += split.getPlus().getSize();
+ }
+ }
+
+ return minusSize > plusSize ? SplitLocation.MINUS : SplitLocation.PLUS;
+ }
+
/** Split the boundaries of the region by the given hyperplane, adding the split parts into the
* corresponding lists.
* @param splitter splitting hyperplane
diff --git a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/AbstractConvexHyperplaneBoundedRegionTest.java b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/AbstractConvexHyperplaneBoundedRegionTest.java
index c67c46f..bd73f02 100644
--- a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/AbstractConvexHyperplaneBoundedRegionTest.java
+++ b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/AbstractConvexHyperplaneBoundedRegionTest.java
@@ -292,6 +292,63 @@ public class AbstractConvexHyperplaneBoundedRegionTest {
checkClassify(plus, RegionLocation.INSIDE, new TestPoint2D(1.5, -0.25));
}
+ // The following tests are designed to check the situation where there are
+ // inconsistencies between how a splitter splits a set of boundaries and how
+ // the boundaries split the splitter. For example, no portion of the splitter
+ // may lie inside the region (on the minus sides of all boundaries), but some
+ // of the boundaries may be determined to lie on both sides of the splitter.
+ // One potential cause of this situation is accumulated floating point errors.
+
+ @Test
+ public void testSplit_inconsistentBoundarySplitLocations_minus() {
+ // arrange
+ TestLine a = new TestLine(new TestPoint2D(0, 0), new TestPoint2D(1, 1));
+ TestLine b = new TestLine(new TestPoint2D(-1, 1), new TestPoint2D(0, 0));
+
+ StubRegion region = new StubRegion(Arrays.asList(
+ new TestLineSegment(-1e-8, Double.POSITIVE_INFINITY, a),
+ new TestLineSegment(Double.NEGATIVE_INFINITY, 1e-8, b)
+ ));
+
+ List<TestLineSegment> segments = region.getBoundaries();
+ PartitionTestUtils.assertPointsEqual(segments.get(0).getStartPoint(), segments.get(1).getEndPoint());
+
+ TestLine splitter = new TestLine(new TestPoint2D(0, 0), new TestPoint2D(1, 0));
+
+ // act
+ Split<StubRegion> split = region.split(splitter);
+
+ // assert
+ Assert.assertEquals(SplitLocation.MINUS, split.getLocation());
+ Assert.assertSame(region, split.getMinus());
+ Assert.assertNull(split.getPlus());
+ }
+
+ @Test
+ public void testSplit_inconsistentBoundarySplitLocations_plus() {
+ // arrange
+ TestLine a = new TestLine(new TestPoint2D(0, 0), new TestPoint2D(1, 1));
+ TestLine b = new TestLine(new TestPoint2D(-1, 1), new TestPoint2D(0, 0));
+
+ StubRegion region = new StubRegion(Arrays.asList(
+ new TestLineSegment(-1e-8, Double.POSITIVE_INFINITY, a),
+ new TestLineSegment(Double.NEGATIVE_INFINITY, 1e-8, b)
+ ));
+
+ List<TestLineSegment> segments = region.getBoundaries();
+ PartitionTestUtils.assertPointsEqual(segments.get(0).getStartPoint(), segments.get(1).getEndPoint());
+
+ TestLine splitter = new TestLine(new TestPoint2D(1, 0), new TestPoint2D(0, 0));
+
+ // act
+ Split<StubRegion> split = region.split(splitter);
+
+ // assert
+ Assert.assertEquals(SplitLocation.PLUS, split.getLocation());
+ Assert.assertNull(split.getMinus());
+ Assert.assertSame(region, split.getPlus());
+ }
+
@Test
public void testTransform_full() {
// arrange