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/08/09 16:02:56 UTC
[commons-geometry] branch master updated: GEOMETRY-63: reducing the
complexity of several methods
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 84bf4c1 GEOMETRY-63: reducing the complexity of several methods
84bf4c1 is described below
commit 84bf4c1daf8357039a801add583c983fca59f2ac
Author: Matt Juntunen <ma...@apache.org>
AuthorDate: Sun Aug 9 10:40:25 2020 -0400
GEOMETRY-63: reducing the complexity of several methods
---
.../AbstractConvexHyperplaneBoundedRegion.java | 150 ++++++++++++---------
.../bsp/AbstractPartitionedRegionBuilder.java | 83 ++++++++----
.../commons/geometry/euclidean/oned/Interval.java | 68 +++++-----
.../geometry/euclidean/oned/IntervalTest.java | 7 +
4 files changed, 183 insertions(+), 125 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 6df261f..01b9a1d 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
@@ -18,6 +18,7 @@ package org.apache.commons.geometry.core.partitioning;
import java.util.ArrayList;
import java.util.Collections;
+import java.util.Iterator;
import java.util.List;
import java.util.function.Function;
@@ -223,55 +224,85 @@ public abstract class AbstractConvexHyperplaneBoundedRegion<P extends Point<P>,
final Hyperplane<P> splitter, final R thisInstance, final Class<S> boundaryType,
final Function<List<S>, R> factory) {
- if (isFull()) {
- final R minus = factory.apply(Collections.singletonList(boundaryType.cast(splitter.span())));
- final R plus = factory.apply(Collections.singletonList(boundaryType.cast(splitter.reverse().span())));
+ return isFull() ?
+ splitInternalFull(splitter, thisInstance, boundaryType, factory) :
+ splitInternalNonFull(splitter, thisInstance, boundaryType, factory);
+ }
- return new Split<>(minus, plus);
- } else {
- final HyperplaneConvexSubset<P> trimmedSplitter = trim(splitter.span());
+ /** Internal split method for use with full regions, i.e. regions that cover the entire space.
+ * @param splitter splitting hyperplane
+ * @param thisInstance a reference to the current instance; this is passed as
+ * an argument in order to allow it to be a generic type
+ * @param boundaryType the type used for the boundary hyperplane subsets
+ * @param factory function used to create new convex region instances
+ * @param <R> Region implementation type
+ * @return the result of the split operation
+ */
+ private <R extends AbstractConvexHyperplaneBoundedRegion<P, S>> Split<R> splitInternalFull(
+ final Hyperplane<P> splitter, final R thisInstance, final Class<S> boundaryType,
+ final Function<List<S>, R> factory) {
- 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.
+ final R minus = factory.apply(Collections.singletonList(boundaryType.cast(splitter.span())));
+ final R plus = factory.apply(Collections.singletonList(boundaryType.cast(splitter.reverse().span())));
- final SplitLocation regionLoc = determineRegionPlusMinusLocation(splitter);
- return regionLoc == SplitLocation.MINUS ?
- new Split<>(thisInstance, null) :
- new Split<>(null, thisInstance);
- }
+ return new Split<>(minus, plus);
+ }
- // the splitter passes through the region; split the other region boundaries
- // by the splitter
- final ArrayList<S> minusBoundaries = new ArrayList<>();
- final ArrayList<S> plusBoundaries = new ArrayList<>();
-
- splitBoundaries(splitter, boundaryType, minusBoundaries, plusBoundaries);
-
- // if the splitter was trimmed by the region boundaries, double-check that the split boundaries
- // actually lie on both sides of the splitter; this is another case where floating point errors
- // can cause a discrepancy between the results of splitting the splitter by the boundaries and
- // splitting the boundaries by the splitter
- if (!trimmedSplitter.isFull()) {
- if (minusBoundaries.isEmpty()) {
- if (plusBoundaries.isEmpty()) {
- return new Split<>(null, null);
- }
- return new Split<>(null, thisInstance);
- } else if (plusBoundaries.isEmpty()) {
- return new Split<>(thisInstance, null);
+ /** Internal split method for use with non-full regions, i.e. regions that do not cover the entire space.
+ * @param splitter splitting hyperplane
+ * @param thisInstance a reference to the current instance; this is passed as
+ * an argument in order to allow it to be a generic type
+ * @param boundaryType the type used for the boundary hyperplane subsets
+ * @param factory function used to create new convex region instances
+ * @param <R> Region implementation type
+ * @return the result of the split operation
+ */
+ private <R extends AbstractConvexHyperplaneBoundedRegion<P, S>> Split<R> splitInternalNonFull(
+ final Hyperplane<P> splitter, final R thisInstance, final Class<S> boundaryType,
+ final Function<List<S>, R> factory) {
+
+ final HyperplaneConvexSubset<P> trimmedSplitter = trim(splitter.span());
+
+ 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.
+
+ final SplitLocation regionLoc = determineRegionPlusMinusLocation(splitter);
+ return regionLoc == SplitLocation.MINUS ?
+ new Split<>(thisInstance, null) :
+ new Split<>(null, thisInstance);
+ }
+
+ // the splitter passes through the region; split the other region boundaries
+ // by the splitter
+ final ArrayList<S> minusBoundaries = new ArrayList<>();
+ final ArrayList<S> plusBoundaries = new ArrayList<>();
+
+ splitBoundaries(splitter, boundaryType, minusBoundaries, plusBoundaries);
+
+ // if the splitter was trimmed by the region boundaries, double-check that the split boundaries
+ // actually lie on both sides of the splitter; this is another case where floating point errors
+ // can cause a discrepancy between the results of splitting the splitter by the boundaries and
+ // splitting the boundaries by the splitter
+ if (!trimmedSplitter.isFull()) {
+ if (minusBoundaries.isEmpty()) {
+ if (plusBoundaries.isEmpty()) {
+ return new Split<>(null, null);
}
+ return new Split<>(null, thisInstance);
+ } else if (plusBoundaries.isEmpty()) {
+ return new Split<>(thisInstance, null);
}
+ }
- // we have a consistent region split; create the new plus and minus regions
- minusBoundaries.add(boundaryType.cast(trimmedSplitter));
- plusBoundaries.add(boundaryType.cast(trimmedSplitter.reverse()));
+ // we have a consistent region split; create the new plus and minus regions
+ minusBoundaries.add(boundaryType.cast(trimmedSplitter));
+ plusBoundaries.add(boundaryType.cast(trimmedSplitter.reverse()));
- minusBoundaries.trimToSize();
- plusBoundaries.trimToSize();
+ minusBoundaries.trimToSize();
+ plusBoundaries.trimToSize();
- return new Split<>(factory.apply(minusBoundaries), factory.apply(plusBoundaries));
- }
+ return new Split<>(factory.apply(minusBoundaries), factory.apply(plusBoundaries));
}
/** Determine whether the region lies on the plus or minus side of the given splitter. It is assumed
@@ -385,7 +416,7 @@ 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 region boundaries
- int boundIdx = 0;
+ int boundIdx = -1;
HyperplaneConvexSubset<P> boundary;
for (final Hyperplane<P> currentBound : bounds) {
@@ -419,8 +450,13 @@ public abstract class AbstractConvexHyperplaneBoundedRegion<P extends Point<P>,
HyperplaneConvexSubset<P> boundary = currentBound.span();
- int splitterIdx = 0;
- for (final Hyperplane<P> splitter : bounds) {
+ final Iterator<? extends Hyperplane<P>> boundsIt = bounds.iterator();
+
+ Hyperplane<P> splitter;
+ int splitterIdx = -1;
+
+ while (boundsIt.hasNext() && boundary != null) {
+ splitter = boundsIt.next();
++splitterIdx;
if (currentBound == splitter) {
@@ -435,28 +471,20 @@ public abstract class AbstractConvexHyperplaneBoundedRegion<P extends Point<P>,
// split the boundary
final Split<? extends HyperplaneConvexSubset<P>> split = boundary.split(splitter);
- if (split.getLocation() == SplitLocation.NEITHER) {
- // the boundary 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 {
+ if (split.getLocation() != SplitLocation.NEITHER) {
// retain the minus portion of the split
boundary = split.getMinus();
+ } else 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;
}
}
-
- if (boundary == null) {
- break;
- }
}
return boundary;
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractPartitionedRegionBuilder.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractPartitionedRegionBuilder.java
index 8859875..9af05a5 100644
--- a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractPartitionedRegionBuilder.java
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractPartitionedRegionBuilder.java
@@ -149,45 +149,70 @@ public abstract class AbstractPartitionedRegionBuilder<
private void insertBoundaryRecursive(final N node, final HyperplaneConvexSubset<P> insert,
final HyperplaneConvexSubset<P> trimmed, final BiConsumer<N, HyperplaneConvexSubset<P>> leafFn) {
if (node.isLeaf()) {
- leafFn.accept(node, trimmed);
+ insertBoundaryRecursiveLeafNode(node, insert, trimmed, leafFn);
} else {
- final Split<? extends HyperplaneConvexSubset<P>> insertSplit =
- insert.split(node.getCutHyperplane());
+ insertBoundaryRecursiveInternalNode(node, insert, trimmed, leafFn);
+ }
+ }
- final HyperplaneConvexSubset<P> minus = insertSplit.getMinus();
- final HyperplaneConvexSubset<P> plus = insertSplit.getPlus();
+ /** Recursive boundary insertion method for leaf nodes.
+ * @param node node to insert into
+ * @param insert the hyperplane convex subset to insert
+ * @param trimmed version of the hyperplane convex subset filling the entire space of {@code node}
+ * @param leafFn function to apply to leaf nodes
+ * @see #insertBoundaryRecursive(AbstractRegionNode, HyperplaneConvexSubset, HyperplaneConvexSubset, BiConsumer)
+ */
+ private void insertBoundaryRecursiveLeafNode(final N node, final HyperplaneConvexSubset<P> insert,
+ final HyperplaneConvexSubset<P> trimmed, final BiConsumer<N, HyperplaneConvexSubset<P>> leafFn) {
+ leafFn.accept(node, trimmed);
+ }
- if (minus == null && plus == null && isPartitionNode(node)) {
- // the inserted boundary lies directly on a partition; proceed down the tree with the
- // rest of the insertion algorithm but instead of cutting the final leaf nodes, just
- // set the location
+ /** Recursive boundary insertion method for internal nodes.
+ * @param node node to insert into
+ * @param insert the hyperplane convex subset to insert
+ * @param trimmed version of the hyperplane convex subset filling the entire space of {@code node}
+ * @param leafFn function to apply to leaf nodes
+ * @see #insertBoundaryRecursive(AbstractRegionNode, HyperplaneConvexSubset, HyperplaneConvexSubset, BiConsumer)
+ */
+ private void insertBoundaryRecursiveInternalNode(final N node, final HyperplaneConvexSubset<P> insert,
+ final HyperplaneConvexSubset<P> trimmed, final BiConsumer<N, HyperplaneConvexSubset<P>> leafFn) {
- // remove this node from the set of partition nodes since this is now a boundary cut
- partitionNodes.remove(node);
+ final Split<? extends HyperplaneConvexSubset<P>> insertSplit =
+ insert.split(node.getCutHyperplane());
- final boolean sameOrientation = node.getCutHyperplane().similarOrientation(insert.getHyperplane());
- final N insertMinus = sameOrientation ? node.getMinus() : node.getPlus();
- final N insertPlus = sameOrientation ? node.getPlus() : node.getMinus();
+ final HyperplaneConvexSubset<P> minus = insertSplit.getMinus();
+ final HyperplaneConvexSubset<P> plus = insertSplit.getPlus();
- insertBoundaryRecursive(insertMinus, insert, trimmed,
- (leaf, cut) -> leaf.setLocation(RegionLocation.INSIDE));
+ if (minus == null && plus == null && isPartitionNode(node)) {
+ // the inserted boundary lies directly on a partition; proceed down the tree with the
+ // rest of the insertion algorithm but instead of cutting the final leaf nodes, just
+ // set the location
- insertBoundaryRecursive(insertPlus, insert, trimmed,
- (leaf, cut) -> leaf.setLocation(RegionLocation.OUTSIDE));
+ // remove this node from the set of partition nodes since this is now a boundary cut
+ partitionNodes.remove(node);
- } else if (minus != null || plus != null) {
- final Split<? extends HyperplaneConvexSubset<P>> trimmedSplit =
- trimmed.split(node.getCutHyperplane());
+ final boolean sameOrientation = node.getCutHyperplane().similarOrientation(insert.getHyperplane());
+ final N insertMinus = sameOrientation ? node.getMinus() : node.getPlus();
+ final N insertPlus = sameOrientation ? node.getPlus() : node.getMinus();
- final HyperplaneConvexSubset<P> trimmedMinus = trimmedSplit.getMinus();
- final HyperplaneConvexSubset<P> trimmedPlus = trimmedSplit.getPlus();
+ insertBoundaryRecursive(insertMinus, insert, trimmed,
+ (leaf, cut) -> leaf.setLocation(RegionLocation.INSIDE));
- if (minus != null) {
- insertBoundaryRecursive(node.getMinus(), minus, trimmedMinus, leafFn);
- }
- if (plus != null) {
- insertBoundaryRecursive(node.getPlus(), plus, trimmedPlus, leafFn);
- }
+ insertBoundaryRecursive(insertPlus, insert, trimmed,
+ (leaf, cut) -> leaf.setLocation(RegionLocation.OUTSIDE));
+
+ } else if (minus != null || plus != null) {
+ final Split<? extends HyperplaneConvexSubset<P>> trimmedSplit =
+ trimmed.split(node.getCutHyperplane());
+
+ final HyperplaneConvexSubset<P> trimmedMinus = trimmedSplit.getMinus();
+ final HyperplaneConvexSubset<P> trimmedPlus = trimmedSplit.getPlus();
+
+ if (minus != null) {
+ insertBoundaryRecursive(node.getMinus(), minus, trimmedMinus, leafFn);
+ }
+ if (plus != null) {
+ insertBoundaryRecursive(node.getPlus(), plus, trimmedPlus, leafFn);
}
}
}
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/oned/Interval.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/oned/Interval.java
index bce3da4..419e8b7 100644
--- a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/oned/Interval.java
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/oned/Interval.java
@@ -407,46 +407,22 @@ public final class Interval implements HyperplaneBoundedRegion<Vector1D> {
* the negative-facing hyperplane)
*/
public static Interval of(final OrientedPoint a, final OrientedPoint b) {
- // determine the ordering of the hyperplanes
- OrientedPoint minBoundary = null;
- OrientedPoint maxBoundary = null;
- if (a != null && b != null) {
- // both hyperplanes are present, so validate then against each other
- if (a.isPositiveFacing() == b.isPositiveFacing()) {
- throw new IllegalArgumentException(
- MessageFormat.format("Invalid interval: hyperplanes have same orientation: {0}, {1}", a, b));
- }
+ validateBoundaryRelationship(a, b);
- if (a.classify(b.getPoint()) == HyperplaneLocation.PLUS ||
- b.classify(a.getPoint()) == HyperplaneLocation.PLUS) {
- throw new IllegalArgumentException(
- MessageFormat.format("Invalid interval: hyperplanes do not form interval: {0}, {1}", a, b));
- }
-
- // min boundary faces -infinity, max boundary faces +infinity
- minBoundary = a.isPositiveFacing() ? b : a;
- maxBoundary = a.isPositiveFacing() ? a : b;
- } else if (a == null) {
- if (b == null) {
- // no boundaries; return the full number line
- return FULL;
- }
+ final boolean hasA = a != null;
+ final boolean hasB = b != null;
- if (b.isPositiveFacing()) {
- maxBoundary = b;
- } else {
- minBoundary = b;
- }
- } else {
- if (a.isPositiveFacing()) {
- maxBoundary = a;
- } else {
- minBoundary = a;
- }
+ if (!hasA && !hasB) {
+ // both boundaries null; return the full space
+ return FULL;
}
- // validate the boundary locations
+ // determine the ordering of the hyperplanes; we know that at least one is non-null
+ final OrientedPoint minBoundary = ((hasA && !a.isPositiveFacing()) || (hasB && b.isPositiveFacing())) ? a : b;
+ final OrientedPoint maxBoundary = ((hasA && a.isPositiveFacing()) || (hasB && !b.isPositiveFacing())) ? a : b;
+
+ // validate the boundary locations; this will ensure that we don't have NaN values
final double minLoc = (minBoundary != null) ? minBoundary.getLocation() : Double.NEGATIVE_INFINITY;
final double maxLoc = (maxBoundary != null) ? maxBoundary.getLocation() : Double.POSITIVE_INFINITY;
@@ -494,6 +470,28 @@ public final class Interval implements HyperplaneBoundedRegion<Vector1D> {
return FULL;
}
+ /** Validate that the orientations and positions of the arguments may be used to create an interval.
+ * The arguments may be given in any order. Does nothing if one or both arguments are null.
+ * @param a first boundary; may be null
+ * @param b second boundary may be null
+ * @throws IllegalArgumentException is {@code a} and {@code b} have the same orientation or one does
+ * not lie on the plus side of the other.
+ */
+ private static void validateBoundaryRelationship(final OrientedPoint a, final OrientedPoint b) {
+ if (a != null && b != null) {
+ if (a.isPositiveFacing() == b.isPositiveFacing()) {
+ throw new IllegalArgumentException(
+ MessageFormat.format("Invalid interval: hyperplanes have same orientation: {0}, {1}", a, b));
+ }
+
+ if (a.classify(b.getPoint()) == HyperplaneLocation.PLUS ||
+ b.classify(a.getPoint()) == HyperplaneLocation.PLUS) {
+ throw new IllegalArgumentException(
+ MessageFormat.format("Invalid interval: hyperplanes do not form interval: {0}, {1}", a, b));
+ }
+ }
+ }
+
/** Validate that the given value can be used to construct an interval. The values
* must not be NaN and if infinite, must have opposite signs.
* @param a first value
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/oned/IntervalTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/oned/IntervalTest.java
index 5688223..dd612cc 100644
--- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/oned/IntervalTest.java
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/oned/IntervalTest.java
@@ -100,6 +100,8 @@ public class IntervalTest {
@Test
public void testOf_hyperplanes() {
// act/assert
+ Assert.assertSame(Interval.full(), Interval.of(null, null));
+
checkInterval(Interval.of(
OrientedPoints.fromLocationAndDirection(1, true, TEST_PRECISION),
OrientedPoints.fromLocationAndDirection(1, false, TEST_PRECISION)), 1, 1);
@@ -170,6 +172,11 @@ public class IntervalTest {
() -> Interval.of(
OrientedPoints.fromLocationAndDirection(Double.NaN, false, TEST_PRECISION),
OrientedPoints.fromLocationAndDirection(Double.NaN, true, TEST_PRECISION)), excType);
+
+ GeometryTestUtils.assertThrows(
+ () -> Interval.of(
+ null,
+ OrientedPoints.fromLocationAndDirection(Double.NaN, true, TEST_PRECISION)), excType);
}
@Test