Class AbstractRegionBSPTree<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>>
- java.lang.Object
-
- org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree<P,N>
-
- org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree<P,N>
-
- Type Parameters:
P
- Point implementation typeN
- BSP tree node implementation type
- All Implemented Interfaces:
BSPSubtree<P,N>
,BSPTree<P,N>
,HyperplaneBoundedRegion<P>
,Splittable<P,HyperplaneBoundedRegion<P>>
,Region<P>
,Sized
- Direct Known Subclasses:
RegionBSPTree1D
,RegionBSPTree1S
,RegionBSPTree2D
,RegionBSPTree2S
,RegionBSPTree3D
public abstract class AbstractRegionBSPTree<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>> extends AbstractBSPTree<P,N> implements HyperplaneBoundedRegion<P>
AbstractBSPTree
specialized for representing regions of space. For example, this class can be used to represent polygons in Euclidean 2D space and polyhedrons in Euclidean 3D space.This class is not thread safe.
- See Also:
HyperplaneBoundedRegion
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
AbstractRegionBSPTree.AbstractRegionNode<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>>
BSPTree.Node
implementation for use withAbstractRegionBSPTree
s.protected static class
AbstractRegionBSPTree.BoundaryProjector<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>>
Class used to compute the point on the region's boundary that is closest to a target point.private static class
AbstractRegionBSPTree.Condenser<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>>
Internal class used to perform tree condense operations.private static class
AbstractRegionBSPTree.DifferenceOperator<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>>
Class for performing boolean difference operations on region trees.private static class
AbstractRegionBSPTree.IntersectionOperator<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>>
Class for performing boolean intersection operations on region trees.private static class
AbstractRegionBSPTree.RegionBoundaryIterator<P extends Point<P>,C extends HyperplaneConvexSubset<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>>
Class that iterates over the boundary hyperplane convex subsets from a set of region nodes.private static class
AbstractRegionBSPTree.RegionMergeOperator<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>>
Class containing the basic algorithm for merging region BSP trees.protected static class
AbstractRegionBSPTree.RegionSizeProperties<P extends Point<P>>
Class containing the primary size-related properties of a region.private static class
AbstractRegionBSPTree.UnionOperator<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>>
Class for performing boolean union operations on region trees.private static class
AbstractRegionBSPTree.XorOperator<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>>
Class for performing boolean symmetric difference (xor) operations on region trees.-
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
Fields Modifier and Type Field Description private double
boundarySize
The region boundary size; this is computed when requested and then cached.private static RegionCutRule
DEFAULT_REGION_CUT_RULE
The defaultRegionCutRule
.private AbstractRegionBSPTree.RegionSizeProperties<P>
regionSizeProperties
The current size properties for the region.private static double
UNKNOWN_SIZE
Value used to indicate an unknown size.
-
Constructor Summary
Constructors Modifier Constructor Description protected
AbstractRegionBSPTree(boolean full)
Construct a new region will the given boolean determining whether or not the region will be full (including the entire space) or empty (excluding the entire space).
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description java.lang.Iterable<? extends HyperplaneConvexSubset<P>>
boundaries()
Return anIterable
for iterating over the boundaries of the region.RegionLocation
classify(P point)
Classify the given point with respect to the region.private RegionLocation
classifyRecursive(AbstractRegionBSPTree.AbstractRegionNode<P,N> node, P point)
Recursively classify a point with respect to the region.void
complement()
Change this region into its complement.void
complement(AbstractRegionBSPTree<P,N> tree)
Set this instance to be the complement of the given tree.private void
complementRecursive(AbstractRegionBSPTree.AbstractRegionNode<P,N> node)
Recursively switch all inside nodes to outside nodes and vice versa.protected abstract AbstractRegionBSPTree.RegionSizeProperties<P>
computeRegionSizeProperties()
Compute the size-related properties of the region.boolean
condense()
Condense this tree by removing redundant subtrees, returning true if the tree structure was modified.protected void
copyNodeProperties(N src, N dst)
Copy non-structural node properties fromsrc
todst
.protected <C extends HyperplaneConvexSubset<P>>
java.lang.Iterable<C>createBoundaryIterable(java.util.function.Function<HyperplaneConvexSubset<P>,C> typeConverter)
Internal method for creating the iterable instances used to iterate the region boundaries.protected <C extends HyperplaneConvexSubset<P>>
java.util.List<C>createBoundaryList(java.util.function.Function<HyperplaneConvexSubset<P>,C> typeConverter)
Internal method for creating a list of the region boundaries.void
difference(AbstractRegionBSPTree<P,N> other)
Compute the difference of this instance and the given region, storing the result back in this instance.void
difference(AbstractRegionBSPTree<P,N> a, AbstractRegionBSPTree<P,N> b)
Compute the difference of the two regions passed as arguments and store the result in this instance.java.util.List<? extends HyperplaneConvexSubset<P>>
getBoundaries()
Return a list containing the boundaries of the region.double
getBoundarySize()
Get the size of the boundary of the region.P
getCentroid()
Get the centroid, or geometric center, of the region or null if no centroid exists or one exists but is not unique.protected AbstractRegionBSPTree.RegionSizeProperties<P>
getRegionSizeProperties()
Get the size-related properties for the region.double
getSize()
Get the size of the instance.protected AbstractBSPTree.SubtreeInitializer<N>
getSubtreeInitializer(RegionCutRule cutRule)
Get the subtree initializer to use for the given region cut rule.private boolean
hasNodeWithLocationRecursive(AbstractRegionBSPTree.AbstractRegionNode<P,N> node, RegionLocation location)
Return true if any node in the subtree rooted at the given node has a location with the given value.void
insert(java.lang.Iterable<? extends HyperplaneConvexSubset<P>> convexSubs)
Insert a set of hyperplane convex subsets into the tree, using the defaultRegionCutRule
ofMINUS_INSIDE
.void
insert(java.lang.Iterable<? extends HyperplaneConvexSubset<P>> convexSubs, RegionCutRule cutRule)
Insert a set of hyperplane convex subsets into the tree.void
insert(BoundarySource<? extends HyperplaneConvexSubset<P>> boundarySrc)
Insert all hyperplane convex subsets from the given source into the tree, using the defaultRegionCutRule
ofMINUS_INSIDE
.void
insert(BoundarySource<? extends HyperplaneConvexSubset<P>> boundarySrc, RegionCutRule cutRule)
Insert all hyperplane convex subsets from the given source into the tree.void
insert(HyperplaneConvexSubset<P> convexSub)
Insert a hyperplane convex subset into the tree, using the defaultRegionCutRule
ofMINUS_INSIDE
.void
insert(HyperplaneConvexSubset<P> convexSub, RegionCutRule cutRule)
Insert a hyperplane convex subset into the tree.void
insert(HyperplaneSubset<P> sub)
Insert a hyperplane subset into the tree, using the defaultRegionCutRule
ofMINUS_INSIDE
.void
insert(HyperplaneSubset<P> sub, RegionCutRule cutRule)
Insert a hyperplane subset into the tree.void
intersection(AbstractRegionBSPTree<P,N> other)
Compute the intersection of this instance and the given region, storing the result back in this instance.void
intersection(AbstractRegionBSPTree<P,N> a, AbstractRegionBSPTree<P,N> b)
Compute the intersection of the two regions passed as arguments and store the result in this instance.protected void
invalidate()
Invalidate any previously computed properties that rely on the internal structure of the tree.boolean
isEmpty()
Return true if the region is completely empty, ie all points in the space are classified asoutside
.boolean
isFull()
Return true if the region spans the entire space.P
project(P pt)
Project a point onto the boundary of the region.void
setEmpty()
Modify this instance so that is is completely empty.void
setFull()
Modify this instance so that it contains the entire space.protected <T extends AbstractRegionBSPTree<P,N>>
Split<T>split(Hyperplane<P> splitter, T minus, T plus)
Helper method implementing the algorithm for splitting a tree by a hyperplane.void
union(AbstractRegionBSPTree<P,N> other)
Compute the union of this instance and the given region, storing the result back in this instance.void
union(AbstractRegionBSPTree<P,N> a, AbstractRegionBSPTree<P,N> b)
Compute the union of the two regions passed as arguments and store the result in this instance.void
xor(AbstractRegionBSPTree<P,N> other)
Compute the symmetric difference (xor) of this instance and the given region, storing the result back in this instance.void
xor(AbstractRegionBSPTree<P,N> a, AbstractRegionBSPTree<P,N> b)
Compute the symmetric difference (xor) of the two regions passed as arguments and store the result in this instance.-
Methods inherited from class org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree
accept, accept, copy, copyNode, copySubtree, count, createNode, 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.core.Sized
isFinite, isInfinite
-
Methods inherited from interface org.apache.commons.geometry.core.partitioning.Splittable
split
-
-
-
-
Field Detail
-
DEFAULT_REGION_CUT_RULE
private static final RegionCutRule DEFAULT_REGION_CUT_RULE
The defaultRegionCutRule
.
-
UNKNOWN_SIZE
private static final double UNKNOWN_SIZE
Value used to indicate an unknown size.- See Also:
- Constant Field Values
-
boundarySize
private double boundarySize
The region boundary size; this is computed when requested and then cached.
-
regionSizeProperties
private AbstractRegionBSPTree.RegionSizeProperties<P extends Point<P>> regionSizeProperties
The current size properties for the region.
-
-
Constructor Detail
-
AbstractRegionBSPTree
protected AbstractRegionBSPTree(boolean full)
Construct a new region will the given boolean determining whether or not the region will be full (including the entire space) or empty (excluding the entire space).- Parameters:
full
- if true, the region will cover the entire space, otherwise it will be empty
-
-
Method Detail
-
isEmpty
public boolean isEmpty()
Return true if the region is completely empty, ie all points in the space are classified asoutside
.
-
isFull
public boolean isFull()
Return true if the region spans the entire space. In other words, a region is full if no points in the space are classified asoutside
.
-
hasNodeWithLocationRecursive
private boolean hasNodeWithLocationRecursive(AbstractRegionBSPTree.AbstractRegionNode<P,N> node, RegionLocation location)
Return true if any node in the subtree rooted at the given node has a location with the given value.- Parameters:
node
- the node at the root of the subtree to searchlocation
- the location to find- Returns:
- true if any node in the subtree has the given location
-
setFull
public void setFull()
Modify this instance so that it contains the entire space.- See Also:
isFull()
-
setEmpty
public void setEmpty()
Modify this instance so that is is completely empty.- See Also:
isEmpty()
-
getSize
public double getSize()
Get the size of the instance.
-
getBoundarySize
public double getBoundarySize()
Get the size of the boundary of the region. The size is a value in thed-1
dimension space. For example, in Euclidean space, this will be a length in 2D and an area in 3D.- Specified by:
getBoundarySize
in interfaceRegion<P extends Point<P>>
- Returns:
- the size of the boundary of the region
-
insert
public void insert(HyperplaneSubset<P> sub)
Insert a hyperplane subset into the tree, using the defaultRegionCutRule
ofMINUS_INSIDE
.- Parameters:
sub
- the hyperplane subset to insert into the tree
-
insert
public void insert(HyperplaneSubset<P> sub, RegionCutRule cutRule)
Insert a hyperplane subset into the tree.- Parameters:
sub
- the hyperplane subset to insert into the treecutRule
- rule used to determine the region locations of new child nodes
-
insert
public void insert(HyperplaneConvexSubset<P> convexSub)
Insert a hyperplane convex subset into the tree, using the defaultRegionCutRule
ofMINUS_INSIDE
.- Parameters:
convexSub
- the hyperplane convex subset to insert into the tree
-
insert
public void insert(HyperplaneConvexSubset<P> convexSub, RegionCutRule cutRule)
Insert a hyperplane convex subset into the tree.- Parameters:
convexSub
- the hyperplane convex subset to insert into the treecutRule
- rule used to determine the region locations of new child nodes
-
insert
public void insert(java.lang.Iterable<? extends HyperplaneConvexSubset<P>> convexSubs)
Insert a set of hyperplane convex subsets into the tree, using the defaultRegionCutRule
ofMINUS_INSIDE
.- Parameters:
convexSubs
- iterable containing a collection of hyperplane convex subsets to insert into the tree
-
insert
public void insert(java.lang.Iterable<? extends HyperplaneConvexSubset<P>> convexSubs, RegionCutRule cutRule)
Insert a set of hyperplane convex subsets into the tree.- Parameters:
convexSubs
- iterable containing a collection of hyperplane convex subsets to insert into the treecutRule
- rule used to determine the region locations of new child nodes
-
insert
public void insert(BoundarySource<? extends HyperplaneConvexSubset<P>> boundarySrc)
Insert all hyperplane convex subsets from the given source into the tree, using the defaultRegionCutRule
ofMINUS_INSIDE
.- Parameters:
boundarySrc
- source of boundary hyperplane subsets to insert into the tree
-
insert
public void insert(BoundarySource<? extends HyperplaneConvexSubset<P>> boundarySrc, RegionCutRule cutRule)
Insert all hyperplane convex subsets from the given source into the tree.- Parameters:
boundarySrc
- source of boundary hyperplane subsets to insert into the treecutRule
- rule used to determine the region locations of new child nodes
-
getSubtreeInitializer
protected AbstractBSPTree.SubtreeInitializer<N> getSubtreeInitializer(RegionCutRule cutRule)
Get the subtree initializer to use for the given region cut rule.- Parameters:
cutRule
- the cut rule to get an initializer for- Returns:
- the subtree initializer for the given region cut rule
-
boundaries
public java.lang.Iterable<? extends HyperplaneConvexSubset<P>> 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.- Returns:
- an
Iterable
for iterating over the boundaries of the region - See Also:
getBoundaries()
-
createBoundaryIterable
protected <C extends HyperplaneConvexSubset<P>> java.lang.Iterable<C> createBoundaryIterable(java.util.function.Function<HyperplaneConvexSubset<P>,C> typeConverter)
Internal method for creating the iterable instances used to iterate the region boundaries.- Type Parameters:
C
- HyperplaneConvexSubset implementation type- Parameters:
typeConverter
- function to convert the generic hyperplane subset type into the type specific for this tree- Returns:
- an iterable to iterating the region boundaries
-
getBoundaries
public java.util.List<? extends HyperplaneConvexSubset<P>> 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.- Returns:
- a list of the boundaries of the region
-
createBoundaryList
protected <C extends HyperplaneConvexSubset<P>> java.util.List<C> createBoundaryList(java.util.function.Function<HyperplaneConvexSubset<P>,C> typeConverter)
Internal method for creating a list of the region boundaries.- Type Parameters:
C
- HyperplaneConvexSubset implementation type- Parameters:
typeConverter
- function to convert the generic convex subset type into the type specific for this tree- Returns:
- a list of the region boundaries
-
getCentroid
public P getCentroid()
Get the centroid, or geometric center, of the region or null if no centroid exists or one exists but is not unique. A centroid will not exist for empty or infinite regions.The centroid of a geometric object is defined as the mean position of all points in the object, including interior points, vertices, and other points lying on the boundary. If a physical object has a uniform density, then its center of mass is the same as its geometric centroid.
-
split
protected <T extends AbstractRegionBSPTree<P,N>> Split<T> split(Hyperplane<P> splitter, T minus, T plus)
Helper method implementing the algorithm for splitting a tree by a hyperplane. Subclasses should call this method with two instantiated trees of the correct type.- Type Parameters:
T
- Tree implementation type- Parameters:
splitter
- splitting hyperplaneminus
- tree that will contain the minus side of the split resultplus
- tree that will contain the plus side of the split result- Returns:
- result of splitting this tree with the given hyperplane
-
getRegionSizeProperties
protected AbstractRegionBSPTree.RegionSizeProperties<P> getRegionSizeProperties()
Get the size-related properties for the region. The value is computed lazily and cached.- Returns:
- the size-related properties for the region
-
computeRegionSizeProperties
protected abstract AbstractRegionBSPTree.RegionSizeProperties<P> computeRegionSizeProperties()
Compute the size-related properties of the region.- Returns:
- object containing size properties for the region
-
classify
public RegionLocation classify(P point)
Classify the given point with respect to the region.If the point is
NaN
, thenRegionLocation.OUTSIDE
is returned.
-
classifyRecursive
private RegionLocation classifyRecursive(AbstractRegionBSPTree.AbstractRegionNode<P,N> node, P point)
Recursively classify a point with respect to the region.- Parameters:
node
- the node to classify againstpoint
- the point to classify- Returns:
- the classification of the point with respect to the region rooted at the given node
-
complement
public void complement()
Change this region into its complement. All inside nodes become outside nodes and vice versa. The orientations of the node cuts are not modified.
-
complement
public void complement(AbstractRegionBSPTree<P,N> tree)
Set this instance to be the complement of the given tree. The argument is not modified.- Parameters:
tree
- the tree to become the complement of
-
complementRecursive
private void complementRecursive(AbstractRegionBSPTree.AbstractRegionNode<P,N> node)
Recursively switch all inside nodes to outside nodes and vice versa.- Parameters:
node
- the node at the root of the subtree to switch
-
union
public void union(AbstractRegionBSPTree<P,N> other)
Compute the union of this instance and the given region, storing the result back in this instance. The argument is not modified.- Parameters:
other
- the tree to compute the union with
-
union
public void union(AbstractRegionBSPTree<P,N> a, AbstractRegionBSPTree<P,N> b)
Compute the union of the two regions passed as arguments and store the result in this instance. Any nodes currently existing in this instance are removed.- Parameters:
a
- first argument to the union operationb
- second argument to the union operation
-
intersection
public void intersection(AbstractRegionBSPTree<P,N> other)
Compute the intersection of this instance and the given region, storing the result back in this instance. The argument is not modified.- Parameters:
other
- the tree to compute the intersection with
-
intersection
public void intersection(AbstractRegionBSPTree<P,N> a, AbstractRegionBSPTree<P,N> b)
Compute the intersection of the two regions passed as arguments and store the result in this instance. Any nodes currently existing in this instance are removed.- Parameters:
a
- first argument to the intersection operationb
- second argument to the intersection operation
-
difference
public void difference(AbstractRegionBSPTree<P,N> other)
Compute the difference of this instance and the given region, storing the result back in this instance. The argument is not modified.- Parameters:
other
- the tree to compute the difference with
-
difference
public void difference(AbstractRegionBSPTree<P,N> a, AbstractRegionBSPTree<P,N> b)
Compute the difference of the two regions passed as arguments and store the result in this instance. Any nodes currently existing in this instance are removed.- Parameters:
a
- first argument to the difference operationb
- second argument to the difference operation
-
xor
public void xor(AbstractRegionBSPTree<P,N> other)
Compute the symmetric difference (xor) of this instance and the given region, storing the result back in this instance. The argument is not modified.- Parameters:
other
- the tree to compute the symmetric difference with
-
xor
public void xor(AbstractRegionBSPTree<P,N> a, AbstractRegionBSPTree<P,N> b)
Compute the symmetric difference (xor) of the two regions passed as arguments and store the result in this instance. Any nodes currently existing in this instance are removed.- Parameters:
a
- first argument to the symmetric difference operationb
- second argument to the symmetric difference operation
-
condense
public boolean condense()
Condense this tree by removing redundant subtrees, returning true if the tree structure was modified.This operation can be used to reduce the total number of nodes in the tree after performing node manipulations. For example, if two sibling leaf nodes both represent the same
RegionLocation
, then there is no reason from the perspective of the geometric region to retain both nodes. They are therefore both merged into their parent node. This method performs this simplification process.- Returns:
- true if the tree structure was modified, otherwise false
-
copyNodeProperties
protected void copyNodeProperties(N src, N dst)
Copy non-structural node properties fromsrc
todst
. Non-structural properties are those properties not directly related to the structure of the BSP tree, i.e. properties other than parent/child connections and cuts. Subclasses should override this method to copy additional properties stored on nodes.- Specified by:
copyNodeProperties
in classAbstractBSPTree<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>>
- Parameters:
src
- source nodedst
- destination node
-
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 classAbstractBSPTree<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>>
- See Also:
AbstractBSPTree.getVersion()
-
-