Interface BSPTree<P extends Point<P>, N extends BSPTree.Node<P,N>>

Type Parameters:
P - Point implementation type
N - Node implementation type
All Superinterfaces:
BSPSubtree<P,N>
All Known Implementing Classes:
AbstractBSPTree, AbstractRegionBSPTree, RegionBSPTree1D, RegionBSPTree1S, RegionBSPTree2D, RegionBSPTree2S, RegionBSPTree3D
public interface BSPTree<P extends Point<P>, N extends BSPTree.Node<P,N>> extends BSPSubtree<P,N>
Interface for Binary Space Partitioning (BSP) trees. BSP trees are spatial data structures that recursively subdivide a space using hyperplanes. They can be used for a wide variety of purposes, such as representing arbitrary polytopes, storing data for fast spatial lookups, determining the correct rendering order for objects in a 3D scene, and so on.

This interface contains a number of methods for extracting information from existing trees, but it does not include methods for constructing trees or modifying tree structure. This is due to the large number of possible use cases for BSP trees. Each use case is likely to have its own specific methods and rules for tree construction, making it difficult to define a single API at this level. Thus, it is left to implementation classes to define their own API for tree construction and modification.

See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Interface
    Description
    static enum 
    BSPTree.FindNodeCutRule
    Enum specifying possible behaviors when a point used to locate a node falls directly on the cut of an internal node.
    static interface 
    BSPTree.Node<P extends Point<P>, N extends BSPTree.Node<P,N>>
    Interface for Binary Space Partitioning (BSP) tree nodes.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    copy(BSPTree<P,N> src)
    Make the current instance a deep copy of the argument.
    void
    extract(N node)
    Set this instance to the region represented by the given node.
    default N
    findNode(P pt)
    Find a node in this subtree containing the given point or its interior or boundary.
    N
    findNode(P pt, BSPTree.FindNodeCutRule cutRule)
    Find a node in this subtree containing the given point on its interior or boundary.
    N
    getRoot()
    Get the root node of the tree.
    void
    transform(Transform<P> transform)
    Transform this tree.

    Methods inherited from interface BSPSubtree

    accept, count, height, nodes

  • Method Details

    • getRoot

      N getRoot()
      Get the root node of the tree.
      Returns:
      the root node of the tree

    • findNode

      default N findNode(P pt)
      Find a node in this subtree containing the given point or its interior or boundary. When a point lies directly on the cut of an internal node, the minus child of the cut is chosen. This is equivalent to subtree.findNode(pt, FindNodeCutRule.MINUS) and always returns a leaf node.
      Parameters:
      pt - test point used to locate a node in the tree
      Returns:
      leaf node containing the point on its interior or boundary
      See Also:

    • findNode

      N findNode(P pt, BSPTree.FindNodeCutRule cutRule)
      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.
      Parameters:
      pt - test point used to locate a node in the tree
      cutRule - 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:

    • copy

      void copy(BSPTree<P,N> src)
      Make the current instance a deep copy of the argument.
      Parameters:
      src - the tree to copy

    • extract

      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.
      Parameters:
      node - the node to extract

    • transform

      void transform(Transform<P> transform)
      Transform this tree. Each cut in the tree is transformed in place using the given Transform.
      Parameters:
      transform - the transform to apply