BSPTree (Apache Commons Math 3.6.1 API)

java.lang.Object
- org.apache.commons.math3.geometry.partitioning.BSPTree<S>

Type Parameters:
S - Type of the space.
```
public class BSPTree<S extends Space>
extends Object
```
This class represent a Binary Space Partition tree.
BSP trees are an efficient way to represent space partitions and to associate attributes with each cell. Each node in a BSP tree represents a convex region which is partitioned in two convex sub-regions at each side of a cut hyperplane. The root tree contains the complete space.

The main use of such partitions is to use a boolean attribute to define an inside/outside property, hence representing arbitrary polytopes (line segments in 1D, polygons in 2D and polyhedrons in 3D) and to operate on them.

Another example would be to represent Voronoi tesselations, the attribute of each cell holding the defining point of the cell.

The application-defined attributes are shared among copied instances and propagated to split parts. These attributes are not used by the BSP-tree algorithms themselves, so the application can use them for any purpose. Since the tree visiting method holds internal and leaf nodes differently, it is possible to use different classes for internal nodes attributes and leaf nodes attributes. This should be used with care, though, because if the tree is modified in any way after attributes have been set, some internal nodes may become leaf nodes and some leaf nodes may become internal nodes.

One of the main sources for the development of this package was Bruce Naylor, John Amanatides and William Thibault paper Merging BSP Trees Yields Polyhedral Set Operations Proc. Siggraph '90, Computer Graphics 24(4), August 1990, pp 115-124, published by the Association for Computing Machinery (ACM).

Since:

3.0

Nested Class Summary

Nested Classes
Modifier and Type	Class and Description
`static interface`	`BSPTree.LeafMerger<S extends Space>` This interface gather the merging operations between a BSP tree leaf and another BSP tree.
`static interface`	`BSPTree.VanishingCutHandler<S extends Space>` This interface handles the corner cases when an internal node cut sub-hyperplane vanishes.

Constructor Summary

Constructors
Constructor and Description
`BSPTree()` Build a tree having only one root cell representing the whole space.
`BSPTree(Object attribute)` Build a tree having only one root cell representing the whole space.
`BSPTree(SubHyperplane<S> cut, BSPTree<S> plus, BSPTree<S> minus, Object attribute)` Build a BSPTree from its underlying elements.

Method Summary

Methods
Modifier and Type	Method and Description
`BSPTree<S>`	`copySelf()` Copy the instance.
`Object`	`getAttribute()` Get the attribute associated with the instance.
`BSPTree<S>`	`getCell(Point<S> point, double tolerance)` Get the cell to which a point belongs.
`BSPTree<S>`	`getCell(Vector<S> point)` Deprecated. as of 3.3, replaced with `getCell(Point, double)`
`List<BSPTree<S>>`	`getCloseCuts(Point<S> point, double maxOffset)` Get the cells whose cut sub-hyperplanes are close to the point.
`SubHyperplane<S>`	`getCut()` Get the cut sub-hyperplane.
`BSPTree<S>`	`getMinus()` Get the tree on the minus side of the cut hyperplane.
`BSPTree<S>`	`getParent()` Get the parent node.
`BSPTree<S>`	`getPlus()` Get the tree on the plus side of the cut hyperplane.
`boolean`	`insertCut(Hyperplane<S> hyperplane)` Insert a cut sub-hyperplane in a node.
`void`	`insertInTree(BSPTree<S> parentTree, boolean isPlusChild)` Deprecated. as of 3.4, replaced with `insertInTree(BSPTree, boolean, VanishingCutHandler)`
`void`	`insertInTree(BSPTree<S> parentTree, boolean isPlusChild, BSPTree.VanishingCutHandler<S> vanishingHandler)` Insert the instance into another tree.
`BSPTree<S>`	`merge(BSPTree<S> tree, BSPTree.LeafMerger<S> leafMerger)` Merge a BSP tree with the instance.
`BSPTree<S>`	`pruneAroundConvexCell(Object cellAttribute, Object otherLeafsAttributes, Object internalAttributes)` Prune a tree around a cell.
`void`	`setAttribute(Object attribute)` Associate an attribute with the instance.
`BSPTree<S>`	`split(SubHyperplane<S> sub)` Split a BSP tree by an external sub-hyperplane.
`void`	`visit(BSPTreeVisitor<S> visitor)` Visit the BSP tree nodes.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - BSPTree
```
public BSPTree()
```
    Build a tree having only one root cell representing the whole space.
  - BSPTree
```
public BSPTree(Object attribute)
```
    Build a tree having only one root cell representing the whole space.
    
    Parameters:
    attribute - attribute of the tree (may be null)
  - BSPTree
