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

  • Type Parameters:
    P - Point implementation type
    N - 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 the invalidate method. Properties can be cached directly on nodes using the checkValid and nodeInvalidated 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 to insert and cutNode in order to set the correct properties on tree nodes. To support tree copying, subclasses must also override copyNodeProperties.
    • This class is not thread safe.
    See Also:
    BSPTree
    • 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
      • 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.
    • Constructor Detail

      • AbstractBSPTree

        public AbstractBSPTree()
    • Method Detail

      • setRoot

        protected void setRoot​(N root)
        Set the root node for the tree. Cached tree properties are invalidated with invalidate().
        Parameters:
        root - new root node for 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.
      • 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. The cutRule argument specifies what should happen in this case.
        Specified by:
        findNode in interface BSPTree<P extends Point<P>,​N extends AbstractBSPTree.AbstractNode<P,​N>>
        Parameters:
        pt - test point used to locate a node in the tree
        cutBehavior - 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 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
      • 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.
        Specified by:
        extract in interface BSPTree<P extends Point<P>,​N extends AbstractBSPTree.AbstractNode<P,​N>>
        Parameters:
        node - the node to extract
      • 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 to maxDepth.
        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 class java.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 from src to dst. 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 node
        dst - 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 if src and dst reference the same node.
        Parameters:
        src - the node representing the source subtree; does not need to belong to the current tree
        dst - 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 from src to the root of its tree and set it as the parent path of dst. 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 of dst are not modified, with the exception of its parent node reference.
        Parameters:
        src - the source node to copy the parent path from
        dst - 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 with
        pt - the point to check
        cutRule - 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 process
        visitor - 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 visit
        visitor - 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:
        1. The hyperplane is trimmed by splitting it with each cut hyperplane on the path from the given node to the root of the tree.
        2. 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.
        3. 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 cut
        cutter - the hyperplane to cut the node with
        subtreeInitializer - 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 or null 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.
        These rules are designed to allow the creation of trees with node regions that are the thickness of a single hyperplane. For example, in two dimensions, a tree could be constructed with an internal node containing a cut along the x-axis in the positive direction and with a child node containing a cut along the x-axis in the opposite direction. If the nodes in the tree are given inside and outside attributes, then this tree could be used to represent a region consisting of a single line or a region consisting of the entire space except for the single line. This would not be possible if nodes were not able to have cut hyperplanes that were coincident with parent cuts but in opposite directions.

        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 to
        sub - 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
      • 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 with subtreeInitializer.

        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 cut
        cut - the hyperplane convex subset to set as the node cut
        subtreeInitializer - 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 with subtreeInit.
        Parameters:
        convexSub - hyperplane convex subset to insert into the tree
        subtreeInit - 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 with
        insert - the hyperplane subset to insert
        trimmed - hyperplane subset containing the result of splitting the entire space with each hyperplane from this node to the root
        subtreeInit - 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 as node recursively.
        Parameters:
        node - the root node of the subtree to transform
        t - the transform to apply
        swapChildren - 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 hyperplane
        minus - tree that will contain the portion of the tree on the minus side of the splitter
        plus - 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 at node 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 modified
        partitioner - 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 split
        partitioner - 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 split
        partitioner - 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()