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.

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    AbstractNode(AbstractBSPTree<P,N> tree)
    Simple constructor.

  • Method Summary

    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 the BSPTree 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 from checkValid() when updates are detected in the tree.
    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.
    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.

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Constructor Details

  • 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

      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 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.