org.apache.commons.geometry.euclidean.twod

Class RegionBSPTree2D.PartitionedRegionBuilder2D

java.lang.Object

org.apache.commons.geometry.core.partitioning.bsp.AbstractPartitionedRegionBuilder<Vector2D,RegionBSPTree2D.RegionNode2D>

org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D.PartitionedRegionBuilder2D

Enclosing class:

RegionBSPTree2D

public static final class RegionBSPTree2D.PartitionedRegionBuilder2D
extends AbstractPartitionedRegionBuilder<Vector2D,RegionBSPTree2D.RegionNode2D>

Class used to build regions in Euclidean 2D space by inserting boundaries into a BSP tree containing "partitions", i.e. structural cuts where both sides of the cut have the same region location. When partitions are chosen that effectively divide the region boundaries at each partition level, the constructed tree is shallower and more balanced than one constructed from the region boundaries alone, resulting in improved performance. For example, consider a line segment approximation of a circle. The region is convex so each boundary has all of the other boundaries on its minus side; the plus sides are all empty. When these boundaries are inserted directly into a tree, the tree degenerates into a simple linked list of nodes with a height directly proportional to the number of boundaries. This means that many operations on the tree, such as inside/outside testing of points, involve iterating through each and every region boundary. In contrast, if a partition is first inserted that passes through the circle center, the first BSP tree node contains region nodes on its plus and minus sides, cutting the height of the tree in half. Operations such as inside/outside testing are then able to skip half of the tree nodes with a single test on the root node, resulting in drastically improved performance. Insertion of additional partitions (using a grid layout, for example) can produce even shallower trees, although there is a point unique to each boundary set at which the addition of more partitions begins to decrease instead of increase performance.

Usage

Usage of this class consists of 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 insertPartition or similar methods. The INHERIT cut rule is used internally to insert the cut so 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, using insertBoundary or similar methods. 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 build method is used to perform final processing and return the computed tree.

Method Summary

Modifier and Type	Method and Description
RegionBSPTree2D	build() Build and return the region BSP tree.
RegionBSPTree2D.PartitionedRegionBuilder2D	insertAxisAlignedGrid(Bounds2D bounds, int level, Precision.DoubleEquivalence precision) Insert a grid of partitions.
RegionBSPTree2D.PartitionedRegionBuilder2D	insertAxisAlignedPartitions(Vector2D center, Precision.DoubleEquivalence precision) Insert two axis aligned lines intersecting at the given point as partitions.
RegionBSPTree2D.PartitionedRegionBuilder2D	insertBoundaries(BoundarySource2D boundarySrc) Insert all boundaries from the given source.
RegionBSPTree2D.PartitionedRegionBuilder2D	insertBoundaries(Iterable<? extends LineConvexSubset> boundaries) Insert a collection of region boundaries.
RegionBSPTree2D.PartitionedRegionBuilder2D	insertBoundary(LineConvexSubset boundary) Insert a region boundary.
RegionBSPTree2D.PartitionedRegionBuilder2D	insertPartition(Line partition) Insert a partition line.
RegionBSPTree2D.PartitionedRegionBuilder2D	insertPartition(LineConvexSubset partition) Insert a line convex subset as a partition.

Methods inherited from class org.apache.commons.geometry.core.partitioning.bsp.AbstractPartitionedRegionBuilder

buildInternal, insertBoundaryInternal, insertPartitionInternal

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

insertPartition

public RegionBSPTree2D.PartitionedRegionBuilder2D insertPartition(Line partition)

Insert a partition line.

Parameters:

partition - partition to insert

Returns:

this instance

Throws:

IllegalStateException - if a boundary has previously been inserted

insertPartition

public RegionBSPTree2D.PartitionedRegionBuilder2D insertPartition(LineConvexSubset partition)

Insert a line convex subset as a partition.

Parameters:

partition - partition to insert

Returns:

this instance

Throws:

IllegalStateException - if a boundary has previously been inserted

insertAxisAlignedPartitions

public RegionBSPTree2D.PartitionedRegionBuilder2D insertAxisAlignedPartitions(Vector2D center,
                                                                              Precision.DoubleEquivalence precision)

Insert two axis aligned lines intersecting at the given point as partitions. The lines each contain the center point and have the directions +x and +y in that order. If inserted into an empty tree, this will partition the space into 4 sections.

Parameters:

center - center point for the partitions; the inserted lines intersect at this point

precision - precision context used to construct the lines

Returns:

this instance

Throws:

IllegalStateException - if a boundary has previously been inserted

insertAxisAlignedGrid

public RegionBSPTree2D.PartitionedRegionBuilder2D insertAxisAlignedGrid(Bounds2D bounds,
                                                                        int level,
                                                                        Precision.DoubleEquivalence precision)

Insert a grid of partitions. The partitions are constructed recursively: at each level two axis-aligned partitioning lines are inserted using insertAxisAlignedPartitions. The algorithm then recurses using bounding boxes from the min point to the center and from the center point to the max. Note that this means no partitions are ever inserted directly on the boundaries of the given bounding box. This is intentional and done to allow this method to be called directly with the bounding box from a set of boundaries to be inserted without unnecessarily adding partitions that will never have region boundaries on both sides.

Parameters:

bounds - bounding box for the grid

level - recursion level for the grid; each level subdivides each grid cube into 4 sections, making the total number of grid cubes equal to 4 ^ level

precision - precision context used to construct the partition lines

Returns:

this instance

Throws:

IllegalStateException - if a boundary has previously been inserted

insertBoundary

public RegionBSPTree2D.PartitionedRegionBuilder2D insertBoundary(LineConvexSubset boundary)

Insert a region boundary.

Parameters:

boundary - region boundary to insert

Returns:

this instance

insertBoundaries

public RegionBSPTree2D.PartitionedRegionBuilder2D insertBoundaries(Iterable<? extends LineConvexSubset> boundaries)

Insert a collection of region boundaries.

Parameters:

boundaries - boundaries to insert

Returns:

this instance

insertBoundaries

public RegionBSPTree2D.PartitionedRegionBuilder2D insertBoundaries(BoundarySource2D boundarySrc)

Insert all boundaries from the given source.

Parameters:

boundarySrc - source of boundaries to insert

Returns:

this instance

build

public RegionBSPTree2D build()

Build and return the region BSP tree.

Returns:

the region BSP tree