P
- Point implementation typeN
- BSP tree node implementation typepublic abstract class AbstractRegionBSPTree<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>> extends AbstractBSPTree<P,N> implements HyperplaneBoundedRegion<P>
BSPTree
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.
HyperplaneBoundedRegion
Modifier and Type | Class and Description |
---|---|
static class |
AbstractRegionBSPTree.AbstractRegionNode<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>>
BSPTree.Node implementation for use with AbstractRegionBSPTree 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.
|
protected static class |
AbstractRegionBSPTree.RegionSizeProperties<P extends Point<P>>
Class containing the primary size-related properties of a region.
|
AbstractBSPTree.AbstractNode<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>, AbstractBSPTree.SubtreeInitializer<N extends AbstractBSPTree.AbstractNode<?,?>>
BSPTree.FindNodeCutRule, BSPTree.Node<P extends Point<P>,N extends BSPTree.Node<P,N>>
Modifier | Constructor and 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).
|
Modifier and Type | Method and Description |
---|---|
Iterable<? extends HyperplaneConvexSubset<P>> |
boundaries()
Return an
Iterable for iterating over the boundaries of the region. |
RegionLocation |
classify(P point)
Classify the given 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.
|
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 from
src to dst . |
protected <C extends HyperplaneConvexSubset<P>> |
createBoundaryIterable(Function<HyperplaneConvexSubset<P>,C> typeConverter)
Internal method for creating the iterable instances used to iterate the region boundaries.
|
protected <C extends HyperplaneConvexSubset<P>> |
createBoundaryList(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.
|
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.
|
void |
insert(BoundarySource<? extends HyperplaneConvexSubset<P>> boundarySrc)
Insert all hyperplane convex subsets from the given source into the tree, using the default
RegionCutRule of MINUS_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 default
RegionCutRule of
MINUS_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 default
RegionCutRule of
MINUS_INSIDE . |
void |
insert(HyperplaneSubset<P> sub,
RegionCutRule cutRule)
Insert a hyperplane subset into the tree.
|
void |
insert(Iterable<? extends HyperplaneConvexSubset<P>> convexSubs)
Insert a set of hyperplane convex subsets into the tree, using the default
RegionCutRule of
MINUS_INSIDE . |
void |
insert(Iterable<? extends HyperplaneConvexSubset<P>> convexSubs,
RegionCutRule cutRule)
Insert a set of hyperplane convex subsets 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 as
outside . |
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(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.
|
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
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
isFinite, isInfinite
split
protected AbstractRegionBSPTree(boolean full)
full
- if true, the region will cover the entire space, otherwise it will
be emptypublic boolean isEmpty()
outside
.public boolean isFull()
outside
.public void setFull()
isFull()
public void setEmpty()
isEmpty()
public double getSize()
public double getBoundarySize()
d-1
dimension space. For example, in Euclidean space,
this will be a length in 2D and an area in 3D.getBoundarySize
in interface Region<P extends Point<P>>
public void insert(HyperplaneSubset<P> sub)
RegionCutRule
of
MINUS_INSIDE
.sub
- the hyperplane subset to insert into the treepublic void insert(HyperplaneSubset<P> sub, RegionCutRule cutRule)
sub
- the hyperplane subset to insert into the treecutRule
- rule used to determine the region locations of new child nodespublic void insert(HyperplaneConvexSubset<P> convexSub)
RegionCutRule
of
MINUS_INSIDE
.convexSub
- the hyperplane convex subset to insert into the treepublic void insert(HyperplaneConvexSubset<P> convexSub, RegionCutRule cutRule)
convexSub
- the hyperplane convex subset to insert into the treecutRule
- rule used to determine the region locations of new child nodespublic void insert(Iterable<? extends HyperplaneConvexSubset<P>> convexSubs)
RegionCutRule
of
MINUS_INSIDE
.convexSubs
- iterable containing a collection of hyperplane convex subsets
to insert into the treepublic void insert(Iterable<? extends HyperplaneConvexSubset<P>> convexSubs, RegionCutRule cutRule)
convexSubs
- iterable containing a collection of hyperplane convex subsets
to insert into the treecutRule
- rule used to determine the region locations of new child nodespublic void insert(BoundarySource<? extends HyperplaneConvexSubset<P>> boundarySrc)
RegionCutRule
of MINUS_INSIDE
.boundarySrc
- source of boundary hyperplane subsets to insert
into the treepublic void insert(BoundarySource<? extends HyperplaneConvexSubset<P>> boundarySrc, RegionCutRule cutRule)
boundarySrc
- source of boundary hyperplane subsets to insert
into the treecutRule
- rule used to determine the region locations of new child nodesprotected AbstractBSPTree.SubtreeInitializer<N> getSubtreeInitializer(RegionCutRule cutRule)
cutRule
- the cut rule to get an initializer forpublic Iterable<? extends HyperplaneConvexSubset<P>> boundaries()
Iterable
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.Iterable
for iterating over the boundaries of the regiongetBoundaries()
protected <C extends HyperplaneConvexSubset<P>> Iterable<C> createBoundaryIterable(Function<HyperplaneConvexSubset<P>,C> typeConverter)
C
- HyperplaneConvexSubset implementation typetypeConverter
- function to convert the generic hyperplane subset type into
the type specific for this treepublic List<? extends HyperplaneConvexSubset<P>> getBoundaries()
protected <C extends HyperplaneConvexSubset<P>> List<C> createBoundaryList(Function<HyperplaneConvexSubset<P>,C> typeConverter)
C
- HyperplaneConvexSubset implementation typetypeConverter
- function to convert the generic convex subset type into
the type specific for this treepublic P getCentroid()
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.
protected <T extends AbstractRegionBSPTree<P,N>> Split<T> split(Hyperplane<P> splitter, T minus, T plus)
T
- Tree implementation typesplitter
- splitting hyperplaneminus
- tree that will contain the minus side of the split resultplus
- tree that will contain the plus side of the split resultprotected AbstractRegionBSPTree.RegionSizeProperties<P> getRegionSizeProperties()
protected abstract AbstractRegionBSPTree.RegionSizeProperties<P> computeRegionSizeProperties()
public RegionLocation classify(P point)
If the point is NaN
, then
RegionLocation.OUTSIDE
is returned.
public void complement()
public void complement(AbstractRegionBSPTree<P,N> tree)
tree
- the tree to become the complement ofpublic void union(AbstractRegionBSPTree<P,N> other)
other
- the tree to compute the union withpublic void union(AbstractRegionBSPTree<P,N> a, AbstractRegionBSPTree<P,N> b)
a
- first argument to the union operationb
- second argument to the union operationpublic void intersection(AbstractRegionBSPTree<P,N> other)
other
- the tree to compute the intersection withpublic void intersection(AbstractRegionBSPTree<P,N> a, AbstractRegionBSPTree<P,N> b)
a
- first argument to the intersection operationb
- second argument to the intersection operationpublic void difference(AbstractRegionBSPTree<P,N> other)
other
- the tree to compute the difference withpublic void difference(AbstractRegionBSPTree<P,N> a, AbstractRegionBSPTree<P,N> b)
a
- first argument to the difference operationb
- second argument to the difference operationpublic void xor(AbstractRegionBSPTree<P,N> other)
other
- the tree to compute the symmetric difference withpublic void xor(AbstractRegionBSPTree<P,N> a, AbstractRegionBSPTree<P,N> b)
a
- first argument to the symmetric difference operationb
- second argument to the symmetric difference operationpublic boolean condense()
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.
protected void copyNodeProperties(N src, N dst)
src
to dst
.
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.copyNodeProperties
in class AbstractBSPTree<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>>
src
- source nodedst
- destination nodeprotected void invalidate()
This method increments the tree's AbstractBSPTree.version
property.
invalidate
in class AbstractBSPTree<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>>
AbstractBSPTree.getVersion()
Copyright © 2016–2021 The Apache Software Foundation. All rights reserved.