Class RegionBSPTree2D
java.lang.Object
org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree<Vector2D,RegionBSPTree2D.RegionNode2D>
org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree<Vector2D,RegionBSPTree2D.RegionNode2D>
org.apache.commons.geometry.euclidean.twod.RegionBSPTree2D
- All Implemented Interfaces:
BoundarySource<LineConvexSubset>
,BSPSubtree<Vector2D,
,RegionBSPTree2D.RegionNode2D> BSPTree<Vector2D,
,RegionBSPTree2D.RegionNode2D> HyperplaneBoundedRegion<Vector2D>
,Splittable<Vector2D,
,HyperplaneBoundedRegion<Vector2D>> Region<Vector2D>
,Sized
,BoundarySource2D
,Linecastable2D
public final class RegionBSPTree2D
extends AbstractRegionBSPTree<Vector2D,RegionBSPTree2D.RegionNode2D>
implements BoundarySource2D
Binary space partitioning (BSP) tree representing a region in two dimensional
Euclidean space.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static final class
Class used to project points onto the 2D region boundary.private static final class
BSP tree visitor that performs a linecast operation against the boundaries of the visited tree.static final class
Class used to build regions in Euclidean 2D space by inserting boundaries into a BSP tree containing "partitions", i.e.static final class
BSP tree node for two dimensional Euclidean space.Nested classes/interfaces inherited from class org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree
AbstractRegionBSPTree.AbstractRegionNode<P extends Point<P>,
N extends AbstractRegionBSPTree.AbstractRegionNode<P, N>>, AbstractRegionBSPTree.BoundaryProjector<P extends Point<P>, N extends AbstractRegionBSPTree.AbstractRegionNode<P, N>>, AbstractRegionBSPTree.RegionSizeProperties<P extends Point<P>> Nested classes/interfaces inherited from class org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree
AbstractBSPTree.AbstractNode<P extends Point<P>,
N extends AbstractBSPTree.AbstractNode<P, N>>, AbstractBSPTree.SubtreeInitializer<N extends AbstractBSPTree.AbstractNode<?, ?>> Nested classes/interfaces inherited from interface org.apache.commons.geometry.core.partitioning.bsp.BSPTree
BSPTree.FindNodeCutRule, BSPTree.Node<P extends Point<P>,
N extends BSPTree.Node<P, N>> -
Field Summary
FieldsModifier and TypeFieldDescriptionList of line subset paths comprising the region boundary. -
Constructor Summary
ConstructorsConstructorDescriptionCreate a new, empty region.RegionBSPTree2D
(boolean full) Create a new region. -
Method Summary
Modifier and TypeMethodDescriptionvoid
add
(ConvexArea area) Add a convex area to this region.Return anIterable
for iterating over the boundaries of the region.Return a stream containing the boundaries for this instance.Compute the line subset paths comprising the region boundary.Compute the size-related properties of the region.copy()
Return a deep copy of this instance.protected RegionBSPTree2D.RegionNode2D
Create a new node for this tree.static RegionBSPTree2D
empty()
Return a new, emptyRegionBSPTree2D
instance.static RegionBSPTree2D
from
(Iterable<? extends LineConvexSubset> boundaries) Construct a new tree from the given boundaries.static RegionBSPTree2D
from
(Iterable<? extends LineConvexSubset> boundaries, boolean full) Construct a new tree from the given boundaries.static RegionBSPTree2D
full()
Return a newRegionBSPTree2D
instance containing the entire space.Return a list containing the boundaries of the region.Get the boundary of the region as a list of connected line subset paths.protected void
Invalidate any previously computed properties that rely on the internal structure of the tree.linecast
(LineConvexSubset subset) Intersect the given line subset against the boundaries in this instance, returning a list of all intersections in order of increasing position along the line.linecastFirst
(LineConvexSubset subset) Intersect the given line subset against the boundaries in this instance, returning the first intersection found when traveling in the direction of the line subset from its start location.Create a newRegionBSPTree2D.PartitionedRegionBuilder2D
instance which can be used to build balanced BSP trees from region boundaries.Project a point onto the boundary of the region.split
(Hyperplane<Vector2D> splitter) Split this instance with the given hyperplane.toConvex()
Return a list ofConvexArea
s representing the same region as this instance.private void
toConvexRecursive
(RegionBSPTree2D.RegionNode2D node, ConvexArea nodeArea, List<? super ConvexArea> result) Recursive method to compute the convex areas of all inside leaf nodes in the subtree rooted at the given node.toTree()
Return the current instance.Methods inherited from class org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree
classify, complement, complement, condense, copyNodeProperties, createBoundaryIterable, createBoundaryList, difference, difference, getBoundarySize, getCentroid, getRegionSizeProperties, getSize, getSubtreeInitializer, insert, insert, insert, insert, insert, insert, insert, insert, intersection, intersection, isEmpty, isFull, setEmpty, setFull, split, union, union, xor, xor
Methods inherited from class org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree
accept, accept, copy, copyNode, copySubtree, count, cutNode, extract, extractParentPath, findNode, findNode, getRoot, getVersion, height, importSubtree, insert, nodes, removeNodeCut, setNodeCut, setRoot, splitIntoTrees, splitSubtree, swapsInsideOutside, toString, transform, treeString, treeString, trimToNode
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
Methods inherited from interface org.apache.commons.geometry.euclidean.twod.BoundarySource2D
getBounds, toList
Methods inherited from interface org.apache.commons.geometry.euclidean.twod.Linecastable2D
linecast, linecastFirst
Methods inherited from interface org.apache.commons.geometry.core.Sized
isFinite, isInfinite
-
Field Details
-
boundaryPaths
List of line subset paths comprising the region boundary.
-
-
Constructor Details
-
RegionBSPTree2D
public RegionBSPTree2D()Create a new, empty region. -
RegionBSPTree2D
public RegionBSPTree2D(boolean full) Create a new region. Iffull
is true, then the region will represent the entire 2D space. Otherwise, it will be empty.- Parameters:
full
- whether or not the region should contain the entire 2D space or be empty
-
-
Method Details
-
copy
Return a deep copy of this instance.- Returns:
- a deep copy of this instance.
- See Also:
-
boundaries
Return anIterable
for iterating over the boundaries of the region. Each boundary is oriented such that its plus side points to the outside of the region. The exact ordering of the boundaries is determined by the internal structure of the tree.- Overrides:
boundaries
in classAbstractRegionBSPTree<Vector2D,
RegionBSPTree2D.RegionNode2D> - Returns:
- an
Iterable
for iterating over the boundaries of the region - See Also:
-
boundaryStream
Return a stream containing the boundaries for this instance.- Specified by:
boundaryStream
in interfaceBoundarySource<LineConvexSubset>
- Returns:
- a stream containing the boundaries for this instance
-
getBoundaries
Return a list containing the boundaries of the region. Each boundary is oriented such that its plus side points to the outside of the region. The exact ordering of the boundaries is determined by the internal structure of the tree.- Overrides:
getBoundaries
in classAbstractRegionBSPTree<Vector2D,
RegionBSPTree2D.RegionNode2D> - Returns:
- a list of the boundaries of the region
-
getBoundaryPaths
Get the boundary of the region as a list of connected line subset paths. The line subset are oriented such that their minus (left) side lies on the interior of the region.- Returns:
- line subset paths representing the region boundary
-
add
Add a convex area to this region. The resulting region will be the union of the convex area and the region represented by this instance.- Parameters:
area
- the convex area to add
-
toConvex
Return a list ofConvexArea
s representing the same region as this instance. One convex area is returned for each interior leaf node in the tree.- Returns:
- a list of convex areas representing the same region as this instance
-
toConvexRecursive
private void toConvexRecursive(RegionBSPTree2D.RegionNode2D node, ConvexArea nodeArea, List<? super ConvexArea> result) Recursive method to compute the convex areas of all inside leaf nodes in the subtree rooted at the given node. The computed convex areas are added to the given list.- Parameters:
node
- root of the subtree to compute the convex areas fornodeArea
- the convex area for the current node; this will be split by the node's cut hyperplane to form the convex areas for any child nodesresult
- list containing the results of the computation
-
split
Split this instance with the given hyperplane.- Specified by:
split
in interfaceSplittable<Vector2D,
HyperplaneBoundedRegion<Vector2D>> - Parameters:
splitter
- the hyperplane to split this object with.- Returns:
- result of the split operation
-
project
Project a point onto the boundary of the region. Null is returned if the region contains no boundaries (ie, is eitherfull
orempty
).- Specified by:
project
in interfaceRegion<Vector2D>
- Overrides:
project
in classAbstractRegionBSPTree<Vector2D,
RegionBSPTree2D.RegionNode2D> - Parameters:
pt
- pt to project- Returns:
- projection of the point on the boundary of the region or null if the region does not contain any boundaries
-
toTree
Return the current instance.- Specified by:
toTree
in interfaceBoundarySource2D
- Returns:
- a BSP tree constructed from the boundaries in this instance
- See Also:
-
linecast
Intersect the given line subset against the boundaries in this instance, returning a list of all intersections in order of increasing position along the line. An empty list is returned if no intersections are discovered.- Specified by:
linecast
in interfaceBoundarySource2D
- Specified by:
linecast
in interfaceLinecastable2D
- Parameters:
subset
- line subset to intersect- Returns:
- a list of computed intersections in order of increasing position along the line
-
linecastFirst
Intersect the given line subset against the boundaries in this instance, returning the first intersection found when traveling in the direction of the line subset from its start location.- Specified by:
linecastFirst
in interfaceBoundarySource2D
- Specified by:
linecastFirst
in interfaceLinecastable2D
- Parameters:
subset
- line subset to intersect- Returns:
- the first intersection found or null if no intersection is found
-
computeBoundaryPaths
Compute the line subset paths comprising the region boundary.- Returns:
- the line subset paths comprising the region boundary
-
computeRegionSizeProperties
Compute the size-related properties of the region.- Specified by:
computeRegionSizeProperties
in classAbstractRegionBSPTree<Vector2D,
RegionBSPTree2D.RegionNode2D> - Returns:
- object containing size properties for the region
-
invalidate
protected void invalidate()Invalidate any previously computed properties that rely on the internal structure of the tree. This method must be called any time the tree's internal structure changes in order to force cacheable tree and node properties to be recomputed the next time they are requested.This method increments the tree's
AbstractBSPTree.version
property.- Overrides:
invalidate
in classAbstractRegionBSPTree<Vector2D,
RegionBSPTree2D.RegionNode2D> - See Also:
-
createNode
Create a new node for this tree.- Specified by:
createNode
in classAbstractBSPTree<Vector2D,
RegionBSPTree2D.RegionNode2D> - Returns:
- a new node for this tree
-
full
Return a newRegionBSPTree2D
instance containing the entire space.- Returns:
- a new
RegionBSPTree2D
instance containing the entire space
-
empty
Return a new, emptyRegionBSPTree2D
instance.- Returns:
- a new, empty
RegionBSPTree2D
instance
-
from
Construct a new tree from the given boundaries. If no boundaries are present, the returned tree is empty.- Parameters:
boundaries
- boundaries to construct the tree from- Returns:
- a new tree instance constructed from the given boundaries
- See Also:
-
from
Construct a new tree from the given boundaries. Iffull
is true, then the initial tree before boundary insertion contains the entire space. Otherwise, it is empty.- Parameters:
boundaries
- boundaries to construct the tree fromfull
- if true, the initial tree will contain the entire space- Returns:
- a new tree instance constructed from the given boundaries
-
partitionedRegionBuilder
Create a newRegionBSPTree2D.PartitionedRegionBuilder2D
instance which can be used to build balanced BSP trees from region boundaries.- Returns:
- a new
RegionBSPTree2D.PartitionedRegionBuilder2D
instance
-