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
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:
-
Nested Class Summary
Nested ClassesModifier and TypeInterfaceDescriptionstatic enum
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
Modifier and TypeMethodDescriptionvoid
Make the current instance a deep copy of the argument.void
Set this instance to the region represented by the given node.default N
Find a node in this subtree containing the given point or its interior or boundary.findNode
(P pt, BSPTree.FindNodeCutRule cutRule) Find a node in this subtree containing the given point on its interior or boundary.getRoot()
Get the root node of the tree.void
Transform this tree.Methods inherited from interface org.apache.commons.geometry.core.partitioning.bsp.BSPSubtree
accept, count, height, nodes
-
Method Details
-
getRoot
N getRoot()Get the root node of the tree.- Returns:
- the root node of the tree
-
findNode
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
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:
-
copy
Make the current instance a deep copy of the argument.- Parameters:
src
- the tree to copy
-
extract
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
-
transform
Transform this tree. Each cut in the tree is transformed in place using the givenTransform
.- Parameters:
transform
- the transform to apply
-