```
public BSPTree(SubHyperplane<S> cut,
       BSPTree<S> plus,
       BSPTree<S> minus,
       Object attribute)
```
    Build a BSPTree from its underlying elements.
    This method does not perform any verification on consistency of its arguments, it should therefore be used only when then caller knows what it is doing.
    
    This method is mainly useful to build trees bottom-up. Building trees top-down is realized with the help of method insertCut.
    
    Parameters:
    cut - cut sub-hyperplane for the tree
    plus - plus side sub-tree
    minus - minus side sub-tree
    attribute - attribute associated with the node (may be null)
    See Also:
    insertCut(org.apache.commons.math3.geometry.partitioning.Hyperplane<S>)
- Method Detail
  - insertCut
```
public boolean insertCut(Hyperplane<S> hyperplane)
```
    Insert a cut sub-hyperplane in a node.
    The sub-tree starting at this node will be completely overwritten. The new cut sub-hyperplane will be built from the intersection of the provided hyperplane with the cell. If the hyperplane does intersect the cell, the cell will have two children cells with null attributes on each side of the inserted cut sub-hyperplane. If the hyperplane does not intersect the cell then no cut hyperplane will be inserted and the cell will be changed to a leaf cell. The attribute of the node is never changed.
    
    This method is mainly useful when called on leaf nodes (i.e. nodes for which getCut returns null), in this case it provides a way to build a tree top-down (whereas the 4 arguments constructor is devoted to build trees bottom-up).
    
    Parameters:
    hyperplane - hyperplane to insert, it will be chopped in order to fit in the cell defined by the parent nodes of the instance
    
    Returns:
    true if a cut sub-hyperplane has been inserted (i.e. if the cell now has two leaf child nodes)
    See Also:
    BSPTree(SubHyperplane, BSPTree, BSPTree, Object)
  - copySelf
```
public BSPTree<S> copySelf()
```
    Copy the instance.
    The instance created is completely independent of the original one. A deep copy is used, none of the underlying objects are shared (except for the nodes attributes and immutable objects).
    
    Returns:
    a new tree, copy of the instance
  - getCut
```
public SubHyperplane<S> getCut()
```
    Get the cut sub-hyperplane.
    
    Returns:
    cut sub-hyperplane, null if this is a leaf tree
  - getPlus
```
public BSPTree<S> getPlus()
```
    Get the tree on the plus side of the cut hyperplane.
    
    Returns:
    tree on the plus side of the cut hyperplane, null if this is a leaf tree
  - getMinus
```
public BSPTree<S> getMinus()
```
    Get the tree on the minus side of the cut hyperplane.
    
    Returns:
    tree on the minus side of the cut hyperplane, null if this is a leaf tree
  - getParent
```
public BSPTree<S> getParent()
```
    Get the parent node.
    
    Returns:
    parent node, null if the node has no parents
  - setAttribute
```
public void setAttribute(Object attribute)
```
    Associate an attribute with the instance.
    
    Parameters:
    attribute - attribute to associate with the node
    See Also:
    getAttribute()
  - getAttribute
```
public Object getAttribute()
```
    Get the attribute associated with the instance.
    
    Returns:
    attribute associated with the node or null if no attribute has been explicitly set using the setAttribute method
    See Also:
    setAttribute(java.lang.Object)
  - visit
```
public void visit(BSPTreeVisitor<S> visitor)
```
    Visit the BSP tree nodes.
    
    Parameters:
    visitor - object visiting the tree nodes
  - getCell
```
@Deprecated
public BSPTree<S> getCell(Vector<S> point)
```
    Deprecated. as of 3.3, replaced with getCell(Point, double)
    
    Get the cell to which a point belongs.
    If the returned cell is a leaf node the points belongs to the interior of the node, if the cell is an internal node the points belongs to the node cut sub-hyperplane.
    
    Parameters:
    point - point to check
    
    Returns:
    the tree cell to which the point belongs
  - getCell
```
public BSPTree<S> getCell(Point<S> point,
                 double tolerance)
```
    Get the cell to which a point belongs.
    If the returned cell is a leaf node the points belongs to the interior of the node, if the cell is an internal node the points belongs to the node cut sub-hyperplane.
    
    Parameters:
    point - point to check
    tolerance - tolerance below which points close to a cut hyperplane are considered to belong to the hyperplane itself
    
    Returns:
    the tree cell to which the point belongs
  - getCloseCuts
