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 type
N - 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 Object implements BSPTree.Node<P,N>
Abstract implementation of BSPTree.Node. This class is intended for use with AbstractBSPTree and delegates tree mutation methods back to the parent tree object.
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private int
    The total number of nodes in the subtree rooted at this node.
    The hyperplane convex subset cutting the node's region; this will be null for leaf nodes.
    private int
    The depth of this node in the tree.
    private int
    The height of the subtree rooted at this node.
    private N
    The node lying on the minus side of the cut hyperplane; this will be null for leaf nodes.
    private int
    The current version of the node.
    private N
    The parent node; this will be null for the tree root node.
    private N
    The node lying on the plus side of the cut hyperplane; this will be null for leaf nodes.
    private final AbstractBSPTree<P,N>
    The owning tree instance.
  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    Simple constructor.
  • Method Summary

    Modifier and Type
    Method
    Description
    void
    Accept a visitor instance, calling it with each node from the subtree.
    protected void
    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
    Return the total number of nodes in the subtree.
    int
    Get the depth of the node in the tree.
    Get the cut for the node.
    Get the hyperplane containing the node cut, if it exists.
    Get the node for the minus region of the cell.
    Get the parent of the node.
    Get the node for the plus region of the cell.
    protected abstract N
    Get a reference to the current instance, cast to type N.
    Get the BSPTree that owns the node.
    int
    The height of the subtree, ie the length of the longest downward path from the subtree root to a leaf node.
    boolean
    Return true if the node is an internal node, meaning that is has a binary partitioner (aka "cut") and therefore two child nodes.
    boolean
    Return true if the node is a leaf node, meaning that it has no binary partitioner (aka "cut") and therefore no child nodes.
    boolean
    Return true if the node has a parent and is the parent's minus child.
    boolean
    Return true if the node has a parent and is the parent's plus child.
    protected void
    Make this node a root node, detaching it from its parent and settings its depth to zero.
    protected void
    Method called from checkValid() when updates are detected in the tree.
    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.
    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.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
  • Field Details

    • 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 and AbstractBSPTree.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 to AbstractBSPTree.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 to AbstractBSPTree.UNKNOWN_VALUE when the value needs to be computed.
  • Constructor Details

    • AbstractNode

      protected AbstractNode(AbstractBSPTree<P,N> tree)
      Simple constructor.
      Parameters:
      tree - the tree instance that owns this node
  • Method Details

    • getTree

      public AbstractBSPTree<P,N> getTree()
      Get the BSPTree that owns the node.
      Specified by:
      getTree in interface BSPTree.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 interface BSPTree.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 interface BSPSubtree<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 interface BSPSubtree<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
      Returns:
      the total number of nodes in the subtree.
    • nodes

      public Iterable<N> nodes()
      Get an iterable for accessing the nodes in this subtree. This provides a simple alternative to BSPSubtree.accept(BSPTreeVisitor) for accessing tree nodes but is not as powerful or flexible since the node iteration order is fixed.
      Specified by:
      nodes in interface BSPSubtree<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 interface BSPSubtree<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 interface BSPTree.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 interface BSPTree.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 interface BSPTree.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 interface BSPTree.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 interface BSPTree.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 interface BSPTree.Node<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
      Returns:
      the cut for the cell
      See Also:
    • getCutHyperplane

      public Hyperplane<P> getCutHyperplane()
      Get the hyperplane containing the node cut, if it exists.
      Specified by:
      getCutHyperplane in interface BSPTree.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:
    • 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 interface BSPTree.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 interface BSPTree.Node<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
      Returns:
      the node for the minus region of the cell
    • trim

      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 interface BSPTree.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 String toString()
      Overrides:
      toString in class 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 node
      newMinus - the new minus child for the node
      newPlus - 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, the nodeInvalidated() 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 from checkValid() 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.