Class AbstractBSPTree<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
- java.lang.Object
-
- org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree<P,N>
-
- Type Parameters:
P
- Point implementation typeN
- BSP tree node implementation type
- All Implemented Interfaces:
BSPSubtree<P,N>
,BSPTree<P,N>
- Direct Known Subclasses:
AbstractRegionBSPTree
public abstract class AbstractBSPTree<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>> extends java.lang.Object implements BSPTree<P,N>
Abstract class for Binary Space Partitioning (BSP) tree implementations. This class contains basic structures and algorithms that should be common to all BSP tree implementations, regardless of the end use cases for the tree (eg, whether the tree is intended to represent polytopes, hold attributes like a map, etc).Implementation Notes
- The
AbstractBSPTree
class is designed to work closely with its nested node type,AbstractBSPTree.AbstractNode
. The tree class handles all tree manipulation operations while the node type is primarily a simple data type and delegates tree operations to internal methods within its parent tree. This allows for easier overriding of tree behavior in subclasses. - Each time the structure of the tree is modified, a
version number
is incremented in the tree. This allows certain tree properties to be computed lazily and then cached. The tree version number is incremented with theinvalidate
method. Properties can be cached directly on nodes using thecheckValid
andnodeInvalidated
methods. - Since the methods used to construct and modify trees can vary by use case, no public API is provided
for manipulating the tree. Subclasses are expected to use the protected methods of this class to
create their own. For tree construction, subclasses are expected to pass their own
AbstractBSPTree.SubtreeInitializer
instances toinsert
andcutNode
in order to set the correct properties on tree nodes. To support tree copying, subclasses must also overridecopyNodeProperties
. - This class is not thread safe.
- See Also:
BSPTree
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
AbstractBSPTree.AbstractNode<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
Abstract implementation ofBSPTree.Node
.private static class
AbstractBSPTree.NodeIterator<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
Class for iterating through the nodes in a BSP subtree.static interface
AbstractBSPTree.SubtreeInitializer<N extends AbstractBSPTree.AbstractNode<?,?>>
Interface used to initialize newly created BSP subtrees, consisting of a single parent node and two child nodes.-
Nested classes/interfaces inherited from interface org.apache.commons.geometry.core.partitioning.bsp.BSPTree
BSPTree.FindNodeCutRule, BSPTree.Node<P extends Point<P>,N extends BSPTree.Node<P,N>>
-
-
Field Summary
Fields Modifier and Type Field Description private static int
DEFAULT_TREE_STRING_MAX_DEPTH
The default number of levels to print when creating a string representation of the tree.private N
root
The root node for the tree.private static int
UNKNOWN_VALUE
Integer value set on various node fields when a value is unknown.private int
version
The current modification version for the tree structure.
-
Constructor Summary
Constructors Constructor Description AbstractBSPTree()
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description protected void
accept(N node, BSPTreeVisitor<P,N> visitor)
Visit the nodes in a subtree.void
accept(BSPTreeVisitor<P,N> visitor)
Accept a visitor instance, calling it with each node from the subtree.private boolean
acceptRecursive(N node, BSPTreeVisitor<P,N> visitor)
Recursively visit the nodes in the subtree rooted at the given node.void
copy(BSPTree<P,N> src)
Make the current instance a deep copy of the argument.protected N
copyNode(N src)
Create a non-structural copy of the given node.protected abstract void
copyNodeProperties(N src, N dst)
Copy non-structural node properties fromsrc
todst
.protected N
copySubtree(N src, N dst)
Recursively copy a subtree.int
count()
Return the total number of nodes in the subtree.protected abstract N
createNode()
Create a new node for this tree.protected boolean
cutNode(N node, Hyperplane<P> cutter, AbstractBSPTree.SubtreeInitializer<N> subtreeInitializer)
Cut a node with a hyperplane.void
extract(N node)
Set this instance to the region represented by the given node.protected N
extractParentPath(N src, N dst)
Extract the path fromsrc
to the root of its tree and set it as the parent path ofdst
.protected N
findNode(N start, P pt, BSPTree.FindNodeCutRule cutRule)
Find the smallest node in the tree containing the point, starting at the given node.N
findNode(P pt, BSPTree.FindNodeCutRule cutBehavior)
Find a node in this subtree containing the given point on its interior or boundary.N
getRoot()
Get the root node of the tree.protected int
getVersion()
Get the current structural version of the tree.int
height()
The height of the subtree, ie the length of the longest downward path from the subtree root to a leaf node.protected N
importSubtree(N src)
Import the subtree represented by the given node into this tree.protected void
insert(HyperplaneConvexSubset<P> convexSub, AbstractBSPTree.SubtreeInitializer<N> subtreeInit)
Insert the given hyperplane convex subset into the tree, starting at the root node.private void
insertRecursive(N node, HyperplaneConvexSubset<P> insert, HyperplaneConvexSubset<P> trimmed, AbstractBSPTree.SubtreeInitializer<N> subtreeInit)
Recursively insert a hyperplane convex subset into the tree at the given node.protected void
invalidate()
Invalidate any previously computed properties that rely on the internal structure of the tree.java.lang.Iterable<N>
nodes()
Get an iterable for accessing the nodes in this subtree.protected boolean
removeNodeCut(N node)
Remove the cut from the given node.protected void
setNodeCut(N node, HyperplaneConvexSubset<P> cut, AbstractBSPTree.SubtreeInitializer<N> subtreeInitializer)
Set the cut hyperplane subset for the given node.protected void
setRoot(N root)
Set the root node for the tree.private boolean
shouldContinueVisit(BSPTreeVisitor.Result result)
Return true if the given BSP tree visit result indicates that the current visit operation should continue.private N
splitInternalNode(N node, HyperplaneConvexSubset<P> partitioner)
Split the given internal node by a partitioning convex subset defined on the same region as the node and import it into this tree.protected void
splitIntoTrees(Hyperplane<P> splitter, AbstractBSPTree<P,N> minus, AbstractBSPTree<P,N> plus)
Split this tree with the given hyperplane, placing the split contents into the given target trees.private N
splitLeafNode(N node, HyperplaneConvexSubset<P> partitioner)
Split the given leaf node by a partitioning convex subset defined on the same region and import it into this tree.protected N
splitSubtree(N node, HyperplaneConvexSubset<P> partitioner)
Split the subtree rooted at the given node by a partitioning convex subset defined on the same region as the node.protected boolean
swapsInsideOutside(Transform<P> transform)
Return true if the given transform swaps the inside and outside of the region.java.lang.String
toString()
void
transform(Transform<P> transform)
Transform this tree.private void
transformRecursive(N node, Transform<P> t, boolean swapChildren)
Transform the subtree rooted asnode
recursively.java.lang.String
treeString()
Get a simple string representation of the tree structure.java.lang.String
treeString(int maxDepth)
Get a simple string representation of the tree structure.protected HyperplaneConvexSubset<P>
trimToNode(N node, HyperplaneConvexSubset<P> sub)
Trim the given hyperplane convex subset to the region defined by the given node.
-
-
-
Field Detail
-
DEFAULT_TREE_STRING_MAX_DEPTH
private static final int DEFAULT_TREE_STRING_MAX_DEPTH
The default number of levels to print when creating a string representation of the tree.- See Also:
- Constant Field Values
-
UNKNOWN_VALUE
private static final int UNKNOWN_VALUE
Integer value set on various node fields when a value is unknown.- See Also:
- Constant Field Values
-
root
private N extends AbstractBSPTree.AbstractNode<P,N> root
The root node for the tree.
-
version
private int version
The current modification version for the tree structure. This is incremented each time a structural change occurs in the tree and is used to determine when cached values must be recomputed.
-
-
Method Detail
-
getRoot
public N getRoot()
Get the root node of the tree.
-
setRoot
protected void setRoot(N root)
Set the root node for the tree. Cached tree properties are invalidated withinvalidate()
.- Parameters:
root
- new root node for the tree
-
count
public int count()
Return the total number of nodes in the subtree.- Specified by:
count
in interfaceBSPSubtree<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
- Returns:
- the total number of nodes in the subtree.
-
height
public int height()
The height of the subtree, ie the length of the longest downward path from the subtree root to a leaf node. A leaf node has a height of 0.- Specified by:
height
in interfaceBSPSubtree<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
- Returns:
- the height of the subtree.
-
accept
public void accept(BSPTreeVisitor<P,N> visitor)
Accept a visitor instance, calling it with each node from the subtree.- Specified by:
accept
in interfaceBSPSubtree<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
- Parameters:
visitor
- visitor called with each subtree node
-
findNode
public N findNode(P pt, BSPTree.FindNodeCutRule cutBehavior)
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
- Specified by:
findNode
in interfaceBSPTree<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
- Parameters:
pt
- test point used to locate a node in the treecutBehavior
- 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:
BSPTree.findNode(Point)
-
nodes
public java.lang.Iterable<N> nodes()
Get an iterable for accessing the nodes in this subtree. This provides a simple alternative toBSPSubtree.accept(BSPTreeVisitor)
for accessing tree nodes but is not as powerful or flexible since the node iteration order is fixed.- Specified by:
nodes
in interfaceBSPSubtree<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
- Returns:
- an iterable for accessing the nodes in this subtree
-
extract
public 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.
-
transform
public void transform(Transform<P> transform)
Transform this tree. Each cut in the tree is transformed in place using the givenTransform
.
-
treeString
public java.lang.String treeString()
Get a simple string representation of the tree structure. The returned string contains the tree structure down to the default max depth of 8.- Returns:
- a string representation of the tree
-
treeString
public java.lang.String treeString(int maxDepth)
Get a simple string representation of the tree structure. The returned string contains the tree structure down tomaxDepth
.- Parameters:
maxDepth
- the maximum depth in the tree to print; nodes below this depth are skipped- Returns:
- a string representation of the tree
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
createNode
protected abstract N createNode()
Create a new node for this tree.- Returns:
- a new node for this tree
-
copyNodeProperties
protected abstract void copyNodeProperties(N src, N dst)
Copy non-structural node properties fromsrc
todst
. Non-structural properties are those properties not directly related to the structure of the BSP tree, i.e. properties other than parent/child connections and cuts. Subclasses should override this method to copy additional properties stored on nodes.- Parameters:
src
- source nodedst
- destination node
-
copyNode
protected N copyNode(N src)
Create a non-structural copy of the given node. Properties such as parent/child connections and cuts are not copied.- Parameters:
src
- the node to copy; does not need to belong to the current tree- Returns:
- the copied node
- See Also:
copyNodeProperties(AbstractNode, AbstractNode)
-
copySubtree
protected N copySubtree(N src, N dst)
Recursively copy a subtree. The returned node is not attached to the current tree. Structural and non-structural properties are copied from the source subtree to the destination subtree. This method does nothing ifsrc
anddst
reference the same node.- Parameters:
src
- the node representing the source subtree; does not need to belong to the current treedst
- the node representing the destination subtree- Returns:
- the copied node, ie
dst
-
importSubtree
protected N importSubtree(N src)
Import the subtree represented by the given node into this tree. If the given node already belongs to this tree, then the node is returned directly without modification. If the node does not belong to this tree, a new node is created and the src node subtree is copied into it.This method does not modify the current structure of the tree.
- Parameters:
src
- node to import- Returns:
- the given node if it belongs to this tree, otherwise a new node containing a copy of the given node's subtree
- See Also:
copySubtree(AbstractNode, AbstractNode)
-
extractParentPath
protected N extractParentPath(N src, N dst)
Extract the path fromsrc
to the root of its tree and set it as the parent path ofdst
. Leaf nodes created during the extraction are given the same node properties as their counterparts in the source tree but without the cuts and child nodes. The properties ofdst
are not modified, with the exception of its parent node reference.- Parameters:
src
- the source node to copy the parent path fromdst
- the destination node to place under the extracted path- Returns:
- the root node of the extracted path
-
findNode
protected N findNode(N start, P pt, BSPTree.FindNodeCutRule cutRule)
Find the smallest node in the tree containing the point, starting at the given node.- Parameters:
start
- the node to begin the search withpt
- the point to checkcutRule
- value determining the search behavior when the test point lies directly on the cut of an internal node- Returns:
- the smallest node in the tree containing the point
-
accept
protected void accept(N node, BSPTreeVisitor<P,N> visitor)
Visit the nodes in a subtree.- Parameters:
node
- the node to begin the visit processvisitor
- the visitor to pass nodes to
-
acceptRecursive
private boolean acceptRecursive(N node, BSPTreeVisitor<P,N> visitor)
Recursively visit the nodes in the subtree rooted at the given node.- Parameters:
node
- the node located at the root of the subtree to visitvisitor
- the visitor to pass nodes to- Returns:
- true if the visit operation should continue
-
shouldContinueVisit
private boolean shouldContinueVisit(BSPTreeVisitor.Result result)
Return true if the given BSP tree visit result indicates that the current visit operation should continue.- Parameters:
result
- visit result from BSP tree node visit operation- Returns:
- true if the visit operation should continue with remaining nodes in the BSP tree
-
cutNode
protected boolean cutNode(N node, Hyperplane<P> cutter, AbstractBSPTree.SubtreeInitializer<N> subtreeInitializer)
Cut a node with a hyperplane. The algorithm proceeds as follows:- The hyperplane is trimmed by splitting it with each cut hyperplane on the path from the given node to the root of the tree.
- If the remaining portion of the hyperplane is not empty, then
- the remaining portion becomes the cut hyperplane subset for the node,
- two new child nodes are created and initialized with
subtreeInitializer
, and - true is returned.
- If the remaining portion of the hyperplane is empty (ie, the
cutting hyperplane does not intersect the node's region), then
- the node is converted to a leaf node (meaning that previous child nodes are lost), and
- false is returned.
It is important to note that since this method uses the path from given node to the tree root, it must only be used on nodes that are already inserted into the tree.
This method calls
invalidate()
to invalidate cached tree properties if the tree structure is changed.- Parameters:
node
- the node to cutcutter
- the hyperplane to cut the node withsubtreeInitializer
- object used to initialize any newly-created subtrees- Returns:
- true if the node was cut and two new child nodes were created; otherwise false
- See Also:
trimToNode(AbstractNode, HyperplaneConvexSubset)
,setNodeCut(AbstractNode, HyperplaneConvexSubset, SubtreeInitializer)
,removeNodeCut(AbstractNode)
,invalidate()
-
trimToNode
protected HyperplaneConvexSubset<P> trimToNode(N node, HyperplaneConvexSubset<P> sub)
Trim the given hyperplane convex subset to the region defined by the given node. This method cuts the subset with the cut hyperplanes (binary partitioners) of all parent nodes up to the root and returns the trimmed subset ornull
if the subset lies outside of the region defined by the node.If the subset is directly coincident with a binary partitioner of a parent node, then the relative orientations of the associated hyperplanes are used to determine the behavior, as described below.
- If the orientations are similar, then the subset is determined to
lie outside of the node's region and
null
is returned. - If the orientations are different (ie, opposite), then the subset is determined to lie inside of the node's region and the fit operation continues with the remaining parent nodes.
Another way of looking at the rules above is that inserting a hyperplane into the tree that exactly matches the hyperplane of a parent node does not add any information to the tree. However, adding a hyperplane to the tree that is coincident with a parent node but with the opposite orientation, does add information to the tree.
- Parameters:
node
- the node representing the region to fit the hyperplane subset tosub
- the hyperplane subset to trim to the node's region- Returns:
- the trimmed hyperplane subset or null if the given hyperplane subset does not intersect the node's region
- If the orientations are similar, then the subset is determined to
lie outside of the node's region and
-
removeNodeCut
protected boolean removeNodeCut(N node)
Remove the cut from the given node. Returns true if the node had a cut before the call to this method. Any previous child nodes are lost.This method calls
invalidate()
to invalidate cached tree properties if the tree structure changed.- Parameters:
node
- the node to remove the cut from- Returns:
- true if the node previously had a cut
-
setNodeCut
protected void setNodeCut(N node, HyperplaneConvexSubset<P> cut, AbstractBSPTree.SubtreeInitializer<N> subtreeInitializer)
Set the cut hyperplane subset for the given node. Two new child nodes are created for the node and the new subtree is initialized withsubtreeInitializer
.This method performs absolutely no validation on the given cut hyperplane subset. It is the responsibility of the caller to ensure that the hyperplane subset fits the region represented by the node.
This method always calls
invalidate()
to invalidate cached tree properties.- Parameters:
node
- the node to cutcut
- the hyperplane convex subset to set as the node cutsubtreeInitializer
- object used to initialize the newly-created subtree
-
insert
protected void insert(HyperplaneConvexSubset<P> convexSub, AbstractBSPTree.SubtreeInitializer<N> subtreeInit)
Insert the given hyperplane convex subset into the tree, starting at the root node. Any subtrees created are initialized withsubtreeInit
.- Parameters:
convexSub
- hyperplane convex subset to insert into the treesubtreeInit
- object used to initialize newly created subtrees
-
insertRecursive
private void insertRecursive(N node, HyperplaneConvexSubset<P> insert, HyperplaneConvexSubset<P> trimmed, AbstractBSPTree.SubtreeInitializer<N> subtreeInit)
Recursively insert a hyperplane convex subset into the tree at the given node.- Parameters:
node
- the node to begin insertion withinsert
- the hyperplane subset to inserttrimmed
- hyperplane subset containing the result of splitting the entire space with each hyperplane from this node to the rootsubtreeInit
- object used to initialize newly created subtrees
-
swapsInsideOutside
protected boolean swapsInsideOutside(Transform<P> transform)
Return true if the given transform swaps the inside and outside of the region.The default behavior of this method is to return true if the transform does not preserve spatial orientation (ie,
Transform.preservesOrientation()
is false). Subclasses may need to override this method to implement the correct behavior for their space and dimension.- Parameters:
transform
- transform to check- Returns:
- true if the given transform swaps the interior and exterior of the region
-
transformRecursive
private void transformRecursive(N node, Transform<P> t, boolean swapChildren)
Transform the subtree rooted asnode
recursively.- Parameters:
node
- the root node of the subtree to transformt
- the transform to applyswapChildren
- if true, the plus and minus child nodes of each internal node will be swapped; this should be the case when the transform is a reflection
-
splitIntoTrees
protected void splitIntoTrees(Hyperplane<P> splitter, AbstractBSPTree<P,N> minus, AbstractBSPTree<P,N> plus)
Split this tree with the given hyperplane, placing the split contents into the given target trees. One of the given trees may be null, in which case that portion of the split will not be exported. The current tree is not modified.- Parameters:
splitter
- splitting hyperplaneminus
- tree that will contain the portion of the tree on the minus side of the splitterplus
- tree that will contain the portion of the tree on the plus side of the splitter
-
splitSubtree
protected N splitSubtree(N node, HyperplaneConvexSubset<P> partitioner)
Split the subtree rooted at the given node by a partitioning convex subset defined on the same region as the node. The subtree rooted atnode
is imported into this tree, meaning that if it comes from a different tree, the other tree is not modified.- Parameters:
node
- the root node of the subtree to split; may come from a different tree, in which case the other tree is not modifiedpartitioner
- partitioning convex subset- Returns:
- node containing the split subtree
-
splitLeafNode
private N splitLeafNode(N node, HyperplaneConvexSubset<P> partitioner)
Split the given leaf node by a partitioning convex subset defined on the same region and import it into this tree.- Parameters:
node
- the leaf node to splitpartitioner
- partitioning convex subset- Returns:
- node containing the split subtree
-
splitInternalNode
private N splitInternalNode(N node, HyperplaneConvexSubset<P> partitioner)
Split the given internal node by a partitioning convex subset defined on the same region as the node and import it into this tree.- Parameters:
node
- the internal node to splitpartitioner
- partitioning convex subset- Returns:
- node containing the split subtree
-
invalidate
protected void invalidate()
Invalidate any previously computed properties that rely on the internal structure of the tree. This method must be called any time the tree's internal structure changes in order to force cacheable tree and node properties to be recomputed the next time they are requested.This method increments the tree's
version
property.- See Also:
getVersion()
-
getVersion
protected int getVersion()
Get the current structural version of the tree. This is incremented each time the tree structure is changes and can be used by nodes to allow caching of computed values.- Returns:
- the current version of the tree structure
- See Also:
invalidate()
-
-