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
The following commit(s) were added to refs/heads/master by this push:
new 78b5c21 GEOMETRY-63: simplifying
AbstractConvexHyperplaneBoundedRegion.ConvexRegionBoundaryBuilder; adding
assertions to WelzlEncloser2DTest test method
new 7c5ff83 Merge branch 'GEOMETRY-63__Matt'
78b5c21 is described below
commit 78b5c21fcda551b032d09a5197d4344fc319a101
Author: Matt Juntunen <matt.juntu...@hotmail.com>
AuthorDate: Mon Feb 3 22:49:56 2020 -0500
GEOMETRY-63: simplifying
AbstractConvexHyperplaneBoundedRegion.ConvexRegionBoundaryBuilder; adding
assertions to WelzlEncloser2DTest test method
---
.../AbstractConvexHyperplaneBoundedRegion.java | 121 +++++++++++++--------
.../AbstractConvexHyperplaneBoundedRegionTest.java | 3 +-
.../euclidean/twod/WelzlEncloser2DTest.java | 8 +-
3 files changed, 82 insertions(+), 50 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 116c6a0..00fa774 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
@@ -324,65 +324,90 @@ public abstract class
AbstractConvexHyperplaneBoundedRegion<P extends Point<P>,
final List<S> boundaries = new ArrayList<>();
- // cut each hyperplane by every other hyperplane in order to get
the subplane boundaries
- boolean notConvex = false;
- int outerIdx = 0;
- ConvexSubHyperplane<P> subhp;
-
- for (final Hyperplane<P> hp : bounds) {
- ++outerIdx;
- subhp = hp.span();
-
- int innerIdx = 0;
- for (final Hyperplane<P> splitter : bounds) {
- ++innerIdx;
-
- if (hp != splitter) {
- final Split<? extends ConvexSubHyperplane<P>> split =
subhp.split(splitter);
-
- if (split.getLocation() == SplitLocation.NEITHER) {
- if (hp.similarOrientation(splitter)) {
- // two or more splitters are the equivalent;
only
- // use the segment from the first one
- if (outerIdx > innerIdx) {
- subhp = null;
- }
- } else {
- // two or more splitters are coincident and
have opposite
- // orientations, meaning that no area is on
the minus side
- // of both
- notConvex = true;
- break;
- }
- } else {
- subhp = subhp.split(splitter).getMinus();
- }
+ // cut each hyperplane by every other hyperplane in order to get
the region boundaries
+ int boundIdx = 0;
+ ConvexSubHyperplane<P> boundary;
- if (subhp == null) {
- break;
- }
- } else if (outerIdx > innerIdx) {
+ for (final Hyperplane<P> currentBound : bounds) {
+ ++boundIdx;
+
+ boundary = splitBound(currentBound, bounds, boundIdx);
+ if (boundary != null) {
+ boundaries.add(subhyperplaneType.cast(boundary));
+ }
+ }
+
+ if (boundIdx > 0 && boundaries.isEmpty()) {
+ // nothing was added
+ throw nonConvexException(bounds);
+ }
+
+ return boundaries;
+ }
+
+ /** Split the given bounding hyperplane by all of the other
hyperplanes in the given collection, returning the
+ * remaining subhyperplane.
+ * @param currentBound the bound to split; this value is assumed to
have come from {@code bounds}
+ * @param bounds collection of bounds to use to split {@code
currentBound}
+ * @param currentBoundIdx the index of {@code currentBound} in {@code
bounds}
+ * @return the part of {@code currentBound}'s subhyperplane that lies
on the minus side of all of the
+ * splitting hyperplanes
+ * @throws IllegalArgumentException if the hyperplanes do not form a
convex region
+ */
+ private ConvexSubHyperplane<P> splitBound(final Hyperplane<P>
currentBound,
+ final Iterable<? extends Hyperplane<P>> bounds, final int
currentBoundIdx) {
+
+ ConvexSubHyperplane<P> boundary = currentBound.span();
+
+ int splitterIdx = 0;
+ for (final Hyperplane<P> splitter : bounds) {
+ ++splitterIdx;
+
+ if (currentBound == splitter) {
+ // do not split the bound with itself
+
+ if (currentBoundIdx > splitterIdx) {
// this hyperplane is duplicated in the list; skip all
but the
// first insertion of its subhyperplane
- subhp = null;
- break;
+ return null;
+ }
+ } else {
+ // split the subhyperplane
+ final Split<? extends ConvexSubHyperplane<P>> split =
boundary.split(splitter);
+
+ if (split.getLocation() == SplitLocation.NEITHER) {
+ // the subhyperplane lies directly on the splitter
+
+ if (!currentBound.similarOrientation(splitter)) {
+ // two or more splitters are coincident and have
opposite
+ // orientations, meaning that no area is on the
minus side
+ // of both
+ throw nonConvexException(bounds);
+ } else if (currentBoundIdx > splitterIdx) {
+ // two or more hyperplanes are equivalent; only use
the boundary
+ // from the first one and return null for this one
+ return null;
+ }
+ } else {
+ // retain the minus portion of the split
+ boundary = split.getMinus();
}
}
- if (notConvex) {
+ if (boundary == null) {
break;
}
-
- if (subhp != null) {
- boundaries.add(subhyperplaneType.cast(subhp));
- }
}
- if (notConvex || (outerIdx > 0 && boundaries.isEmpty())) {
- throw new IllegalArgumentException("Bounding hyperplanes do
not produce a convex region: " + bounds);
- }
+ return boundary;
+ }
- return boundaries;
+ /** Return an exception indicating that the given collection of
hyperplanes do not produce a convex region.
+ * @param bounds collection of hyperplanes
+ * @return an exception indicating that the given collection of
hyperplanes do not produce a convex region
+ */
+ private IllegalArgumentException nonConvexException(final Iterable<?
extends Hyperplane<P>> bounds) {
+ return new IllegalArgumentException("Bounding hyperplanes do not
produce a convex region: " + bounds);
}
}
}
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 7cdfbcd..c67c46f 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
@@ -480,7 +480,8 @@ public class AbstractConvexHyperplaneBoundedRegionTest {
StubRegion.fromBounds(Arrays.asList(
TestLine.X_AXIS,
TestLine.Y_AXIS,
- new TestLine(new TestPoint2D(1, 0), new TestPoint2D(0,
-1))));
+ new TestLine(new TestPoint2D(1, 0), new TestPoint2D(0,
-1)),
+ new TestLine(new TestPoint2D(1, 0), new TestPoint2D(0,
-2))));
}, IllegalArgumentException.class);
}
diff --git
a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/twod/WelzlEncloser2DTest.java
b/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/twod/WelzlEncloser2DTest.java
index 6fb32b7..4f92579 100755
---
a/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/twod/WelzlEncloser2DTest.java
+++
b/commons-geometry-enclosing/src/test/java/org/apache/commons/geometry/enclosing/euclidean/twod/WelzlEncloser2DTest.java
@@ -24,6 +24,7 @@ import org.apache.commons.geometry.core.GeometryTestUtils;
import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
import
org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
import org.apache.commons.geometry.enclosing.EnclosingBall;
+import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
import org.apache.commons.geometry.euclidean.twod.Vector2D;
import org.apache.commons.rng.UniformRandomProvider;
import org.apache.commons.rng.simple.RandomSource;
@@ -130,7 +131,12 @@ public class WelzlEncloser2DTest {
WelzlEncloser2D customPrecisionEncloser = new
WelzlEncloser2D(precisionContext);
// act
- customPrecisionEncloser.enclose(points);
+ EnclosingBall<Vector2D> result =
customPrecisionEncloser.enclose(points);
+
+ // assert
+ Assert.assertEquals(27.099954200964234, result.getRadius(), TEST_EPS);
+
EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(296.0056977503686,
53.469890753441945),
+ result.getCenter(), TEST_EPS);
}
private List<Vector2D> buildList(final double... coordinates) {
