Class AbstractBSPTree.AbstractNode<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
- java.lang.Object
-
- org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree.AbstractNode<P,N>
-
- Type Parameters:
P
- Point implementation typeN
- BSP tree node implementation type
- All Implemented Interfaces:
BSPSubtree<P,N>
,BSPTree.Node<P,N>
- Direct Known Subclasses:
AbstractRegionBSPTree.AbstractRegionNode
- Enclosing class:
- AbstractBSPTree<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
public abstract static class AbstractBSPTree.AbstractNode<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>> extends java.lang.Object implements BSPTree.Node<P,N>
Abstract implementation ofBSPTree.Node
. This class is intended for use withAbstractBSPTree
and delegates tree mutation methods back to the parent tree object.
-
-
Field Summary
Fields Modifier and Type Field Description private int
count
The total number of nodes in the subtree rooted at this node.private HyperplaneConvexSubset<P>
cut
The hyperplane convex subset cutting the node's region; this will be null for leaf nodes.private int
depth
The depth of this node in the tree.private int
height
The height of the subtree rooted at this node.private N
minus
The node lying on the minus side of the cut hyperplane; this will be null for leaf nodes.private int
nodeVersion
The current version of the node.private N
parent
The parent node; this will be null for the tree root node.private N
plus
The node lying on the plus side of the cut hyperplane; this will be null for leaf nodes.private AbstractBSPTree<P,N>
tree
The owning tree instance.
-
Constructor Summary
Constructors Modifier Constructor Description protected
AbstractNode(AbstractBSPTree<P,N> tree)
Simple constructor.
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description void
accept(BSPTreeVisitor<P,N> visitor)
Accept a visitor instance, calling it with each node from the subtree.protected void
checkValid()
Check if cached node properties are valid, meaning that no structural updates have occurred in the tree since the last call to this method.int
count()
Return the total number of nodes in the subtree.int
depth()
Get the depth of the node in the tree.HyperplaneConvexSubset<P>
getCut()
Get the cut for the node.Hyperplane<P>
getCutHyperplane()
Get the hyperplane containing the node cut, if it exists.N
getMinus()
Get the node for the minus region of the cell.N
getParent()
Get the parent of the node.N
getPlus()
Get the node for the plus region of the cell.protected abstract N
getSelf()
Get a reference to the current instance, cast to type N.AbstractBSPTree<P,N>
getTree()
Get theBSPTree
that owns the node.int
height()
The height of the subtree, ie the length of the longest downward path from the subtree root to a leaf node.boolean
isInternal()
Return true if the node is an internal node, meaning that is has a binary partitioner (aka "cut") and therefore two child nodes.boolean
isLeaf()
Return true if the node is a leaf node, meaning that it has no binary partitioner (aka "cut") and therefore no child nodes.boolean
isMinus()
Return true if the node has a parent and is the parent's minus child.boolean
isPlus()
Return true if the node has a parent and is the parent's plus child.protected void
makeRoot()
Make this node a root node, detaching it from its parent and settings its depth to zero.protected void
nodeInvalidated()
Method called fromcheckValid()
when updates are detected in the tree.java.lang.Iterable<N>
nodes()
Get an iterable for accessing the nodes in this subtree.protected void
setSubtree(HyperplaneConvexSubset<P> newCut, N newMinus, N newPlus)
Set the parameters for the subtree rooted at this node.java.lang.String
toString()
HyperplaneConvexSubset<P>
trim(HyperplaneConvexSubset<P> sub)
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.
-
-
-
Field Detail
-
tree
private final AbstractBSPTree<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>> tree
The owning tree instance.
-
parent
private N extends AbstractBSPTree.AbstractNode<P,N> parent
The parent node; this will be null for the tree root node.
-
cut
private HyperplaneConvexSubset<P extends Point<P>> cut
The hyperplane convex subset cutting the node's region; this will be null for leaf nodes.
-
minus
private N extends AbstractBSPTree.AbstractNode<P,N> minus
The node lying on the minus side of the cut hyperplane; this will be null for leaf nodes.
-
plus
private N extends AbstractBSPTree.AbstractNode<P,N> plus
The node lying on the plus side of the cut hyperplane; this will be null for leaf nodes.
-
nodeVersion
private int nodeVersion
The current version of the node. This is set to track the tree's version and is used to detect when certain values need to be recomputed due to structural changes in the tree.
-
depth
private int depth
The depth of this node in the tree. This will be zero for the root node andAbstractBSPTree.UNKNOWN_VALUE
when the value needs to be computed.
-
count
private int count
The total number of nodes in the subtree rooted at this node. This will be set toAbstractBSPTree.UNKNOWN_VALUE
when the value needs to be computed.
-
height
private int height
The height of the subtree rooted at this node. This will be set toAbstractBSPTree.UNKNOWN_VALUE
when the value needs to be computed.
-
-
Constructor Detail
-
AbstractNode
protected AbstractNode(AbstractBSPTree<P,N> tree)
Simple constructor.- Parameters:
tree
- the tree instance that owns this node
-
-
Method Detail
-
getTree
public AbstractBSPTree<P,N> getTree()
Get theBSPTree
that owns the node.- Specified by:
getTree
in interfaceBSPTree.Node<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
- Returns:
- the owning tree
-
depth
public int depth()
Get the depth of the node in the tree. The root node of the tree has a depth of 0.- Specified by:
depth
in interfaceBSPTree.Node<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
- Returns:
- the depth of the node in the tree
-
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.
-
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.
-
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
-
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
-
getParent
public N getParent()
Get the parent of the node. This will be null if the node is the root of the tree.- Specified by:
getParent
in interfaceBSPTree.Node<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
- Returns:
- the parent node for this instance
-
isLeaf
public boolean isLeaf()
Return true if the node is a leaf node, meaning that it has no binary partitioner (aka "cut") and therefore no child nodes.- Specified by:
isLeaf
in interfaceBSPTree.Node<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
- Returns:
- true if the node is a leaf node
-
isInternal
public boolean isInternal()
Return true if the node is an internal node, meaning that is has a binary partitioner (aka "cut") and therefore two child nodes.- Specified by:
isInternal
in interfaceBSPTree.Node<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
- Returns:
- true if the node is an internal node
-
isPlus
public boolean isPlus()
Return true if the node has a parent and is the parent's plus child.- Specified by:
isPlus
in interfaceBSPTree.Node<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
- Returns:
- true if the node is the plus child of its parent
-
isMinus
public boolean isMinus()
Return true if the node has a parent and is the parent's minus child.- Specified by:
isMinus
in interfaceBSPTree.Node<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
- Returns:
- true if the node is the minus child of its parent
-
getCut
public HyperplaneConvexSubset<P> getCut()
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.- Specified by:
getCut
in interfaceBSPTree.Node<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
- Returns:
- the cut for the cell
- See Also:
BSPTree.Node.getPlus()
,BSPTree.Node.getMinus()
,BSPTree.Node.getCutHyperplane()
-
getCutHyperplane
public Hyperplane<P> getCutHyperplane()
Get the hyperplane containing the node cut, if it exists.- Specified by:
getCutHyperplane
in interfaceBSPTree.Node<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
- Returns:
- the hyperplane containing the node cut, or null if the node does not have a cut
- See Also:
BSPTree.Node.getCut()
-
getPlus
public N getPlus()
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.- Specified by:
getPlus
in interfaceBSPTree.Node<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
- Returns:
- the node for the plus region of the cell
-
getMinus
public N getMinus()
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.- Specified by:
getMinus
in interfaceBSPTree.Node<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
- Returns:
- the node for the minus region of the cell
-
trim
public HyperplaneConvexSubset<P> trim(HyperplaneConvexSubset<P> sub)
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.- Specified by:
trim
in interfaceBSPTree.Node<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
- Parameters:
sub
- the hyperplane subset to trim- Returns:
- the trimmed hyperplane subset or null if no part of the argument lies within the node's region
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
setSubtree
protected void setSubtree(HyperplaneConvexSubset<P> newCut, N newMinus, N newPlus)
Set the parameters for the subtree rooted at this node. The arguments should either be all null (representing a leaf node) or all non-null (representing an internal node).Absolutely no validation is performed on the arguments. Callers are responsible for ensuring that any given hyperplane subset fits the region defined by the node and that any child nodes belong to this tree and are correctly initialized.
- Parameters:
newCut
- the new cut hyperplane subset for the nodenewMinus
- the new minus child for the nodenewPlus
- the new plus child for the node
-
makeRoot
protected void makeRoot()
Make this node a root node, detaching it from its parent and settings its depth to zero. Any previous parent node will be left in an invalid state since one of its children now does not have a reference back to it.
-
checkValid
protected void checkValid()
Check if cached node properties are valid, meaning that no structural updates have occurred in the tree since the last call to this method. If updates have occurred, thenodeInvalidated()
method is called to clear the cached properties. This method should be called at the beginning of any method that fetches cacheable properties to ensure that no stale values are returned.
-
nodeInvalidated
protected void nodeInvalidated()
Method called fromcheckValid()
when updates are detected in the tree. This method should clear out any computed properties that rely on the structure of the tree and prepare them for recalculation.
-
getSelf
protected abstract N getSelf()
Get a reference to the current instance, cast to type N.- Returns:
- a reference to the current instance, as type N.
-
-