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.