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:
    Binary space partitioning
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Interface Description
      static class  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 Detail

      • 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(Point, FindNodeCutRule)
      • 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:
        findNode(Point)
      • 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