P
- Point implementation typeN
- BSP tree node implementation typepublic abstract class AbstractBSPTree<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>> extends Object implements BSPTree<P,N>
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.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.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
.BSPTree
Modifier and Type | Class and Description |
---|---|
static class |
AbstractBSPTree.AbstractNode<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
Abstract implementation of
BSPTree.Node . |
static interface |
AbstractBSPTree.SubtreeInitializer<N extends AbstractBSPTree.AbstractNode<?,?>>
Interface used to initialize newly created BSP subtrees, consisting of a single parent
node and two child nodes.
|
BSPTree.FindNodeCutRule, BSPTree.Node<P extends Point<P>,N extends BSPTree.Node<P,N>>
Constructor and Description |
---|
AbstractBSPTree() |
Modifier and Type | Method and Description |
---|---|
void |
accept(BSPTreeVisitor<P,N> visitor)
Accept a visitor instance, calling it with each node from the subtree.
|
protected void |
accept(N node,
BSPTreeVisitor<P,N> visitor)
Visit the nodes in a subtree.
|
void |
copy(BSPTree<P,N> src)
Make the current instance a deep copy of the argument.
|
protected N |
copyNode(N src)
Create a non-structural copy of the given node.
|
protected abstract void |
copyNodeProperties(N src,
N dst)
Copy non-structural node properties from
src to dst . |
protected N |
copySubtree(N src,
N dst)
Recursively copy a subtree.
|
int |
count()
Return the total number of nodes in the subtree.
|
protected abstract N |
createNode()
Create a new node for this tree.
|
protected boolean |
cutNode(N node,
Hyperplane<P> cutter,
AbstractBSPTree.SubtreeInitializer<N> subtreeInitializer)
Cut a node with a hyperplane.
|
void |
extract(N node)
Set this instance to the region represented by the given node.
|
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 . |
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.
|
N |
findNode(P pt,
BSPTree.FindNodeCutRule cutBehavior)
Find a node in this subtree containing the given point on its interior or boundary.
|
N |
getRoot()
Get the root node of the tree.
|
protected int |
getVersion()
Get the current structural version of the tree.
|
int |
height()
The height of the subtree, ie the length of the longest downward path from
the subtree root to a leaf node.
|
protected N |
importSubtree(N src)
Import the subtree represented by the given node into this tree.
|
protected void |
insert(HyperplaneConvexSubset<P> convexSub,
AbstractBSPTree.SubtreeInitializer<N> subtreeInit)
Insert the given hyperplane convex subset into the tree, starting at the root node.
|
protected void |
invalidate()
Invalidate any previously computed properties that rely on the internal structure of the tree.
|
Iterable<N> |
nodes()
Get an iterable for accessing the nodes in this subtree.
|
protected boolean |
removeNodeCut(N node)
Remove the cut from the given node.
|
protected void |
setNodeCut(N node,
HyperplaneConvexSubset<P> cut,
AbstractBSPTree.SubtreeInitializer<N> subtreeInitializer)
Set the cut hyperplane subset for the given node.
|
protected void |
setRoot(N root)
Set the root node for the tree.
|
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.
|
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.
|
protected boolean |
swapsInsideOutside(Transform<P> transform)
Return true if the given transform swaps the inside and outside of
the region.
|
String |
toString() |
void |
transform(Transform<P> transform)
Transform this tree.
|
String |
treeString()
Get a simple string representation of the tree structure.
|
String |
treeString(int maxDepth)
Get a simple string representation of the tree structure.
|
protected HyperplaneConvexSubset<P> |
trimToNode(N node,
HyperplaneConvexSubset<P> sub)
Trim the given hyperplane convex subset to the region defined by the given node.
|
public AbstractBSPTree()
protected void setRoot(N root)
invalidate()
.root
- new root node for the treepublic int count()
count
in interface BSPSubtree<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
public int height()
height
in interface BSPSubtree<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
public void accept(BSPTreeVisitor<P,N> visitor)
accept
in interface BSPSubtree<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
visitor
- visitor called with each subtree nodepublic N findNode(P pt, BSPTree.FindNodeCutRule cutBehavior)
cutRule
argument specifies what should happen in this case.
BSPTree.FindNodeCutRule.MINUS
- continue the search in the minus subtreeBSPTree.FindNodeCutRule.PLUS
- continue the search in the plus subtreeBSPTree.FindNodeCutRule.NODE
- stop the search and return the internal nodefindNode
in interface BSPTree<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
pt
- test point used to locate a node in the treecutBehavior
- value used to determine the search behavior when the test point lies
exactly on the cut of an internal nodeBSPTree.findNode(Point)
public Iterable<N> nodes()
BSPSubtree.accept(BSPTreeVisitor)
for accessing tree nodes but is not
as powerful or flexible since the node iteration order is fixed.nodes
in interface BSPSubtree<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>
public void extract(N node)
public void transform(Transform<P> transform)
Transform
.public String treeString()
public String treeString(int maxDepth)
maxDepth
.maxDepth
- the maximum depth in the tree to print; nodes below this depth are skippedprotected abstract N createNode()
protected abstract void copyNodeProperties(N src, N dst)
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.src
- source nodedst
- destination nodeprotected N copyNode(N src)
src
- the node to copy; does not need to belong to the current treecopyNodeProperties(AbstractNode, AbstractNode)
protected N copySubtree(N src, N dst)
src
and dst
reference the same node.src
- the node representing the source subtree; does not need to belong to the
current treedst
- the node representing the destination subtreedst
protected N importSubtree(N src)
This method does not modify the current structure of the tree.
src
- node to importcopySubtree(AbstractNode, AbstractNode)
protected N extractParentPath(N src, N dst)
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.src
- the source node to copy the parent path fromdst
- the destination node to place under the extracted pathprotected N findNode(N start, P pt, BSPTree.FindNodeCutRule cutRule)
start
- the node to begin the search withpt
- the point to checkcutRule
- value determining the search behavior when the test point
lies directly on the cut of an internal nodeprotected void accept(N node, BSPTreeVisitor<P,N> visitor)
node
- the node to begin the visit processvisitor
- the visitor to pass nodes toprotected boolean cutNode(N node, Hyperplane<P> cutter, AbstractBSPTree.SubtreeInitializer<N> subtreeInitializer)
subtreeInitializer
, andIt 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.
node
- the node to cutcutter
- the hyperplane to cut the node withsubtreeInitializer
- object used to initialize any newly-created subtreestrimToNode(AbstractNode, HyperplaneConvexSubset)
,
setNodeCut(AbstractNode, HyperplaneConvexSubset, SubtreeInitializer)
,
removeNodeCut(AbstractNode)
,
invalidate()
protected HyperplaneConvexSubset<P> trimToNode(N node, HyperplaneConvexSubset<P> sub)
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.
null
is returned.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.
node
- the node representing the region to fit the hyperplane subset tosub
- the hyperplane subset to trim to the node's regionprotected boolean removeNodeCut(N node)
This method calls invalidate()
to invalidate cached tree properties if the tree
structure changed.
node
- the node to remove the cut fromprotected void setNodeCut(N node, HyperplaneConvexSubset<P> cut, AbstractBSPTree.SubtreeInitializer<N> subtreeInitializer)
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.
node
- the node to cutcut
- the hyperplane convex subset to set as the node cutsubtreeInitializer
- object used to initialize the newly-created subtreeprotected void insert(HyperplaneConvexSubset<P> convexSub, AbstractBSPTree.SubtreeInitializer<N> subtreeInit)
subtreeInit
.convexSub
- hyperplane convex subset to insert into the treesubtreeInit
- object used to initialize newly created subtreesprotected boolean swapsInsideOutside(Transform<P> transform)
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.
transform
- transform to checkprotected void splitIntoTrees(Hyperplane<P> splitter, AbstractBSPTree<P,N> minus, AbstractBSPTree<P,N> plus)
splitter
- splitting hyperplaneminus
- tree that will contain the portion of the tree on the minus side of the splitterplus
- tree that will contain the portion of the tree on the plus side of the splitterprotected N splitSubtree(N node, HyperplaneConvexSubset<P> partitioner)
node
is imported into
this tree, meaning that if it comes from a different tree, the other tree is not
modified.node
- the root node of the subtree to split; may come from a different tree,
in which case the other tree is not modifiedpartitioner
- partitioning convex subsetprotected void invalidate()
This method increments the tree's version
property.
getVersion()
protected int getVersion()
invalidate()
Copyright © 2016–2021 The Apache Software Foundation. All rights reserved.