BSPTree.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;
import org.apache.commons.geometry.core.Transform;
import org.apache.commons.geometry.core.partitioning.Hyperplane;
import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset;
/** 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> {
/** Enum specifying possible behaviors when a point used to locate a node
* falls directly on the cut of an internal node.
*/
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
* node search.
*/
MINUS,
/** Choose the plus child of the internal node and continue searching.
* This behavior will result in a leaf node always being returned by the
* node search.
*/
PLUS,
/** Choose the internal node and stop searching. This behavior may result
* in non-leaf nodes being returned by the node search.
*/
NODE
}
/** Get the root node of the tree.
* @return the root node of the tree
*/
N getRoot();
/** 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, 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, FindNodeCutRule)
*/
default N findNode(final P pt) {
return findNode(pt, FindNodeCutRule.MINUS);
}
/** Find a node in this subtree containing the given point on its interior or boundary. The
* search should always return a leaf node except in the cases where the given point lies
* exactly on the cut of an internal node. In this case, it is unclear whether
* 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 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
* exactly on the cut of an internal node
* @return node containing the point on its interior or boundary
* @see #findNode(Point)
*/
N findNode(P pt, FindNodeCutRule cutRule);
/** Make the current instance a deep copy of the argument.
* @param src the tree to copy
*/
void copy(BSPTree<P, N> src);
/** Set this instance to the region represented by the given node. The
* given node could have come from this tree or a different tree.
* @param node the node to extract
*/
void extract(N node);
/** Transform this tree. Each cut in the tree is transformed in place using
* the given {@link Transform}.
* @param transform the transform to apply
*/
void transform(Transform<P> transform);
/** Interface for Binary Space Partitioning (BSP) tree nodes.
* @param <P> Point type
* @param <N> BSP tree node implementation type
*/
interface Node<P extends Point<P>, N extends Node<P, N>> extends BSPSubtree<P, N> {
/** Get the {@link BSPTree} that owns the node.
* @return the owning tree
*/
BSPTree<P, N> getTree();
/** Get the depth of the node in the tree. The root node of the tree
* has a depth of 0.
* @return the depth of the node in the tree
*/
int depth();
/** Get the parent of the node. This will be null if the node is the
* root of the tree.
* @return the parent node for this instance
*/
N getParent();
/** Get the cut for the node. This is a hyperplane convex subset that splits
* the region for the cell into two disjoint regions, namely the plus and
* minus regions. This will be null for leaf nodes.
* @see #getPlus()
* @see #getMinus()
* @return the cut for the cell
* @see #getCutHyperplane()
*/
HyperplaneConvexSubset<P> getCut();
/** Get the hyperplane containing the node cut, if it exists.
* @return the hyperplane containing the node cut, or null if
* the node does not have a cut
* @see #getCut()
*/
Hyperplane<P> getCutHyperplane();
/** Get the node for the minus region of the cell. This will be null if the
* node has not been cut, ie if it is a leaf node.
* @return the node for the minus region of the cell
*/
N getMinus();
/** Get the node for the plus region of the cell. This will be null if the
* node has not been cut, ie if it is a leaf node.
* @return the node for the plus region of the cell
*/
N getPlus();
/** Return true if the node is a leaf node, meaning that it has no
* binary partitioner (aka "cut") and therefore no child nodes.
* @return true if the node is a leaf node
*/
boolean isLeaf();
/** Return true if the node is an internal node, meaning that is
* has a binary partitioner (aka "cut") and therefore two child nodes.
* @return true if the node is an internal node
*/
boolean isInternal();
/** Return true if the node has a parent and is the parent's minus
* child.
* @return true if the node is the minus child of its parent
*/
boolean isMinus();
/** Return true if the node has a parent and is the parent's plus
* child.
* @return true if the node is the plus child of its parent
*/
boolean isPlus();
/** Trim the given hyperplane subset 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 hyperplane subset lies outside of the region
* defined by the node.
* @param sub the hyperplane subset to trim
* @return the trimmed hyperplane subset or null if no part of the argument lies
* within the node's region
*/
HyperplaneConvexSubset<P> trim(HyperplaneConvexSubset<P> sub);
}
}