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 <mattjuntu...@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