Class AbstractPartitionedRegionBuilder<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>>
- Type Parameters:
P
- Point implementation typeN
- BSP tree node implementation type
- Direct Known Subclasses:
RegionBSPTree2D.PartitionedRegionBuilder2D
,RegionBSPTree3D.PartitionedRegionBuilder3D
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
FieldsModifier and TypeFieldDescriptionprivate static final Comparator
<BSPTree.Node<?, ?>> Comparator for sorting nodes with the deepest nodes first.private boolean
Flag indicating whether or not partitions may still be inserted into the tree.Set of all internal nodes used as partitioning nodes.private final AbstractBSPTree.SubtreeInitializer
<N> Subtree initializer for inserted boundaries.private final AbstractRegionBSPTree
<P, N> Tree being constructed. -
Constructor Summary
ConstructorsModifierConstructorDescriptionprotected
Construct a new instance that builds a partitioned region in the given tree. -
Method Summary
Modifier and TypeMethodDescriptionprotected AbstractRegionBSPTree
<P, N> Internal method to build and return the tree representing the final partitioned region.private void
collectOutsidePartitionedLeavesRecursive
(N node, boolean parentIsPartitionNode, List<N> result) Recursively collect all outside leaf nodes that have a parent marked as a partition node.private void
Throw an exception if the instance is no longer accepting partitions.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, BiConsumer<N, HyperplaneConvexSubset<P>> leafFn) Insert a region boundary into the tree.private void
insertBoundaryRecursiveInternalNode
(N node, HyperplaneConvexSubset<P> insert, HyperplaneConvexSubset<P> trimmed, 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
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 Details
-
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, treeN>> Tree being constructed. -
subtreeInit
private final AbstractBSPTree.SubtreeInitializer<N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>> subtreeInitSubtree initializer for inserted boundaries. -
insertingPartitions
private boolean insertingPartitionsFlag indicating whether or not partitions may still be inserted into the tree. -
partitionNodes
Set of all internal nodes used as partitioning nodes.
-
-
Constructor Details
-
AbstractPartitionedRegionBuilder
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:
IllegalArgumentException
- if the tree is not empty
-
-
Method Details
-
buildInternal
Internal method to build and return the tree representing the final partitioned region.- Returns:
- the partitioned region
-
insertPartitionInternal
Internal method to insert a partition into the tree.- Parameters:
partition
- partition to insert- Throws:
IllegalStateException
- if a boundary has previously been inserted
-
insertBoundaryInternal
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, 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, 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:
-
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
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, 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
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
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:
IllegalStateException
- if the instance is no longer accepting partitions
-