```
public List<BSPTree<S>> getCloseCuts(Point<S> point,
                            double maxOffset)
```
    Get the cells whose cut sub-hyperplanes are close to the point.
    
    Parameters:
    point - point to check
    maxOffset - offset below which a cut sub-hyperplane is considered close to the point (in absolute value)
    
    Returns:
    close cells (may be empty if all cut sub-hyperplanes are farther than maxOffset from the point)
  - merge
```
public BSPTree<S> merge(BSPTree<S> tree,
               BSPTree.LeafMerger<S> leafMerger)
```
    Merge a BSP tree with the instance.
    All trees are modified (parts of them are reused in the new tree), it is the responsibility of the caller to ensure a copy has been done before if any of the former tree should be preserved, no such copy is done here!
    
    The algorithm used here is directly derived from the one described in the Naylor, Amanatides and Thibault paper (section III, Binary Partitioning of a BSP Tree).
    
    Parameters:
    tree - other tree to merge with the instance (will be unusable after the operation, as well as the instance itself)
    leafMerger - object implementing the final merging phase (this is where the semantic of the operation occurs, generally depending on the attribute of the leaf node)
    
    Returns:
    a new tree, result of instance <op> tree, this value can be ignored if parentTree is not null since all connections have already been established
  - split
```
public BSPTree<S> split(SubHyperplane<S> sub)
```
    Split a BSP tree by an external sub-hyperplane.
    Split a tree in two halves, on each side of the sub-hyperplane. The instance is not modified.
    
    The tree returned is not upward-consistent: despite all of its sub-trees cut sub-hyperplanes (including its own cut sub-hyperplane) are bounded to the current cell, it is not attached to any parent tree yet. This tree is intended to be later inserted into an higher level tree.
    
    The algorithm used here is the one given in Naylor, Amanatides and Thibault paper (section III, Binary Partitioning of a BSP Tree).
    
    Parameters:
    sub - partitioning sub-hyperplane, must be already clipped to the convex region represented by the instance, will be used as the cut sub-hyperplane of the returned tree
    
    Returns:
    a tree having the specified sub-hyperplane as its cut sub-hyperplane, the two parts of the split instance as its two sub-trees and a null parent
  - insertInTree
```
@Deprecated
public void insertInTree(BSPTree<S> parentTree,
                           boolean isPlusChild)
```
    Deprecated. as of 3.4, replaced with insertInTree(BSPTree, boolean, VanishingCutHandler)
    
    Insert the instance into another tree.
    The instance itself is modified so its former parent should not be used anymore.
    
    Parameters:
    parentTree - parent tree to connect to (may be null)
    isPlusChild - if true and if parentTree is not null, the resulting tree should be the plus child of its parent, ignored if parentTree is null
    See Also:
    BSPTree.LeafMerger
  - insertInTree
```
public void insertInTree(BSPTree<S> parentTree,
                boolean isPlusChild,
                BSPTree.VanishingCutHandler<S> vanishingHandler)
```
    Insert the instance into another tree.
    The instance itself is modified so its former parent should not be used anymore.
    
    Parameters:
    parentTree - parent tree to connect to (may be null)
    isPlusChild - if true and if parentTree is not null, the resulting tree should be the plus child of its parent, ignored if parentTree is null
    vanishingHandler - handler to use for handling very rare corner cases of vanishing cut sub-hyperplanes in internal nodes during merging
    Since:
    
    3.4
    
    See Also:
    BSPTree.LeafMerger
  - pruneAroundConvexCell
```
public BSPTree<S> pruneAroundConvexCell(Object cellAttribute,
                               Object otherLeafsAttributes,
                               Object internalAttributes)
```
    Prune a tree around a cell.
    This method can be used to extract a convex cell from a tree. The original cell may either be a leaf node or an internal node. If it is an internal node, it's subtree will be ignored (i.e. the extracted cell will be a leaf node in all cases). The original tree to which the original cell belongs is not touched at all, a new independent tree will be built.
    
    Parameters:
    cellAttribute - attribute to set for the leaf node corresponding to the initial instance cell
    otherLeafsAttributes - attribute to set for the other leaf nodes
    internalAttributes - attribute to set for the internal nodes
    
    Returns:
    a new tree (the original tree is left untouched) containing a single branch with the cell as a leaf node, and other leaf nodes as the remnants of the pruned branches
    Since:
    
    3.3

Class BSPTree<S extends Space>

Nested Class Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

BSPTree

BSPTree

BSPTree

Method Detail

insertCut

copySelf

getCut

getPlus

getMinus

getParent

setAttribute

getAttribute

visit

getCell

getCell

getCloseCuts

merge

split

insertInTree

insertInTree

pruneAroundConvexCell