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 type
N - 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 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 Details

  • Constructor Details

    • 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:
      IllegalArgumentException - if the tree is not empty
  • Method Details

    • 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:
      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, BiConsumer<N,HyperplaneConvexSubset<P>> leafFn)
      Insert a region boundary into the tree.
      Parameters:
      node - node to insert into
      insert - the hyperplane convex subset to insert
      trimmed - version of the hyperplane convex subset filling the entire space of node
      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 into
      insert - the hyperplane convex subset to insert
      trimmed - version of the hyperplane convex subset filling the entire space of node
      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

      private 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, 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 from
      parentIsPartitionNode - true if the parent of node is a partition node
      result - list of accumulated results
    • touchesInside

      private boolean touchesInside(HyperplaneConvexSubset<P> sub, N node)
      Return true if sub touches an inside leaf node anywhere in the subtree rooted at node.
      Parameters:
      sub - convex subset to check
      node - root node of the subtree to test against
      Returns:
      true if sub touches an inside leaf node anywhere in the subtree rooted at node
    • 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:
      IllegalStateException - if the instance is no longer accepting partitions