Interface BSPTree<P extends Point<P>,N extends BSPTree.Node<P,N>>
-
- Type Parameters:
P
- Point implementation typeN
- Node implementation type
- All Superinterfaces:
BSPSubtree<P,N>
- All Known Implementing Classes:
AbstractBSPTree
,AbstractRegionBSPTree
,RegionBSPTree1D
,RegionBSPTree1S
,RegionBSPTree2D
,RegionBSPTree2S
,RegionBSPTree3D
public interface BSPTree<P extends Point<P>,N extends BSPTree.Node<P,N>> extends BSPSubtree<P,N>
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.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.
- See Also:
- Binary space partitioning
-
-
Nested Class Summary
Nested Classes Modifier and Type Interface Description static class
BSPTree.FindNodeCutRule
Enum specifying possible behaviors when a point used to locate a node falls directly on the cut of an internal node.static interface
BSPTree.Node<P extends Point<P>,N extends BSPTree.Node<P,N>>
Interface for Binary Space Partitioning (BSP) tree nodes.
-
Method Summary
All Methods Instance Methods Abstract Methods Default Methods Modifier and Type Method Description void
copy(BSPTree<P,N> src)
Make the current instance a deep copy of the argument.void
extract(N node)
Set this instance to the region represented by the given node.default N
findNode(P pt)
Find a node in this subtree containing the given point or its interior or boundary.N
findNode(P pt, BSPTree.FindNodeCutRule cutRule)
Find a node in this subtree containing the given point on its interior or boundary.N
getRoot()
Get the root node of the tree.void
transform(Transform<P> transform)
Transform this tree.-
Methods inherited from interface org.apache.commons.geometry.core.partitioning.bsp.BSPSubtree
accept, count, height, nodes
-
-
-
-
Method Detail
-
getRoot
N getRoot()
Get the root node of the tree.- Returns:
- the root node of the tree
-
findNode
default N findNode(P pt)
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 tosubtree.findNode(pt, FindNodeCutRule.MINUS)
and always returns a leaf node.- Parameters:
pt
- test point used to locate a node in the tree- Returns:
- leaf node containing the point on its interior or boundary
- See Also:
findNode(Point, FindNodeCutRule)
-
findNode
N findNode(P pt, BSPTree.FindNodeCutRule cutRule)
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. ThecutRule
argument specifies what should happen in this case.BSPTree.FindNodeCutRule.MINUS
- continue the search in the minus subtreeBSPTree.FindNodeCutRule.PLUS
- continue the search in the plus subtreeBSPTree.FindNodeCutRule.NODE
- stop the search and return the internal node
- Parameters:
pt
- test point used to locate a node in the treecutRule
- value used to determine the search behavior when the test point lies exactly on the cut of an internal node- Returns:
- node containing the point on its interior or boundary
- See Also:
findNode(Point)
-
copy
void copy(BSPTree<P,N> src)
Make the current instance a deep copy of the argument.- Parameters:
src
- the tree to copy
-
extract
void extract(N node)
Set this instance to the region represented by the given node. The given node could have come from this tree or a different tree.- Parameters:
node
- the node to extract
-
-