BSPTreeVisitor.java
/*
* 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 org.apache.commons.geometry.core.Point;
/** Interface for visiting the nodes in a {@link BSPTree} or {@link BSPSubtree}.
* @param <P> Point implementation type
* @param <N> BSP tree node implementation type
*/
@FunctionalInterface
public interface BSPTreeVisitor<P extends Point<P>, N extends BSPTree.Node<P, N>> {
/** Enum used to specify the order in which visitors should visit the nodes
* in the tree.
*/
enum Order {
/** Indicates that the visitor should first visit the plus sub-tree, then
* the minus sub-tree and then the current node.
*/
PLUS_MINUS_NODE,
/** Indicates that the visitor should first visit the plus sub-tree, then
* the current node, and then the minus sub-tree.
*/
PLUS_NODE_MINUS,
/** Indicates that the visitor should first visit the minus sub-tree, then
* the plus sub-tree, and then the current node.
*/
MINUS_PLUS_NODE,
/** Indicates that the visitor should first visit the minus sub-tree, then the
* current node, and then the plus sub-tree.
*/
MINUS_NODE_PLUS,
/** Indicates that the visitor should first visit the current node, then the
* plus sub-tree, and then the minus sub-tree.
*/
NODE_PLUS_MINUS,
/** Indicates that the visitor should first visit the current node, then the
* minus sub-tree, and then the plus sub-tree.
*/
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 Result {
/** 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
*/
Result 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
* or {@link Order#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;
}
/** Abstract class for {@link BSPTreeVisitor} implementations that base their visit
* ordering on a target point.
* @param <P> Point implementation type
* @param <N> BSP tree node implementation type
*/
abstract class TargetPointVisitor<P extends Point<P>, N extends BSPTree.Node<P, N>>
implements BSPTreeVisitor<P, N> {
/** Point serving as the target of the traversal. */
private final P target;
/** Simple constructor.
* @param target the point serving as the target for the tree traversal
*/
protected TargetPointVisitor(final P target) {
this.target = target;
}
/** Get the target point for the tree traversal.
* @return the target point for the tree traversal
*/
public P getTarget() {
return target;
}
}
/** {@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
* 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
*/
abstract class ClosestFirstVisitor<P extends Point<P>, N extends BSPTree.Node<P, N>>
extends TargetPointVisitor<P, N> {
/** Simple constructor.
* @param target the point serving as the target for the traversal
*/
protected ClosestFirstVisitor(final P target) {
super(target);
}
/** {@inheritDoc} */
@Override
public Order visitOrder(final N node) {
if (node.getCutHyperplane().offset(getTarget()) > 0) {
return Order.PLUS_NODE_MINUS;
}
return Order.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
* 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
*/
abstract class FarthestFirstVisitor<P extends Point<P>, N extends BSPTree.Node<P, N>>
extends TargetPointVisitor<P, N> {
/** Simple constructor.
* @param target the point serving as the target for the traversal
*/
protected FarthestFirstVisitor(final P target) {
super(target);
}
/** {@inheritDoc} */
@Override
public Order visitOrder(final N node) {
if (node.getCutHyperplane().offset(getTarget()) < 0) {
return Order.PLUS_NODE_MINUS;
}
return Order.MINUS_NODE_PLUS;
}
}
}