Class AbstractBSPTree.AbstractNode<P extends Point<P>,​N extends AbstractBSPTree.AbstractNode<P,​N>>

    • 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.
    • 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 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.
      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.
      • Methods inherited from class java.lang.Object

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

      • 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 Detail

      • AbstractNode

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

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

        public java.lang.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
      • 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
      • 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 java.lang.String toString()
        Overrides:
        toString in class java.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 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.