You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by er...@apache.org on 2020/02/20 15:21:00 UTC
[commons-geometry] branch master updated: GEOMETRY-74: adding
RegionCutRule for fine-grain control of region BSP tree insertion behavior
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 3276f24 GEOMETRY-74: adding RegionCutRule for fine-grain control of region BSP tree insertion behavior
new adecd9a Merge branch 'GEOMETRY-74__Matt'
3276f24 is described below
commit 3276f24ade965941557676b2205c961e683dcea2
Author: Matt Juntunen <ma...@hotmail.com>
AuthorDate: Thu Feb 20 08:05:34 2020 -0500
GEOMETRY-74: adding RegionCutRule for fine-grain control of region BSP tree insertion behavior
---
.../core/partitioning/bsp/AbstractBSPTree.java | 217 ++---
.../partitioning/bsp/AbstractRegionBSPTree.java | 335 ++++++--
.../geometry/core/partitioning/bsp/BSPSubtree.java | 1 +
.../geometry/core/partitioning/bsp/BSPTree.java | 88 +-
.../core/partitioning/bsp/RegionCutRule.java | 41 +
.../core/partition/test/AttributeBSPTree.java | 30 +-
.../geometry/core/partition/test/TestBSPTree.java | 42 +-
.../core/partition/test/TestRegionBSPTree.java | 8 +-
.../core/partitioning/bsp/AbstractBSPTreeTest.java | 56 +-
.../bsp/AbstractRegionBSPTreeBooleanTest.java | 695 ++++++++++++++++
.../bsp/AbstractRegionBSPTreeTest.java | 892 ++++++---------------
.../geometry/euclidean/oned/RegionBSPTree1D.java | 5 +-
.../euclidean/threed/BoundarySource3D.java | 14 +-
.../geometry/euclidean/threed/ConvexVolume.java | 7 +
.../geometry/euclidean/threed/RegionBSPTree3D.java | 33 +-
.../geometry/euclidean/twod/BoundarySource2D.java | 14 +-
.../geometry/euclidean/twod/ConvexArea.java | 7 +
.../geometry/euclidean/twod/RegionBSPTree2D.java | 35 +-
.../euclidean/DocumentationExamplesTest.java | 60 +-
.../euclidean/threed/BoundarySource3DTest.java | 33 +
.../euclidean/threed/ConvexVolumeTest.java | 13 +
.../euclidean/threed/RegionBSPTree3DTest.java | 102 ++-
.../geometry/euclidean/threed/SubPlaneTest.java | 6 +-
.../euclidean/twod/BoundarySource2DTest.java | 31 +
.../geometry/euclidean/twod/ConvexAreaTest.java | 16 +
.../euclidean/twod/RegionBSPTree2DTest.java | 139 ++--
.../geometry/spherical/twod/BoundarySource2S.java | 14 +-
.../geometry/spherical/twod/ConvexArea2S.java | 7 +
.../geometry/spherical/twod/RegionBSPTree2S.java | 33 +-
.../spherical/twod/BoundarySource2STest.java | 63 ++
.../geometry/spherical/twod/ConvexArea2STest.java | 13 +
.../geometry/spherical/twod/GreatArcPathTest.java | 4 +-
.../spherical/twod/RegionBSPTree2STest.java | 55 +-
.../resources/spotbugs/spotbugs-exclude-filter.xml | 4 +-
src/site/xdoc/userguide/index.xml | 57 +-
35 files changed, 2048 insertions(+), 1122 deletions(-)
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractBSPTree.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractBSPTree.java
index b5c23b8..a7d7a2b 100644
--- a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractBSPTree.java
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractBSPTree.java
@@ -20,24 +20,63 @@ import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;
-import java.util.stream.Stream;
import org.apache.commons.geometry.core.Point;
import org.apache.commons.geometry.core.Transform;
-import org.apache.commons.geometry.core.partitioning.BoundarySource;
import org.apache.commons.geometry.core.partitioning.ConvexSubHyperplane;
import org.apache.commons.geometry.core.partitioning.Hyperplane;
import org.apache.commons.geometry.core.partitioning.HyperplaneLocation;
import org.apache.commons.geometry.core.partitioning.Split;
import org.apache.commons.geometry.core.partitioning.SplitLocation;
-import org.apache.commons.geometry.core.partitioning.SubHyperplane;
-/** Abstract class for Binary Space Partitioning (BSP) tree implementations.
+/** Abstract class for Binary Space Partitioning (BSP) tree implementations. This
+ * class contains basic structures and algorithms that should be common
+ * to all BSP tree implementations, regardless of the end use cases for the tree
+ * (eg, whether the tree is intended to represent polytopes, hold attributes like
+ * a map, etc).
+ *
+ * <h2>Implementation Notes</h2>
+ * <ul>
+ * <li>The {@link AbstractBSPTree} class is designed to work closely with its nested node type,
+ * {@link AbstractNode}. The tree class handles all tree manipulation operations while the node type
+ * is primarily a simple data type and delegates tree operations to internal methods within its
+ * parent tree. This allows for easier overriding of tree behavior in subclasses.</li>
+ * <li>Each time the structure of the tree is modified, a {@link #getVersion() version number} is
+ * incremented in the tree. This allows certain tree properties to be computed lazily and then
+ * cached. The tree version number is incremented with the {@link #invalidate() invalidate} method. Properties
+ * can be cached directly on nodes using the {@link AbstractBSPTree.AbstractNode#checkValid() checkValid}
+ * and {@link AbstractBSPTree.AbstractNode#nodeInvalidated() nodeInvalidated} methods.</li>
+ * <li>Since the methods used to construct and modify trees can vary by use case, no public API is provided
+ * for manipulating the tree. Subclasses are expected to use the protected methods of this class to
+ * create their own. For tree construction, subclasses are expected to pass their own {@link SubtreeInitializer}
+ * instances to {@link #insert(ConvexSubHyperplane, SubtreeInitializer) insert} and
+ * {@link #cutNode(AbstractNode, Hyperplane, SubtreeInitializer) cutNode} in order to set the correct properties on
+ * tree nodes. To support tree copying, subclasses must also override
+ * {@link #copyNodeProperties(AbstractNode, AbstractNode) copyNodeProperties}.</li>
+ * <li>This class is not thread safe.</li>
+ * </ul>
+ *
* @param <P> Point implementation type
* @param <N> BSP tree node implementation type
+ * @see BSPTree
*/
public abstract class AbstractBSPTree<P extends Point<P>, N extends AbstractBSPTree.AbstractNode<P, N>>
implements BSPTree<P, N> {
+
+ /** Interface used to initialize newly created BSP subtrees, consisting of a single parent
+ * node and two child nodes.
+ * @param <N> BSP tree node implementation type
+ */
+ @FunctionalInterface
+ public interface SubtreeInitializer<N extends AbstractBSPTree.AbstractNode<?, ?>> {
+
+ /** Initialize the given newly-created subtree. The subtree consists of a single root node and two
+ * child nodes.
+ * @param root the root node of the new subtree
+ */
+ void initSubtree(N root);
+ }
+
/** The default number of levels to print when creating a string representation of the tree. */
private static final int DEFAULT_TREE_STRING_MAX_DEPTH = 8;
@@ -94,41 +133,12 @@ public abstract class AbstractBSPTree<P extends Point<P>, N extends AbstractBSPT
/** {@inheritDoc} */
@Override
- public N findNode(final P pt, final NodeCutRule cutBehavior) {
+ public N findNode(final P pt, final FindNodeCutRule cutBehavior) {
return findNode(getRoot(), pt, cutBehavior);
}
/** {@inheritDoc} */
@Override
- public void insert(final SubHyperplane<P> sub) {
- insert(sub.toConvex());
- }
-
- /** {@inheritDoc} */
- @Override
- public void insert(final ConvexSubHyperplane<P> convexSub) {
- insertRecursive(getRoot(), convexSub,
- convexSub.getHyperplane().span());
- }
-
- /** {@inheritDoc} */
- @Override
- public void insert(final Iterable<? extends ConvexSubHyperplane<P>> convexSubs) {
- for (final ConvexSubHyperplane<P> convexSub : convexSubs) {
- insert(convexSub);
- }
- }
-
- /** {@inheritDoc} */
- @Override
- public void insert(final BoundarySource<? extends ConvexSubHyperplane<P>> boundarySrc) {
- try (Stream<? extends ConvexSubHyperplane<P>> stream = boundarySrc.boundaryStream()) {
- stream.forEach(this::insert);
- }
- }
-
- /** {@inheritDoc} */
- @Override
public Iterable<N> nodes() {
return () -> new NodeIterator<>(getRoot());
}
@@ -211,17 +221,6 @@ public abstract class AbstractBSPTree<P extends Point<P>, N extends AbstractBSPT
// no-op
}
- /** Method called to initialize a new child node. Subclasses can use this method to
- * set initial attributes on the node.
- * @param parent the parent node
- * @param child the new child node
- * @param isPlus true if the child will be assigned as the parent's plus child;
- * false if it will be the parent's minus child
- */
- protected void initChildNode(final N parent, final N child, final boolean isPlus) {
- // no-op
- }
-
/** Create a non-structural copy of the given node. Properties such as parent/child
* connections and cut subhyperplanes are <em>not</em> copied.
* @param src the node to copy; does not need to belong to the current tree
@@ -333,11 +332,11 @@ public abstract class AbstractBSPTree<P extends Point<P>, N extends AbstractBSPT
* at the given node.
* @param start the node to begin the search with
* @param pt the point to check
- * @param cutBehavior value determining the search behavior when the test point
+ * @param cutRule value determining the search behavior when the test point
* lies directly on the cut subhyperplane of an internal node
* @return the smallest node in the tree containing the point
*/
- protected N findNode(final N start, final P pt, final NodeCutRule cutBehavior) {
+ protected N findNode(final N start, final P pt, final FindNodeCutRule cutRule) {
final Hyperplane<P> cutHyper = start.getCutHyperplane();
if (cutHyper != null) {
final HyperplaneLocation cutLoc = cutHyper.classify(pt);
@@ -346,10 +345,10 @@ public abstract class AbstractBSPTree<P extends Point<P>, N extends AbstractBSPT
final boolean onMinusSide = cutLoc == HyperplaneLocation.MINUS;
final boolean onCut = !onPlusSide && !onMinusSide;
- if (onMinusSide || (onCut && cutBehavior == NodeCutRule.MINUS)) {
- return findNode(start.getMinus(), pt, cutBehavior);
- } else if (onPlusSide || cutBehavior == NodeCutRule.PLUS) {
- return findNode(start.getPlus(), pt, cutBehavior);
+ if (onMinusSide || (onCut && cutRule == FindNodeCutRule.MINUS)) {
+ return findNode(start.getMinus(), pt, cutRule);
+ } else if (onPlusSide || cutRule == FindNodeCutRule.PLUS) {
+ return findNode(start.getPlus(), pt, cutRule);
}
}
return start;
@@ -428,10 +427,10 @@ public abstract class AbstractBSPTree<P extends Point<P>, N extends AbstractBSPT
* <ul>
* <li>the remaining portion becomes the cut subhyperplane for the node,</li>
* <li>two new child nodes are created and initialized with
- * {@link #initChildNode(AbstractNode, AbstractNode, boolean)}, and</li>
+ * {@code subtreeInitializer}, and</li>
* <li>true is returned.</li>
* </ul>
- * </li>
+ * </li>
* <li>If the remaining portion of the hyperplane <em>is</em> empty (ie, the
* cutting hyperplane does not intersect the node's region), then
* <ul>
@@ -446,27 +445,32 @@ public abstract class AbstractBSPTree<P extends Point<P>, N extends AbstractBSPT
* to the tree root, it must only be used on nodes that are already inserted into
* the tree.</p>
*
- * <p>This method always calls {@link #invalidate()} to invalidate cached tree properties.</p>
+ * <p>This method calls {@link #invalidate()} to invalidate cached tree properties if the tree
+ * structure is changed.</p>
*
* @param node the node to cut
* @param cutter the hyperplane to cut the node with
+ * @param subtreeInitializer object used to initialize any newly-created subtrees
* @return true if the node was cut and two new child nodes were created;
* otherwise false
* @see #trimToNode(AbstractNode, ConvexSubHyperplane)
- * @see #cutNode(AbstractNode, ConvexSubHyperplane)
+ * @see #setNodeCut(AbstractNode, ConvexSubHyperplane, SubtreeInitializer)
+ * @see #removeNodeCut(AbstractNode)
* @see #invalidate()
*/
- protected boolean insertNodeCut(final N node, final Hyperplane<P> cutter) {
+ protected boolean cutNode(final N node, final Hyperplane<P> cutter,
+ final SubtreeInitializer<N> subtreeInitializer) {
+
// cut the hyperplane using all hyperplanes from this node up
// to the root
final ConvexSubHyperplane<P> cut = trimToNode(node, cutter.span());
if (cut == null || cut.isEmpty()) {
// insertion failed; the node was not cut
- cutNode(node, null);
+ removeNodeCut(node);
return false;
}
- cutNode(node, cut);
+ setNodeCut(node, cut, subtreeInitializer);
return true;
}
@@ -534,20 +538,26 @@ public abstract class AbstractBSPTree<P extends Point<P>, N extends AbstractBSPT
/** Remove the cut from the given node. Returns true if the node had a cut before
* the call to this method. Any previous child nodes are lost.
+ *
+ * <p>This method calls {@link #invalidate()} to invalidate cached tree properties if the tree
+ * structure changed.</p>
* @param node the node to remove the cut from
* @return true if the node previously had a cut
*/
protected boolean removeNodeCut(final N node) {
- boolean hadCut = node.getCut() != null;
- cutNode(node, null);
+ if (node.getCut() != null) {
+ node.setSubtree(null, null, null);
+
+ invalidate();
+
+ return true;
+ }
- return hadCut;
+ return false;
}
- /** Set the cut subhyperplane for the given node. If {@code cut} is {@code null} then any
- * existing child nodes are removed. If {@code cut} is not {@code null}, two new child
- * nodes are created and initialized with
- * {@link AbstractBSPTree#initChildNode(AbstractNode, AbstractNode, boolean)}.
+ /** Set the cut subhyperplane for the given node. Two new child nodes are created for the given
+ * node and the new subtree is initialized with {@code subtreeInitializer}.
*
* <p>This method performs absolutely <em>no</em> validation on the given cut
* subhyperplane. It is the responsibility of the caller to ensure that the
@@ -556,37 +566,26 @@ public abstract class AbstractBSPTree<P extends Point<P>, N extends AbstractBSPT
* <p>This method always calls {@link #invalidate()} to invalidate cached tree properties.</p>
* @param node the node to cut
* @param cut the convex subhyperplane to set as the node cut
+ * @param subtreeInitializer object used to initialize the newly-created subtree
*/
- protected void cutNode(final N node, final ConvexSubHyperplane<P> cut) {
- N plus = null;
- N minus = null;
+ protected void setNodeCut(final N node, final ConvexSubHyperplane<P> cut,
+ final SubtreeInitializer<N> subtreeInitializer) {
- if (cut != null) {
- minus = createNode();
- initChildNode(node, minus, false);
+ node.setSubtree(cut, createNode(), createNode());
- plus = createNode();
- initChildNode(node, plus, true);
- }
-
- node.setSubtree(cut, minus, plus);
+ subtreeInitializer.initSubtree(node);
invalidate();
}
- /** Return true if the given transform swaps the inside and outside of
- * the region.
- *
- * <p>The default behavior of this method is to return true if the transform
- * does not preserve spatial orientation (ie, {@link Transform#preservesOrientation()}
- * is false). Subclasses may need to override this method to implement the correct
- * behavior for their space and dimension.</p>
- * @param transform transform to check
- * @return true if the given transform swaps the interior and exterior of
- * the region
+ /** Insert the given convex subhyperplane into the tree, starting at the root node. Any subtrees
+ * created are initialized with {@code subtreeInit}.
+ * @param convexSub convex subhyperplane to insert into the tree
+ * @param subtreeInit object used to initialize newly created subtrees
*/
- protected boolean swapsInsideOutside(final Transform<P> transform) {
- return !transform.preservesOrientation();
+ protected void insert(final ConvexSubHyperplane<P> convexSub, final SubtreeInitializer<N> subtreeInit) {
+ insertRecursive(getRoot(), convexSub,
+ convexSub.getHyperplane().span(), subtreeInit);
}
/** Recursively insert a subhyperplane into the tree at the given node.
@@ -594,11 +593,12 @@ public abstract class AbstractBSPTree<P extends Point<P>, N extends AbstractBSPT
* @param insert the subhyperplane to insert
* @param trimmed subhyperplane containing the result of splitting the entire
* space with each hyperplane from this node to the root
+ * @param subtreeInit object used to initialize newly created subtrees
*/
private void insertRecursive(final N node, final ConvexSubHyperplane<P> insert,
- final ConvexSubHyperplane<P> trimmed) {
+ final ConvexSubHyperplane<P> trimmed, final SubtreeInitializer<N> subtreeInit) {
if (node.isLeaf()) {
- cutNode(node, trimmed);
+ setNodeCut(node, trimmed, subtreeInit);
} else {
final Split<? extends ConvexSubHyperplane<P>> insertSplit = insert.split(node.getCutHyperplane());
@@ -609,15 +609,30 @@ public abstract class AbstractBSPTree<P extends Point<P>, N extends AbstractBSPT
final Split<? extends ConvexSubHyperplane<P>> trimmedSplit = trimmed.split(node.getCutHyperplane());
if (minus != null) {
- insertRecursive(node.getMinus(), minus, trimmedSplit.getMinus());
+ insertRecursive(node.getMinus(), minus, trimmedSplit.getMinus(), subtreeInit);
}
if (plus != null) {
- insertRecursive(node.getPlus(), plus, trimmedSplit.getPlus());
+ insertRecursive(node.getPlus(), plus, trimmedSplit.getPlus(), subtreeInit);
}
}
}
}
+ /** Return true if the given transform swaps the inside and outside of
+ * the region.
+ *
+ * <p>The default behavior of this method is to return true if the transform
+ * does not preserve spatial orientation (ie, {@link Transform#preservesOrientation()}
+ * is false). Subclasses may need to override this method to implement the correct
+ * behavior for their space and dimension.</p>
+ * @param transform transform to check
+ * @return true if the given transform swaps the interior and exterior of
+ * the region
+ */
+ protected boolean swapsInsideOutside(final Transform<P> transform) {
+ return !transform.preservesOrientation();
+ }
+
/** Transform the subtree rooted as {@code node} recursively.
* @param node the root node of the subtree to transform
* @param t the transform to apply
@@ -970,22 +985,8 @@ public abstract class AbstractBSPTree<P extends Point<P>, N extends AbstractBSPT
/** {@inheritDoc} */
@Override
- public boolean insertCut(final Hyperplane<P> cutter) {
- return tree.insertNodeCut(getSelf(), cutter);
- }
-
- /** {@inheritDoc} */
- @Override
- public boolean clearCut() {
- return tree.removeNodeCut(getSelf());
- }
-
- /** {@inheritDoc} */
- @Override
- public N cut(final Hyperplane<P> cutter) {
- this.insertCut(cutter);
-
- return getSelf();
+ public ConvexSubHyperplane<P> trim(final ConvexSubHyperplane<P> sub) {
+ return getTree().trimToNode(getSelf(), sub);
}
/** {@inheritDoc} */
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractRegionBSPTree.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractRegionBSPTree.java
index 15a1680..b795b15 100644
--- a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractRegionBSPTree.java
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractRegionBSPTree.java
@@ -20,10 +20,12 @@ import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.function.Function;
+import java.util.stream.Stream;
import org.apache.commons.geometry.core.Point;
import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.core.internal.IteratorTransform;
+import org.apache.commons.geometry.core.partitioning.BoundarySource;
import org.apache.commons.geometry.core.partitioning.ConvexSubHyperplane;
import org.apache.commons.geometry.core.partitioning.Hyperplane;
import org.apache.commons.geometry.core.partitioning.HyperplaneBoundedRegion;
@@ -33,16 +35,23 @@ import org.apache.commons.geometry.core.partitioning.SplitLocation;
import org.apache.commons.geometry.core.partitioning.SubHyperplane;
import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor.ClosestFirstVisitor;
-/** {@link BSPTree} specialized for representing regions of space. For example, this
- * class can be used to represent polygons in Euclidean 2D space and polyhedrons
+/** Abstract {@link BSPTree} specialized for representing regions of space. For example,
+ * this class can be used to represent polygons in Euclidean 2D space and polyhedrons
* in Euclidean 3D space.
+ *
+ * <p>This class is not thread safe.</p>
* @param <P> Point implementation type
* @param <N> BSP tree node implementation type
+ * @see HyperplaneBoundedRegion
*/
public abstract class AbstractRegionBSPTree<
P extends Point<P>,
N extends AbstractRegionBSPTree.AbstractRegionNode<P, N>>
extends AbstractBSPTree<P, N> implements HyperplaneBoundedRegion<P> {
+
+ /** The default {@link RegionCutRule}. */
+ private static final RegionCutRule DEFAULT_REGION_CUT_RULE = RegionCutRule.MINUS_INSIDE;
+
/** Value used to indicate an unknown size. */
private static final double UNKNOWN_SIZE = -1.0;
@@ -59,7 +68,7 @@ public abstract class AbstractRegionBSPTree<
* be empty
*/
protected AbstractRegionBSPTree(final boolean full) {
- getRoot().setLocation(full ? RegionLocation.INSIDE : RegionLocation.OUTSIDE);
+ getRoot().setLocationValue(full ? RegionLocation.INSIDE : RegionLocation.OUTSIDE);
}
/** {@inheritDoc} */
@@ -97,7 +106,7 @@ public abstract class AbstractRegionBSPTree<
final N root = getRoot();
root.clearCut();
- root.setLocation(RegionLocation.INSIDE);
+ root.setLocationValue(RegionLocation.INSIDE);
}
/** Modify this instance so that is is completely empty.
@@ -107,7 +116,7 @@ public abstract class AbstractRegionBSPTree<
final N root = getRoot();
root.clearCut();
- root.setLocation(RegionLocation.OUTSIDE);
+ root.setLocationValue(RegionLocation.OUTSIDE);
}
/** {@inheritDoc} */
@@ -137,6 +146,105 @@ public abstract class AbstractRegionBSPTree<
return boundarySize;
}
+ /** Insert a subhyperplane into the tree, using the default {@link RegionCutRule} of
+ * {@link RegionCutRule#MINUS_INSIDE MINUS_INSIDE}.
+ * @param sub the subhyperplane to insert into the tree
+ */
+ public void insert(final SubHyperplane<P> sub) {
+ insert(sub, DEFAULT_REGION_CUT_RULE);
+ }
+
+ /** Insert a subhyperplane into the tree.
+ * @param sub the subhyperplane to insert into the tree
+ * @param cutRule rule used to determine the region locations of new child nodes
+ */
+ public void insert(final SubHyperplane<P> sub, final RegionCutRule cutRule) {
+ insert(sub.toConvex(), cutRule);
+ }
+
+ /** Insert a convex subhyperplane into the tree, using the default {@link RegionCutRule} of
+ * {@link RegionCutRule#MINUS_INSIDE MINUS_INSIDE}.
+ * @param convexSub the convex subhyperplane to insert into the tree
+ */
+ public void insert(final ConvexSubHyperplane<P> convexSub) {
+ insert(convexSub, DEFAULT_REGION_CUT_RULE);
+ }
+
+ /** Insert a convex subhyperplane into the tree.
+ * @param convexSub the convex subhyperplane to insert into the tree
+ * @param cutRule rule used to determine the region locations of new child nodes
+ */
+ public void insert(final ConvexSubHyperplane<P> convexSub, final RegionCutRule cutRule) {
+ insert(convexSub, getSubtreeInitializer(cutRule));
+ }
+
+ /** Insert a set of convex subhyperplanes into the tree, using the default {@link RegionCutRule} of
+ * {@link RegionCutRule#MINUS_INSIDE MINUS_INSIDE}.
+ * @param convexSubs iterable containing a collection of subhyperplanes
+ * to insert into the tree
+ */
+ public void insert(final Iterable<? extends ConvexSubHyperplane<P>> convexSubs) {
+ insert(convexSubs, DEFAULT_REGION_CUT_RULE);
+ }
+
+ /** Insert a set of convex subhyperplanes into the tree.
+ * @param convexSubs iterable containing a collection of subhyperplanes
+ * to insert into the tree
+ * @param cutRule rule used to determine the region locations of new child nodes
+ */
+ public void insert(final Iterable<? extends ConvexSubHyperplane<P>> convexSubs, final RegionCutRule cutRule) {
+ for (final ConvexSubHyperplane<P> convexSub : convexSubs) {
+ insert(convexSub, cutRule);
+ }
+ }
+
+ /** Insert all convex subhyperplanes from the given source into the tree, using the default
+ * {@link RegionCutRule} of {@link RegionCutRule#MINUS_INSIDE MINUS_INSIDE}.
+ * @param boundarySrc source of boundary convex subhyperplanes to insert
+ * into the tree
+ */
+ public void insert(final BoundarySource<? extends ConvexSubHyperplane<P>> boundarySrc) {
+ insert(boundarySrc, DEFAULT_REGION_CUT_RULE);
+ }
+
+ /** Insert all convex subhyperplanes from the given source into the tree.
+ * @param boundarySrc source of boundary convex subhyperplanes to insert
+ * into the tree
+ * @param cutRule rule used to determine the region locations of new child nodes
+ */
+ public void insert(final BoundarySource<? extends ConvexSubHyperplane<P>> boundarySrc,
+ final RegionCutRule cutRule) {
+ try (Stream<? extends ConvexSubHyperplane<P>> stream = boundarySrc.boundaryStream()) {
+ stream.forEach(c -> insert(c, cutRule));
+ }
+ }
+
+ /** Get the subtree initializer to use for the given region cut rule.
+ * @param cutRule the cut rule to get an initializer for
+ * @return the subtree initializer for the given region cut rule
+ */
+ protected SubtreeInitializer<N> getSubtreeInitializer(final RegionCutRule cutRule) {
+ switch (cutRule) {
+ case INHERIT:
+ return root -> {
+ final RegionLocation rootLoc = root.getLocation();
+
+ root.getMinus().setLocationValue(rootLoc);
+ root.getPlus().setLocationValue(rootLoc);
+ };
+ case PLUS_INSIDE:
+ return root -> {
+ root.getMinus().setLocationValue(RegionLocation.OUTSIDE);
+ root.getPlus().setLocationValue(RegionLocation.INSIDE);
+ };
+ default:
+ return root -> {
+ root.getMinus().setLocationValue(RegionLocation.INSIDE);
+ root.getPlus().setLocationValue(RegionLocation.OUTSIDE);
+ };
+ }
+ }
+
/** Return an {@link Iterable} for iterating over the boundaries of the region.
* Each boundary is oriented such that its plus side points to the outside of the
* region. The exact ordering of the boundaries is determined by the internal structure
@@ -220,13 +328,13 @@ public abstract class AbstractRegionBSPTree<
T splitPlus = null;
if (minus != null) {
- minus.getRoot().getPlus().setLocation(RegionLocation.OUTSIDE);
+ minus.getRoot().getPlus().setLocationValue(RegionLocation.OUTSIDE);
minus.condense();
splitMinus = minus.isEmpty() ? null : minus;
}
if (plus != null) {
- plus.getRoot().getMinus().setLocation(RegionLocation.OUTSIDE);
+ plus.getRoot().getMinus().setLocationValue(RegionLocation.OUTSIDE);
plus.condense();
splitPlus = plus.isEmpty() ? null : plus;
@@ -318,11 +426,11 @@ public abstract class AbstractRegionBSPTree<
*/
private void complementRecursive(final AbstractRegionNode<P, N> node) {
if (node != null) {
- final RegionLocation newLoc = (node.getLocationValue() == RegionLocation.INSIDE) ?
+ final RegionLocation newLoc = (node.getLocation() == RegionLocation.INSIDE) ?
RegionLocation.OUTSIDE :
RegionLocation.INSIDE;
- node.setLocation(newLoc);
+ node.setLocationValue(newLoc);
complementRecursive(node.getMinus());
complementRecursive(node.getPlus());
@@ -397,7 +505,8 @@ public abstract class AbstractRegionBSPTree<
new XorOperator<P, N>().apply(a, b, this);
}
- /** Condense this tree by removing redundant subtrees.
+ /** Condense this tree by removing redundant subtrees, returning true if the
+ * tree structure was modified.
*
* <p>This operation can be used to reduce the total number of nodes in the
* tree after performing node manipulations. For example, if two sibling leaf
@@ -406,47 +515,16 @@ public abstract class AbstractRegionBSPTree<
* therefore both merged into their parent node. This method performs this
* simplification process.
* </p>
+ * @return true if the tree structure was modified, otherwise false
*/
- protected void condense() {
- condenseRecursive(getRoot());
- }
-
- /** Recursively condense nodes that have children with homogenous location attributes
- * (eg, both inside, both outside) into single nodes.
- * @param node the root of the subtree to condense
- * @return the location of the successfully condensed subtree or null if no condensing was
- * able to be performed
- */
- private RegionLocation condenseRecursive(final N node) {
- if (node.isLeaf()) {
- return node.getLocation();
- }
-
- final RegionLocation minusLocation = condenseRecursive(node.getMinus());
- final RegionLocation plusLocation = condenseRecursive(node.getPlus());
-
- if (minusLocation != null && plusLocation != null && minusLocation == plusLocation) {
- node.setLocation(minusLocation);
- node.clearCut();
-
- return minusLocation;
- }
-
- return null;
+ public boolean condense() {
+ return new Condenser<P, N>().condense(getRoot());
}
/** {@inheritDoc} */
@Override
protected void copyNodeProperties(final N src, final N dst) {
- dst.setLocation(src.getLocationValue());
- }
-
- /** {@inheritDoc} */
- @Override
- protected void initChildNode(final N parent, final N child, final boolean isPlus) {
- super.initChildNode(parent, child, isPlus);
-
- child.setLocation(isPlus ? RegionLocation.OUTSIDE : RegionLocation.INSIDE);
+ dst.setLocationValue(src.getLocation());
}
/** {@inheritDoc} */
@@ -487,12 +565,36 @@ public abstract class AbstractRegionBSPTree<
return (AbstractRegionBSPTree<P, N>) super.getTree();
}
- /** Get the location of the node. This value will only be non-null for
- * leaf nodes.
- * @return the location of the node; will be null for internal nodes
+ /** Get the location property of the node. Only the locations of leaf nodes are meaningful
+ * as they relate to the region represented by the BSP tree. For example, changing
+ * the location of an internal node will only affect the geometric properties
+ * of the region if the node later becomes a leaf node.
+ * @return the location of the node
*/
public RegionLocation getLocation() {
- return isLeaf() ? location : null;
+ return location;
+ }
+
+ /** Set the location property for the node. If the location is changed, the tree is
+ * invalidated.
+ *
+ * <p>Only the locations of leaf nodes are meaningful
+ * as they relate to the region represented by the BSP tree. For example, changing
+ * the location of an internal node will only affect the geometric properties
+ * of the region if the node later becomes a leaf node.</p>
+ * @param location the location for the node
+ * @throws IllegalArgumentException if {@code location} is not one of
+ * {@link RegionLocation#INSIDE INSIDE} or {@link RegionLocation#OUTSIDE OUTSIDE}
+ */
+ public void setLocation(final RegionLocation location) {
+ if (location != RegionLocation.INSIDE && location != RegionLocation.OUTSIDE) {
+ throw new IllegalArgumentException("Invalid node location: " + location);
+ }
+ if (this.location != location) {
+ this.location = location;
+
+ getTree().invalidate();
+ }
}
/** True if the node is a leaf node and has a location of {@link RegionLocation#INSIDE}.
@@ -500,7 +602,7 @@ public abstract class AbstractRegionBSPTree<
* {@link RegionLocation#INSIDE}
*/
public boolean isInside() {
- return getLocation() == RegionLocation.INSIDE;
+ return isLeaf() && getLocation() == RegionLocation.INSIDE;
}
/** True if the node is a leaf node and has a location of {@link RegionLocation#OUTSIDE}.
@@ -508,7 +610,70 @@ public abstract class AbstractRegionBSPTree<
* {@link RegionLocation#OUTSIDE}
*/
public boolean isOutside() {
- return getLocation() == RegionLocation.OUTSIDE;
+ return isLeaf() && getLocation() == RegionLocation.OUTSIDE;
+ }
+
+ /** Insert a cut into this node, using the default region cut rule of
+ * (@link {@link RegionCutRule#MINUS_INSIDE}.
+ * @param cutter the hyperplane to cut the node's region with
+ * @return true if the cutting hyperplane intersected the node's region, resulting
+ * in the creation of new child nodes
+ * @see #insertCut(Hyperplane, RegionCutRule)
+ */
+ public boolean insertCut(final Hyperplane<P> cutter) {
+ return insertCut(cutter, DEFAULT_REGION_CUT_RULE);
+ }
+
+ /** Insert a cut into this node. If the given hyperplane intersects
+ * this node's region, then the node's cut is set to the {@link ConvexSubHyperplane}
+ * representing the intersection, new plus and minus child leaf nodes
+ * are assigned, and true is returned. If the hyperplane does not intersect
+ * the node's region, then the node's cut and plus and minus child references
+ * are all set to null (ie, it becomes a leaf node) and false is returned. In
+ * either case, any existing cut and/or child nodes are removed by this method.
+ * @param cutter the hyperplane to cut the node's region with
+ * @param cutRule rule used to determine the region locations of newly created
+ * child nodes
+ * @return true if the cutting hyperplane intersected the node's region, resulting
+ * in the creation of new child nodes
+ */
+ public boolean insertCut(final Hyperplane<P> cutter, final RegionCutRule cutRule) {
+ final AbstractRegionBSPTree<P, N> tree = getTree();
+ return tree.cutNode(getSelf(), cutter, tree.getSubtreeInitializer(cutRule));
+ }
+
+ /** Remove the cut from this node. Returns true if the node previously had a cut.
+ * @return true if the node had a cut before the call to this method
+ */
+ public boolean clearCut() {
+ return getTree().removeNodeCut(getSelf());
+ }
+
+ /** Cut this node with the given hyperplane. The same node is returned, regardless of
+ * the outcome of the cut operation. If the operation succeeded, then the node will
+ * have plus and minus child nodes.
+ * @param cutter the hyperplane to cut the node's region with
+ * @return this node
+ * @see #insertCut(Hyperplane)
+ */
+ public N cut(final Hyperplane<P> cutter) {
+ return cut(cutter, DEFAULT_REGION_CUT_RULE);
+ }
+
+ /** Cut this node with the given hyperplane, using {@code cutRule} to determine the region
+ * locations of any new child nodes. The same node is returned, regardless of
+ * the outcome of the cut operation. If the operation succeeded, then the node will
+ * have plus and minus child nodes.
+ * @param cutter the hyperplane to cut the node's region with
+ * @param cutRule rule used to determine the region locations of newly created
+ * child nodes
+ * @return this node
+ * @see #insertCut(Hyperplane, RegionCutRule)
+ */
+ public N cut(final Hyperplane<P> cutter, final RegionCutRule cutRule) {
+ this.insertCut(cutter, cutRule);
+
+ return getSelf();
}
/** Get the portion of the node's cut subhyperplane that lies on the boundary of the
@@ -629,19 +794,13 @@ public abstract class AbstractRegionBSPTree<
cutBoundary = null;
}
- /** Set the location attribute for the node.
- * @param location the location attribute for the node
+ /** Directly set the value of the location property for the node. No input validation
+ * is performed and the tree is not invalidated.
+ * @param locationValue the new location value for the node
+ * @see #setLocation(RegionLocation)
*/
- protected void setLocation(final RegionLocation location) {
- this.location = location;
- }
-
- /** Get the value of the location property, unmodified based on the
- * node's leaf state.
- * @return the value of the location property
- */
- protected RegionLocation getLocationValue() {
- return location;
+ protected void setLocationValue(final RegionLocation locationValue) {
+ this.location = locationValue;
}
}
@@ -842,7 +1001,7 @@ public abstract class AbstractRegionBSPTree<
} else if (node2.isInside()) {
// this region is inside of tree2 and so cannot be in the result region
final N output = outputNode();
- output.setLocation(RegionLocation.OUTSIDE);
+ output.setLocationValue(RegionLocation.OUTSIDE);
return output;
}
@@ -886,6 +1045,54 @@ public abstract class AbstractRegionBSPTree<
}
}
+ /** Internal class used to perform tree condense operations.
+ * @param <P> Point implementation type
+ * @param <N> BSP tree node implementation type
+ */
+ private static final class Condenser<P extends Point<P>, N extends AbstractRegionNode<P, N>> {
+ /** Flag set to true if the tree was modified during the operation. */
+ private boolean modifiedTree;
+
+ /** Condense the nodes in the subtree rooted at the given node. Redundant child nodes are
+ * removed. The tree is invalidated if the tree structure was modified.
+ * @param node the root node of the subtree to condense
+ * @return true if the tree was modified.
+ */
+ boolean condense(final N node) {
+ modifiedTree = false;
+
+ condenseRecursive(node);
+
+ return modifiedTree;
+ }
+
+ /** Recursively condense nodes that have children with homogenous location attributes
+ * (eg, both inside, both outside) into single nodes.
+ * @param node the root of the subtree to condense
+ * @return the location of the successfully condensed subtree or null if no condensing was
+ * able to be performed
+ */
+ private RegionLocation condenseRecursive(final N node) {
+ if (node.isLeaf()) {
+ return node.getLocation();
+ }
+
+ final RegionLocation minusLocation = condenseRecursive(node.getMinus());
+ final RegionLocation plusLocation = condenseRecursive(node.getPlus());
+
+ if (minusLocation != null && plusLocation != null && minusLocation == plusLocation) {
+ node.setLocationValue(minusLocation);
+ node.clearCut();
+
+ modifiedTree = true;
+
+ return minusLocation;
+ }
+
+ return null;
+ }
+ }
+
/** Class that iterates over the boundary convex subhyperplanes from a set of region nodes.
* @param <P> Point implementation type
* @param <C> Boundary convex subhyperplane implementation type
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/BSPSubtree.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/BSPSubtree.java
index a09eff3..a3eb661 100644
--- a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/BSPSubtree.java
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/BSPSubtree.java
@@ -22,6 +22,7 @@ import org.apache.commons.geometry.core.Point;
* themselves as well as each node in a tree.
* @param <P> Point implementation type
* @param <N> Node implementation type
+ * @see BSPTree
*/
public interface BSPSubtree<P extends Point<P>, N extends BSPTree.Node<P, N>> {
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/BSPTree.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/BSPTree.java
index 50dd742..c359173 100644
--- a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/BSPTree.java
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/BSPTree.java
@@ -18,14 +18,25 @@ package org.apache.commons.geometry.core.partitioning.bsp;
import org.apache.commons.geometry.core.Point;
import org.apache.commons.geometry.core.Transform;
-import org.apache.commons.geometry.core.partitioning.BoundarySource;
import org.apache.commons.geometry.core.partitioning.ConvexSubHyperplane;
import org.apache.commons.geometry.core.partitioning.Hyperplane;
-import org.apache.commons.geometry.core.partitioning.SubHyperplane;
-/** Interface for Binary Space Partitioning (BSP) trees.
+/** Interface for Binary Space Partitioning (BSP) trees. BSP trees are spatial data
+ * structures that recursively subdivide a space using hyperplanes. They can be used
+ * for a wide variety of purposes, such as representing arbitrary polytopes, storing
+ * data for fast spatial lookups, determining the correct rendering order for objects
+ * in a 3D scene, and so on.
+ *
+ * <p>This interface contains a number of methods for extracting information from existing
+ * trees, but it does not include methods for constructing trees or modifying tree structure.
+ * This is due to the large number of possible use cases for BSP trees. Each use case is likely
+ * to have its own specific methods and rules for tree construction, making it difficult to define
+ * a single API at this level. Thus, it is left to implementation classes to define their own
+ * API for tree construction and modification.</p>
+ *
* @param <P> Point implementation type
* @param <N> Node implementation type
+ * @see <a href="https://en.wikipedia.org/wiki/Binary_space_partitioning">Binary space partitioning</a>
*/
public interface BSPTree<P extends Point<P>, N extends BSPTree.Node<P, N>>
extends BSPSubtree<P, N> {
@@ -33,7 +44,7 @@ public interface BSPTree<P extends Point<P>, N extends BSPTree.Node<P, N>>
/** Enum specifying possible behaviors when a point used to locate a node
* falls directly on the cut subhyperplane of an internal node.
*/
- enum NodeCutRule {
+ enum FindNodeCutRule {
/** Choose the minus child of the internal node and continue searching.
* This behavior will result in a leaf node always being returned by the
@@ -60,14 +71,14 @@ public interface BSPTree<P extends Point<P>, N extends BSPTree.Node<P, N>>
/** Find a node in this subtree containing the given point or its interior or boundary.
* When a point lies directly on the cut of an internal node, the minus child of the
- * cut is chosen. This is equivalent to {@code subtree.findNode(pt, NodeCutRule.MINUS)}
+ * cut is chosen. This is equivalent to {@code subtree.findNode(pt, FindNodeCutRule.MINUS)}
* and always returns a leaf node.
* @param pt test point used to locate a node in the tree
* @return leaf node containing the point on its interior or boundary
- * @see #findNode(Point, NodeCutRule)
+ * @see #findNode(Point, FindNodeCutRule)
*/
default N findNode(P pt) {
- return findNode(pt, NodeCutRule.MINUS);
+ return findNode(pt, FindNodeCutRule.MINUS);
}
/** Find a node in this subtree containing the given point on it interior or boundary. The
@@ -76,9 +87,9 @@ public interface BSPTree<P extends Point<P>, N extends BSPTree.Node<P, N>>
* the search should continue with the minus child, the plus child, or end with the internal
* node. The {@code cutRule} argument specifies what should happen in this case.
* <ul>
- * <li>{@link NodeCutRule#MINUS} - continue the search in the minus subtree</li>
- * <li>{@link NodeCutRule#PLUS} - continue the search in the plus subtree</li>
- * <li>{@link NodeCutRule#NODE} - stop the search and return the internal node</li>
+ * <li>{@link FindNodeCutRule#MINUS} - continue the search in the minus subtree</li>
+ * <li>{@link FindNodeCutRule#PLUS} - continue the search in the plus subtree</li>
+ * <li>{@link FindNodeCutRule#NODE} - stop the search and return the internal node</li>
* </ul>
* @param pt test point used to locate a node in the tree
* @param cutRule value used to determine the search behavior when the test point lies
@@ -86,29 +97,7 @@ public interface BSPTree<P extends Point<P>, N extends BSPTree.Node<P, N>>
* @return node containing the point on its interior or boundary
* @see #findNode(Point)
*/
- N findNode(P pt, NodeCutRule cutRule);
-
- /** Insert a subhyperplane into the tree.
- * @param sub the subhyperplane to insert into the tree
- */
- void insert(SubHyperplane<P> sub);
-
- /** Insert a convex subhyperplane into the tree.
- * @param convexSub the convex subhyperplane to insert into the tree
- */
- void insert(ConvexSubHyperplane<P> convexSub);
-
- /** Insert a set of convex subhyperplanes into the tree.
- * @param convexSubs iterable containing a collection of subhyperplanes
- * to insert into the tree
- */
- void insert(Iterable<? extends ConvexSubHyperplane<P>> convexSubs);
-
- /** Insert all convex subhyperplanes from the given source into the tree.
- * @param boundarySrc source of boundary convex subhyperplanes to insert
- * into the tree
- */
- void insert(BoundarySource<? extends ConvexSubHyperplane<P>> boundarySrc);
+ N findNode(P pt, FindNodeCutRule cutRule);
/** Make the current instance a deep copy of the argument.
* @param src the tree to copy
@@ -202,31 +191,14 @@ public interface BSPTree<P extends Point<P>, N extends BSPTree.Node<P, N>>
*/
boolean isPlus();
- /** Insert a cut into this node. If the given hyperplane intersects
- * this node's region, then the node's cut is set to the {@link ConvexSubHyperplane}
- * representing the intersection, new plus and minus child leaf nodes
- * are assigned, and true is returned. If the hyperplane does not intersect
- * the node's region, then the node's cut and plus and minus child references
- * are all set to null (ie, it becomes a leaf node) and false is returned. In
- * either case, any existing cut and/or child nodes are removed by this method.
- * @param cutter the hyperplane to cut the node's region with
- * @return true if the cutting hyperplane intersected the node's region, resulting
- * in the creation of new child nodes
- */
- boolean insertCut(Hyperplane<P> cutter);
-
- /** Remove the cut from this node. Returns true if the node previously had a cut.
- * @return true if the node had a cut before the call to this method
- */
- boolean clearCut();
-
- /** Cut this node with the given hyperplane. The same node is returned, regardless of
- * the outcome of the cut operation. If the operation succeeded, then the node will
- * have plus and minus child nodes.
- * @param cutter the hyperplane to cut the node's region with
- * @return this node
- * @see #insertCut(Hyperplane)
+ /** Trim the given subhyperplane to the region defined by this node by cutting
+ * the argument with the cut hyperplanes (binary partitioners) of all parent nodes
+ * up to the root. Null is returned if the subhyperplane lies outside of the region
+ * defined by the node.
+ * @param sub the convex subhyperplane to trim
+ * @return the trimmed convex subhyperplane or null if no part of the argument lies
+ * within the node's region
*/
- N cut(Hyperplane<P> cutter);
+ ConvexSubHyperplane<P> trim(ConvexSubHyperplane<P> sub);
}
}
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/RegionCutRule.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/RegionCutRule.java
new file mode 100644
index 0000000..7369c1d
--- /dev/null
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/RegionCutRule.java
@@ -0,0 +1,41 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.geometry.core.partitioning.bsp;
+
+/** Enum describing the possible behaviors when cutting a region BSP tree node
+ * with a hyperplane to produce two new child nodes.
+ */
+public enum RegionCutRule {
+
+ /** Set the minus side of the cutting hyperplane as the inside of the region
+ * and the plus side as the outside. This is the default convention for hyperplanes.
+ */
+ MINUS_INSIDE,
+
+ /** Set the plus side of the cutting hyperplane as the inside of the region and
+ * the minus side as the outside.
+ */
+ PLUS_INSIDE,
+
+ /** Set both child nodes to the same location as the parent node. For example, if the
+ * parent node is marked as inside, both child nodes will be marked as inside. Similarly
+ * if the parent node is marked as outside, both child nodes will be marked as outside.
+ * This rule can be used to modify the tree structure (to perhaps produce a more efficient,
+ * balanced tree) without changing the represented region.
+ */
+ INHERIT
+}
diff --git a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partition/test/AttributeBSPTree.java b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partition/test/AttributeBSPTree.java
index 09c8b6f..2b83824 100644
--- a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partition/test/AttributeBSPTree.java
+++ b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partition/test/AttributeBSPTree.java
@@ -17,6 +17,7 @@
package org.apache.commons.geometry.core.partition.test;
import org.apache.commons.geometry.core.Point;
+import org.apache.commons.geometry.core.partitioning.Hyperplane;
import org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree;
/** Simple {@link BSPTree} implementation allowing arbitrary values to be
@@ -54,15 +55,6 @@ public class AttributeBSPTree<P extends Point<P>, T>
/** {@inheritDoc} */
@Override
- protected void initChildNode(final AttributeNode<P, T> parent, final AttributeNode<P, T> child,
- final boolean isPlus) {
- super.initChildNode(parent, child, isPlus);
-
- child.setAttribute(initialNodeAttribute);
- }
-
- /** {@inheritDoc} */
- @Override
protected void copyNodeProperties(final AttributeNode<P, T> src, final AttributeNode<P, T> dst) {
dst.setAttribute(src.getAttribute());
}
@@ -90,6 +82,24 @@ public class AttributeBSPTree<P extends Point<P>, T>
return (AttributeBSPTree<P, T>) super.getTree();
}
+ /** Cut this node with the given hyperplane. If the hyperplane intersects the node's region,
+ * then the node becomes an internal node with two child leaf node. If the hyperplane does
+ * not intersect the node's region, then the node is made a leaf node. The same node is
+ * returned, regardless of the outcome of the cut operation.
+ * @param cutter hyperplane to cut the node with
+ * @return this node
+ */
+ public AttributeNode<P, T> cut(final Hyperplane<P> cutter) {
+ final AttributeBSPTree<P, T> tree = getTree();
+
+ tree.cutNode(getSelf(), cutter, root -> {
+ root.getMinus().setAttribute(tree.initialNodeAttribute);
+ root.getPlus().setAttribute(tree.initialNodeAttribute);
+ });
+
+ return this;
+ }
+
/** Get the attribute associated with this node.
* @return the attribute associated with this node
*/
@@ -100,7 +110,7 @@ public class AttributeBSPTree<P extends Point<P>, T>
/** Set the attribute associated with this node.
* @param attribute the attribute to associate with this node
*/
- public void setAttribute(T attribute) {
+ public void setAttribute(final T attribute) {
this.attribute = attribute;
}
diff --git a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partition/test/TestBSPTree.java b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partition/test/TestBSPTree.java
index 81a4f1e..65cdf29 100644
--- a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partition/test/TestBSPTree.java
+++ b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partition/test/TestBSPTree.java
@@ -16,7 +16,10 @@
*/
package org.apache.commons.geometry.core.partition.test;
+import org.apache.commons.geometry.core.partitioning.BoundarySource;
+import org.apache.commons.geometry.core.partitioning.ConvexSubHyperplane;
import org.apache.commons.geometry.core.partitioning.Hyperplane;
+import org.apache.commons.geometry.core.partitioning.SubHyperplane;
import org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree;
/** BSP Tree implementation class for testing purposes.
@@ -29,12 +32,28 @@ public class TestBSPTree extends AbstractBSPTree<TestPoint2D, TestBSPTree.TestNo
return new TestNode(this);
}
+ public void insert(final SubHyperplane<TestPoint2D> sub) {
+ insert(sub.toConvex());
+ }
+
+ public void insert(final ConvexSubHyperplane<TestPoint2D> sub) {
+ insert(sub, root -> { });
+ }
+
+ public void insert(final Iterable<? extends ConvexSubHyperplane<TestPoint2D>> subs) {
+ subs.forEach(this::insert);
+ }
+
+ public void insert(final BoundarySource<TestLineSegment> src) {
+ src.boundaryStream().forEach(this::insert);
+ }
+
/** {@inheritDoc}
*
* <p>Exposed as public for testing.</p>
*/
@Override
- public void splitIntoTrees(Hyperplane<TestPoint2D> splitter,
+ public void splitIntoTrees(final Hyperplane<TestPoint2D> splitter,
final AbstractBSPTree<TestPoint2D, TestBSPTree.TestNode> minus,
final AbstractBSPTree<TestPoint2D, TestBSPTree.TestNode> plus) {
@@ -48,6 +67,27 @@ public class TestBSPTree extends AbstractBSPTree<TestPoint2D, TestBSPTree.TestNo
super(tree);
}
+ /** Cut this node with the given hyperplane. If the hyperplane intersects the node's region,
+ * then the node becomes an internal node with two child leaf node. If the hyperplane does
+ * not intersect the node's region, then the node is made a leaf node. The same node is
+ * returned, regardless of the outcome of the cut operation.
+ * @param cutter hyperplane to cut the node with
+ * @return this node
+ */
+ public TestNode cut(final Hyperplane<TestPoint2D> cutter) {
+ insertCut(cutter);
+
+ return this;
+ }
+
+ public boolean insertCut(final Hyperplane<TestPoint2D> cutter) {
+ return ((TestBSPTree) getTree()).cutNode(getSelf(), cutter, root -> { });
+ }
+
+ public boolean clearCut() {
+ return ((TestBSPTree) getTree()).removeNodeCut(getSelf());
+ }
+
/** {@inheritDoc} */
@Override
protected TestNode getSelf() {
diff --git a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partition/test/TestRegionBSPTree.java b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partition/test/TestRegionBSPTree.java
index a8f052e..d4cbf5c 100644
--- a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partition/test/TestRegionBSPTree.java
+++ b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partition/test/TestRegionBSPTree.java
@@ -22,6 +22,7 @@ import org.apache.commons.geometry.core.partitioning.Hyperplane;
import org.apache.commons.geometry.core.partitioning.Split;
import org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree;
import org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree;
+import org.apache.commons.geometry.core.partitioning.bsp.RegionCutRule;
/** Region BSP Tree implementation class for testing purposes.
*/
@@ -38,9 +39,8 @@ public final class TestRegionBSPTree extends AbstractRegionBSPTree<TestPoint2D,
/**
* Expose the direct node cut method for easier creation of test tree structures.
*/
- @Override
public void cutNode(final TestRegionNode node, final ConvexSubHyperplane<TestPoint2D> cut) {
- super.cutNode(node, cut);
+ super.setNodeCut(node, cut, getSubtreeInitializer(RegionCutRule.MINUS_INSIDE));
}
/** {@inheritDoc} */
@@ -52,8 +52,8 @@ public final class TestRegionBSPTree extends AbstractRegionBSPTree<TestPoint2D,
/** {@inheritDoc} */
@Override
protected RegionSizeProperties<TestPoint2D> computeRegionSizeProperties() {
- // return a set of stub values
- return new RegionSizeProperties<>(1, TestPoint2D.ZERO);
+ // return a set of stub values
+ return new RegionSizeProperties<>(1234, new TestPoint2D(12, 34));
}
/** {@inheritDoc} */
diff --git a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractBSPTreeTest.java b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractBSPTreeTest.java
index 39e6a11..8885be3 100644
--- a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractBSPTreeTest.java
+++ b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractBSPTreeTest.java
@@ -36,7 +36,7 @@ import org.apache.commons.geometry.core.partition.test.TestLineSegmentCollection
import org.apache.commons.geometry.core.partition.test.TestPoint2D;
import org.apache.commons.geometry.core.partition.test.TestTransform2D;
import org.apache.commons.geometry.core.partitioning.BoundarySource;
-import org.apache.commons.geometry.core.partitioning.bsp.BSPTree.NodeCutRule;
+import org.apache.commons.geometry.core.partitioning.bsp.BSPTree.FindNodeCutRule;
import org.junit.Assert;
import org.junit.Test;
@@ -355,15 +355,15 @@ public class AbstractBSPTreeTest {
}
for (TestPoint2D pt : testPoints) {
- Assert.assertSame(root, tree.findNode(pt, NodeCutRule.NODE));
+ Assert.assertSame(root, tree.findNode(pt, FindNodeCutRule.NODE));
}
for (TestPoint2D pt : testPoints) {
- Assert.assertSame(root, tree.findNode(pt, NodeCutRule.MINUS));
+ Assert.assertSame(root, tree.findNode(pt, FindNodeCutRule.MINUS));
}
for (TestPoint2D pt : testPoints) {
- Assert.assertSame(root, tree.findNode(pt, NodeCutRule.PLUS));
+ Assert.assertSame(root, tree.findNode(pt, FindNodeCutRule.PLUS));
}
}
@@ -427,7 +427,7 @@ public class AbstractBSPTreeTest {
TestNode underDiagonal = diagonalCut.getPlus();
TestNode aboveDiagonal = diagonalCut.getMinus();
- NodeCutRule cutBehavior = NodeCutRule.NODE;
+ FindNodeCutRule cutBehavior = FindNodeCutRule.NODE;
// act/assert
Assert.assertSame(root, tree.findNode(new TestPoint2D(0, 0), cutBehavior));
@@ -467,7 +467,7 @@ public class AbstractBSPTreeTest {
TestNode underDiagonal = diagonalCut.getPlus();
TestNode aboveDiagonal = diagonalCut.getMinus();
- NodeCutRule cutBehavior = NodeCutRule.MINUS;
+ FindNodeCutRule cutBehavior = FindNodeCutRule.MINUS;
// act/assert
Assert.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(0, 0), cutBehavior));
@@ -507,7 +507,7 @@ public class AbstractBSPTreeTest {
TestNode underDiagonal = diagonalCut.getPlus();
TestNode aboveDiagonal = diagonalCut.getMinus();
- NodeCutRule cutBehavior = NodeCutRule.PLUS;
+ FindNodeCutRule cutBehavior = FindNodeCutRule.PLUS;
// act/assert
Assert.assertSame(minusY, tree.findNode(new TestPoint2D(0, 0), cutBehavior));
@@ -1244,6 +1244,41 @@ public class AbstractBSPTreeTest {
}
@Test
+ public void testNodeTrim() {
+ // arrange
+ TestBSPTree tree = new TestBSPTree();
+ tree.getRoot().cut(TestLine.Y_AXIS)
+ .getPlus()
+ .cut(new TestLine(new TestPoint2D(0, 0), new TestPoint2D(1, 1)))
+ .getPlus()
+ .cut(new TestLine(new TestPoint2D(1.5, 1.5), new TestPoint2D(2, 1)));
+
+ TestNode root = tree.getRoot();
+ TestNode plus = root.getPlus();
+ TestNode plusMinus = plus.getMinus();
+ TestNode plusPlusPlus = plus.getPlus().getPlus();
+
+ TestLineSegment xAxisSeg = TestLine.X_AXIS.span();
+ TestLineSegment shortSeg = new TestLineSegment(new TestPoint2D(2, 0), new TestPoint2D(2, 2));
+
+ // act/assert
+ Assert.assertSame(xAxisSeg, root.trim(xAxisSeg));
+ Assert.assertSame(shortSeg, root.trim(shortSeg));
+
+ PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(0, Double.POSITIVE_INFINITY, TestLine.X_AXIS),
+ (TestLineSegment) plus.trim(xAxisSeg));
+ Assert.assertSame(shortSeg, plus.trim(shortSeg));
+
+ Assert.assertNull(plusMinus.trim(xAxisSeg));
+ Assert.assertNull(plusMinus.trim(shortSeg));
+
+ PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(0, 3, TestLine.X_AXIS),
+ (TestLineSegment) plusPlusPlus.trim(xAxisSeg));
+ PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(new TestPoint2D(2, 0), new TestPoint2D(2, 1)),
+ (TestLineSegment) plusPlusPlus.trim(shortSeg));
+ }
+
+ @Test
public void testCopy_rootOnly() {
// arrange
TestBSPTree tree = new TestBSPTree();
@@ -1274,9 +1309,7 @@ public class AbstractBSPTreeTest {
// assert
Assert.assertNotSame(tree, copy);
-
assertNodesCopiedRecursive(tree.getRoot(), copy.getRoot());
-
Assert.assertEquals(tree.count(), copy.count());
}
@@ -1522,7 +1555,6 @@ public class AbstractBSPTreeTest {
Assert.assertEquals(1, segments.size());
TestLineSegment seg = segments.get(0);
-
PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.NEGATIVE_INFINITY, 2), seg.getStartPoint());
PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.POSITIVE_INFINITY, 2), seg.getEndPoint());
}
@@ -1902,7 +1934,7 @@ public class AbstractBSPTreeTest {
for (int x = min; x <= max; ++x) {
for (int y = min; y <= max; ++y) {
TestPoint2D pt = new TestPoint2D(x, y);
- TestNode node = tree.findNode(pt, NodeCutRule.NODE);
+ TestNode node = tree.findNode(pt, FindNodeCutRule.NODE);
map.put(pt, node);
}
@@ -1925,7 +1957,7 @@ public class AbstractBSPTreeTest {
TestPoint2D transformedPt = transform.apply(pt);
String msg = "Expected transformed point " + transformedPt + " to resolve to node " + expectedNode;
- Assert.assertSame(msg, expectedNode, transformedTree.findNode(transformedPt, NodeCutRule.NODE));
+ Assert.assertSame(msg, expectedNode, transformedTree.findNode(transformedPt, FindNodeCutRule.NODE));
}
}
diff --git a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractRegionBSPTreeBooleanTest.java b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractRegionBSPTreeBooleanTest.java
new file mode 100644
index 0000000..999c79d
--- /dev/null
+++ b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractRegionBSPTreeBooleanTest.java
@@ -0,0 +1,695 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.geometry.core.partitioning.bsp;
+
+import java.util.Arrays;
+import java.util.function.Supplier;
+
+import org.apache.commons.geometry.core.partition.test.PartitionTestUtils;
+import org.apache.commons.geometry.core.partition.test.TestLine;
+import org.apache.commons.geometry.core.partition.test.TestLineSegment;
+import org.apache.commons.geometry.core.partition.test.TestPoint2D;
+import org.apache.commons.geometry.core.partition.test.TestRegionBSPTree;
+import org.junit.Test;
+
+public class AbstractRegionBSPTreeBooleanTest {
+
+ @Test
+ public void testUnion_singleNodeTrees() {
+ // act/assert
+ unionChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
+ .full(false)
+ .empty(true)
+ .count(1)
+ .check();
+
+ unionChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
+ .full(true)
+ .empty(false)
+ .count(1)
+ .check();
+
+ unionChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::fullTree)
+ .full(true)
+ .empty(false)
+ .count(1)
+ .check();
+
+ unionChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::fullTree)
+ .full(true)
+ .empty(false)
+ .count(1)
+ .check();
+ }
+
+ @Test
+ public void testUnion_simpleCrossingCuts() {
+ // act/assert
+ unionChecker(AbstractRegionBSPTreeBooleanTest::xAxisTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
+ .full(false)
+ .empty(false)
+ .count(3)
+ .check();
+
+ unionChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::xAxisTree)
+ .full(false)
+ .empty(false)
+ .count(3)
+ .check();
+
+ unionChecker(AbstractRegionBSPTreeBooleanTest::yAxisTree, AbstractRegionBSPTreeBooleanTest::fullTree)
+ .full(true)
+ .empty(false)
+ .count(1)
+ .check();
+
+ unionChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::yAxisTree)
+ .full(true)
+ .empty(false)
+ .count(1)
+ .check();
+
+ unionChecker(AbstractRegionBSPTreeBooleanTest::xAxisTree, AbstractRegionBSPTreeBooleanTest::yAxisTree)
+ .full(false)
+ .empty(false)
+ .inside(new TestPoint2D(1, 1), new TestPoint2D(-1, 1), new TestPoint2D(-1, -1))
+ .outside(new TestPoint2D(1, -1))
+ .boundary(TestPoint2D.ZERO)
+ .count(5)
+ .check(t -> {
+ TestLineSegment seg = (TestLineSegment) t.getRoot().getPlus().getCut();
+
+ PartitionTestUtils.assertPointsEqual(new TestPoint2D(0.0, Double.NEGATIVE_INFINITY), seg.getStartPoint());
+ PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, seg.getEndPoint());
+ });
+ }
+
+ @Test
+ public void testUnion_mixedCutRules() {
+ // arrange
+ Supplier<TestRegionBSPTree> r1 = () -> {
+ TestRegionBSPTree tree = new TestRegionBSPTree(false);
+ tree.insert(TestLine.X_AXIS.span(), RegionCutRule.PLUS_INSIDE);
+ tree.insert(new TestLine(new TestPoint2D(5, 0), new TestPoint2D(5, 1)).span(), RegionCutRule.INHERIT);
+
+ return tree;
+ };
+
+ Supplier<TestRegionBSPTree> r2 = () -> {
+ TestRegionBSPTree tree = new TestRegionBSPTree(false);
+ tree.insert(TestLine.Y_AXIS.span(), RegionCutRule.MINUS_INSIDE);
+
+ return tree;
+ };
+
+ // act/assert
+ // Note that the tree node count is different from other tests because one input tree is not condensed.
+ // However, the resulting regions are equivalent.
+ unionChecker(r1, r2)
+ .full(false)
+ .empty(false)
+ .inside(new TestPoint2D(1, -1), new TestPoint2D(-1, 1), new TestPoint2D(-1, -1))
+ .outside(new TestPoint2D(1, 1), new TestPoint2D(10, 10))
+ .boundary(TestPoint2D.ZERO)
+ .count(7)
+ .check(t -> {
+ TestLineSegment seg = (TestLineSegment) t.getRoot().getMinus().getMinus().getCut();
+
+ PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, seg.getStartPoint());
+ PartitionTestUtils.assertPointsEqual(new TestPoint2D(0.0, Double.POSITIVE_INFINITY), seg.getEndPoint());
+ });
+ }
+
+ @Test
+ public void testUnion_boxTreeWithSingleCutTree() {
+ // arrange
+ Supplier<TestRegionBSPTree> boxFactory = () -> {
+ TestRegionBSPTree box = fullTree();
+ insertBox(box, TestPoint2D.ZERO, new TestPoint2D(2, -4));
+ return box;
+ };
+
+ Supplier<TestRegionBSPTree> horizonalFactory = () -> {
+ TestRegionBSPTree horizontal = fullTree();
+ horizontal.getRoot().insertCut(new TestLine(new TestPoint2D(2, 2), new TestPoint2D(0, 2)));
+
+ return horizontal;
+ };
+
+ // act/assert
+ unionChecker(horizonalFactory, boxFactory)
+ .count(3)
+ .inside(TestPoint2D.ZERO, new TestPoint2D(1, 1), new TestPoint2D(1, -1))
+ .outside(new TestPoint2D(0, 3), new TestPoint2D(3, 3))
+ .boundary(new TestPoint2D(-1, 2), new TestPoint2D(3, 2))
+ .check();
+ }
+
+ @Test
+ public void testUnion_treeWithComplement() {
+ // arrange
+ Supplier<TestRegionBSPTree> treeFactory = () -> {
+ TestRegionBSPTree t = fullTree();
+ insertSkewedBowtie(t);
+
+ return t;
+ };
+ Supplier<TestRegionBSPTree> complementFactory = () -> {
+ TestRegionBSPTree t = treeFactory.get();
+ t.complement();
+
+ return t;
+ };
+
+ // act/assert
+ unionChecker(treeFactory, complementFactory)
+ .full(true)
+ .empty(false)
+ .count(1)
+ .check();
+ }
+
+ @Test
+ public void testIntersection_singleNodeTrees() {
+ // act/assert
+ intersectionChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
+ .full(false)
+ .empty(true)
+ .count(1)
+ .check();
+
+ intersectionChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
+ .full(false)
+ .empty(true)
+ .count(1)
+ .check();
+
+ intersectionChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::fullTree)
+ .full(false)
+ .empty(true)
+ .count(1)
+ .check();
+
+ intersectionChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::fullTree)
+ .full(true)
+ .empty(false)
+ .count(1)
+ .check();
+ }
+
+ @Test
+ public void testIntersection_simpleCrossingCuts() {
+ // act/assert
+ intersectionChecker(AbstractRegionBSPTreeBooleanTest::xAxisTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
+ .full(false)
+ .empty(true)
+ .count(1)
+ .check();
+
+ intersectionChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::xAxisTree)
+ .full(false)
+ .empty(true)
+ .count(1)
+ .check();
+
+ intersectionChecker(AbstractRegionBSPTreeBooleanTest::yAxisTree, AbstractRegionBSPTreeBooleanTest::fullTree)
+ .full(false)
+ .empty(false)
+ .inside(new TestPoint2D(-1, 1), new TestPoint2D(-1, -1))
+ .outside(new TestPoint2D(1, 1), new TestPoint2D(1, -1))
+ .boundary(new TestPoint2D(0, 1), new TestPoint2D(0, -1))
+ .count(3)
+ .check();
+
+ intersectionChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::yAxisTree)
+ .full(false)
+ .empty(false)
+ .inside(new TestPoint2D(-1, 1), new TestPoint2D(-1, -1))
+ .outside(new TestPoint2D(1, 1), new TestPoint2D(1, -1))
+ .boundary(new TestPoint2D(0, 1), new TestPoint2D(0, -1))
+ .count(3)
+ .check();
+
+ intersectionChecker(AbstractRegionBSPTreeBooleanTest::xAxisTree, AbstractRegionBSPTreeBooleanTest::yAxisTree)
+ .full(false)
+ .empty(false)
+ .inside(new TestPoint2D(-1, 1))
+ .outside(new TestPoint2D(1, 1), new TestPoint2D(1, -1), new TestPoint2D(-1, -1))
+ .boundary(TestPoint2D.ZERO)
+ .count(5)
+ .check(t -> {
+ TestLineSegment seg = (TestLineSegment) t.getRoot().getMinus().getCut();
+
+ PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, seg.getStartPoint());
+ PartitionTestUtils.assertPointsEqual(new TestPoint2D(0.0, Double.POSITIVE_INFINITY), seg.getEndPoint());
+ });
+ }
+
+ @Test
+ public void testIntersection_boxTreeWithSingleCutTree() {
+ // arrange
+ Supplier<TestRegionBSPTree> boxFactory = () -> {
+ TestRegionBSPTree box = fullTree();
+ insertBox(box, TestPoint2D.ZERO, new TestPoint2D(2, -4));
+ return box;
+ };
+
+ Supplier<TestRegionBSPTree> horizonalFactory = () -> {
+ TestRegionBSPTree horizontal = fullTree();
+ horizontal.getRoot().insertCut(new TestLine(new TestPoint2D(2, -2), new TestPoint2D(0, -2)));
+
+ return horizontal;
+ };
+
+ // act/assert
+ intersectionChecker(horizonalFactory, boxFactory)
+ .inside(new TestPoint2D(1, -3))
+ .outside(new TestPoint2D(1, -1), new TestPoint2D(-1, -3),
+ new TestPoint2D(1, -5), new TestPoint2D(3, -3))
+ .boundary(new TestPoint2D(0, -2), new TestPoint2D(2, -2),
+ new TestPoint2D(0, -4), new TestPoint2D(2, -4))
+ .count(9)
+ .check();
+ }
+
+ @Test
+ public void testIntersection_treeWithComplement() {
+ // arrange
+ Supplier<TestRegionBSPTree> treeFactory = () -> {
+ TestRegionBSPTree t = fullTree();
+ insertSkewedBowtie(t);
+
+ return t;
+ };
+ Supplier<TestRegionBSPTree> complementFactory = () -> {
+ TestRegionBSPTree t = treeFactory.get();
+ t.complement();
+
+ return t;
+ };
+
+ // act/assert
+ intersectionChecker(treeFactory, complementFactory)
+ .full(false)
+ .empty(true)
+ .count(1)
+ .check();
+ }
+
+ @Test
+ public void testDifference_singleNodeTrees() {
+ // act/assert
+ differenceChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
+ .full(false)
+ .empty(true)
+ .count(1)
+ .check();
+
+ differenceChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
+ .full(true)
+ .empty(false)
+ .count(1)
+ .check();
+
+ differenceChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::fullTree)
+ .full(false)
+ .empty(true)
+ .count(1)
+ .check();
+
+ differenceChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::fullTree)
+ .full(false)
+ .empty(true)
+ .count(1)
+ .check();
+ }
+
+ @Test
+ public void testDifference_simpleCrossingCuts() {
+ // act/assert
+ differenceChecker(AbstractRegionBSPTreeBooleanTest::xAxisTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
+ .full(false)
+ .empty(false)
+ .inside(new TestPoint2D(0, 1))
+ .outside(new TestPoint2D(0, -1))
+ .boundary(TestPoint2D.ZERO)
+ .count(3)
+ .check();
+
+ differenceChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::xAxisTree)
+ .full(false)
+ .empty(true)
+ .count(1)
+ .check();
+
+ differenceChecker(AbstractRegionBSPTreeBooleanTest::yAxisTree, AbstractRegionBSPTreeBooleanTest::fullTree)
+ .full(false)
+ .empty(true)
+ .count(1)
+ .check();
+
+ differenceChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::yAxisTree)
+ .full(false)
+ .empty(false)
+ .inside(new TestPoint2D(1, 1), new TestPoint2D(1, -1))
+ .outside(new TestPoint2D(-1, 1), new TestPoint2D(-1, -1))
+ .boundary(new TestPoint2D(0, 1), new TestPoint2D(0, -1))
+ .count(3)
+ .check();
+
+ differenceChecker(AbstractRegionBSPTreeBooleanTest::xAxisTree, AbstractRegionBSPTreeBooleanTest::yAxisTree)
+ .full(false)
+ .empty(false)
+ .inside(new TestPoint2D(1, 1))
+ .outside(new TestPoint2D(-1, 1), new TestPoint2D(1, -1), new TestPoint2D(-1, -1))
+ .boundary(TestPoint2D.ZERO)
+ .count(5)
+ .check(t -> {
+ TestLineSegment seg = (TestLineSegment) t.getRoot().getMinus().getCut();
+
+ PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, seg.getStartPoint());
+ PartitionTestUtils.assertPointsEqual(new TestPoint2D(0.0, Double.POSITIVE_INFINITY), seg.getEndPoint());
+ });
+ }
+
+ @Test
+ public void testDifference_boxTreeWithSingleCutTree() {
+ // arrange
+ Supplier<TestRegionBSPTree> boxFactory = () -> {
+ TestRegionBSPTree box = fullTree();
+ insertBox(box, TestPoint2D.ZERO, new TestPoint2D(2, -4));
+ return box;
+ };
+
+ Supplier<TestRegionBSPTree> horizonalFactory = () -> {
+ TestRegionBSPTree horizontal = fullTree();
+ horizontal.getRoot().insertCut(new TestLine(new TestPoint2D(2, -2), new TestPoint2D(0, -2)));
+
+ return horizontal;
+ };
+
+ // act/assert
+ differenceChecker(horizonalFactory, boxFactory)
+ .inside(new TestPoint2D(-1, -3), new TestPoint2D(-1, -5),
+ new TestPoint2D(1, -5), new TestPoint2D(3, -5),
+ new TestPoint2D(4, -3))
+ .outside(new TestPoint2D(1, -1), new TestPoint2D(1, -1),
+ new TestPoint2D(3, -1), new TestPoint2D(1, -3))
+ .boundary(new TestPoint2D(0, -2), new TestPoint2D(0, -4),
+ new TestPoint2D(2, -4), new TestPoint2D(2, -2))
+ .count(9)
+ .check();
+ }
+
+ @Test
+ public void testDifference_treeWithCopy() {
+ // arrange
+ Supplier<TestRegionBSPTree> treeFactory = () -> {
+ TestRegionBSPTree t = fullTree();
+ insertSkewedBowtie(t);
+
+ return t;
+ };
+
+ // act/assert
+ differenceChecker(treeFactory, treeFactory)
+ .full(false)
+ .empty(true)
+ .count(1)
+ .check();
+ }
+
+ @Test
+ public void testXor_singleNodeTrees() {
+ // act/assert
+ xorChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
+ .full(false)
+ .empty(true)
+ .count(1)
+ .check();
+
+ xorChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
+ .full(true)
+ .empty(false)
+ .count(1)
+ .check();
+
+ xorChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::fullTree)
+ .full(true)
+ .empty(false)
+ .count(1)
+ .check();
+
+ xorChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::fullTree)
+ .full(false)
+ .empty(true)
+ .count(1)
+ .check();
+ }
+
+ @Test
+ public void testXor_simpleCrossingCuts() {
+ // act/assert
+ xorChecker(AbstractRegionBSPTreeBooleanTest::xAxisTree, AbstractRegionBSPTreeBooleanTest::emptyTree)
+ .full(false)
+ .empty(false)
+ .inside(new TestPoint2D(0, 1))
+ .outside(new TestPoint2D(0, -1))
+ .boundary(TestPoint2D.ZERO)
+ .count(3)
+ .check();
+
+ xorChecker(AbstractRegionBSPTreeBooleanTest::emptyTree, AbstractRegionBSPTreeBooleanTest::xAxisTree)
+ .full(false)
+ .empty(false)
+ .inside(new TestPoint2D(0, 1))
+ .outside(new TestPoint2D(0, -1))
+ .boundary(TestPoint2D.ZERO)
+ .count(3)
+ .check();
+
+ xorChecker(AbstractRegionBSPTreeBooleanTest::yAxisTree, AbstractRegionBSPTreeBooleanTest::fullTree)
+ .full(false)
+ .empty(false)
+ .inside(new TestPoint2D(1, 1), new TestPoint2D(1, -1))
+ .outside(new TestPoint2D(-1, 1), new TestPoint2D(-1, -1))
+ .boundary(new TestPoint2D(0, 1), new TestPoint2D(0, -1))
+ .count(3)
+ .check();
+
+ xorChecker(AbstractRegionBSPTreeBooleanTest::fullTree, AbstractRegionBSPTreeBooleanTest::yAxisTree)
+ .full(false)
+ .empty(false)
+ .inside(new TestPoint2D(1, 1), new TestPoint2D(1, -1))
+ .outside(new TestPoint2D(-1, 1), new TestPoint2D(-1, -1))
+ .boundary(new TestPoint2D(0, 1), new TestPoint2D(0, -1))
+ .count(3)
+ .check();
+
+ xorChecker(AbstractRegionBSPTreeBooleanTest::xAxisTree, AbstractRegionBSPTreeBooleanTest::yAxisTree)
+ .full(false)
+ .empty(false)
+ .inside(new TestPoint2D(1, 1), new TestPoint2D(-1, -1))
+ .outside(new TestPoint2D(-1, 1), new TestPoint2D(1, -1))
+ .boundary(TestPoint2D.ZERO)
+ .count(7)
+ .check(t -> {
+ TestLineSegment minusSeg = (TestLineSegment) t.getRoot().getMinus().getCut();
+
+ PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, minusSeg.getStartPoint());
+ PartitionTestUtils.assertPointsEqual(new TestPoint2D(0.0, Double.POSITIVE_INFINITY), minusSeg.getEndPoint());
+
+ TestLineSegment plusSeg = (TestLineSegment) t.getRoot().getPlus().getCut();
+
+ PartitionTestUtils.assertPointsEqual(new TestPoint2D(0.0, Double.NEGATIVE_INFINITY), plusSeg.getStartPoint());
+ PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, plusSeg.getEndPoint());
+ });
+ }
+
+ @Test
+ public void testXor_boxTreeWithSingleCutTree() {
+ // arrange
+ Supplier<TestRegionBSPTree> boxFactory = () -> {
+ TestRegionBSPTree box = fullTree();
+ insertBox(box, TestPoint2D.ZERO, new TestPoint2D(2, -4));
+ return box;
+ };
+
+ Supplier<TestRegionBSPTree> horizonalFactory = () -> {
+ TestRegionBSPTree horizontal = fullTree();
+ horizontal.getRoot().insertCut(new TestLine(new TestPoint2D(2, -2), new TestPoint2D(0, -2)));
+
+ return horizontal;
+ };
+
+ // act/assert
+ xorChecker(horizonalFactory, boxFactory)
+ .inside(new TestPoint2D(-1, -3), new TestPoint2D(-1, -5),
+ new TestPoint2D(1, -5), new TestPoint2D(3, -5),
+ new TestPoint2D(4, -3), new TestPoint2D(1, -1))
+ .outside(new TestPoint2D(3, -1), new TestPoint2D(1, -3),
+ new TestPoint2D(1, 1), new TestPoint2D(5, -1))
+ .boundary(new TestPoint2D(0, -2), new TestPoint2D(0, -4),
+ new TestPoint2D(2, -4), new TestPoint2D(2, -2),
+ TestPoint2D.ZERO, new TestPoint2D(2, 0))
+ .count(15)
+ .check();
+ }
+
+ @Test
+ public void testXor_treeWithComplement() {
+ // arrange
+ Supplier<TestRegionBSPTree> treeFactory = () -> {
+ TestRegionBSPTree t = fullTree();
+ insertSkewedBowtie(t);
+
+ return t;
+ };
+ Supplier<TestRegionBSPTree> complementFactory = () -> {
+ TestRegionBSPTree t = treeFactory.get();
+ t.complement();
+
+ return t;
+ };
+
+ // act/assert
+ xorChecker(treeFactory, complementFactory)
+ .full(true)
+ .empty(false)
+ .count(1)
+ .check();
+ }
+
+ private static TestRegionBSPTree emptyTree() {
+ return new TestRegionBSPTree(false);
+ }
+
+ private static TestRegionBSPTree fullTree() {
+ return new TestRegionBSPTree(true);
+ }
+
+ private static TestRegionBSPTree xAxisTree() {
+ TestRegionBSPTree tree = fullTree();
+ tree.getRoot().cut(TestLine.X_AXIS);
+
+ return tree;
+ }
+
+ private static TestRegionBSPTree yAxisTree() {
+ TestRegionBSPTree tree = fullTree();
+ tree.getRoot().cut(TestLine.Y_AXIS);
+
+ return tree;
+ }
+
+ private static void insertBox(final TestRegionBSPTree tree, final TestPoint2D upperLeft,
+ final TestPoint2D lowerRight) {
+ final TestPoint2D upperRight = new TestPoint2D(lowerRight.getX(), upperLeft.getY());
+ final TestPoint2D lowerLeft = new TestPoint2D(upperLeft.getX(), lowerRight.getY());
+
+ tree.insert(Arrays.asList(
+ new TestLineSegment(lowerRight, upperRight),
+ new TestLineSegment(upperRight, upperLeft),
+ new TestLineSegment(upperLeft, lowerLeft),
+ new TestLineSegment(lowerLeft, lowerRight)
+ ));
+ }
+
+ private static void insertSkewedBowtie(final TestRegionBSPTree tree) {
+ tree.insert(Arrays.asList(
+ new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
+
+ new TestLineSegment(new TestPoint2D(4, 0), new TestPoint2D(4, 1)),
+ new TestLineSegment(new TestPoint2D(-4, 0), new TestPoint2D(-4, -1)),
+
+ new TestLineSegment(new TestPoint2D(4, 5), new TestPoint2D(-1, 0)),
+ new TestLineSegment(new TestPoint2D(-4, -5), new TestPoint2D(1, 0))));
+ }
+
+ private static MergeChecker unionChecker(
+ final Supplier<TestRegionBSPTree> r1,
+ final Supplier<TestRegionBSPTree> r2) {
+
+ MergeChecker.Operation constOperation = (a, b) -> {
+ TestRegionBSPTree result = fullTree();
+ result.union(a, b);
+
+ return result;
+ };
+
+ MergeChecker.Operation inPlaceOperation = (a, b) -> {
+ a.union(b);
+ return a;
+ };
+
+ return new MergeChecker(r1, r2, constOperation, inPlaceOperation);
+ }
+
+ private static MergeChecker intersectionChecker(
+ final Supplier<TestRegionBSPTree> tree1Factory,
+ final Supplier<TestRegionBSPTree> tree2Factory) {
+
+ MergeChecker.Operation constOperation = (a, b) -> {
+ TestRegionBSPTree result = fullTree();
+ result.intersection(a, b);
+ return result;
+ };
+
+ MergeChecker.Operation inPlaceOperation = (a, b) -> {
+ a.intersection(b);
+ return a;
+ };
+
+ return new MergeChecker(tree1Factory, tree2Factory, constOperation, inPlaceOperation);
+ }
+
+ private static MergeChecker differenceChecker(
+ final Supplier<TestRegionBSPTree> tree1Factory,
+ final Supplier<TestRegionBSPTree> tree2Factory) {
+
+ MergeChecker.Operation constOperation = (a, b) -> {
+ TestRegionBSPTree result = fullTree();
+ result.difference(a, b);
+ return result;
+ };
+
+ MergeChecker.Operation inPlaceOperation = (a, b) -> {
+ a.difference(b);
+ return a;
+ };
+
+ return new MergeChecker(tree1Factory, tree2Factory, constOperation, inPlaceOperation);
+ }
+
+ private static MergeChecker xorChecker(
+ final Supplier<TestRegionBSPTree> tree1Factory,
+ final Supplier<TestRegionBSPTree> tree2Factory) {
+
+ MergeChecker.Operation constOperation = (a, b) -> {
+ TestRegionBSPTree result = fullTree();
+ result.xor(a, b);
+ return result;
+ };
+
+ MergeChecker.Operation inPlaceOperation = (a, b) -> {
+ a.xor(b);
+ return a;
+ };
+
+ return new MergeChecker(tree1Factory, tree2Factory, constOperation, inPlaceOperation);
+ }
+}
diff --git a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractRegionBSPTreeTest.java b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractRegionBSPTreeTest.java
index a634ed2..0dbd048 100644
--- a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractRegionBSPTreeTest.java
+++ b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/bsp/AbstractRegionBSPTreeTest.java
@@ -19,8 +19,10 @@ package org.apache.commons.geometry.core.partitioning.bsp;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
-import java.util.function.Supplier;
+import java.util.function.Consumer;
+import java.util.function.Function;
+import org.apache.commons.geometry.core.GeometryTestUtils;
import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.core.Transform;
import org.apache.commons.geometry.core.partition.test.PartitionTestUtils;
@@ -31,6 +33,7 @@ import org.apache.commons.geometry.core.partition.test.TestPoint2D;
import org.apache.commons.geometry.core.partition.test.TestRegionBSPTree;
import org.apache.commons.geometry.core.partition.test.TestRegionBSPTree.TestRegionNode;
import org.apache.commons.geometry.core.partition.test.TestTransform2D;
+import org.apache.commons.geometry.core.partitioning.BoundarySource;
import org.apache.commons.geometry.core.partitioning.ConvexSubHyperplane;
import org.apache.commons.geometry.core.partitioning.Split;
import org.apache.commons.geometry.core.partitioning.SplitLocation;
@@ -106,6 +109,106 @@ public class AbstractRegionBSPTreeTest {
}
@Test
+ public void testInsert_subhyperplanes_mixedCutRules() {
+ // act/assert
+ checkMixedCutRuleInsertion(segs -> {
+ tree.insert(new TestLineSegmentCollection(Arrays.asList(segs[0])), RegionCutRule.PLUS_INSIDE);
+ tree.insert(new TestLineSegmentCollection(Arrays.asList(segs[1]))); // default rule
+ tree.insert(new TestLineSegmentCollection(Arrays.asList(segs[2])), RegionCutRule.PLUS_INSIDE);
+ tree.insert(new TestLineSegmentCollection(Arrays.asList(segs[3])), RegionCutRule.MINUS_INSIDE);
+ tree.insert(new TestLineSegmentCollection(Arrays.asList(segs[4])), RegionCutRule.INHERIT);
+ });
+
+ }
+
+ @Test
+ public void testInsert_convexSubhyperplanes_mixedCutRules() {
+ // act/assert
+ checkMixedCutRuleInsertion(segs -> {
+ tree.insert(segs[0], RegionCutRule.PLUS_INSIDE);
+ tree.insert(segs[1]); // default rule
+ tree.insert(segs[2], RegionCutRule.PLUS_INSIDE);
+ tree.insert(segs[3], RegionCutRule.MINUS_INSIDE);
+ tree.insert(segs[4], RegionCutRule.INHERIT);
+ });
+ }
+
+ @Test
+ public void testInsert_convexSubhyperplaneList_mixedCutRules() {
+ // act/assert
+ checkMixedCutRuleInsertion(segs -> {
+ tree.insert(Arrays.asList(segs[0]), RegionCutRule.PLUS_INSIDE);
+ tree.insert(Arrays.asList(segs[1])); // default rule
+ tree.insert(Arrays.asList(segs[2]), RegionCutRule.PLUS_INSIDE);
+ tree.insert(Arrays.asList(segs[3]), RegionCutRule.MINUS_INSIDE);
+ tree.insert(Arrays.asList(segs[4]), RegionCutRule.INHERIT);
+ });
+ }
+
+ @Test
+ public void testInsert_boundarySource_mixedCutRules() {
+ // arrange
+ final Function<TestLineSegment, BoundarySource<TestLineSegment>> factory = seg -> {
+ return () -> Arrays.asList(seg).stream();
+ };
+
+ // act/assert
+ checkMixedCutRuleInsertion(segs -> {
+ tree.insert(factory.apply(segs[0]), RegionCutRule.PLUS_INSIDE);
+ tree.insert(factory.apply(segs[1])); // default rule
+ tree.insert(factory.apply(segs[2]), RegionCutRule.PLUS_INSIDE);
+ tree.insert(factory.apply(segs[3]), RegionCutRule.MINUS_INSIDE);
+ tree.insert(factory.apply(segs[4]), RegionCutRule.INHERIT);
+ });
+ }
+
+ /** Helper function to check the insertion of subhyperplanes using different region cut rules.
+ * @param fn
+ */
+ private void checkMixedCutRuleInsertion(Consumer<TestLineSegment[]> fn) {
+ // arrange
+ TestLineSegment bottom = new TestLineSegment(new TestPoint2D(1, 0), new TestPoint2D(0, 0));
+ TestLineSegment right = new TestLineSegment(new TestPoint2D(1, 0), new TestPoint2D(1, 1));
+ TestLineSegment top = new TestLineSegment(new TestPoint2D(0, 1), new TestPoint2D(1, 1));
+ TestLineSegment left = new TestLineSegment(new TestPoint2D(0, 1), new TestPoint2D(0, 0));
+ TestLineSegment diag = new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 1));
+
+ tree = emptyTree();
+
+ // act
+ fn.accept(new TestLineSegment[] {
+ bottom,
+ right,
+ top,
+ left,
+ diag
+ });
+
+ // assert
+ TestRegionNode node = tree.getRoot();
+ Assert.assertEquals(RegionLocation.OUTSIDE, node.getLocation());
+
+ Assert.assertEquals(RegionLocation.OUTSIDE, node.getMinus().getLocation());
+ Assert.assertEquals(RegionLocation.INSIDE, node.getPlus().getLocation());
+
+ node = node.getPlus();
+ Assert.assertEquals(RegionLocation.INSIDE, node.getMinus().getLocation());
+ Assert.assertEquals(RegionLocation.OUTSIDE, node.getPlus().getLocation());
+
+ node = node.getMinus();
+ Assert.assertEquals(RegionLocation.OUTSIDE, node.getMinus().getLocation());
+ Assert.assertEquals(RegionLocation.INSIDE, node.getPlus().getLocation());
+
+ node = node.getPlus();
+ Assert.assertEquals(RegionLocation.INSIDE, node.getMinus().getLocation());
+ Assert.assertEquals(RegionLocation.OUTSIDE, node.getPlus().getLocation());
+
+ node = node.getMinus();
+ Assert.assertEquals(RegionLocation.INSIDE, node.getMinus().getLocation());
+ Assert.assertEquals(RegionLocation.INSIDE, node.getPlus().getLocation());
+ }
+
+ @Test
public void testGetLocation_emptyRoot() {
// act/assert
Assert.assertEquals(RegionLocation.INSIDE, root.getLocation());
@@ -117,9 +220,19 @@ public class AbstractRegionBSPTreeTest {
root.insertCut(TestLine.X_AXIS);
// act/assert
- Assert.assertNull(root.getLocation());
- Assert.assertEquals(RegionLocation.INSIDE, root.getMinus().getLocation());
- Assert.assertEquals(RegionLocation.OUTSIDE, root.getPlus().getLocation());
+ Assert.assertEquals(RegionLocation.INSIDE, root.getLocation());
+ Assert.assertFalse(root.isInside());
+ Assert.assertFalse(root.isOutside());
+
+ TestRegionNode minus = root.getMinus();
+ Assert.assertEquals(RegionLocation.INSIDE, minus.getLocation());
+ Assert.assertTrue(minus.isInside());
+ Assert.assertFalse(minus.isOutside());
+
+ TestRegionNode plus = root.getPlus();
+ Assert.assertEquals(RegionLocation.OUTSIDE, plus.getLocation());
+ Assert.assertFalse(plus.isInside());
+ Assert.assertTrue(plus.isOutside());
}
@Test
@@ -131,10 +244,10 @@ public class AbstractRegionBSPTreeTest {
new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, -1))));
// act/assert
- Assert.assertNull(root.getLocation());
+ Assert.assertEquals(RegionLocation.INSIDE, root.getLocation());
TestRegionNode plus = root.getPlus();
- Assert.assertNull(plus.getLocation());
+ Assert.assertEquals(RegionLocation.OUTSIDE, plus.getLocation());
TestRegionNode plusPlus = plus.getPlus();
Assert.assertEquals(RegionLocation.OUTSIDE, plusPlus.getLocation());
@@ -143,7 +256,7 @@ public class AbstractRegionBSPTreeTest {
Assert.assertEquals(RegionLocation.INSIDE, plusMinus.getLocation());
TestRegionNode minus = root.getMinus();
- Assert.assertNull(minus.getLocation());
+ Assert.assertEquals(RegionLocation.INSIDE, minus.getLocation());
TestRegionNode minusPlus = minus.getPlus();
Assert.assertEquals(RegionLocation.OUTSIDE, minusPlus.getLocation());
@@ -153,37 +266,161 @@ public class AbstractRegionBSPTreeTest {
}
@Test
- public void testGetLocation_resetsLocationWhenNodeCleared() {
+ public void testSetLocation() {
// arrange
- tree.insert(Arrays.asList(
- new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
- new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1)),
- new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, -1))));
+ tree = emptyTree();
+ tree.insert(TestLine.Y_AXIS.span());
+
+ TestRegionNode node = tree.getRoot().getMinus();
// act
- root.getPlus().clearCut();
- root.getMinus().clearCut();
+ node.setLocation(RegionLocation.OUTSIDE);
// assert
- Assert.assertNull(root.getLocation());
+ Assert.assertEquals(RegionLocation.OUTSIDE, node.getLocation());
+ Assert.assertTrue(tree.isEmpty());
+ }
+
+ @Test
+ public void testSetLocation_invalidatesRegionProperties() {
+ // arrange
+ tree = emptyTree();
+ tree.insert(TestLine.Y_AXIS.span());
+
+ TestRegionNode node = tree.getRoot().getMinus();
- Assert.assertEquals(RegionLocation.INSIDE, root.getMinus().getLocation());
- Assert.assertEquals(RegionLocation.OUTSIDE, root.getPlus().getLocation());
+ RegionSizeProperties<TestPoint2D> prevProps = tree.getRegionSizeProperties();
+
+ // act
+ node.setLocation(RegionLocation.OUTSIDE);
+
+ // assert
+ Assert.assertNotSame(prevProps, tree.getRegionSizeProperties());
}
@Test
- public void testGetLocation_resetRoot() {
+ public void testSetLocation_noChange_doesNotInvalidateTree() {
// arrange
- tree.insert(Arrays.asList(
- new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
- new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1)),
- new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, -1))));
+ tree = emptyTree();
+ tree.insert(TestLine.Y_AXIS.span());
+
+ TestRegionNode node = tree.getRoot().getMinus();
+
+ RegionSizeProperties<TestPoint2D> prevProps = tree.getRegionSizeProperties();
// act
- root.clearCut();
+ node.setLocation(RegionLocation.INSIDE);
// assert
- Assert.assertEquals(RegionLocation.INSIDE, root.getLocation());
+ Assert.assertSame(prevProps, tree.getRegionSizeProperties());
+ }
+
+ @Test
+ public void testSetLocation_invalidArgs() {
+ // act/assert
+ GeometryTestUtils.assertThrows(() -> root.setLocation(null),
+ IllegalArgumentException.class, "Invalid node location: null");
+ GeometryTestUtils.assertThrows(() -> root.setLocation(RegionLocation.BOUNDARY),
+ IllegalArgumentException.class, "Invalid node location: BOUNDARY");
+ }
+
+ @Test
+ public void testCondense() {
+ // arrange
+ tree = emptyTree();
+ tree.insert(TestLine.Y_AXIS.span(), RegionCutRule.MINUS_INSIDE);
+ tree.insert(TestLine.X_AXIS.span(), RegionCutRule.INHERIT);
+
+ // act
+ boolean result = tree.condense();
+
+ // assert
+ Assert.assertTrue(result);
+
+ Assert.assertEquals(3, tree.count());
+ Assert.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getLocation());
+ Assert.assertEquals(RegionLocation.INSIDE, tree.getRoot().getMinus().getLocation());
+ Assert.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getPlus().getLocation());
+ }
+
+ @Test
+ public void testCondense_alreadyCondensed() {
+ // arrange
+ tree = emptyTree();
+ tree.insert(TestLine.Y_AXIS.span(), RegionCutRule.MINUS_INSIDE);
+
+ // act
+ boolean result = tree.condense();
+
+ // assert
+ Assert.assertFalse(result);
+
+ Assert.assertEquals(3, tree.count());
+ Assert.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getLocation());
+ Assert.assertEquals(RegionLocation.INSIDE, tree.getRoot().getMinus().getLocation());
+ Assert.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getPlus().getLocation());
+ }
+
+ @Test
+ public void testCondense_invalidatesTreeWhenChanged() {
+ // arrange
+ tree = emptyTree();
+ tree.insert(TestLine.Y_AXIS.span(), RegionCutRule.MINUS_INSIDE);
+ tree.insert(TestLine.X_AXIS.span(), RegionCutRule.INHERIT);
+
+ RegionSizeProperties<TestPoint2D> prevProps = tree.getRegionSizeProperties();
+
+ // act
+ boolean result = tree.condense();
+
+ // assert
+ Assert.assertTrue(result);
+
+ Assert.assertNotSame(prevProps, tree.getRegionSizeProperties());
+ }
+
+ @Test
+ public void testCondense_doesNotInvalidateTreeWhenNotChanged() {
+ // arrange
+ tree = emptyTree();
+
+ RegionSizeProperties<TestPoint2D> prevProps = tree.getRegionSizeProperties();
+
+ // act
+ boolean result = tree.condense();
+
+ // assert
+ Assert.assertFalse(result);
+
+ Assert.assertSame(prevProps, tree.getRegionSizeProperties());
+ }
+
+ @Test
+ public void testCut_nodeMethod() {
+ // arrange
+ tree = emptyTree();
+
+ // act
+ tree.getRoot().cut(TestLine.X_AXIS, RegionCutRule.PLUS_INSIDE)
+ .getPlus()
+ .cut(TestLine.Y_AXIS, RegionCutRule.MINUS_INSIDE)
+ .getMinus()
+ .cut(new TestLine(TestPoint2D.ZERO, new TestPoint2D(-1, -1)), RegionCutRule.INHERIT);
+
+ // assert
+ TestRegionNode node = tree.getRoot();
+ Assert.assertEquals(RegionLocation.OUTSIDE, node.getLocation());
+
+ Assert.assertEquals(RegionLocation.OUTSIDE, node.getMinus().getLocation());
+ Assert.assertEquals(RegionLocation.INSIDE, node.getPlus().getLocation());
+
+ node = node.getPlus();
+ Assert.assertEquals(RegionLocation.INSIDE, node.getMinus().getLocation());
+ Assert.assertEquals(RegionLocation.OUTSIDE, node.getPlus().getLocation());
+
+ node = node.getMinus();
+ Assert.assertEquals(RegionLocation.INSIDE, node.getMinus().getLocation());
+ Assert.assertEquals(RegionLocation.INSIDE, node.getPlus().getLocation());
}
@Test
@@ -402,22 +639,22 @@ public class AbstractRegionBSPTreeTest {
Assert.assertSame(first, second);
Assert.assertNotSame(second, third);
- Assert.assertEquals(1, first.getSize(), PartitionTestUtils.EPS);
- Assert.assertSame(TestPoint2D.ZERO, first.getBarycenter());
+ Assert.assertEquals(1234, first.getSize(), PartitionTestUtils.EPS);
+ PartitionTestUtils.assertPointsEqual(new TestPoint2D(12, 34), first.getBarycenter());
}
@Test
public void testGetSize() {
// act/assert
// make sure our stub value is pulled
- Assert.assertEquals(1, tree.getSize(), PartitionTestUtils.EPS);
+ Assert.assertEquals(1234, tree.getSize(), PartitionTestUtils.EPS);
}
@Test
public void testGetBarycenter() {
// act/assert
// make sure our stub value is pulled
- Assert.assertSame(TestPoint2D.ZERO, tree.getBarycenter());
+ PartitionTestUtils.assertPointsEqual(new TestPoint2D(12, 34), tree.getBarycenter());
}
@Test
@@ -1036,10 +1273,10 @@ public class AbstractRegionBSPTreeTest {
Assert.assertEquals(tree.count(), copy.count());
List<RegionLocation> origLocations = new ArrayList<>();
- tree.nodes().forEach(n -> origLocations.add(n.getLocationValue()));
+ tree.nodes().forEach(n -> origLocations.add(n.getLocation()));
List<RegionLocation> copyLocations = new ArrayList<>();
- copy.nodes().forEach(n -> copyLocations.add(n.getLocationValue()));
+ copy.nodes().forEach(n -> copyLocations.add(n.getLocation()));
Assert.assertEquals(origLocations, copyLocations);
}
@@ -1098,515 +1335,6 @@ public class AbstractRegionBSPTreeTest {
}
- @Test
- public void testUnion_singleNodeTrees() {
- // act/assert
- unionChecker(AbstractRegionBSPTreeTest::emptyTree, AbstractRegionBSPTreeTest::emptyTree)
- .full(false)
- .empty(true)
- .count(1)
- .check();
-
- unionChecker(AbstractRegionBSPTreeTest::fullTree, AbstractRegionBSPTreeTest::emptyTree)
- .full(true)
- .empty(false)
- .count(1)
- .check();
-
- unionChecker(AbstractRegionBSPTreeTest::emptyTree, AbstractRegionBSPTreeTest::fullTree)
- .full(true)
- .empty(false)
- .count(1)
- .check();
-
- unionChecker(AbstractRegionBSPTreeTest::fullTree, AbstractRegionBSPTreeTest::fullTree)
- .full(true)
- .empty(false)
- .count(1)
- .check();
- }
-
- @Test
- public void testUnion_simpleCrossingCuts() {
- // act/assert
- unionChecker(AbstractRegionBSPTreeTest::xAxisTree, AbstractRegionBSPTreeTest::emptyTree)
- .full(false)
- .empty(false)
- .count(3)
- .check();
-
- unionChecker(AbstractRegionBSPTreeTest::emptyTree, AbstractRegionBSPTreeTest::xAxisTree)
- .full(false)
- .empty(false)
- .count(3)
- .check();
-
- unionChecker(AbstractRegionBSPTreeTest::yAxisTree, AbstractRegionBSPTreeTest::fullTree)
- .full(true)
- .empty(false)
- .count(1)
- .check();
-
- unionChecker(AbstractRegionBSPTreeTest::fullTree, AbstractRegionBSPTreeTest::yAxisTree)
- .full(true)
- .empty(false)
- .count(1)
- .check();
-
- unionChecker(AbstractRegionBSPTreeTest::xAxisTree, AbstractRegionBSPTreeTest::yAxisTree)
- .full(false)
- .empty(false)
- .inside(new TestPoint2D(1, 1), new TestPoint2D(-1, 1), new TestPoint2D(-1, -1))
- .outside(new TestPoint2D(1, -1))
- .boundary(TestPoint2D.ZERO)
- .count(5)
- .check(t -> {
- TestLineSegment seg = (TestLineSegment) t.getRoot().getPlus().getCut();
-
- PartitionTestUtils.assertPointsEqual(new TestPoint2D(0.0, Double.NEGATIVE_INFINITY), seg.getStartPoint());
- PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, seg.getEndPoint());
- });
- }
-
- @Test
- public void testUnion_boxTreeWithSingleCutTree() {
- // arrange
- Supplier<TestRegionBSPTree> boxFactory = () -> {
- TestRegionBSPTree box = fullTree();
- insertBox(box, TestPoint2D.ZERO, new TestPoint2D(2, -4));
- return box;
- };
-
- Supplier<TestRegionBSPTree> horizonalFactory = () -> {
- TestRegionBSPTree horizontal = fullTree();
- horizontal.getRoot().insertCut(new TestLine(new TestPoint2D(2, 2), new TestPoint2D(0, 2)));
-
- return horizontal;
- };
-
- // act/assert
- unionChecker(horizonalFactory, boxFactory)
- .count(3)
- .inside(TestPoint2D.ZERO, new TestPoint2D(1, 1), new TestPoint2D(1, -1))
- .outside(new TestPoint2D(0, 3), new TestPoint2D(3, 3))
- .boundary(new TestPoint2D(-1, 2), new TestPoint2D(3, 2))
- .check();
- }
-
- @Test
- public void testUnion_treeWithComplement() {
- // arrange
- Supplier<TestRegionBSPTree> treeFactory = () -> {
- TestRegionBSPTree t = fullTree();
- insertSkewedBowtie(t);
-
- return t;
- };
- Supplier<TestRegionBSPTree> complementFactory = () -> {
- TestRegionBSPTree t = treeFactory.get();
- t.complement();
-
- return t;
- };
-
- // act/assert
- unionChecker(treeFactory, complementFactory)
- .full(true)
- .empty(false)
- .count(1)
- .check();
- }
-
- @Test
- public void testIntersection_singleNodeTrees() {
- // act/assert
- intersectionChecker(AbstractRegionBSPTreeTest::emptyTree, AbstractRegionBSPTreeTest::emptyTree)
- .full(false)
- .empty(true)
- .count(1)
- .check();
-
- intersectionChecker(AbstractRegionBSPTreeTest::fullTree, AbstractRegionBSPTreeTest::emptyTree)
- .full(false)
- .empty(true)
- .count(1)
- .check();
-
- intersectionChecker(AbstractRegionBSPTreeTest::emptyTree, AbstractRegionBSPTreeTest::fullTree)
- .full(false)
- .empty(true)
- .count(1)
- .check();
-
- intersectionChecker(AbstractRegionBSPTreeTest::fullTree, AbstractRegionBSPTreeTest::fullTree)
- .full(true)
- .empty(false)
- .count(1)
- .check();
- }
-
- @Test
- public void testIntersection_simpleCrossingCuts() {
- // act/assert
- intersectionChecker(AbstractRegionBSPTreeTest::xAxisTree, AbstractRegionBSPTreeTest::emptyTree)
- .full(false)
- .empty(true)
- .count(1)
- .check();
-
- intersectionChecker(AbstractRegionBSPTreeTest::emptyTree, AbstractRegionBSPTreeTest::xAxisTree)
- .full(false)
- .empty(true)
- .count(1)
- .check();
-
- intersectionChecker(AbstractRegionBSPTreeTest::yAxisTree, AbstractRegionBSPTreeTest::fullTree)
- .full(false)
- .empty(false)
- .inside(new TestPoint2D(-1, 1), new TestPoint2D(-1, -1))
- .outside(new TestPoint2D(1, 1), new TestPoint2D(1, -1))
- .boundary(new TestPoint2D(0, 1), new TestPoint2D(0, -1))
- .count(3)
- .check();
-
- intersectionChecker(AbstractRegionBSPTreeTest::fullTree, AbstractRegionBSPTreeTest::yAxisTree)
- .full(false)
- .empty(false)
- .inside(new TestPoint2D(-1, 1), new TestPoint2D(-1, -1))
- .outside(new TestPoint2D(1, 1), new TestPoint2D(1, -1))
- .boundary(new TestPoint2D(0, 1), new TestPoint2D(0, -1))
- .count(3)
- .check();
-
- intersectionChecker(AbstractRegionBSPTreeTest::xAxisTree, AbstractRegionBSPTreeTest::yAxisTree)
- .full(false)
- .empty(false)
- .inside(new TestPoint2D(-1, 1))
- .outside(new TestPoint2D(1, 1), new TestPoint2D(1, -1), new TestPoint2D(-1, -1))
- .boundary(TestPoint2D.ZERO)
- .count(5)
- .check(t -> {
- TestLineSegment seg = (TestLineSegment) t.getRoot().getMinus().getCut();
-
- PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, seg.getStartPoint());
- PartitionTestUtils.assertPointsEqual(new TestPoint2D(0.0, Double.POSITIVE_INFINITY), seg.getEndPoint());
- });
- }
-
- @Test
- public void testIntersection_boxTreeWithSingleCutTree() {
- // arrange
- Supplier<TestRegionBSPTree> boxFactory = () -> {
- TestRegionBSPTree box = fullTree();
- insertBox(box, TestPoint2D.ZERO, new TestPoint2D(2, -4));
- return box;
- };
-
- Supplier<TestRegionBSPTree> horizonalFactory = () -> {
- TestRegionBSPTree horizontal = fullTree();
- horizontal.getRoot().insertCut(new TestLine(new TestPoint2D(2, -2), new TestPoint2D(0, -2)));
-
- return horizontal;
- };
-
- // act/assert
- intersectionChecker(horizonalFactory, boxFactory)
- .inside(new TestPoint2D(1, -3))
- .outside(new TestPoint2D(1, -1), new TestPoint2D(-1, -3),
- new TestPoint2D(1, -5), new TestPoint2D(3, -3))
- .boundary(new TestPoint2D(0, -2), new TestPoint2D(2, -2),
- new TestPoint2D(0, -4), new TestPoint2D(2, -4))
- .count(9)
- .check();
- }
-
- @Test
- public void testIntersection_treeWithComplement() {
- // arrange
- Supplier<TestRegionBSPTree> treeFactory = () -> {
- TestRegionBSPTree t = fullTree();
- insertSkewedBowtie(t);
-
- return t;
- };
- Supplier<TestRegionBSPTree> complementFactory = () -> {
- TestRegionBSPTree t = treeFactory.get();
- t.complement();
-
- return t;
- };
-
- // act/assert
- intersectionChecker(treeFactory, complementFactory)
- .full(false)
- .empty(true)
- .count(1)
- .check();
- }
-
- @Test
- public void testDifference_singleNodeTrees() {
- // act/assert
- differenceChecker(AbstractRegionBSPTreeTest::emptyTree, AbstractRegionBSPTreeTest::emptyTree)
- .full(false)
- .empty(true)
- .count(1)
- .check();
-
- differenceChecker(AbstractRegionBSPTreeTest::fullTree, AbstractRegionBSPTreeTest::emptyTree)
- .full(true)
- .empty(false)
- .count(1)
- .check();
-
- differenceChecker(AbstractRegionBSPTreeTest::emptyTree, AbstractRegionBSPTreeTest::fullTree)
- .full(false)
- .empty(true)
- .count(1)
- .check();
-
- differenceChecker(AbstractRegionBSPTreeTest::fullTree, AbstractRegionBSPTreeTest::fullTree)
- .full(false)
- .empty(true)
- .count(1)
- .check();
- }
-
- @Test
- public void testDifference_simpleCrossingCuts() {
- // act/assert
- differenceChecker(AbstractRegionBSPTreeTest::xAxisTree, AbstractRegionBSPTreeTest::emptyTree)
- .full(false)
- .empty(false)
- .inside(new TestPoint2D(0, 1))
- .outside(new TestPoint2D(0, -1))
- .boundary(TestPoint2D.ZERO)
- .count(3)
- .check();
-
- differenceChecker(AbstractRegionBSPTreeTest::emptyTree, AbstractRegionBSPTreeTest::xAxisTree)
- .full(false)
- .empty(true)
- .count(1)
- .check();
-
- differenceChecker(AbstractRegionBSPTreeTest::yAxisTree, AbstractRegionBSPTreeTest::fullTree)
- .full(false)
- .empty(true)
- .count(1)
- .check();
-
- differenceChecker(AbstractRegionBSPTreeTest::fullTree, AbstractRegionBSPTreeTest::yAxisTree)
- .full(false)
- .empty(false)
- .inside(new TestPoint2D(1, 1), new TestPoint2D(1, -1))
- .outside(new TestPoint2D(-1, 1), new TestPoint2D(-1, -1))
- .boundary(new TestPoint2D(0, 1), new TestPoint2D(0, -1))
- .count(3)
- .check();
-
- differenceChecker(AbstractRegionBSPTreeTest::xAxisTree, AbstractRegionBSPTreeTest::yAxisTree)
- .full(false)
- .empty(false)
- .inside(new TestPoint2D(1, 1))
- .outside(new TestPoint2D(-1, 1), new TestPoint2D(1, -1), new TestPoint2D(-1, -1))
- .boundary(TestPoint2D.ZERO)
- .count(5)
- .check(t -> {
- TestLineSegment seg = (TestLineSegment) t.getRoot().getMinus().getCut();
-
- PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, seg.getStartPoint());
- PartitionTestUtils.assertPointsEqual(new TestPoint2D(0.0, Double.POSITIVE_INFINITY), seg.getEndPoint());
- });
- }
-
- @Test
- public void testDifference_boxTreeWithSingleCutTree() {
- // arrange
- Supplier<TestRegionBSPTree> boxFactory = () -> {
- TestRegionBSPTree box = fullTree();
- insertBox(box, TestPoint2D.ZERO, new TestPoint2D(2, -4));
- return box;
- };
-
- Supplier<TestRegionBSPTree> horizonalFactory = () -> {
- TestRegionBSPTree horizontal = fullTree();
- horizontal.getRoot().insertCut(new TestLine(new TestPoint2D(2, -2), new TestPoint2D(0, -2)));
-
- return horizontal;
- };
-
- // act/assert
- differenceChecker(horizonalFactory, boxFactory)
- .inside(new TestPoint2D(-1, -3), new TestPoint2D(-1, -5),
- new TestPoint2D(1, -5), new TestPoint2D(3, -5),
- new TestPoint2D(4, -3))
- .outside(new TestPoint2D(1, -1), new TestPoint2D(1, -1),
- new TestPoint2D(3, -1), new TestPoint2D(1, -3))
- .boundary(new TestPoint2D(0, -2), new TestPoint2D(0, -4),
- new TestPoint2D(2, -4), new TestPoint2D(2, -2))
- .count(9)
- .check();
- }
-
- @Test
- public void testDifference_treeWithCopy() {
- // arrange
- Supplier<TestRegionBSPTree> treeFactory = () -> {
- TestRegionBSPTree t = fullTree();
- insertSkewedBowtie(t);
-
- return t;
- };
-
- // act/assert
- differenceChecker(treeFactory, treeFactory)
- .full(false)
- .empty(true)
- .count(1)
- .check();
- }
-
- @Test
- public void testXor_singleNodeTrees() {
- // act/assert
- xorChecker(AbstractRegionBSPTreeTest::emptyTree, AbstractRegionBSPTreeTest::emptyTree)
- .full(false)
- .empty(true)
- .count(1)
- .check();
-
- xorChecker(AbstractRegionBSPTreeTest::fullTree, AbstractRegionBSPTreeTest::emptyTree)
- .full(true)
- .empty(false)
- .count(1)
- .check();
-
- xorChecker(AbstractRegionBSPTreeTest::emptyTree, AbstractRegionBSPTreeTest::fullTree)
- .full(true)
- .empty(false)
- .count(1)
- .check();
-
- xorChecker(AbstractRegionBSPTreeTest::fullTree, AbstractRegionBSPTreeTest::fullTree)
- .full(false)
- .empty(true)
- .count(1)
- .check();
- }
-
- @Test
- public void testXor_simpleCrossingCuts() {
- // act/assert
- xorChecker(AbstractRegionBSPTreeTest::xAxisTree, AbstractRegionBSPTreeTest::emptyTree)
- .full(false)
- .empty(false)
- .inside(new TestPoint2D(0, 1))
- .outside(new TestPoint2D(0, -1))
- .boundary(TestPoint2D.ZERO)
- .count(3)
- .check();
-
- xorChecker(AbstractRegionBSPTreeTest::emptyTree, AbstractRegionBSPTreeTest::xAxisTree)
- .full(false)
- .empty(false)
- .inside(new TestPoint2D(0, 1))
- .outside(new TestPoint2D(0, -1))
- .boundary(TestPoint2D.ZERO)
- .count(3)
- .check();
-
- xorChecker(AbstractRegionBSPTreeTest::yAxisTree, AbstractRegionBSPTreeTest::fullTree)
- .full(false)
- .empty(false)
- .inside(new TestPoint2D(1, 1), new TestPoint2D(1, -1))
- .outside(new TestPoint2D(-1, 1), new TestPoint2D(-1, -1))
- .boundary(new TestPoint2D(0, 1), new TestPoint2D(0, -1))
- .count(3)
- .check();
-
- xorChecker(AbstractRegionBSPTreeTest::fullTree, AbstractRegionBSPTreeTest::yAxisTree)
- .full(false)
- .empty(false)
- .inside(new TestPoint2D(1, 1), new TestPoint2D(1, -1))
- .outside(new TestPoint2D(-1, 1), new TestPoint2D(-1, -1))
- .boundary(new TestPoint2D(0, 1), new TestPoint2D(0, -1))
- .count(3)
- .check();
-
- xorChecker(AbstractRegionBSPTreeTest::xAxisTree, AbstractRegionBSPTreeTest::yAxisTree)
- .full(false)
- .empty(false)
- .inside(new TestPoint2D(1, 1), new TestPoint2D(-1, -1))
- .outside(new TestPoint2D(-1, 1), new TestPoint2D(1, -1))
- .boundary(TestPoint2D.ZERO)
- .count(7)
- .check(t -> {
- TestLineSegment minusSeg = (TestLineSegment) t.getRoot().getMinus().getCut();
-
- PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, minusSeg.getStartPoint());
- PartitionTestUtils.assertPointsEqual(new TestPoint2D(0.0, Double.POSITIVE_INFINITY), minusSeg.getEndPoint());
-
- TestLineSegment plusSeg = (TestLineSegment) t.getRoot().getPlus().getCut();
-
- PartitionTestUtils.assertPointsEqual(new TestPoint2D(0.0, Double.NEGATIVE_INFINITY), plusSeg.getStartPoint());
- PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, plusSeg.getEndPoint());
- });
- }
-
- @Test
- public void testXor_boxTreeWithSingleCutTree() {
- // arrange
- Supplier<TestRegionBSPTree> boxFactory = () -> {
- TestRegionBSPTree box = fullTree();
- insertBox(box, TestPoint2D.ZERO, new TestPoint2D(2, -4));
- return box;
- };
-
- Supplier<TestRegionBSPTree> horizonalFactory = () -> {
- TestRegionBSPTree horizontal = fullTree();
- horizontal.getRoot().insertCut(new TestLine(new TestPoint2D(2, -2), new TestPoint2D(0, -2)));
-
- return horizontal;
- };
-
- // act/assert
- xorChecker(horizonalFactory, boxFactory)
- .inside(new TestPoint2D(-1, -3), new TestPoint2D(-1, -5),
- new TestPoint2D(1, -5), new TestPoint2D(3, -5),
- new TestPoint2D(4, -3), new TestPoint2D(1, -1))
- .outside(new TestPoint2D(3, -1), new TestPoint2D(1, -3),
- new TestPoint2D(1, 1), new TestPoint2D(5, -1))
- .boundary(new TestPoint2D(0, -2), new TestPoint2D(0, -4),
- new TestPoint2D(2, -4), new TestPoint2D(2, -2),
- TestPoint2D.ZERO, new TestPoint2D(2, 0))
- .count(15)
- .check();
- }
-
- @Test
- public void testXor_treeWithComplement() {
- // arrange
- Supplier<TestRegionBSPTree> treeFactory = () -> {
- TestRegionBSPTree t = fullTree();
- insertSkewedBowtie(t);
-
- return t;
- };
- Supplier<TestRegionBSPTree> complementFactory = () -> {
- TestRegionBSPTree t = treeFactory.get();
- t.complement();
-
- return t;
- };
-
- // act/assert
- xorChecker(treeFactory, complementFactory)
- .full(true)
- .empty(false)
- .count(1)
- .check();
- }
@Test
public void testProject_emptyAndFull() {
@@ -1800,78 +1528,6 @@ public class AbstractRegionBSPTreeTest {
Assert.assertTrue(tree.getRoot().toString().contains("TestRegionNode"));
}
- private static MergeChecker unionChecker(
- final Supplier<TestRegionBSPTree> r1,
- final Supplier<TestRegionBSPTree> r2) {
-
- MergeChecker.Operation constOperation = (a, b) -> {
- TestRegionBSPTree result = fullTree();
- result.union(a, b);
- return result;
- };
-
- MergeChecker.Operation inPlaceOperation = (a, b) -> {
- a.union(b);
- return a;
- };
-
- return new MergeChecker(r1, r2, constOperation, inPlaceOperation);
- }
-
- private static MergeChecker intersectionChecker(
- final Supplier<TestRegionBSPTree> tree1Factory,
- final Supplier<TestRegionBSPTree> tree2Factory) {
-
- MergeChecker.Operation constOperation = (a, b) -> {
- TestRegionBSPTree result = fullTree();
- result.intersection(a, b);
- return result;
- };
-
- MergeChecker.Operation inPlaceOperation = (a, b) -> {
- a.intersection(b);
- return a;
- };
-
- return new MergeChecker(tree1Factory, tree2Factory, constOperation, inPlaceOperation);
- }
-
- private static MergeChecker differenceChecker(
- final Supplier<TestRegionBSPTree> tree1Factory,
- final Supplier<TestRegionBSPTree> tree2Factory) {
-
- MergeChecker.Operation constOperation = (a, b) -> {
- TestRegionBSPTree result = fullTree();
- result.difference(a, b);
- return result;
- };
-
- MergeChecker.Operation inPlaceOperation = (a, b) -> {
- a.difference(b);
- return a;
- };
-
- return new MergeChecker(tree1Factory, tree2Factory, constOperation, inPlaceOperation);
- }
-
- private static MergeChecker xorChecker(
- final Supplier<TestRegionBSPTree> tree1Factory,
- final Supplier<TestRegionBSPTree> tree2Factory) {
-
- MergeChecker.Operation constOperation = (a, b) -> {
- TestRegionBSPTree result = fullTree();
- result.xor(a, b);
- return result;
- };
-
- MergeChecker.Operation inPlaceOperation = (a, b) -> {
- a.xor(b);
- return a;
- };
-
- return new MergeChecker(tree1Factory, tree2Factory, constOperation, inPlaceOperation);
- }
-
private static void insertBox(final TestRegionBSPTree tree, final TestPoint2D upperLeft,
final TestPoint2D lowerRight) {
final TestPoint2D upperRight = new TestPoint2D(lowerRight.getX(), upperLeft.getY());
@@ -1934,18 +1590,4 @@ public class AbstractRegionBSPTreeTest {
private static TestRegionBSPTree fullTree() {
return new TestRegionBSPTree(true);
}
-
- private static TestRegionBSPTree xAxisTree() {
- TestRegionBSPTree tree = fullTree();
- tree.getRoot().cut(TestLine.X_AXIS);
-
- return tree;
- }
-
- private static TestRegionBSPTree yAxisTree() {
- TestRegionBSPTree tree = fullTree();
- tree.getRoot().cut(TestLine.Y_AXIS);
-
- return tree;
- }
}
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/oned/RegionBSPTree1D.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/oned/RegionBSPTree1D.java
index 6d4ca39..28ba778 100644
--- a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/oned/RegionBSPTree1D.java
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/oned/RegionBSPTree1D.java
@@ -28,6 +28,7 @@ import org.apache.commons.geometry.core.partitioning.Hyperplane;
import org.apache.commons.geometry.core.partitioning.Split;
import org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree;
import org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree;
+import org.apache.commons.geometry.core.partitioning.bsp.RegionCutRule;
/** Binary space partitioning (BSP) tree representing a region in one dimensional
* Euclidean space.
@@ -331,13 +332,13 @@ public final class RegionBSPTree1D extends AbstractRegionBSPTree<Vector1D, Regio
RegionNode1D node = tree.getRoot();
if (minBoundary != null) {
- tree.cutNode(node, minBoundary.span());
+ tree.setNodeCut(node, minBoundary.span(), tree.getSubtreeInitializer(RegionCutRule.MINUS_INSIDE));
node = node.getMinus();
}
if (maxBoundary != null) {
- tree.cutNode(node, maxBoundary.span());
+ tree.setNodeCut(node, maxBoundary.span(), tree.getSubtreeInitializer(RegionCutRule.MINUS_INSIDE));
}
return tree;
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/BoundarySource3D.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/BoundarySource3D.java
index 47dda36..1680559 100644
--- a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/BoundarySource3D.java
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/BoundarySource3D.java
@@ -26,14 +26,16 @@ import org.apache.commons.geometry.core.partitioning.BoundarySource;
*/
public interface BoundarySource3D extends BoundarySource<Facet> {
- /** Construct a new BSP tree from the boundaries contained in this
- * instance.
- * @return a new BSP tree constructed from the boundaries in this
- * instance
- * @see RegionBSPTree3D#from(BoundarySource)
+ /** Return a BSP tree constructed from the boundaries contained in this instance.
+ * The default implementation creates a new, empty tree and inserts the
+ * boundaries from this instance.
+ * @return a BSP tree constructed from the boundaries in this instance
*/
default RegionBSPTree3D toTree() {
- return RegionBSPTree3D.from(this);
+ final RegionBSPTree3D tree = RegionBSPTree3D.empty();
+ tree.insert(this);
+
+ return tree;
}
/** Return a {@link BoundarySource3D} instance containing the given boundaries.
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/ConvexVolume.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/ConvexVolume.java
index 6631054..3d6a063 100644
--- a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/ConvexVolume.java
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/ConvexVolume.java
@@ -129,6 +129,13 @@ public final class ConvexVolume extends AbstractConvexHyperplaneBoundedRegion<Ve
return splitInternal(splitter, this, Facet.class, ConvexVolume::new);
}
+ /** Return a BSP tree representing the same region as this instance.
+ */
+ @Override
+ public RegionBSPTree3D toTree() {
+ return RegionBSPTree3D.from(getBoundaries(), true);
+ }
+
/** {@inheritDoc} */
@Override
public List<LinecastPoint3D> linecast(final Segment3D segment) {
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/RegionBSPTree3D.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/RegionBSPTree3D.java
index 3c424d1..071f3b7 100644
--- a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/RegionBSPTree3D.java
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/RegionBSPTree3D.java
@@ -21,7 +21,6 @@ import java.util.List;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;
-import org.apache.commons.geometry.core.partitioning.BoundarySource;
import org.apache.commons.geometry.core.partitioning.Hyperplane;
import org.apache.commons.geometry.core.partitioning.Split;
import org.apache.commons.geometry.core.partitioning.SubHyperplane;
@@ -136,6 +135,13 @@ public final class RegionBSPTree3D extends AbstractRegionBSPTree<Vector3D, Regio
return projector.getProjected();
}
+ /** Return the current instance.
+ */
+ @Override
+ public RegionBSPTree3D toTree() {
+ return this;
+ }
+
/** {@inheritDoc} */
@Override
public List<LinecastPoint3D> linecast(final Segment3D segment) {
@@ -191,26 +197,25 @@ public final class RegionBSPTree3D extends AbstractRegionBSPTree<Vector3D, Regio
}
/** Construct a new tree from the given boundaries. If no boundaries
- * are present, the returned tree contains the full space.
+ * are present, the returned tree is empty.
* @param boundaries boundaries to construct the tree from
* @return a new tree instance constructed from the given boundaries
+ * @see #from(Iterable, boolean)
*/
public static RegionBSPTree3D from(final Iterable<Facet> boundaries) {
- final RegionBSPTree3D tree = RegionBSPTree3D.full();
- tree.insert(boundaries);
-
- return tree;
+ return from(boundaries, false);
}
- /** Construct a new tree from the boundaries in the given boundary source. If no boundaries
- * are present in the given source, their the returned tree contains the full space.
- * @param boundarySrc boundary source to construct a tree from
- * @return a new tree instance constructed from the boundaries in the
- * given source
+ /** Construct a new tree from the given boundaries. If {@code full} is true, then
+ * the initial tree before boundary insertion contains the entire space. Otherwise,
+ * it is empty.
+ * @param boundaries boundaries to construct the tree from
+ * @param full if true, the initial tree will contain the entire space
+ * @return a new tree instance constructed from the given boundaries
*/
- public static RegionBSPTree3D from(final BoundarySource<Facet> boundarySrc) {
- final RegionBSPTree3D tree = RegionBSPTree3D.full();
- tree.insert(boundarySrc);
+ public static RegionBSPTree3D from(final Iterable<Facet> boundaries, final boolean full) {
+ final RegionBSPTree3D tree = new RegionBSPTree3D(full);
+ tree.insert(boundaries);
return tree;
}
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/BoundarySource2D.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/BoundarySource2D.java
index 561b144..ec0fe30 100644
--- a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/BoundarySource2D.java
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/BoundarySource2D.java
@@ -26,14 +26,16 @@ import org.apache.commons.geometry.core.partitioning.BoundarySource;
*/
public interface BoundarySource2D extends BoundarySource<Segment> {
- /** Construct a new BSP tree from the boundaries contained in this
- * instance.
- * @return a new BSP tree constructed from the boundaries in this
- * instance
- * @see RegionBSPTree2D#from(BoundarySource)
+ /** Return a BSP tree constructed from the boundaries contained in this
+ * instance. The default implementation creates a new, empty tree
+ * and inserts the boundaries from this instance.
+ * @return a BSP tree constructed from the boundaries in this instance
*/
default RegionBSPTree2D toTree() {
- return RegionBSPTree2D.from(this);
+ final RegionBSPTree2D tree = RegionBSPTree2D.empty();
+ tree.insert(this);
+
+ return tree;
}
/** Return a {@link BoundarySource2D} instance containing the given segments.
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/ConvexArea.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/ConvexArea.java
index b9ad8c0..ba9f64a 100644
--- a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/ConvexArea.java
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/ConvexArea.java
@@ -165,6 +165,13 @@ public final class ConvexArea extends AbstractConvexHyperplaneBoundedRegion<Vect
return splitInternal(splitter, this, Segment.class, ConvexArea::new);
}
+ /** Return a BSP tree representing the same region as this instance.
+ */
+ @Override
+ public RegionBSPTree2D toTree() {
+ return RegionBSPTree2D.from(getBoundaries(), true);
+ }
+
/** {@inheritDoc} */
@Override
public List<LinecastPoint2D> linecast(final Segment segment) {
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/RegionBSPTree2D.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/RegionBSPTree2D.java
index 77d74fc..3e3c12a 100644
--- a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/RegionBSPTree2D.java
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/RegionBSPTree2D.java
@@ -23,7 +23,6 @@ import java.util.stream.Collectors;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;
-import org.apache.commons.geometry.core.partitioning.BoundarySource;
import org.apache.commons.geometry.core.partitioning.Hyperplane;
import org.apache.commons.geometry.core.partitioning.Split;
import org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree;
@@ -101,7 +100,7 @@ public final class RegionBSPTree2D extends AbstractRegionBSPTree<Vector2D, Regio
* @param area the convex area to add
*/
public void add(final ConvexArea area) {
- union(from(area));
+ union(area.toTree());
}
/** Return a list of {@link ConvexArea}s representing the same region
@@ -157,6 +156,13 @@ public final class RegionBSPTree2D extends AbstractRegionBSPTree<Vector2D, Regio
return projector.getProjected();
}
+ /** Return the current instance.
+ */
+ @Override
+ public RegionBSPTree2D toTree() {
+ return this;
+ }
+
/** {@inheritDoc} */
@Override
public List<LinecastPoint2D> linecast(final Segment segment) {
@@ -275,26 +281,25 @@ public final class RegionBSPTree2D extends AbstractRegionBSPTree<Vector2D, Regio
}
/** Construct a new tree from the given boundaries. If no boundaries
- * are present, the returned tree contains the full space.
+ * are present, the returned tree is empty.
* @param boundaries boundaries to construct the tree from
* @return a new tree instance constructed from the given boundaries
+ * @see #from(Iterable, boolean)
*/
public static RegionBSPTree2D from(final Iterable<Segment> boundaries) {
- final RegionBSPTree2D tree = RegionBSPTree2D.full();
- tree.insert(boundaries);
-
- return tree;
+ return from(boundaries, false);
}
- /** Construct a new tree from the boundaries in the given boundary source. If no boundaries
- * are present in the given source, their the returned tree contains the full space.
- * @param boundarySrc boundary source to construct a tree from
- * @return a new tree instance constructed from the boundaries in the
- * given source
+ /** Construct a new tree from the given boundaries. If {@code full} is true, then
+ * the initial tree before boundary insertion contains the entire space. Otherwise,
+ * it is empty.
+ * @param boundaries boundaries to construct the tree from
+ * @param full if true, the initial tree will contain the entire space
+ * @return a new tree instance constructed from the given boundaries
*/
- public static RegionBSPTree2D from(final BoundarySource<Segment> boundarySrc) {
- final RegionBSPTree2D tree = RegionBSPTree2D.full();
- tree.insert(boundarySrc);
+ public static RegionBSPTree2D from(final Iterable<Segment> boundaries, final boolean full) {
+ final RegionBSPTree2D tree = new RegionBSPTree2D(full);
+ tree.insert(boundaries);
return tree;
}
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/DocumentationExamplesTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/DocumentationExamplesTest.java
index 31eb242..a6afc2c 100644
--- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/DocumentationExamplesTest.java
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/DocumentationExamplesTest.java
@@ -22,6 +22,7 @@ import java.util.stream.Collectors;
import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.core.partitioning.Split;
+import org.apache.commons.geometry.core.partitioning.bsp.RegionCutRule;
import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
import org.apache.commons.geometry.euclidean.oned.Interval;
@@ -131,29 +132,40 @@ public class DocumentationExamplesTest {
// create a tree representing an empty space (nothing "inside")
RegionBSPTree2D tree = RegionBSPTree2D.empty();
- // get the root node
- RegionBSPTree2D.RegionNode2D currentNode = tree.getRoot();
+ // insert a "structural" cut, meaning a cut whose children have the same inside/outside
+ // status as the parent; this will help keep our tree balanced and limit its overall height
+ tree.getRoot().insertCut(Line.fromPointAndDirection(Vector2D.ZERO, Vector2D.of(1, 1), precision),
+ RegionCutRule.INHERIT);
+
+ RegionBSPTree2D.RegionNode2D currentNode;
+
+ // insert on the plus side of the structural diagonal cut
+ currentNode = tree.getRoot().getPlus();
- // cut each minus node with the next hyperplane in the shape
currentNode.insertCut(Line.fromPointAndDirection(Vector2D.ZERO, Vector2D.Unit.PLUS_X, precision));
currentNode = currentNode.getMinus();
- currentNode.insertCut(Line.fromPointAndDirection(Vector2D.Unit.PLUS_X, Vector2D.of(-1, 1), precision));
- currentNode = currentNode.getMinus();
+ currentNode.insertCut(Line.fromPointAndDirection(Vector2D.of(1, 0), Vector2D.Unit.PLUS_Y, precision));
- currentNode.insertCut(Line.fromPointAndDirection(Vector2D.Unit.PLUS_Y, Vector2D.Unit.MINUS_Y, precision));
+ // insert on the plus side of the structural diagonal cut
+ currentNode = tree.getRoot().getMinus();
+
+ currentNode.insertCut(Line.fromPointAndDirection(Vector2D.of(1, 1), Vector2D.Unit.MINUS_X, precision));
currentNode = currentNode.getMinus();
- currentNode.isInside(); // true (node is inside)
- currentNode.getParent().getPlus().isInside(); // false (sibling node is outside)
- tree.getSize(); // size of the region = 0.5
- tree.count(); // number of nodes in the tree = 7
+ currentNode.insertCut(Line.fromPointAndDirection(Vector2D.of(0, 1), Vector2D.Unit.MINUS_Y, precision));
+
+ // compute some tree properties
+ int count = tree.count(); // number of nodes in the tree = 11
+ int height = tree.height(); // height of the tree = 3
+ double size = tree.getSize(); // size of the region = 1
+ Vector2D barycenter = tree.getBarycenter(); // region barycenter = (0.5, 0.5)
// ---------
- Assert.assertTrue(currentNode.isInside());
- Assert.assertFalse(currentNode.getParent().getPlus().isInside());
- Assert.assertEquals(0.5, tree.getSize(), TEST_EPS);
- Assert.assertEquals(7, tree.count());
+ Assert.assertEquals(1, size, TEST_EPS);
+ Assert.assertEquals(11, count);
+ Assert.assertEquals(3, height);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0.5), barycenter, TEST_EPS);
}
@Test
@@ -165,17 +177,23 @@ public class DocumentationExamplesTest {
// insert the subhyperplanes
tree.insert(Arrays.asList(
- Segment.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, precision),
- Segment.fromPoints(Vector2D.Unit.PLUS_X, Vector2D.Unit.PLUS_Y, precision),
- Segment.fromPoints(Vector2D.Unit.PLUS_Y, Vector2D.ZERO, precision)
+ Segment.fromPoints(Vector2D.ZERO, Vector2D.of(1, 0), precision),
+ Segment.fromPoints(Vector2D.of(1, 0), Vector2D.of(1, 1), precision),
+ Segment.fromPoints(Vector2D.of(1, 1), Vector2D.of(0, 1), precision),
+ Segment.fromPoints(Vector2D.of(0, 1), Vector2D.ZERO, precision)
));
- tree.getSize(); // size of the region = 0.5
- tree.count(); // number of nodes in the tree = 7
+ // compute some tree properties
+ int count = tree.count(); // number of nodes in the tree = 9
+ int height = tree.height(); // height of the tree = 4
+ double size = tree.getSize(); // size of the region = 1
+ Vector2D barycenter = tree.getBarycenter(); // region barycenter = (0.5, 0.5)
// ---------
- Assert.assertEquals(0.5, tree.getSize(), TEST_EPS);
- Assert.assertEquals(7, tree.count());
+ Assert.assertEquals(1, size, TEST_EPS);
+ Assert.assertEquals(9, count);
+ Assert.assertEquals(4, height);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0.5), barycenter, TEST_EPS);
}
@Test
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/BoundarySource3DTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/BoundarySource3DTest.java
index 496109a..bdc0636 100644
--- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/BoundarySource3DTest.java
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/BoundarySource3DTest.java
@@ -34,6 +34,39 @@ public class BoundarySource3DTest {
new EpsilonDoublePrecisionContext(TEST_EPS);
@Test
+ public void testToTree() {
+ // act
+ Facet a = Facet.fromVertexLoop(
+ Arrays.asList(Vector3D.ZERO, Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y), TEST_PRECISION);
+ Facet b = Facet.fromVertexLoop(
+ Arrays.asList(Vector3D.ZERO, Vector3D.Unit.PLUS_Y, Vector3D.Unit.MINUS_Z), TEST_PRECISION);
+
+ BoundarySource3D src = BoundarySource3D.from(a, b);
+
+ // act
+ RegionBSPTree3D tree = src.toTree();
+
+ // assert
+ Assert.assertEquals(5, tree.count());
+ Assert.assertFalse(tree.isFull());
+ Assert.assertFalse(tree.isEmpty());
+ }
+
+ @Test
+ public void testToTree_noBoundaries() {
+ // act
+ BoundarySource3D src = BoundarySource3D.from();
+
+ // act
+ RegionBSPTree3D tree = src.toTree();
+
+ // assert
+ Assert.assertEquals(1, tree.count());
+ Assert.assertFalse(tree.isFull());
+ Assert.assertTrue(tree.isEmpty());
+ }
+
+ @Test
public void testFrom_varargs_empty() {
// act
BoundarySource3D src = BoundarySource3D.from();
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/ConvexVolumeTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/ConvexVolumeTest.java
index b84959a..f88d917 100644
--- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/ConvexVolumeTest.java
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/ConvexVolumeTest.java
@@ -85,6 +85,19 @@ public class ConvexVolumeTest {
}
@Test
+ public void testToTree_full() {
+ // arrange
+ ConvexVolume volume = ConvexVolume.full();
+
+ // act
+ RegionBSPTree3D tree = volume.toTree();
+
+ // assert
+ Assert.assertTrue(tree.isFull());
+ Assert.assertFalse(tree.isEmpty());
+ }
+
+ @Test
public void testToTree() {
// arrange
ConvexVolume volume = ConvexVolume.fromBounds(
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/RegionBSPTree3DTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/RegionBSPTree3DTest.java
index 547bf43..ee01f16 100644
--- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/RegionBSPTree3DTest.java
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/RegionBSPTree3DTest.java
@@ -27,6 +27,7 @@ import org.apache.commons.geometry.core.GeometryTestUtils;
import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.core.partitioning.Split;
import org.apache.commons.geometry.core.partitioning.SplitLocation;
+import org.apache.commons.geometry.core.partitioning.bsp.RegionCutRule;
import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
@@ -173,17 +174,12 @@ public class RegionBSPTree3DTest {
}
@Test
- public void testToTree_returnsNewTree() {
+ public void testToTree_returnsSameInstance() {
// arrange
RegionBSPTree3D tree = createRect(Vector3D.ZERO, Vector3D.of(1, 2, 1));
- // act
- RegionBSPTree3D result = tree.toTree();
-
- // assert
- Assert.assertEquals(6, result.getBoundaries().size());
- Assert.assertEquals(2, result.getSize(), TEST_EPS);
- EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0.5, 1, 0.5), result.getBarycenter(), TEST_EPS);
+ // act/assert
+ Assert.assertSame(tree, tree.toTree());
}
@Test
@@ -210,14 +206,55 @@ public class RegionBSPTree3DTest {
}
@Test
- public void testFrom_boundaries_noBoundaries() {
+ public void testGeometricProperties_mixedCutRules() {
// act
- RegionBSPTree3D tree = RegionBSPTree3D.from(Arrays.asList());
+ RegionBSPTree3D tree = RegionBSPTree3D.empty();
+
+ Vector3D min = Vector3D.ZERO;
+ Vector3D max = Vector3D.of(1, 1, 1);
+
+ Plane top = Plane.fromPointAndNormal(max, Vector3D.Unit.PLUS_Z, TEST_PRECISION);
+ Plane bottom = Plane.fromPointAndNormal(min, Vector3D.Unit.MINUS_Z, TEST_PRECISION);
+ Plane left = Plane.fromPointAndNormal(min, Vector3D.Unit.MINUS_X, TEST_PRECISION);
+ Plane right = Plane.fromPointAndNormal(max, Vector3D.Unit.PLUS_X, TEST_PRECISION);
+ Plane front = Plane.fromPointAndNormal(min, Vector3D.Unit.MINUS_Y, TEST_PRECISION);
+ Plane back = Plane.fromPointAndNormal(max, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
+
+ Plane diag = Plane.fromPointAndNormal(Vector3D.of(0.5, 0.5, 0.5), Vector3D.of(0.5, -0.5, 0), TEST_PRECISION);
+ Plane midCut = Plane.fromPointAndNormal(Vector3D.of(0.5, 0.5, 0.5), Vector3D.Unit.PLUS_Z, TEST_PRECISION);
+
+ tree.getRoot()
+ .cut(diag, RegionCutRule.INHERIT);
+
+ tree.getRoot()
+ .getMinus().cut(top)
+ .getMinus().cut(bottom.reverse(), RegionCutRule.PLUS_INSIDE)
+ .getPlus().cut(left, RegionCutRule.MINUS_INSIDE)
+ .getMinus().cut(back.reverse(), RegionCutRule.PLUS_INSIDE)
+ .getPlus().cut(midCut, RegionCutRule.INHERIT);
+
+ tree.getRoot()
+ .getPlus().cut(top.reverse(), RegionCutRule.PLUS_INSIDE)
+ .getPlus().cut(bottom)
+ .getMinus().cut(right, RegionCutRule.MINUS_INSIDE)
+ .getMinus().cut(front.reverse(), RegionCutRule.PLUS_INSIDE)
+ .getPlus().cut(midCut, RegionCutRule.INHERIT);
// assert
- Assert.assertNull(tree.getBarycenter());
- Assert.assertTrue(tree.isFull());
Assert.assertFalse(tree.isEmpty());
+ Assert.assertFalse(tree.isFull());
+
+ Assert.assertEquals(1, tree.getSize(), TEST_EPS);
+ Assert.assertEquals(6, tree.getBoundarySize(), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0.5, 0.5, 0.5), tree.getBarycenter(), TEST_EPS);
+
+ EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE, Vector3D.of(0.5, 0.5, 0.5));
+ EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.BOUNDARY, min, max);
+ EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
+ Vector3D.of(2, 2, 2), Vector3D.of(2, 2, -2),
+ Vector3D.of(2, -2, 2), Vector3D.of(2, -2, -2),
+ Vector3D.of(-2, 2, 2), Vector3D.of(-2, 2, -2),
+ Vector3D.of(-2, -2, 2), Vector3D.of(-2, -2, -2));
}
@Test
@@ -234,6 +271,31 @@ public class RegionBSPTree3DTest {
Assert.assertFalse(tree.isFull());
Assert.assertFalse(tree.isEmpty());
+ Assert.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getLocation());
+
+ EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
+ Vector3D.of(1, 1, -1), Vector3D.of(-1, 1, -1));
+ EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
+ Vector3D.of(1, 1, 1), Vector3D.of(-1, 1, 1), Vector3D.of(1, -1, 1),
+ Vector3D.of(-1, -1, 1), Vector3D.of(1, -1, -1), Vector3D.of(-1, -1, -1));
+ }
+
+ @Test
+ public void testFrom_boundaries_fullIsTrue() {
+ // act
+ RegionBSPTree3D tree = RegionBSPTree3D.from(Arrays.asList(
+ Facet.fromVertexLoop(Arrays.asList(
+ Vector3D.ZERO, Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y), TEST_PRECISION),
+ Facet.fromVertexLoop(Arrays.asList(
+ Vector3D.ZERO, Vector3D.Unit.MINUS_Z, Vector3D.Unit.PLUS_X), TEST_PRECISION)
+ ), true);
+
+ // assert
+ Assert.assertFalse(tree.isFull());
+ Assert.assertFalse(tree.isEmpty());
+
+ Assert.assertEquals(RegionLocation.INSIDE, tree.getRoot().getLocation());
+
EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.INSIDE,
Vector3D.of(1, 1, -1), Vector3D.of(-1, 1, -1));
EuclideanTestUtils.assertRegionLocation(tree, RegionLocation.OUTSIDE,
@@ -242,12 +304,20 @@ public class RegionBSPTree3DTest {
}
@Test
+ public void testFrom_boundaries_noBoundaries() {
+ // act/assert
+ Assert.assertTrue(RegionBSPTree3D.from(Arrays.asList()).isEmpty());
+ Assert.assertTrue(RegionBSPTree3D.from(Arrays.asList(), true).isFull());
+ Assert.assertTrue(RegionBSPTree3D.from(Arrays.asList(), false).isEmpty());
+ }
+
+ @Test
public void testFromConvexVolume_full() {
// arrange
ConvexVolume volume = ConvexVolume.full();
// act
- RegionBSPTree3D tree = RegionBSPTree3D.from(volume);
+ RegionBSPTree3D tree = volume.toTree();
Assert.assertNull(tree.getBarycenter());
// assert
@@ -260,7 +330,7 @@ public class RegionBSPTree3DTest {
ConvexVolume volume = ConvexVolume.fromBounds(Plane.fromNormal(Vector3D.Unit.PLUS_Z, TEST_PRECISION));
// act
- RegionBSPTree3D tree = RegionBSPTree3D.from(volume);
+ RegionBSPTree3D tree = volume.toTree();
// assert
GeometryTestUtils.assertPositiveInfinity(tree.getSize());
@@ -286,7 +356,7 @@ public class RegionBSPTree3DTest {
);
// act
- RegionBSPTree3D tree = RegionBSPTree3D.from(volume);
+ RegionBSPTree3D tree = volume.toTree();
// assert
Assert.assertEquals(1, tree.getSize(), TEST_EPS);
@@ -534,7 +604,7 @@ public class RegionBSPTree3DTest {
// Issue GEOMETRY-43
@Test
- public void testFirstIntersection_lineParallelToFace() {
+ public void testLinecastFirst_lineParallelToFace() {
// arrange - setup box
Vector3D lowerCorner = Vector3D.ZERO;
Vector3D upperCorner = Vector3D.of(1, 1, 1);
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/SubPlaneTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/SubPlaneTest.java
index 8df4201..13b0070 100644
--- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/SubPlaneTest.java
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/SubPlaneTest.java
@@ -348,7 +348,7 @@ public class SubPlaneTest {
Arrays.asList(Vector2D.ZERO, Vector2D.Unit.PLUS_X, Vector2D.Unit.PLUS_Y), TEST_PRECISION);
Plane plane = Plane.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1), Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
- SubPlane sp = new SubPlane(plane, RegionBSPTree2D.from(area));
+ SubPlane sp = new SubPlane(plane, area.toTree());
Transform<Vector3D> transform = AffineTransformMatrix3D.identity()
.rotate(QuaternionRotation.fromAxisAngle(Vector3D.Unit.PLUS_Y, PlaneAngleRadians.PI_OVER_TWO))
@@ -378,7 +378,7 @@ public class SubPlaneTest {
Arrays.asList(Vector2D.ZERO, Vector2D.Unit.PLUS_X, Vector2D.Unit.PLUS_Y), TEST_PRECISION);
Plane plane = Plane.fromPointAndPlaneVectors(Vector3D.of(0, 0, 1), Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
- SubPlane sp = new SubPlane(plane, RegionBSPTree2D.from(area));
+ SubPlane sp = new SubPlane(plane, area.toTree());
Transform<Vector3D> transform = AffineTransformMatrix3D.createScale(-1, 1, 1);
@@ -429,7 +429,7 @@ public class SubPlaneTest {
// act
builder.add(Facet.fromConvexArea(closePlane, a));
- builder.add(new SubPlane(closePlane, RegionBSPTree2D.from(b)));
+ builder.add(new SubPlane(closePlane, b.toTree()));
SubPlane result = builder.build();
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/BoundarySource2DTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/BoundarySource2DTest.java
index 476caf9..130ec5f 100644
--- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/BoundarySource2DTest.java
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/BoundarySource2DTest.java
@@ -33,6 +33,37 @@ public class BoundarySource2DTest {
new EpsilonDoublePrecisionContext(TEST_EPS);
@Test
+ public void testToTree() {
+ // act
+ BoundarySource2D src = BoundarySource2D.from(
+ Segment.fromPoints(Vector2D.ZERO, Vector2D.of(1, 0), TEST_PRECISION),
+ Segment.fromPoints(Vector2D.of(1, 0), Vector2D.of(1, 1), TEST_PRECISION)
+ );
+
+ // act
+ RegionBSPTree2D tree = src.toTree();
+
+ // assert
+ Assert.assertEquals(5, tree.count());
+ Assert.assertFalse(tree.isFull());
+ Assert.assertFalse(tree.isEmpty());
+ }
+
+ @Test
+ public void testToTree_noBoundaries() {
+ // act
+ BoundarySource2D src = BoundarySource2D.from();
+
+ // act
+ RegionBSPTree2D tree = src.toTree();
+
+ // assert
+ Assert.assertEquals(1, tree.count());
+ Assert.assertFalse(tree.isFull());
+ Assert.assertTrue(tree.isEmpty());
+ }
+
+ @Test
public void testFrom_varargs_empty() {
// act
BoundarySource2D src = BoundarySource2D.from();
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/ConvexAreaTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/ConvexAreaTest.java
index e1cc990..7770fd3 100644
--- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/ConvexAreaTest.java
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/ConvexAreaTest.java
@@ -97,11 +97,27 @@ public class ConvexAreaTest {
RegionBSPTree2D tree = area.toTree();
// assert
+ Assert.assertFalse(tree.isFull());
+ Assert.assertFalse(tree.isEmpty());
+
Assert.assertEquals(1, tree.getSize(), TEST_EPS);
EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0.5), tree.getBarycenter(), TEST_EPS);
}
@Test
+ public void testToTree_full() {
+ // arrange
+ ConvexArea area = ConvexArea.full();
+
+ // act
+ RegionBSPTree2D tree = area.toTree();
+
+ // assert
+ Assert.assertTrue(tree.isFull());
+ Assert.assertFalse(tree.isEmpty());
+ }
+
+ @Test
public void testTransform_full() {
// arrange
AffineTransformMatrix2D transform = AffineTransformMatrix2D.createScale(3);
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/RegionBSPTree2DTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/RegionBSPTree2DTest.java
index b224382..91d36b2 100644
--- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/RegionBSPTree2DTest.java
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/RegionBSPTree2DTest.java
@@ -28,6 +28,7 @@ import org.apache.commons.geometry.core.Region;
import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.core.partitioning.Split;
import org.apache.commons.geometry.core.partitioning.SplitLocation;
+import org.apache.commons.geometry.core.partitioning.bsp.RegionCutRule;
import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
@@ -313,8 +314,7 @@ public class RegionBSPTree2DTest {
@Test
public void testToConvex_square() {
// arrange
- RegionBSPTree2D tree = RegionBSPTree2D.from(
- Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION));
+ RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION).toTree();
// act
List<ConvexArea> result = tree.toConvex();
@@ -667,6 +667,44 @@ public class RegionBSPTree2DTest {
}
@Test
+ public void testGeometricProperties_mixedCutRule() {
+ // arrange
+ RegionBSPTree2D tree = RegionBSPTree2D.empty();
+
+ tree.getRoot().cut(Line.fromPointAndAngle(Vector2D.ZERO, 0.25 * Math.PI, TEST_PRECISION),
+ RegionCutRule.INHERIT);
+
+ tree.getRoot()
+ .getPlus().cut(X_AXIS, RegionCutRule.MINUS_INSIDE)
+ .getMinus().cut(Line.fromPointAndAngle(Vector2D.of(1, 0), 0.5 * Math.PI, TEST_PRECISION));
+
+ tree.getRoot()
+ .getMinus().cut(Line.fromPointAndAngle(Vector2D.ZERO, 0.5 * Math.PI, TEST_PRECISION), RegionCutRule.PLUS_INSIDE)
+ .getPlus().cut(Line.fromPointAndAngle(Vector2D.of(1, 1), Math.PI, TEST_PRECISION))
+ .getMinus().cut(Line.fromPointAndAngle(Vector2D.of(0.5, 0.5), 0.75 * Math.PI, TEST_PRECISION), RegionCutRule.INHERIT);
+
+ // act/assert
+ Assert.assertEquals(1, tree.getSize(), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0.5), tree.getBarycenter(), TEST_EPS);
+
+ Assert.assertEquals(4, tree.getBoundarySize(), TEST_EPS);
+
+ List<Polyline> paths = tree.getBoundaryPaths();
+ Assert.assertEquals(1, paths.size());
+
+ Polyline path = paths.get(0);
+ Assert.assertEquals(4, path.getSegments().size());
+
+ List<Vector2D> vertices = path.getVertices();
+ Assert.assertEquals(5, vertices.size());
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, vertices.get(0), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 0), vertices.get(1), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(1, 1), vertices.get(2), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0, 1), vertices.get(3), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector2D.ZERO, vertices.get(4), TEST_EPS);
+ }
+
+ @Test
public void testGeometricProperties_complementedQuadrant() {
// arrange
RegionBSPTree2D tree = RegionBSPTree2D.empty();
@@ -846,17 +884,6 @@ public class RegionBSPTree2DTest {
}
@Test
- public void testFrom_boundaries_noBoundaries() {
- // act
- RegionBSPTree2D tree = RegionBSPTree2D.from(Arrays.asList());
-
- // assert
- Assert.assertNull(tree.getBarycenter());
- Assert.assertTrue(tree.isFull());
- Assert.assertFalse(tree.isEmpty());
- }
-
- @Test
public void testFrom_boundaries() {
// act
RegionBSPTree2D tree = RegionBSPTree2D.from(Arrays.asList(
@@ -869,92 +896,48 @@ public class RegionBSPTree2DTest {
Assert.assertFalse(tree.isFull());
Assert.assertFalse(tree.isEmpty());
+ Assert.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getLocation());
+
checkClassify(tree, RegionLocation.INSIDE, Vector2D.of(-1, 1));
checkClassify(tree, RegionLocation.OUTSIDE,
Vector2D.of(1, 1), Vector2D.of(1, -1), Vector2D.of(-1, -1));
}
@Test
- public void testFrom_boundarySource_noBoundaries() {
- // arrange
- BoundarySource2D src = BoundarySource2D.from();
-
+ public void testFrom_boundaries_fullIsTrue() {
// act
- RegionBSPTree2D tree = RegionBSPTree2D.from(src);
+ RegionBSPTree2D tree = RegionBSPTree2D.from(Arrays.asList(
+ Line.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION).span(),
+ Line.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_Y, TEST_PRECISION)
+ .segmentFrom(Vector2D.ZERO)
+ ), true);
// assert
- Assert.assertNull(tree.getBarycenter());
- Assert.assertTrue(tree.isFull());
+ Assert.assertFalse(tree.isFull());
Assert.assertFalse(tree.isEmpty());
- }
-
- @Test
- public void testFromConvexArea_full() {
- // arrange
- ConvexArea area = ConvexArea.full();
-
- // act
- RegionBSPTree2D tree = RegionBSPTree2D.from(area);
-
- // assert
- Assert.assertNull(tree.getBarycenter());
- Assert.assertTrue(tree.isFull());
- }
-
- @Test
- public void testFromConvexArea_infinite() {
- // arrange
- ConvexArea area = ConvexArea.fromVertices(
- Arrays.asList(Vector2D.ZERO, Vector2D.Unit.PLUS_Y), TEST_PRECISION);
- // act
- RegionBSPTree2D tree = RegionBSPTree2D.from(area);
-
- // assert
- GeometryTestUtils.assertPositiveInfinity(tree.getSize());
- GeometryTestUtils.assertPositiveInfinity(tree.getBoundarySize());
- Assert.assertNull(tree.getBarycenter());
+ Assert.assertEquals(RegionLocation.INSIDE, tree.getRoot().getLocation());
- checkClassify(tree, RegionLocation.OUTSIDE, Vector2D.of(1, 0));
- checkClassify(tree, RegionLocation.BOUNDARY, Vector2D.ZERO);
- checkClassify(tree, RegionLocation.INSIDE, Vector2D.of(-1, 0));
+ checkClassify(tree, RegionLocation.INSIDE, Vector2D.of(-1, 1));
+ checkClassify(tree, RegionLocation.OUTSIDE,
+ Vector2D.of(1, 1), Vector2D.of(1, -1), Vector2D.of(-1, -1));
}
@Test
- public void testFromConvexArea_finite() {
- // arrange
- ConvexArea area = ConvexArea.fromVertexLoop(
- Arrays.asList(Vector2D.ZERO, Vector2D.Unit.PLUS_X, Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y), TEST_PRECISION);
-
- // act
- RegionBSPTree2D tree = RegionBSPTree2D.from(area);
-
- // assert
- Assert.assertEquals(1, tree.getSize(), TEST_EPS);
- Assert.assertEquals(4, tree.getBoundarySize(), TEST_EPS);
- EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 0.5), tree.getBarycenter(), TEST_EPS);
-
- checkClassify(tree, RegionLocation.OUTSIDE,
- Vector2D.of(-1, 0.5), Vector2D.of(2, 0.5),
- Vector2D.of(0.5, -1), Vector2D.of(0.5, 2));
- checkClassify(tree, RegionLocation.BOUNDARY,
- Vector2D.of(0, 0.5), Vector2D.of(1, 0.5),
- Vector2D.of(0.5, 0), Vector2D.of(0.5, 1));
- checkClassify(tree, RegionLocation.INSIDE, Vector2D.of(0.5, 0.5));
+ public void testFrom_boundaries_noBoundaries() {
+ // act/assert
+ Assert.assertTrue(RegionBSPTree2D.from(Arrays.asList()).isEmpty());
+ Assert.assertTrue(RegionBSPTree2D.from(Arrays.asList(), true).isFull());
+ Assert.assertTrue(RegionBSPTree2D.from(Arrays.asList(), false).isEmpty());
}
@Test
- public void testToTree_returnsNewTree() {
+ public void testToTree_returnsSameInstance() {
// arrange
RegionBSPTree2D tree = Parallelogram.axisAligned(Vector2D.ZERO, Vector2D.of(1, 2), TEST_PRECISION).toTree();
- // act
- RegionBSPTree2D result = tree.toTree();
-
- // assert
- Assert.assertNotSame(tree, result);
- Assert.assertEquals(2, result.getSize(), TEST_EPS);
- EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(0.5, 1), result.getBarycenter(), TEST_EPS);
+ // act/assert
+ Assert.assertSame(tree, tree.toTree());
}
@Test
diff --git a/commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/twod/BoundarySource2S.java b/commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/twod/BoundarySource2S.java
index f0173c1..190e53b 100644
--- a/commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/twod/BoundarySource2S.java
+++ b/commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/twod/BoundarySource2S.java
@@ -23,13 +23,15 @@ import org.apache.commons.geometry.core.partitioning.BoundarySource;
*/
public interface BoundarySource2S extends BoundarySource<GreatArc> {
- /** Construct a new BSP tree from the boundaries contained in this
- * instance.
- * @return a new BSP tree constructed from the boundaries in this
- * instance
- * @see RegionBSPTree2S#from(BoundarySource)
+ /** Return a BSP tree constructed from the boundaries contained in this
+ * instance. The default implementation creates a new, empty tree
+ * and inserts the boundaries from this instance.
+ * @return a BSP tree constructed from the boundaries in this instance
*/
default RegionBSPTree2S toTree() {
- return RegionBSPTree2S.from(this);
+ final RegionBSPTree2S tree = RegionBSPTree2S.empty();
+ tree.insert(this);
+
+ return tree;
}
}
diff --git a/commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/twod/ConvexArea2S.java b/commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/twod/ConvexArea2S.java
index 8e3c0a0..39a48b2 100644
--- a/commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/twod/ConvexArea2S.java
+++ b/commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/twod/ConvexArea2S.java
@@ -169,6 +169,13 @@ public final class ConvexArea2S extends AbstractConvexHyperplaneBoundedRegion<Po
return splitInternal(splitter, this, GreatArc.class, ConvexArea2S::new);
}
+ /** Return a BSP tree representing the same region as this instance.
+ */
+ @Override
+ public RegionBSPTree2S toTree() {
+ return RegionBSPTree2S.from(getBoundaries(), true);
+ }
+
/** Return a new instance transformed by the argument.
* @param transform transform to apply
* @return a new instance transformed by the argument
diff --git a/commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/twod/RegionBSPTree2S.java b/commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/twod/RegionBSPTree2S.java
index c62e920..1c5e38e 100644
--- a/commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/twod/RegionBSPTree2S.java
+++ b/commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/twod/RegionBSPTree2S.java
@@ -22,7 +22,6 @@ import java.util.List;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;
-import org.apache.commons.geometry.core.partitioning.BoundarySource;
import org.apache.commons.geometry.core.partitioning.Hyperplane;
import org.apache.commons.geometry.core.partitioning.Split;
import org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree;
@@ -151,6 +150,13 @@ public class RegionBSPTree2S extends AbstractRegionBSPTree<Point2S, RegionBSPTre
return projector.getProjected();
}
+ /** Return the current instance.
+ */
+ @Override
+ public RegionBSPTree2S toTree() {
+ return this;
+ }
+
/** {@inheritDoc} */
@Override
protected RegionSizeProperties<Point2S> computeRegionSizeProperties() {
@@ -217,26 +223,25 @@ public class RegionBSPTree2S extends AbstractRegionBSPTree<Point2S, RegionBSPTre
}
/** Construct a new tree from the given boundaries. If no boundaries
- * are present, the returned tree contains the full space.
+ * are present, the returned tree is empty.
* @param boundaries boundaries to construct the tree from
* @return a new tree instance constructed from the given boundaries
+ * @see #from(Iterable, boolean)
*/
public static RegionBSPTree2S from(final Iterable<GreatArc> boundaries) {
- final RegionBSPTree2S tree = RegionBSPTree2S.full();
- tree.insert(boundaries);
-
- return tree;
+ return from(boundaries, false);
}
- /** Construct a new tree from the boundaries in the given boundary source. If no boundaries
- * are present in the given source, their the returned tree contains the full space.
- * @param boundarySrc boundary source to construct a tree from
- * @return a new tree instance constructed from the boundaries in the
- * given source
+ /** Construct a new tree from the given boundaries. If {@code full} is true, then
+ * the initial tree before boundary insertion contains the entire space. Otherwise,
+ * it is empty.
+ * @param boundaries boundaries to construct the tree from
+ * @param full if true, the initial tree will contain the entire space
+ * @return a new tree instance constructed from the given boundaries
*/
- public static RegionBSPTree2S from(final BoundarySource<GreatArc> boundarySrc) {
- final RegionBSPTree2S tree = RegionBSPTree2S.full();
- tree.insert(boundarySrc);
+ public static RegionBSPTree2S from(final Iterable<GreatArc> boundaries, final boolean full) {
+ final RegionBSPTree2S tree = new RegionBSPTree2S(full);
+ tree.insert(boundaries);
return tree;
}
diff --git a/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/BoundarySource2STest.java b/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/BoundarySource2STest.java
new file mode 100644
index 0000000..6861634
--- /dev/null
+++ b/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/BoundarySource2STest.java
@@ -0,0 +1,63 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.geometry.spherical.twod;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
+import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class BoundarySource2STest {
+
+ private static final double TEST_EPS = 1e-10;
+
+ private static final DoublePrecisionContext TEST_PRECISION =
+ new EpsilonDoublePrecisionContext(TEST_EPS);
+
+ @Test
+ public void testToTree() {
+ // act
+ List<GreatArc> arcs = Arrays.asList(GreatArc.fromPoints(Point2S.PLUS_I, Point2S.PLUS_J, TEST_PRECISION));
+ BoundarySource2S src = () -> arcs.stream();
+
+ // act
+ RegionBSPTree2S tree = src.toTree();
+
+ // assert
+ Assert.assertEquals(3, tree.count());
+ Assert.assertFalse(tree.isFull());
+ Assert.assertFalse(tree.isEmpty());
+ }
+
+ @Test
+ public void testToTree_noBoundaries() {
+ // act
+ BoundarySource2S src = () -> new ArrayList<GreatArc>().stream();
+
+ // act
+ RegionBSPTree2S tree = src.toTree();
+
+ // assert
+ Assert.assertEquals(1, tree.count());
+ Assert.assertFalse(tree.isFull());
+ Assert.assertTrue(tree.isEmpty());
+ }
+}
diff --git a/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/ConvexArea2STest.java b/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/ConvexArea2STest.java
index 759e9db..2e1403b 100644
--- a/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/ConvexArea2STest.java
+++ b/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/ConvexArea2STest.java
@@ -726,6 +726,19 @@ public class ConvexArea2STest {
}
@Test
+ public void testToTree_full() {
+ // arrange
+ ConvexArea2S area = ConvexArea2S.full();
+
+ // act
+ RegionBSPTree2S tree = area.toTree();
+
+ // assert
+ Assert.assertTrue(tree.isFull());
+ Assert.assertFalse(tree.isEmpty());
+ }
+
+ @Test
public void testToTree() {
// arrange
ConvexArea2S area = ConvexArea2S.fromVertexLoop(Arrays.asList(
diff --git a/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/GreatArcPathTest.java b/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/GreatArcPathTest.java
index 626701b..bef2956 100644
--- a/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/GreatArcPathTest.java
+++ b/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/GreatArcPathTest.java
@@ -315,8 +315,8 @@ public class GreatArcPathTest {
RegionBSPTree2S tree = GreatArcPath.empty().toTree();
// assert
- Assert.assertTrue(tree.isFull());
- Assert.assertFalse(tree.isEmpty());
+ Assert.assertFalse(tree.isFull());
+ Assert.assertTrue(tree.isEmpty());
}
@Test
diff --git a/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/RegionBSPTree2STest.java b/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/RegionBSPTree2STest.java
index a7040e9..3991f5f 100644
--- a/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/RegionBSPTree2STest.java
+++ b/commons-geometry-spherical/src/test/java/org/apache/commons/geometry/spherical/twod/RegionBSPTree2STest.java
@@ -112,13 +112,10 @@ public class RegionBSPTree2STest {
@Test
public void testFrom_boundaries_noBoundaries() {
- // act
- RegionBSPTree2S tree = RegionBSPTree2S.from(Arrays.asList());
-
- // assert
- Assert.assertNull(tree.getBarycenter());
- Assert.assertTrue(tree.isFull());
- Assert.assertFalse(tree.isEmpty());
+ // act/assert
+ Assert.assertTrue(RegionBSPTree2S.from(Arrays.asList()).isEmpty());
+ Assert.assertTrue(RegionBSPTree2S.from(Arrays.asList(), true).isFull());
+ Assert.assertTrue(RegionBSPTree2S.from(Arrays.asList(), false).isEmpty());
}
@Test
@@ -134,41 +131,31 @@ public class RegionBSPTree2STest {
Assert.assertFalse(tree.isFull());
Assert.assertFalse(tree.isEmpty());
+ Assert.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getLocation());
+
SphericalTestUtils.checkClassify(tree, RegionLocation.INSIDE, Point2S.of(1, 0.5));
SphericalTestUtils.checkClassify(tree, RegionLocation.OUTSIDE,
Point2S.of(-1, 0.5), Point2S.of(Math.PI, 0.5 * Math.PI));
}
@Test
- public void testFromBoundarySource() {
- // arrange
- ConvexArea2S area = ConvexArea2S.fromVertexLoop(Arrays.asList(
- Point2S.of(0.1, 0.1), Point2S.of(0, 0.5),
- Point2S.of(0.15, 0.75), Point2S.of(0.3, 0.5),
- Point2S.of(0.1, 0.1)
- ), TEST_PRECISION);
-
+ public void testFrom_boundaries_fullIsTrue() {
// act
- RegionBSPTree2S tree = RegionBSPTree2S.from(area);
+ RegionBSPTree2S tree = RegionBSPTree2S.from(Arrays.asList(
+ EQUATOR.arc(Point2S.PLUS_I, Point2S.PLUS_J),
+ X_MERIDIAN.arc(Point2S.PLUS_K, Point2S.PLUS_I),
+ Y_MERIDIAN.arc(Point2S.PLUS_J, Point2S.PLUS_K)
+ ), true);
// assert
Assert.assertFalse(tree.isFull());
Assert.assertFalse(tree.isEmpty());
- Assert.assertEquals(area.getSize(), tree.getSize(), TEST_EPS);
- SphericalTestUtils.assertPointsEq(area.getBarycenter(), tree.getBarycenter(), TEST_EPS);
- }
+ Assert.assertEquals(RegionLocation.INSIDE, tree.getRoot().getLocation());
- @Test
- public void testFromBoundarySource_noBoundaries() {
- // arrange
- BoundarySource2S src = () -> new ArrayList<GreatArc>().stream();
-
- // act
- RegionBSPTree2S tree = RegionBSPTree2S.from(src);
-
- // assert
- Assert.assertTrue(tree.isFull());
+ SphericalTestUtils.checkClassify(tree, RegionLocation.INSIDE, Point2S.of(1, 0.5));
+ SphericalTestUtils.checkClassify(tree, RegionLocation.OUTSIDE,
+ Point2S.of(-1, 0.5), Point2S.of(Math.PI, 0.5 * Math.PI));
}
@Test
@@ -238,17 +225,13 @@ public class RegionBSPTree2STest {
}
@Test
- public void testToTree_returnsNewInstance() {
+ public void testToTree_returnsSameInstance() {
// arrange
RegionBSPTree2S tree = RegionBSPTree2S.empty();
insertPositiveQuadrant(tree);
- // act
- RegionBSPTree2S result = tree.toTree();
-
- // assert
- Assert.assertNotSame(tree, result);
- Assert.assertEquals(3, result.getBoundaries().size());
+ // act/assert
+ Assert.assertSame(tree, tree.toTree());
}
@Test
diff --git a/src/main/resources/spotbugs/spotbugs-exclude-filter.xml b/src/main/resources/spotbugs/spotbugs-exclude-filter.xml
index 138dfed..a888c99 100644
--- a/src/main/resources/spotbugs/spotbugs-exclude-filter.xml
+++ b/src/main/resources/spotbugs/spotbugs-exclude-filter.xml
@@ -29,8 +29,8 @@
<Class name="~.*\.jmh\.generated\..*" />
<Match>
- <!-- This is a false positive -->
- <Class name="org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree"/>
+ <!-- This is a false positive. See https://github.com/spotbugs/spotbugs/issues/756 -->
+ <Class name="org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree"/>
<BugPattern name="RCN_REDUNDANT_NULLCHECK_WOULD_HAVE_BEEN_A_NPE"/>
</Match>
diff --git a/src/site/xdoc/userguide/index.xml b/src/site/xdoc/userguide/index.xml
index a7ebb6a..4f634a1 100644
--- a/src/site/xdoc/userguide/index.xml
+++ b/src/site/xdoc/userguide/index.xml
@@ -297,7 +297,11 @@ v1.eq(v3, precision); // true - approximately equal according to the given preci
minus side of the cutting hyperplane is considered to be inside of the shape, while the child node on the plus
side is considered to be on the outside. For example, in Euclidean 3D space, plane normals point toward the plus
side of the plane. Thus, when splitting a BSP tree node with a plane, the plane normal points outward from
- the shape, as one might expect.
+ the shape, as one might expect. (In <em>Commons Geometry</em>, this default convention can be changed by passing a
+ <a class="code" href="../commons-geometry-core/apidocs/org/apache/commons/geometry/core/partitioning/bsp/RegionCutRule.html">RegionCutRule</a>
+ value when inserting into a tree. This gives fine-grain control over the structure of the tree and can
+ be used to create structural splits in the tree, meaning splits that do not encode region information but are
+ only used to help keep the tree balanced.)
</p>
<p>
One of the main sources for the development of the BSP tree code in this project and the original
@@ -317,8 +321,8 @@ v1.eq(v3, precision); // true - approximately equal according to the given preci
<h5>Manual BSP Tree Region Creation</h5>
<p>
- The example below manually creates a BSP tree representing a right triangle at the origin. This is not the
- recommended way to construct such a tree, but is included here to demonstrate the BSP tree API.
+ The example below creates a BSP tree representing the unit square by directly inserting hyperplane cuts
+ into nodes. A diagonal "structural" cut is used at the root node in order to keep the tree balanced.
</p>
<source>
DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
@@ -326,28 +330,39 @@ DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6);
// create a tree representing an empty space (nothing "inside")
RegionBSPTree2D tree = RegionBSPTree2D.empty();
-// get the root node
-RegionBSPTree2D.RegionNode2D currentNode = tree.getRoot();
+// insert a "structural" cut, meaning a cut whose children have the same inside/outside
+// status as the parent; this will help keep our tree balanced and limit its overall height
+tree.getRoot().insertCut(Line.fromPointAndDirection(Vector2D.ZERO, Vector2D.of(1, 1), precision),
+ RegionCutRule.INHERIT);
+
+RegionBSPTree2D.RegionNode2D currentNode;
+
+// insert on the plus side of the structural diagonal cut
+currentNode = tree.getRoot().getPlus();
-// cut each minus node with the next hyperplane in the shape
currentNode.insertCut(Line.fromPointAndDirection(Vector2D.ZERO, Vector2D.Unit.PLUS_X, precision));
currentNode = currentNode.getMinus();
-currentNode.insertCut(Line.fromPointAndDirection(Vector2D.Unit.PLUS_X, Vector2D.of(-1, 1), precision));
-currentNode = currentNode.getMinus();
+currentNode.insertCut(Line.fromPointAndDirection(Vector2D.of(1, 0), Vector2D.Unit.PLUS_Y, precision));
-currentNode.insertCut(Line.fromPointAndDirection(Vector2D.Unit.PLUS_Y, Vector2D.Unit.MINUS_Y, precision));
+// insert on the plus side of the structural diagonal cut
+currentNode = tree.getRoot().getMinus();
+
+currentNode.insertCut(Line.fromPointAndDirection(Vector2D.of(1, 1), Vector2D.Unit.MINUS_X, precision));
currentNode = currentNode.getMinus();
-currentNode.isInside(); // true (node is inside)
-currentNode.getParent().getPlus().isInside(); // false (sibling node is outside)
-tree.getSize(); // size of the region = 0.5
-tree.count(); // number of nodes in the tree = 7
+currentNode.insertCut(Line.fromPointAndDirection(Vector2D.of(0, 1), Vector2D.Unit.MINUS_Y, precision));
+
+// compute some tree properties
+int count = tree.count(); // number of nodes in the tree = 11
+int height = tree.height(); // height of the tree = 3
+double size = tree.getSize(); // size of the region = 1
+Vector2D barycenter = tree.getBarycenter(); // region barycenter = (0.5, 0.5)
</source>
<h5>Standard BSP Tree Region Creation</h5>
<p>
- The example below uses the recommended approach to building BSP tree regions by inserting subhyperplanes
+ The example below uses the standard approach to building BSP tree regions by inserting subhyperplanes
into the tree. The shape is the same as the example above.
</p>
<source>
@@ -358,13 +373,17 @@ RegionBSPTree2D tree = RegionBSPTree2D.empty();
// insert the subhyperplanes
tree.insert(Arrays.asList(
- Segment.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, precision),
- Segment.fromPoints(Vector2D.Unit.PLUS_X, Vector2D.Unit.PLUS_Y, precision),
- Segment.fromPoints(Vector2D.Unit.PLUS_Y, Vector2D.ZERO, precision)
+ Segment.fromPoints(Vector2D.ZERO, Vector2D.of(1, 0), precision),
+ Segment.fromPoints(Vector2D.of(1, 0), Vector2D.of(1, 1), precision),
+ Segment.fromPoints(Vector2D.of(1, 1), Vector2D.of(0, 1), precision),
+ Segment.fromPoints(Vector2D.of(0, 1), Vector2D.ZERO, precision)
));
-tree.getSize(); // size of the region = 0.5
-tree.count(); // number of nodes in the tree = 7
+// compute some tree properties
+int count = tree.count(); // number of nodes in the tree = 9
+int height = tree.height(); // height of the tree = 4
+double size = tree.getSize(); // size of the region = 1
+Vector2D barycenter = tree.getBarycenter(); // region barycenter = (0.5, 0.5)
</source>
</subsection>