Package org.apache.commons.geometry.euclidean.threed

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

Modifier and Type	Method	Description
java.lang.Iterable<PlaneConvexSubset>	boundaries()	Return an Iterable 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 new RegionBSPTree3D.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 of ConvexVolumes 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.core.partitioning.bsp.BSPTree

findNode

Methods inherited from interface org.apache.commons.geometry.euclidean.threed.line.Linecastable3D

linecast, linecastFirst

Methods inherited from interface org.apache.commons.geometry.core.Region

contains

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. If full 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 an 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.

Overrides:

boundaries in class AbstractRegionBSPTree<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 interface BoundarySource<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 class AbstractRegionBSPTree<Vector3D,RegionBSPTree3D.RegionNode3D>

Returns:

a list of the boundaries of the region

toConvex

public java.util.List<ConvexVolume> toConvex()

Return a list of ConvexVolumes 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 for

nodeVolume - 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 nodes

result - 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 interface Splittable<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 either full or empty).

Specified by:

project in interface Region<Vector3D>

Overrides:

project in class AbstractRegionBSPTree<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 interface BoundarySource3D

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 interface BoundarySource3D

Specified by:

linecast in interface Linecastable3D

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 interface BoundarySource3D

Specified by:

linecastFirst in interface Linecastable3D

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 class AbstractRegionBSPTree<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 class AbstractBSPTree<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. If full is true, then the initial tree before boundary insertion contains the entire space. Otherwise, it is empty.

Parameters:

boundaries - boundaries to construct the tree from

full - 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 new RegionBSPTree3D.PartitionedRegionBuilder3D instance which can be used to build balanced BSP trees from region boundaries.

Returns:

a new RegionBSPTree3D.PartitionedRegionBuilder3D instance