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

java.lang.Object
org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree<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 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:
  • Field Details

    • 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:
    • UNKNOWN_VALUE

      private static final int UNKNOWN_VALUE
      Integer value set on various node fields when a value is unknown.
      See Also:
    • root

      private N extends AbstractBSPTree.AbstractNode<P,N> root
      The root node for the tree.
    • 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 Details

    • AbstractBSPTree

      public AbstractBSPTree()
  • Method Details

    • getRoot

      public N getRoot()
      Get the root node of the tree.
      Specified by:
      getRoot in interface BSPTree<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
      Returns:
      the root node of the tree
    • 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
    • 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.
    • 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.
    • 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
    • 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:
    • 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
    • copy

      public void copy(BSPTree<P,N> src)
      Make the current instance a deep copy of the argument.
      Specified by:
      copy in interface BSPTree<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
      Parameters:
      src - the tree to copy
    • 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
    • transform

      public void transform(Transform<P> transform)
      Transform this tree. Each cut in the tree is transformed in place using the given Transform.
      Specified by:
      transform in interface BSPTree<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
      Parameters:
      transform - the transform to apply
    • treeString

      public 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<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>.
      Returns:
      a string representation of the tree
    • treeString

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

      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

      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: