Class RegionBSPTree3D
- java.lang.Object
-
- org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree<P,N>
-
- org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree<Vector3D,RegionBSPTree3D.RegionNode3D>
-
- org.apache.commons.geometry.euclidean.threed.RegionBSPTree3D
-
- All Implemented Interfaces:
BoundarySource<PlaneConvexSubset>
,BSPSubtree<Vector3D,RegionBSPTree3D.RegionNode3D>
,BSPTree<Vector3D,RegionBSPTree3D.RegionNode3D>
,HyperplaneBoundedRegion<Vector3D>
,Splittable<Vector3D,HyperplaneBoundedRegion<Vector3D>>
,Region<Vector3D>
,Sized
,BoundarySource3D
,Linecastable3D
public final class RegionBSPTree3D extends AbstractRegionBSPTree<Vector3D,RegionBSPTree3D.RegionNode3D> implements BoundarySource3D
Binary space partitioning (BSP) tree representing a region in three dimensional Euclidean space.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
RegionBSPTree3D.BoundaryProjector3D
Class used to project points onto the 3D region boundary.private static class
RegionBSPTree3D.LinecastVisitor
BSP tree visitor that performs a linecast operation against the boundaries of the visited tree.static class
RegionBSPTree3D.PartitionedRegionBuilder3D
Class used to build regions in Euclidean 3D space by inserting boundaries into a BSP tree containing "partitions", i.e.static class
RegionBSPTree3D.RegionNode3D
BSP tree node for three dimensional Euclidean space.private static class
RegionBSPTree3D.RegionSizePropertiesVisitor
Visitor for computing geometric properties for 3D BSP tree instances.-
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>>
-
-
Constructor Summary
Constructors Constructor Description RegionBSPTree3D()
Create a new, empty region.RegionBSPTree3D(boolean full)
Create a new region.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description java.lang.Iterable<PlaneConvexSubset>
boundaries()
Return anIterable
for iterating over the boundaries of the region.java.util.stream.Stream<PlaneConvexSubset>
boundaryStream()
Return a stream containing the boundaries for this instance.protected AbstractRegionBSPTree.RegionSizeProperties<Vector3D>
computeRegionSizeProperties()
Compute the size-related properties of the region.RegionBSPTree3D
copy()
Return a deep copy of this instance.protected RegionBSPTree3D.RegionNode3D
createNode()
Create a new node for this tree.static RegionBSPTree3D
empty()
Return a new, empty instance.static RegionBSPTree3D
from(java.lang.Iterable<? extends PlaneConvexSubset> boundaries)
Construct a new tree from the given boundaries.static RegionBSPTree3D
from(java.lang.Iterable<? extends PlaneConvexSubset> boundaries, boolean full)
Construct a new tree from the given boundaries.static RegionBSPTree3D
full()
Return a new instance containing all of 3D space.java.util.List<PlaneConvexSubset>
getBoundaries()
Return a list containing the boundaries of the region.java.util.List<LinecastPoint3D>
linecast(LineConvexSubset3D subset)
Intersect the given line convex subset against the boundaries in this instance, returning a list of all intersections in order of increasing distance along the line.LinecastPoint3D
linecastFirst(LineConvexSubset3D subset)
Intersect the given line convex subset against the boundaries in this instance, returning the first intersection found when traveling in the direction of the line subset from its start point.static RegionBSPTree3D.PartitionedRegionBuilder3D
partitionedRegionBuilder()
Create a newRegionBSPTree3D.PartitionedRegionBuilder3D
instance which can be used to build balanced BSP trees from region boundaries.Vector3D
project(Vector3D pt)
Project a point onto the boundary of the region.Split<RegionBSPTree3D>
split(Hyperplane<Vector3D> splitter)
Split this instance with the given hyperplane.java.util.List<ConvexVolume>
toConvex()
Return a list ofConvexVolume
s representing the same region as this instance.private void
toConvexRecursive(RegionBSPTree3D.RegionNode3D node, ConvexVolume nodeVolume, java.util.List<? super ConvexVolume> result)
Recursive method to compute the convex volumes of all inside leaf nodes in the subtree rooted at the given node.RegionBSPTree3D
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, invalidate, 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.threed.BoundarySource3D
getBounds, toList, toTriangleMesh, triangleStream
-
Methods inherited from interface org.apache.commons.geometry.euclidean.threed.line.Linecastable3D
linecast, linecastFirst
-
Methods inherited from interface org.apache.commons.geometry.core.Sized
isFinite, isInfinite
-
-
-
-
Constructor Detail
-
RegionBSPTree3D
public RegionBSPTree3D()
Create a new, empty region.
-
RegionBSPTree3D
public RegionBSPTree3D(boolean full)
Create a new region. Iffull
is true, then the region will represent the entire 3D space. Otherwise, it will be empty.- Parameters:
full
- whether or not the region should contain the entire 3D space or be empty
-
-
Method Detail
-
copy
public RegionBSPTree3D copy()
Return a deep copy of this instance.- Returns:
- a deep copy of this instance.
- See Also:
AbstractBSPTree.copy(org.apache.commons.geometry.core.partitioning.bsp.BSPTree)
-
boundaries
public java.lang.Iterable<PlaneConvexSubset> 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<Vector3D,RegionBSPTree3D.RegionNode3D>
- Returns:
- an
Iterable
for iterating over the boundaries of the region - See Also:
AbstractRegionBSPTree.getBoundaries()
-
boundaryStream
public java.util.stream.Stream<PlaneConvexSubset> boundaryStream()
Return a stream containing the boundaries for this instance.- Specified by:
boundaryStream
in interfaceBoundarySource<PlaneConvexSubset>
- Returns:
- a stream containing the boundaries for this instance
-
getBoundaries
public java.util.List<PlaneConvexSubset> 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<Vector3D,RegionBSPTree3D.RegionNode3D>
- Returns:
- a list of the boundaries of the region
-
toConvex
public java.util.List<ConvexVolume> toConvex()
Return a list ofConvexVolume
s representing the same region as this instance. One convex volume is returned for each interior leaf node in the tree.- Returns:
- a list of convex volumes representing the same region as this instance
-
toConvexRecursive
private void toConvexRecursive(RegionBSPTree3D.RegionNode3D node, ConvexVolume nodeVolume, java.util.List<? super ConvexVolume> result)
Recursive method to compute the convex volumes of all inside leaf nodes in the subtree rooted at the given node. The computed convex volumes are added to the given list.- Parameters:
node
- root of the subtree to compute the convex volumes fornodeVolume
- the convex volume for the current node; this will be split by the node's cut hyperplane to form the convex volumes for any child nodesresult
- list containing the results of the computation
-
split
public Split<RegionBSPTree3D> split(Hyperplane<Vector3D> splitter)
Split this instance with the given hyperplane.- Specified by:
split
in interfaceSplittable<Vector3D,HyperplaneBoundedRegion<Vector3D>>
- Parameters:
splitter
- the hyperplane to split this object with.- Returns:
- result of the split operation
-
project
public Vector3D project(Vector3D pt)
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<Vector3D>
- Overrides:
project
in classAbstractRegionBSPTree<Vector3D,RegionBSPTree3D.RegionNode3D>
- 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
public RegionBSPTree3D toTree()
Return the current instance.- Specified by:
toTree
in interfaceBoundarySource3D
- Returns:
- a BSP tree constructed from the boundaries in this instance
- See Also:
partitionedRegionBuilder()
-
linecast
public java.util.List<LinecastPoint3D> linecast(LineConvexSubset3D subset)
Intersect the given line convex subset against the boundaries in this instance, returning a list of all intersections in order of increasing distance along the line. An empty list is returned if no intersections are discovered.- Specified by:
linecast
in interfaceBoundarySource3D
- Specified by:
linecast
in interfaceLinecastable3D
- Parameters:
subset
- line subset to intersect- Returns:
- a list of computed intersections in order of increasing distance along the line
-
linecastFirst
public LinecastPoint3D linecastFirst(LineConvexSubset3D subset)
Intersect the given line convex subset against the boundaries in this instance, returning the first intersection found when traveling in the direction of the line subset from its start point.- Specified by:
linecastFirst
in interfaceBoundarySource3D
- Specified by:
linecastFirst
in interfaceLinecastable3D
- Parameters:
subset
- line subset to intersect- Returns:
- the first intersection found or null if no intersection is found
-
computeRegionSizeProperties
protected AbstractRegionBSPTree.RegionSizeProperties<Vector3D> computeRegionSizeProperties()
Compute the size-related properties of the region.- Specified by:
computeRegionSizeProperties
in classAbstractRegionBSPTree<Vector3D,RegionBSPTree3D.RegionNode3D>
- Returns:
- object containing size properties for the region
-
createNode
protected RegionBSPTree3D.RegionNode3D createNode()
Create a new node for this tree.- Specified by:
createNode
in classAbstractBSPTree<Vector3D,RegionBSPTree3D.RegionNode3D>
- Returns:
- a new node for this tree
-
full
public static RegionBSPTree3D full()
Return a new instance containing all of 3D space.- Returns:
- a new instance containing all of 3D space.
-
empty
public static RegionBSPTree3D empty()
Return a new, empty instance. The represented region is completely empty.- Returns:
- a new, empty instance.
-
from
public static RegionBSPTree3D from(java.lang.Iterable<? extends PlaneConvexSubset> boundaries)
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(Iterable, boolean)
-
from
public static RegionBSPTree3D from(java.lang.Iterable<? extends PlaneConvexSubset> boundaries, boolean full)
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
public static RegionBSPTree3D.PartitionedRegionBuilder3D partitionedRegionBuilder()
Create a newRegionBSPTree3D.PartitionedRegionBuilder3D
instance which can be used to build balanced BSP trees from region boundaries.- Returns:
- a new
RegionBSPTree3D.PartitionedRegionBuilder3D
instance
-
-