Class AbstractPartitionedRegionBuilder<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>>
- java.lang.Object
-
- org.apache.commons.geometry.core.partitioning.bsp.AbstractPartitionedRegionBuilder<P,N>
-
- Type Parameters:
P
- Point implementation typeN
- BSP tree node implementation type
- Direct Known Subclasses:
RegionBSPTree2D.PartitionedRegionBuilder2D
,RegionBSPTree3D.PartitionedRegionBuilder3D
public abstract class AbstractPartitionedRegionBuilder<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>> extends java.lang.Object
Class encapsulating logic for building regions by inserting boundaries into a BSP tree containing structural cuts, i.e. cuts where both sides of the cut have the same region location. This technique only produces accurate results when the inserted boundaries define the entire surface of the region. However, for valid input boundaries, significant performance improvements can be achieved due to the reduced height of the tree, especially where large numbers of boundaries are involved and/or the defined region is convex.Implementation Notes
This class constructs regions in two phases: (1) partition insertion and (2) boundary insertion. Instances begin in the partition insertion phase. Here, partitions can be inserted into the empty tree using the standard BSP insertion logic. The
INHERIT
cut rule is used so that the represented region remains empty even as partitions are inserted.The instance moves into the boundary insertion phase when the caller inserts the first region boundary. Attempting to insert a partition after this point results in an
IllegalStateException
. This ensures that partitioning cuts are always located higher up the tree than boundary cuts.After all boundaries are inserted, the tree undergoes final processing to ensure that the region is consistent and that unnecessary nodes are removed.
This class does not expose any public methods so that subclasses can present their own public API, tailored to the specific types being worked with. In particular, most subclasses will want to restrict the tree types used with the algorithm, which is difficult to implement cleanly at this level.
-
-
Field Summary
Fields Modifier and Type Field Description private static java.util.Comparator<BSPTree.Node<?,?>>
DEEPEST_FIRST_ORDER
Comparator for sorting nodes with the deepest nodes first.private boolean
insertingPartitions
Flag indicating whether or not partitions may still be inserted into the tree.private java.util.Set<N>
partitionNodes
Set of all internal nodes used as partitioning nodes.private AbstractBSPTree.SubtreeInitializer<N>
subtreeInit
Subtree initializer for inserted boundaries.private AbstractRegionBSPTree<P,N>
tree
Tree being constructed.
-
Constructor Summary
Constructors Modifier Constructor Description protected
AbstractPartitionedRegionBuilder(AbstractRegionBSPTree<P,N> tree)
Construct a new instance that builds a partitioned region in the given tree.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected AbstractRegionBSPTree<P,N>
buildInternal()
Internal method to build and return the tree representing the final partitioned region.private void
collectOutsidePartitionedLeavesRecursive(N node, boolean parentIsPartitionNode, java.util.List<N> result)
Recursively collect all outside leaf nodes that have a parent marked as a partition node.private void
ensureInsertingPartitions()
Throw an exception if the instance is no longer accepting partitions.private java.util.List<N>
getOutsidePartitionedLeaves()
Return a list containing all outside leaf nodes that have a parent marked as a partition node.protected void
insertBoundaryInternal(HyperplaneConvexSubset<P> boundary)
Internal method to insert a region boundary into the tree.private void
insertBoundaryRecursive(N node, HyperplaneConvexSubset<P> insert, HyperplaneConvexSubset<P> trimmed, java.util.function.BiConsumer<N,HyperplaneConvexSubset<P>> leafFn)
Insert a region boundary into the tree.private void
insertBoundaryRecursiveInternalNode(N node, HyperplaneConvexSubset<P> insert, HyperplaneConvexSubset<P> trimmed, java.util.function.BiConsumer<N,HyperplaneConvexSubset<P>> leafFn)
Recursive boundary insertion method for internal nodes.protected void
insertPartitionInternal(HyperplaneConvexSubset<P> partition)
Internal method to insert a partition into the tree.private boolean
isPartitionNode(N node)
Return true if the given node is marked as a partition node.private boolean
propagateRegionInterior()
Propagate the region interior to partitioned leaf nodes that have not had a boundary inserted.private boolean
touchesInside(HyperplaneConvexSubset<P> sub, N node)
Return true ifsub
touches an inside leaf node anywhere in the subtree rooted atnode
.
-
-
-
Field Detail
-
DEEPEST_FIRST_ORDER
private static final java.util.Comparator<BSPTree.Node<?,?>> DEEPEST_FIRST_ORDER
Comparator for sorting nodes with the deepest nodes first.
-
tree
private final AbstractRegionBSPTree<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>> tree
Tree being constructed.
-
subtreeInit
private final AbstractBSPTree.SubtreeInitializer<N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>> subtreeInit
Subtree initializer for inserted boundaries.
-
insertingPartitions
private boolean insertingPartitions
Flag indicating whether or not partitions may still be inserted into the tree.
-
partitionNodes
private final java.util.Set<N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>> partitionNodes
Set of all internal nodes used as partitioning nodes.
-
-
Constructor Detail
-
AbstractPartitionedRegionBuilder
protected AbstractPartitionedRegionBuilder(AbstractRegionBSPTree<P,N> tree)
Construct a new instance that builds a partitioned region in the given tree. The tree must be empty.- Parameters:
tree
- tree to build the region in; must be empty- Throws:
java.lang.IllegalArgumentException
- if the tree is not empty
-
-
Method Detail
-
buildInternal
protected AbstractRegionBSPTree<P,N> buildInternal()
Internal method to build and return the tree representing the final partitioned region.- Returns:
- the partitioned region
-
insertPartitionInternal
protected void insertPartitionInternal(HyperplaneConvexSubset<P> partition)
Internal method to insert a partition into the tree.- Parameters:
partition
- partition to insert- Throws:
java.lang.IllegalStateException
- if a boundary has previously been inserted
-
insertBoundaryInternal
protected void insertBoundaryInternal(HyperplaneConvexSubset<P> boundary)
Internal method to insert a region boundary into the tree.- Parameters:
boundary
- boundary to insert
-
insertBoundaryRecursive
private void insertBoundaryRecursive(N node, HyperplaneConvexSubset<P> insert, HyperplaneConvexSubset<P> trimmed, java.util.function.BiConsumer<N,HyperplaneConvexSubset<P>> leafFn)
Insert a region boundary into the tree.- Parameters:
node
- node to insert intoinsert
- the hyperplane convex subset to inserttrimmed
- version of the hyperplane convex subset filling the entire space ofnode
leafFn
- function to apply to leaf nodes
-
insertBoundaryRecursiveInternalNode
private void insertBoundaryRecursiveInternalNode(N node, HyperplaneConvexSubset<P> insert, HyperplaneConvexSubset<P> trimmed, java.util.function.BiConsumer<N,HyperplaneConvexSubset<P>> leafFn)
Recursive boundary insertion method for internal nodes.- Parameters:
node
- node to insert intoinsert
- the hyperplane convex subset to inserttrimmed
- version of the hyperplane convex subset filling the entire space ofnode
leafFn
- function to apply to leaf nodes- See Also:
insertBoundaryRecursive(AbstractRegionNode, HyperplaneConvexSubset, HyperplaneConvexSubset, BiConsumer)
-
propagateRegionInterior
private boolean propagateRegionInterior()
Propagate the region interior to partitioned leaf nodes that have not had a boundary inserted.- Returns:
- true if any nodes were changed
-
getOutsidePartitionedLeaves
private java.util.List<N> getOutsidePartitionedLeaves()
Return a list containing all outside leaf nodes that have a parent marked as a partition node.- Returns:
- a list containing all outside leaf nodes that have a parent marked as a partition node
-
collectOutsidePartitionedLeavesRecursive
private void collectOutsidePartitionedLeavesRecursive(N node, boolean parentIsPartitionNode, java.util.List<N> result)
Recursively collect all outside leaf nodes that have a parent marked as a partition node.- Parameters:
node
- root of the subtree to collect nodes fromparentIsPartitionNode
- true if the parent ofnode
is a partition noderesult
- list of accumulated results
-
touchesInside
private boolean touchesInside(HyperplaneConvexSubset<P> sub, N node)
Return true ifsub
touches an inside leaf node anywhere in the subtree rooted atnode
.- Parameters:
sub
- convex subset to checknode
- root node of the subtree to test against- Returns:
- true if
sub
touches an inside leaf node anywhere in the subtree rooted atnode
-
isPartitionNode
private boolean isPartitionNode(N node)
Return true if the given node is marked as a partition node.- Parameters:
node
- node to check- Returns:
- true if the given node is marked as a partition node
-
ensureInsertingPartitions
private void ensureInsertingPartitions()
Throw an exception if the instance is no longer accepting partitions.- Throws:
java.lang.IllegalStateException
- if the instance is no longer accepting partitions
-
-