GEOMETRY-69: adding return value to BSPTreeVisitor.visit(BSPTree.Node) so that visit operations can terminate early
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 e204e2c..c06c59d 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
@@ -29,7 +29,8 @@
import org.apache.commons.geometry.core.partitioning.Split;
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.Order;
+import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor.VisitOrder;
+import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor.VisitResult;
/** Abstract class for Binary Space Partitioning (BSP) tree implementations.
* @param <P> Point implementation type
@@ -350,51 +351,68 @@
* @param node the node to begin the visit process
* @param visitor the visitor to pass nodes to
*/
- protected void acceptVisitor(final N node, BSPTreeVisitor<P, N> visitor) {
+ protected void acceptVisitor(final N node, final BSPTreeVisitor<P, N> visitor) {
+ acceptVisitorRecursive(node, visitor);
+ }
+
+ /** Recursively visit the nodes in the subtree rooted at the given node.
+ * @param node the node located at the root of the subtree to visit
+ * @param visitor the visitor to pass nodes to
+ * @return true if the visit operation should continue
+ */
+ private boolean acceptVisitorRecursive(final N node, final BSPTreeVisitor<P, N> visitor) {
if (node.isLeaf()) {
- visitor.visit(node);
+ return shouldContinueVisit(visitor.visit(node));
} else {
- final Order order = visitor.visitOrder(node);
+ final VisitOrder order = visitor.visitOrder(node);
if (order != null) {
switch (order) {
case PLUS_MINUS_NODE:
- acceptVisitor(node.getPlus(), visitor);
- acceptVisitor(node.getMinus(), visitor);
- visitor.visit(node);
- break;
+ return acceptVisitorRecursive(node.getPlus(), visitor) &&
+ acceptVisitorRecursive(node.getMinus(), visitor) &&
+ shouldContinueVisit(visitor.visit(node));
case PLUS_NODE_MINUS:
- acceptVisitor(node.getPlus(), visitor);
- visitor.visit(node);
- acceptVisitor(node.getMinus(), visitor);
- break;
+ return acceptVisitorRecursive(node.getPlus(), visitor) &&
+ shouldContinueVisit(visitor.visit(node)) &&
+ acceptVisitorRecursive(node.getMinus(), visitor);
case MINUS_PLUS_NODE:
- acceptVisitor(node.getMinus(), visitor);
- acceptVisitor(node.getPlus(), visitor);
- visitor.visit(node);
- break;
+ return acceptVisitorRecursive(node.getMinus(), visitor) &&
+ acceptVisitorRecursive(node.getPlus(), visitor) &&
+ shouldContinueVisit(visitor.visit(node));
case MINUS_NODE_PLUS:
- acceptVisitor(node.getMinus(), visitor);
- visitor.visit(node);
- acceptVisitor(node.getPlus(), visitor);
- break;
+ return acceptVisitorRecursive(node.getMinus(), visitor) &&
+ shouldContinueVisit(visitor.visit(node)) &&
+ acceptVisitorRecursive(node.getPlus(), visitor);
case NODE_PLUS_MINUS:
- visitor.visit(node);
- acceptVisitor(node.getPlus(), visitor);
- acceptVisitor(node.getMinus(), visitor);
- break;
- default: // NODE_MINUS_PLUS:
- visitor.visit(node);
- acceptVisitor(node.getMinus(), visitor);
- acceptVisitor(node.getPlus(), visitor);
+ return shouldContinueVisit(visitor.visit(node)) &&
+ acceptVisitorRecursive(node.getPlus(), visitor) &&
+ acceptVisitorRecursive(node.getMinus(), visitor);
+ case NODE_MINUS_PLUS:
+ return shouldContinueVisit(visitor.visit(node)) &&
+ acceptVisitorRecursive(node.getMinus(), visitor) &&
+ acceptVisitorRecursive(node.getPlus(), visitor);
+ default: // NONE
break;
}
}
+
+ return true;
}
}
- /** Cut a node with a hyperplane. The algorithm proceeds are follows:
+ /** Return true if the given BSP tree visit result indicates that the current visit
+ * operation should continue.
+ * @param result visit result from BSP tree node visit operation
+ * @return true if the visit operation should continue with remaining nodes in the
+ * BSP tree
+ */
+ private boolean shouldContinueVisit(final VisitResult result) {
+ return result == VisitResult.CONTINUE;
+ }
+
+ /** Cut a node with a hyperplane. The algorithm proceeds as follows:
* <ol>
* <li>The hyperplane is trimmed by splitting it with each cut hyperplane on the
* path from the given node to the root of the tree.</li>
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 93191bc..402c080 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
@@ -805,7 +805,7 @@
/** {@inheritDoc} */
@Override
- public void visit(final N node) {
+ public VisitResult visit(final N node) {
final P point = getTarget();
if (node.isInternal() && (minDist < 0.0 || isPossibleClosestCut(node.getCut(), point, minDist))) {
@@ -824,6 +824,8 @@
projected = disambiguateClosestPoint(point, projected, boundaryPt);
}
}
+
+ return VisitResult.CONTINUE;
}
/** Return true if the given node cut subhyperplane is a possible candidate for containing the
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/BSPTreePrinter.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/BSPTreePrinter.java
index b5df252..464d5a0 100644
--- a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/BSPTreePrinter.java
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/BSPTreePrinter.java
@@ -56,7 +56,7 @@
/** {@inheritDoc} */
@Override
- public void visit(final N node) {
+ public VisitResult visit(final N node) {
final int depth = node.depth();
if (depth <= maxDepth) {
@@ -66,12 +66,17 @@
startLine(node);
write(ELLIPSIS);
}
+
+ return VisitResult.CONTINUE;
}
/** {@inheritDoc} */
@Override
- public Order visitOrder(final N node) {
- return Order.NODE_MINUS_PLUS;
+ public VisitOrder visitOrder(final N node) {
+ if (node.depth() > maxDepth + 1) {
+ return VisitOrder.NONE;
+ }
+ return VisitOrder.NODE_MINUS_PLUS;
}
/** Start a line for the given node.
diff --git a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/BSPTreeVisitor.java b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/BSPTreeVisitor.java
index 6e5d689..f17b25d 100644
--- a/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/BSPTreeVisitor.java
+++ b/commons-geometry-core/src/main/java/org/apache/commons/geometry/core/partitioning/bsp/BSPTreeVisitor.java
@@ -28,7 +28,7 @@
/** Enum used to specify the order in which visitors should visit the nodes
* in the tree.
*/
- enum Order {
+ enum VisitOrder {
/** Indicates that the visitor should first visit the plus sub-tree, then
* the minus sub-tree and then the current node.
@@ -58,24 +58,43 @@
/** Indicates that the visitor should first visit the current node, then the
* minus sub-tree, and then the plus sub-tree.
*/
- NODE_MINUS_PLUS;
+ NODE_MINUS_PLUS,
+
+ /** Indicates that the visitor should not visit any of the nodes in this subtree. */
+ NONE;
+ }
+
+ /** Enum representing the result of a BSP tree node visit operation.
+ */
+ enum VisitResult {
+
+ /** Indicates that the visit operation should continue with the remaining nodes in
+ * the BSP tree.
+ */
+ CONTINUE,
+
+ /** Indicates that the visit operation should terminate and not visit any further
+ * nodes in the tree.
+ */
+ TERMINATE
}
/** Visit a node in a BSP tree. This method is called for both internal nodes and
* leaf nodes.
* @param node the node being visited
+ * @return the result of the visit operation
*/
- void visit(N node);
+ VisitResult visit(N node);
/** Determine the visit order for the given internal node. This is called for each
- * internal node before {@link #visit(BSPTree.Node)} is called. Returning null from
- * this method skips the subtree rooted at the given node. This method is not called
- * on leaf nodes.
+ * internal node before {@link #visit(BSPTree.Node)} is called. Returning null
+ * or {@link VisitOrder#NONE}from this method skips the subtree rooted at the given node.
+ * This method is not called on leaf nodes.
* @param internalNode the internal node to determine the visit order for
* @return the order that the subtree rooted at the given node should be visited
*/
- default Order visitOrder(final N internalNode) {
- return Order.NODE_MINUS_PLUS;
+ default VisitOrder visitOrder(final N internalNode) {
+ return VisitOrder.NODE_MINUS_PLUS;
}
/** Abstract class for {@link BSPTreeVisitor} implementations that base their visit
@@ -104,9 +123,9 @@
}
/** {@link BSPTreeVisitor} base class that orders tree nodes so that nodes closest to the target point are
- * visited first. This is done by choosing {@link Order#MINUS_NODE_PLUS}
- * when the target point lies on the minus side of the node's cut hyperplane and {@link Order#PLUS_NODE_MINUS}
- * when it lies on the plus side. The order {@link Order#MINUS_NODE_PLUS} order is used when
+ * visited first. This is done by choosing {@link VisitOrder#MINUS_NODE_PLUS}
+ * when the target point lies on the minus side of the node's cut hyperplane and {@link VisitOrder#PLUS_NODE_MINUS}
+ * when it lies on the plus side. The order {@link VisitOrder#MINUS_NODE_PLUS} order is used when
* the target point lies directly on the node's cut hyerplane and no child node is closer than the other.
* @param <P> Point implementation type
* @param <N> BSP tree node implementation type
@@ -122,18 +141,18 @@
/** {@inheritDoc} */
@Override
- public Order visitOrder(N node) {
+ public VisitOrder visitOrder(N node) {
if (node.getCutHyperplane().offset(getTarget()) > 0.0) {
- return Order.PLUS_NODE_MINUS;
+ return VisitOrder.PLUS_NODE_MINUS;
}
- return Order.MINUS_NODE_PLUS;
+ return VisitOrder.MINUS_NODE_PLUS;
}
}
/** {@link BSPTreeVisitor} base class that orders tree nodes so that nodes farthest from the target point
- * are traversed first. This is done by choosing {@link Order#PLUS_NODE_MINUS}
- * when the target point lies on the minus side of the node's cut hyperplane and {@link Order#MINUS_NODE_PLUS}
- * when it lies on the plus side. The order {@link Order#MINUS_NODE_PLUS} order is used when
+ * are traversed first. This is done by choosing {@link VisitOrder#PLUS_NODE_MINUS}
+ * when the target point lies on the minus side of the node's cut hyperplane and {@link VisitOrder#MINUS_NODE_PLUS}
+ * when it lies on the plus side. The order {@link VisitOrder#MINUS_NODE_PLUS} order is used when
* the target point lies directly on the node's cut hyerplane and no child node is closer than the other.
* @param <P> Point implementation type
* @param <N> BSP tree node implementation type
@@ -149,11 +168,11 @@
/** {@inheritDoc} */
@Override
- public Order visitOrder(N node) {
+ public VisitOrder visitOrder(N node) {
if (node.getCutHyperplane().offset(getTarget()) < 0.0) {
- return Order.PLUS_NODE_MINUS;
+ return VisitOrder.PLUS_NODE_MINUS;
}
- return Order.MINUS_NODE_PLUS;
+ return VisitOrder.MINUS_NODE_PLUS;
}
}
}
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 46a88da..c9b5e60 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
@@ -33,7 +33,8 @@
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.bsp.BSPTree.NodeCutRule;
-import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor.Order;
+import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor.VisitOrder;
+import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor.VisitResult;
import org.junit.Assert;
import org.junit.Test;
@@ -814,7 +815,10 @@
List<TestNode> nodes = new ArrayList<>();
// act
- tree.accept(node -> nodes.add(node));
+ tree.accept(node -> {
+ nodes.add(node);
+ return VisitResult.CONTINUE;
+ });
// assert
Assert.assertEquals(
@@ -836,37 +840,37 @@
TestNode minusPlus = minus.getPlus();
// act/assert
- TestVisitor plusMinusNode = new TestVisitor(Order.PLUS_MINUS_NODE);
+ TestVisitor plusMinusNode = new TestVisitor(VisitOrder.PLUS_MINUS_NODE);
tree.accept(plusMinusNode);
Assert.assertEquals(
Arrays.asList(plus, minusPlus, minusMinus, minus, root),
plusMinusNode.getVisited());
- TestVisitor plusNodeMinus = new TestVisitor(Order.PLUS_NODE_MINUS);
+ TestVisitor plusNodeMinus = new TestVisitor(VisitOrder.PLUS_NODE_MINUS);
tree.accept(plusNodeMinus);
Assert.assertEquals(
Arrays.asList(plus, root, minusPlus, minus, minusMinus),
plusNodeMinus.getVisited());
- TestVisitor minusPlusNode = new TestVisitor(Order.MINUS_PLUS_NODE);
+ TestVisitor minusPlusNode = new TestVisitor(VisitOrder.MINUS_PLUS_NODE);
tree.accept(minusPlusNode);
Assert.assertEquals(
Arrays.asList(minusMinus, minusPlus, minus, plus, root),
minusPlusNode.getVisited());
- TestVisitor minusNodePlus = new TestVisitor(Order.MINUS_NODE_PLUS);
+ TestVisitor minusNodePlus = new TestVisitor(VisitOrder.MINUS_NODE_PLUS);
tree.accept(minusNodePlus);
Assert.assertEquals(
Arrays.asList(minusMinus, minus, minusPlus, root, plus),
minusNodePlus.getVisited());
- TestVisitor nodeMinusPlus = new TestVisitor(Order.NODE_MINUS_PLUS);
+ TestVisitor nodeMinusPlus = new TestVisitor(VisitOrder.NODE_MINUS_PLUS);
tree.accept(nodeMinusPlus);
Assert.assertEquals(
Arrays.asList(root, minus, minusMinus, minusPlus, plus),
nodeMinusPlus.getVisited());
- TestVisitor nodePlusMinus = new TestVisitor(Order.NODE_PLUS_MINUS);
+ TestVisitor nodePlusMinus = new TestVisitor(VisitOrder.NODE_PLUS_MINUS);
tree.accept(nodePlusMinus);
Assert.assertEquals(
Arrays.asList(root, plus, minus, minusPlus, minusMinus),
@@ -881,23 +885,126 @@
.getMinus().cut(TestLine.Y_AXIS);
TestNode root = tree.getRoot();
+ TestNode plus = root.getPlus();
TestNode minus = root.getMinus();
- TestNode minusMinus = minus.getMinus();
- TestNode minusPlus = minus.getPlus();
- TestVisitor visitor = new TestVisitor(Order.NODE_MINUS_PLUS);
+ TestVisitor visitor = new TestVisitor(VisitOrder.NODE_MINUS_PLUS) {
+ @Override
+ public VisitOrder visitOrder(TestNode node) {
+ if (node == minus) {
+ return null;
+ }
+ return super.visitOrder(node);
+ }
+ };
// act
- minus.accept(visitor);
+ tree.accept(visitor);
// assert
Assert.assertEquals(
- Arrays.asList(minus, minusMinus, minusPlus),
+ Arrays.asList(root, plus),
visitor.getVisited());
}
@Test
- public void testVisit_visitNode() {
+ public void testVisit_noneVisitOrderSkipsSubtree() {
+ // arrange
+ TestBSPTree tree = new TestBSPTree();
+ tree.getRoot().cut(TestLine.X_AXIS)
+ .getMinus().cut(TestLine.Y_AXIS);
+
+ TestNode root = tree.getRoot();
+ TestNode plus = root.getPlus();
+ TestNode minus = root.getMinus();
+
+ TestVisitor visitor = new TestVisitor(VisitOrder.NODE_MINUS_PLUS) {
+ @Override
+ public VisitOrder visitOrder(TestNode node) {
+ if (node == minus) {
+ return VisitOrder.NONE;
+ }
+ return super.visitOrder(node);
+ }
+ };
+
+ // act
+ tree.accept(visitor);
+
+ // assert
+ Assert.assertEquals(
+ Arrays.asList(root, plus),
+ visitor.getVisited());
+ }
+
+ @Test
+ public void testVisit_visitorReturnsNull_terminatesEarly() {
+ // arrange
+ TestBSPTree tree = new TestBSPTree();
+ tree.getRoot().cut(TestLine.X_AXIS)
+ .getMinus().cut(TestLine.Y_AXIS);
+
+ TestNode root = tree.getRoot();
+ TestNode minus = root.getMinus();
+ TestNode minusMinus = minus.getMinus();
+ TestNode minusPlus = minus.getPlus();
+
+ TestVisitor visitor = new TestVisitor(VisitOrder.MINUS_PLUS_NODE) {
+ @Override
+ public VisitResult visit(TestNode node) {
+ super.visit(node);
+
+ if (node == minus) {
+ return null;
+ }
+ return VisitResult.CONTINUE;
+ }
+ };
+
+ // act
+ tree.accept(visitor);
+
+ // assert
+ Assert.assertEquals(
+ Arrays.asList(minusMinus, minusPlus, minus),
+ visitor.getVisited());
+ }
+
+ @Test
+ public void testVisit_visitorReturnsTerminate_terminatesEarly() {
+ // arrange
+ TestBSPTree tree = new TestBSPTree();
+ tree.getRoot().cut(TestLine.X_AXIS)
+ .getMinus().cut(TestLine.Y_AXIS);
+
+ TestNode root = tree.getRoot();
+ TestNode minus = root.getMinus();
+ TestNode minusMinus = minus.getMinus();
+ TestNode minusPlus = minus.getPlus();
+
+ TestVisitor visitor = new TestVisitor(VisitOrder.MINUS_PLUS_NODE) {
+ @Override
+ public VisitResult visit(TestNode node) {
+ super.visit(node);
+
+ if (node == minus) {
+ return VisitResult.TERMINATE;
+ }
+ return VisitResult.CONTINUE;
+ }
+ };
+
+ // act
+ tree.accept(visitor);
+
+ // assert
+ Assert.assertEquals(
+ Arrays.asList(minusMinus, minusPlus, minus),
+ visitor.getVisited());
+ }
+
+ @Test
+ public void testVisit_earlyTerminationPermutations() {
// arrange
TestBSPTree tree = new TestBSPTree();
tree.getRoot().cut(TestLine.X_AXIS)
@@ -909,14 +1016,67 @@
TestNode minusMinus = minus.getMinus();
TestNode minusPlus = minus.getPlus();
+ // act/assert
+ TestVisitor plusMinusNode = new TestVisitor(VisitOrder.PLUS_MINUS_NODE).withTerminationNode(minus);
+ tree.accept(plusMinusNode);
+ Assert.assertEquals(
+ Arrays.asList(plus, minusPlus, minusMinus, minus),
+ plusMinusNode.getVisited());
+
+ TestVisitor plusNodeMinus = new TestVisitor(VisitOrder.PLUS_NODE_MINUS).withTerminationNode(minus);
+ tree.accept(plusNodeMinus);
+ Assert.assertEquals(
+ Arrays.asList(plus, root, minusPlus, minus),
+ plusNodeMinus.getVisited());
+
+ TestVisitor minusPlusNode = new TestVisitor(VisitOrder.MINUS_PLUS_NODE).withTerminationNode(minus);
+ tree.accept(minusPlusNode);
+ Assert.assertEquals(
+ Arrays.asList(minusMinus, minusPlus, minus),
+ minusPlusNode.getVisited());
+
+ TestVisitor minusNodePlus = new TestVisitor(VisitOrder.MINUS_NODE_PLUS).withTerminationNode(minus);
+ tree.accept(minusNodePlus);
+ Assert.assertEquals(
+ Arrays.asList(minusMinus, minus),
+ minusNodePlus.getVisited());
+
+ TestVisitor nodeMinusPlus = new TestVisitor(VisitOrder.NODE_MINUS_PLUS).withTerminationNode(minus);
+ tree.accept(nodeMinusPlus);
+ Assert.assertEquals(
+ Arrays.asList(root, minus),
+ nodeMinusPlus.getVisited());
+
+ TestVisitor nodePlusMinus = new TestVisitor(VisitOrder.NODE_PLUS_MINUS).withTerminationNode(minus);
+ tree.accept(nodePlusMinus);
+ Assert.assertEquals(
+ Arrays.asList(root, plus, minus),
+ nodePlusMinus.getVisited());
+ }
+
+ @Test
+ public void testVisit_visitNode() {
+ // arrange
+ TestBSPTree tree = new TestBSPTree();
+ tree.getRoot().cut(TestLine.X_AXIS)
+ .getMinus().cut(TestLine.Y_AXIS);
+
+ TestNode root = tree.getRoot();
+ TestNode minus = root.getMinus();
+ TestNode minusMinus = minus.getMinus();
+ TestNode minusPlus = minus.getPlus();
+
List<TestNode> nodes = new ArrayList<>();
// act
- tree.accept(node -> nodes.add(node));
+ minus.accept(node -> {
+ nodes.add(node);
+ return VisitResult.CONTINUE;
+ });
// assert
Assert.assertEquals(
- Arrays.asList(root, minus, minusMinus, minusPlus, plus),
+ Arrays.asList(minus, minusMinus, minusPlus),
nodes);
}
@@ -1781,21 +1941,33 @@
private static class TestVisitor implements BSPTreeVisitor<TestPoint2D, TestNode> {
- private final Order order;
+ private final VisitOrder order;
+
+ private TestNode terminationNode;
private final List<TestNode> visited = new ArrayList<>();
- public TestVisitor(Order order) {
+ public TestVisitor(VisitOrder order) {
this.order = order;
}
- @Override
- public void visit(TestNode node) {
- visited.add(node);
+ public TestVisitor withTerminationNode(TestNode terminationNode) {
+ this.terminationNode = terminationNode;
+
+ return this;
}
@Override
- public Order visitOrder(TestNode node) {
+ public VisitResult visit(TestNode node) {
+ visited.add(node);
+
+ return (terminationNode == node) ?
+ VisitResult.TERMINATE :
+ VisitResult.CONTINUE;
+ }
+
+ @Override
+ public VisitOrder visitOrder(TestNode node) {
return order;
}
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 32471b7..53ad322 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
@@ -2201,8 +2201,6 @@
private static class TestRegionBSPTree extends AbstractRegionBSPTree<TestPoint2D, TestRegionNode> {
- private static final long serialVersionUID = 20190405L;
-
TestRegionBSPTree() {
this(true);
}
@@ -2243,8 +2241,6 @@
private static class TestRegionNode extends AbstractRegionNode<TestPoint2D, TestRegionNode> {
- private static final long serialVersionUID = 20190405L;
-
protected TestRegionNode(AbstractBSPTree<TestPoint2D, TestRegionNode> tree) {
super(tree);
}
diff --git a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/bsp/BSPTreeVisitorTest.java b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/bsp/BSPTreeVisitorTest.java
index 2e692ae..f70f450 100644
--- a/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/bsp/BSPTreeVisitorTest.java
+++ b/commons-geometry-core/src/test/java/org/apache/commons/geometry/core/partitioning/bsp/BSPTreeVisitorTest.java
@@ -18,12 +18,12 @@
import org.apache.commons.geometry.core.partition.test.TestBSPTree;
import org.apache.commons.geometry.core.partition.test.TestBSPTree.TestNode;
-import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor;
-import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor.ClosestFirstVisitor;
-import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor.FarthestFirstVisitor;
-import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor.Order;
import org.apache.commons.geometry.core.partition.test.TestLine;
import org.apache.commons.geometry.core.partition.test.TestPoint2D;
+import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor.ClosestFirstVisitor;
+import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor.FarthestFirstVisitor;
+import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor.VisitOrder;
+import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor.VisitResult;
import org.junit.Assert;
import org.junit.Test;
@@ -32,10 +32,10 @@
@Test
public void testDefaultVisitOrder() {
// arrange
- BSPTreeVisitor<TestPoint2D, TestNode> visitor = n -> {};
+ BSPTreeVisitor<TestPoint2D, TestNode> visitor = n -> VisitResult.CONTINUE;
// act/assert
- Assert.assertEquals(Order.NODE_MINUS_PLUS, visitor.visitOrder(null));
+ Assert.assertEquals(VisitOrder.NODE_MINUS_PLUS, visitor.visitOrder(null));
}
@Test
@@ -48,25 +48,25 @@
root.getPlus().cut(TestLine.Y_AXIS);
// act
- checkClosestFirst(new TestPoint2D(1, 1), root, Order.MINUS_NODE_PLUS);
- checkClosestFirst(new TestPoint2D(1, 1), root.getMinus(), Order.PLUS_NODE_MINUS);
- checkClosestFirst(new TestPoint2D(1, 1), root.getPlus(), Order.PLUS_NODE_MINUS);
+ checkClosestFirst(new TestPoint2D(1, 1), root, VisitOrder.MINUS_NODE_PLUS);
+ checkClosestFirst(new TestPoint2D(1, 1), root.getMinus(), VisitOrder.PLUS_NODE_MINUS);
+ checkClosestFirst(new TestPoint2D(1, 1), root.getPlus(), VisitOrder.PLUS_NODE_MINUS);
- checkClosestFirst(new TestPoint2D(-1, 1), root, Order.MINUS_NODE_PLUS);
- checkClosestFirst(new TestPoint2D(-1, 1), root.getMinus(), Order.MINUS_NODE_PLUS);
- checkClosestFirst(new TestPoint2D(-1, 1), root.getPlus(), Order.MINUS_NODE_PLUS);
+ checkClosestFirst(new TestPoint2D(-1, 1), root, VisitOrder.MINUS_NODE_PLUS);
+ checkClosestFirst(new TestPoint2D(-1, 1), root.getMinus(), VisitOrder.MINUS_NODE_PLUS);
+ checkClosestFirst(new TestPoint2D(-1, 1), root.getPlus(), VisitOrder.MINUS_NODE_PLUS);
- checkClosestFirst(new TestPoint2D(-1, -1), root, Order.PLUS_NODE_MINUS);
- checkClosestFirst(new TestPoint2D(-1, -1), root.getMinus(), Order.MINUS_NODE_PLUS);
- checkClosestFirst(new TestPoint2D(-1, -1), root.getPlus(), Order.MINUS_NODE_PLUS);
+ checkClosestFirst(new TestPoint2D(-1, -1), root, VisitOrder.PLUS_NODE_MINUS);
+ checkClosestFirst(new TestPoint2D(-1, -1), root.getMinus(), VisitOrder.MINUS_NODE_PLUS);
+ checkClosestFirst(new TestPoint2D(-1, -1), root.getPlus(), VisitOrder.MINUS_NODE_PLUS);
- checkClosestFirst(new TestPoint2D(1, -1), root, Order.PLUS_NODE_MINUS);
- checkClosestFirst(new TestPoint2D(1, -1), root.getMinus(), Order.PLUS_NODE_MINUS);
- checkClosestFirst(new TestPoint2D(1, -1), root.getPlus(), Order.PLUS_NODE_MINUS);
+ checkClosestFirst(new TestPoint2D(1, -1), root, VisitOrder.PLUS_NODE_MINUS);
+ checkClosestFirst(new TestPoint2D(1, -1), root.getMinus(), VisitOrder.PLUS_NODE_MINUS);
+ checkClosestFirst(new TestPoint2D(1, -1), root.getPlus(), VisitOrder.PLUS_NODE_MINUS);
- checkClosestFirst(TestPoint2D.ZERO, root.getPlus(), Order.MINUS_NODE_PLUS);
- checkClosestFirst(TestPoint2D.ZERO, root.getPlus(), Order.MINUS_NODE_PLUS);
- checkClosestFirst(TestPoint2D.ZERO, root.getPlus(), Order.MINUS_NODE_PLUS);
+ checkClosestFirst(TestPoint2D.ZERO, root.getPlus(), VisitOrder.MINUS_NODE_PLUS);
+ checkClosestFirst(TestPoint2D.ZERO, root.getPlus(), VisitOrder.MINUS_NODE_PLUS);
+ checkClosestFirst(TestPoint2D.ZERO, root.getPlus(), VisitOrder.MINUS_NODE_PLUS);
}
@Test
@@ -79,35 +79,35 @@
root.getPlus().cut(TestLine.Y_AXIS);
// act
- checkFarthestFirst(new TestPoint2D(1, 1), root, Order.PLUS_NODE_MINUS);
- checkFarthestFirst(new TestPoint2D(1, 1), root.getMinus(), Order.MINUS_NODE_PLUS);
- checkFarthestFirst(new TestPoint2D(1, 1), root.getPlus(), Order.MINUS_NODE_PLUS);
+ checkFarthestFirst(new TestPoint2D(1, 1), root, VisitOrder.PLUS_NODE_MINUS);
+ checkFarthestFirst(new TestPoint2D(1, 1), root.getMinus(), VisitOrder.MINUS_NODE_PLUS);
+ checkFarthestFirst(new TestPoint2D(1, 1), root.getPlus(), VisitOrder.MINUS_NODE_PLUS);
- checkFarthestFirst(new TestPoint2D(-1, 1), root, Order.PLUS_NODE_MINUS);
- checkFarthestFirst(new TestPoint2D(-1, 1), root.getMinus(), Order.PLUS_NODE_MINUS);
- checkFarthestFirst(new TestPoint2D(-1, 1), root.getPlus(), Order.PLUS_NODE_MINUS);
+ checkFarthestFirst(new TestPoint2D(-1, 1), root, VisitOrder.PLUS_NODE_MINUS);
+ checkFarthestFirst(new TestPoint2D(-1, 1), root.getMinus(), VisitOrder.PLUS_NODE_MINUS);
+ checkFarthestFirst(new TestPoint2D(-1, 1), root.getPlus(), VisitOrder.PLUS_NODE_MINUS);
- checkFarthestFirst(new TestPoint2D(-1, -1), root, Order.MINUS_NODE_PLUS);
- checkFarthestFirst(new TestPoint2D(-1, -1), root.getMinus(), Order.PLUS_NODE_MINUS);
- checkFarthestFirst(new TestPoint2D(-1, -1), root.getPlus(), Order.PLUS_NODE_MINUS);
+ checkFarthestFirst(new TestPoint2D(-1, -1), root, VisitOrder.MINUS_NODE_PLUS);
+ checkFarthestFirst(new TestPoint2D(-1, -1), root.getMinus(), VisitOrder.PLUS_NODE_MINUS);
+ checkFarthestFirst(new TestPoint2D(-1, -1), root.getPlus(), VisitOrder.PLUS_NODE_MINUS);
- checkFarthestFirst(new TestPoint2D(1, -1), root, Order.MINUS_NODE_PLUS);
- checkFarthestFirst(new TestPoint2D(1, -1), root.getMinus(), Order.MINUS_NODE_PLUS);
- checkFarthestFirst(new TestPoint2D(1, -1), root.getPlus(), Order.MINUS_NODE_PLUS);
+ checkFarthestFirst(new TestPoint2D(1, -1), root, VisitOrder.MINUS_NODE_PLUS);
+ checkFarthestFirst(new TestPoint2D(1, -1), root.getMinus(), VisitOrder.MINUS_NODE_PLUS);
+ checkFarthestFirst(new TestPoint2D(1, -1), root.getPlus(), VisitOrder.MINUS_NODE_PLUS);
- checkFarthestFirst(TestPoint2D.ZERO, root.getPlus(), Order.MINUS_NODE_PLUS);
- checkFarthestFirst(TestPoint2D.ZERO, root.getPlus(), Order.MINUS_NODE_PLUS);
- checkFarthestFirst(TestPoint2D.ZERO, root.getPlus(), Order.MINUS_NODE_PLUS);
+ checkFarthestFirst(TestPoint2D.ZERO, root.getPlus(), VisitOrder.MINUS_NODE_PLUS);
+ checkFarthestFirst(TestPoint2D.ZERO, root.getPlus(), VisitOrder.MINUS_NODE_PLUS);
+ checkFarthestFirst(TestPoint2D.ZERO, root.getPlus(), VisitOrder.MINUS_NODE_PLUS);
}
- private static void checkClosestFirst(TestPoint2D target, TestNode node, Order order) {
+ private static void checkClosestFirst(TestPoint2D target, TestNode node, VisitOrder order) {
ClosestFirstStubVisitor visitor = new ClosestFirstStubVisitor(target);
Assert.assertSame(target, visitor.getTarget());
Assert.assertEquals(order, visitor.visitOrder(node));
}
- private static void checkFarthestFirst(TestPoint2D target, TestNode node, Order order) {
+ private static void checkFarthestFirst(TestPoint2D target, TestNode node, VisitOrder order) {
FarthestFirstStubVisitor visitor = new FarthestFirstStubVisitor(target);
Assert.assertSame(target, visitor.getTarget());
@@ -116,27 +116,25 @@
private static class ClosestFirstStubVisitor extends ClosestFirstVisitor<TestPoint2D, TestNode> {
- private static final long serialVersionUID = 1L;
-
public ClosestFirstStubVisitor(TestPoint2D target) {
super(target);
}
@Override
- public void visit(TestNode node) {
+ public VisitResult visit(TestNode node) {
+ return VisitResult.CONTINUE;
}
}
private static class FarthestFirstStubVisitor extends FarthestFirstVisitor<TestPoint2D, TestNode> {
- private static final long serialVersionUID = 1L;
-
public FarthestFirstStubVisitor(TestPoint2D target) {
super(target);
}
@Override
- public void visit(TestNode node) {
+ public VisitResult visit(TestNode node) {
+ return VisitResult.CONTINUE;
}
}
}
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 451046a..07e8df6 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
@@ -30,8 +30,8 @@
import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor;
import org.apache.commons.geometry.core.partitioning.bsp.RegionCutBoundary;
import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
-import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D;
import org.apache.commons.geometry.euclidean.twod.Polyline;
+import org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D;
import org.apache.commons.geometry.euclidean.twod.Vector2D;
/** Binary space partitioning (BSP) tree representing a region in three dimensional
@@ -138,77 +138,10 @@
* intersection exists
*/
public ConvexSubPlane raycastFirst(final Segment3D ray) {
- return raycastFirstRecursive(getRoot(), ray);
- }
+ final RaycastIntersectionVisitor visitor = new RaycastIntersectionVisitor(ray);
+ getRoot().accept(visitor);
- /** Recursive method used to find the first intersection of the given ray/line segment
- * with the boundary of the region.
- * @param node current BSP tree node
- * @param ray the ray used for the raycast operation
- * @return the node cut subhyperplane containing the intersection or null if no
- * intersection exists
- */
- private ConvexSubPlane raycastFirstRecursive(final RegionNode3D node, final Segment3D ray) {
- if (node.isLeaf()) {
- // no boundary to intersect with on leaf nodes
- return null;
- }
-
- // establish search order
- final Plane cut = (Plane) node.getCutHyperplane();
- final Line3D line = ray.getLine();
-
- final boolean plusIsNear = line.getDirection().dot(cut.getNormal()) < 0;
-
- final RegionNode3D nearNode = plusIsNear ? node.getPlus() : node.getMinus();
- final RegionNode3D farNode = plusIsNear ? node.getMinus() : node.getPlus();
-
- // check the near node
- final ConvexSubPlane nearResult = raycastFirstRecursive(nearNode, ray);
- if (nearResult != null) {
- return nearResult;
- }
-
- // check ourselves
- final Vector3D intersection = computeRegionCutBoundaryIntersection(node, ray);
- if (intersection != null) {
- // we intersect, so our cut is the answer
- return (ConvexSubPlane) node.getCut();
- }
-
- // check the far node
- final ConvexSubPlane farResult = raycastFirstRecursive(farNode, ray);
- if (farResult != null) {
- return farResult;
- }
-
- return null;
- }
-
- /** Compute the intersection point between the region cut boundary and the given line segment.
- * @param node BSP tree node to compute the region cut boundary intersection for
- * @param segment line segment to compute the intersection for
- * @return the intersection point between the region cut boundary and the given line segment or
- * null if one does not exist.
- */
- private Vector3D computeRegionCutBoundaryIntersection(final RegionNode3D node, final Segment3D segment) {
- if (node.isInternal()) {
- final Line3D line = segment.getLine();
- final Vector3D intersection = ((Plane) node.getCutHyperplane()).intersection(line);
-
- if (intersection != null && segment.contains(intersection)) {
-
- final RegionCutBoundary<Vector3D> boundary = node.getCutBoundary();
-
- if ((boundary.getInsideFacing() != null && boundary.getInsideFacing().contains(intersection)) ||
- boundary.getOutsideFacing() != null && boundary.getOutsideFacing().contains(intersection)) {
-
- return intersection;
- }
- }
- }
-
- return null;
+ return visitor.getIntersectionCut();
}
/** {@inheritDoc} */
@@ -616,12 +549,14 @@
/** {@inheritDoc} */
@Override
- public void visit(final RegionNode3D node) {
+ public VisitResult visit(final RegionNode3D node) {
if (node.isInternal()) {
RegionCutBoundary<Vector3D> boundary = node.getCutBoundary();
addFacetContribution(boundary.getOutsideFacing(), false);
addFacetContribution(boundary.getInsideFacing(), true);
}
+
+ return VisitResult.CONTINUE;
}
/** Return the computed size properties for the visited region.
@@ -683,4 +618,72 @@
}
}
}
+
+ /** BSP tree visitor that locates the node cut subhyperplane for the first intersection between a
+ * given line segment and BSP tree region boundary.
+ */
+ private static final class RaycastIntersectionVisitor implements BSPTreeVisitor<Vector3D, RegionNode3D> {
+
+ /** The line segment to intersect with the BSP tree. */
+ private final Segment3D segment;
+
+ /** The node cut subhyperplane containing the first boundary intersection. */
+ private ConvexSubPlane intersectionCut;
+
+ /** Create a new instance that locates the first boundary intersection between the given line segment and
+ * the visited BSP tree.
+ * @param segment segment to intersect with the BSP tree region boundary
+ */
+ RaycastIntersectionVisitor(final Segment3D segment) {
+ this.segment = segment;
+ }
+
+ /** Get the node cut subhyperplane containing the first intersection between the configured line segment
+ * and the BSP tree region boundary. This must be called after the tree nodes have been visited.
+ * @return the node cut subhyperplane containing the first intersection between the configured line segment
+ * and the BSP tree region boundary or null if no such intersection was found
+ */
+ public ConvexSubPlane getIntersectionCut() {
+ return intersectionCut;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public VisitOrder visitOrder(final RegionNode3D internalNode) {
+ final Plane cut = (Plane) internalNode.getCutHyperplane();
+ final Line3D line = segment.getLine();
+
+ final boolean plusIsNear = line.getDirection().dot(cut.getNormal()) < 0;
+
+ return plusIsNear ?
+ VisitOrder.PLUS_NODE_MINUS :
+ VisitOrder.MINUS_NODE_PLUS;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public VisitResult visit(final RegionNode3D node) {
+ if (node.isInternal()) {
+ // check if the line segment intersects the cut subhyperplane
+ final Line3D line = segment.getLine();
+ final Vector3D intersection = ((Plane) node.getCutHyperplane()).intersection(line);
+
+ if (intersection != null && segment.contains(intersection)) {
+
+ final RegionCutBoundary<Vector3D> boundary = node.getCutBoundary();
+
+ // check if the intersection point lies on the region boundary
+ if ((boundary.getInsideFacing() != null && boundary.getInsideFacing().contains(intersection)) ||
+ boundary.getOutsideFacing() != null && boundary.getOutsideFacing().contains(intersection)) {
+
+ intersectionCut = (ConvexSubPlane) node.getCut();
+
+ return VisitResult.TERMINATE;
+ }
+ }
+ }
+
+ return VisitResult.CONTINUE;
+ }
+ }
}
