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 Classes

Modifier and Type	Class	Description
static final class	RegionBSPTree2D.PartitionedRegionBuilder2D	Class used to build regions in Euclidean 2D space by inserting boundaries into a BSP tree containing "partitions", i.e. structural cuts where both sides of the cut have the same region location.
static final class	RegionBSPTree2D.RegionNode2D	BSP tree node for two dimensional Euclidean space.

Nested classes/interfaces inherited from class AbstractRegionBSPTree

AbstractRegionBSPTree.AbstractRegionNode<P,N>, AbstractRegionBSPTree.BoundaryProjector<P,N>, AbstractRegionBSPTree.RegionSizeProperties<P>

Nested classes/interfaces inherited from class AbstractBSPTree

AbstractBSPTree.AbstractNode<P,N>, AbstractBSPTree.SubtreeInitializer<N>

Nested classes/interfaces inherited from interface BSPTree

BSPTree.FindNodeCutRule, BSPTree.Node<P,N>

Constructor Summary

Constructors

Constructor	Description
RegionBSPTree2D()	Create a new, empty region.
RegionBSPTree2D(boolean full)	Create a new region.

Method Summary

Modifier and Type	Method	Description
void	add(ConvexArea area)	Add a convex area to this region.
Iterable<LineConvexSubset>	boundaries()	Return an Iterable for iterating over the boundaries of the region.
Stream<LineConvexSubset>	boundaryStream()	Return a stream containing the boundaries for this instance.
protected AbstractRegionBSPTree.RegionSizeProperties<Vector2D>	computeRegionSizeProperties()	Compute the size-related properties of the region.
RegionBSPTree2D	copy()	Return a deep copy of this instance.
protected RegionBSPTree2D.RegionNode2D	createNode()	Create a new node for this tree.
static RegionBSPTree2D	empty()	Return a new, empty RegionBSPTree2D 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 new RegionBSPTree2D instance containing the entire space.
List<LineConvexSubset>	getBoundaries()	Return a list containing the boundaries of the region.
List<LinePath>	getBoundaryPaths()	Get the boundary of the region as a list of connected line subset paths.
protected void	invalidate()	Invalidate any previously computed properties that rely on the internal structure of the tree.
List<LinecastPoint2D>	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.
LinecastPoint2D	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.
static RegionBSPTree2D.PartitionedRegionBuilder2D	partitionedRegionBuilder()	Create a new RegionBSPTree2D.PartitionedRegionBuilder2D instance which can be used to build balanced BSP trees from region boundaries.
Vector2D	project(Vector2D pt)	Project a point onto the boundary of the region.
Split<RegionBSPTree2D>	split(Hyperplane<Vector2D> splitter)	Split this instance with the given hyperplane.
List<ConvexArea>	toConvex()	Return a list of ConvexAreas representing the same region as this instance.
RegionBSPTree2D	toTree()	Return the current instance.

Methods inherited from class 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 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 Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface BoundarySource2D

getBounds, toList

Methods inherited from interface BSPTree

findNode

Methods inherited from interface Linecastable2D

linecast, linecastFirst

Methods inherited from interface Region

contains

Methods inherited from interface Sized

isFinite, isInfinite

Constructor Details

RegionBSPTree2D

public RegionBSPTree2D()

Create a new, empty region.

RegionBSPTree2D

public RegionBSPTree2D(boolean full)

Create a new region. If full 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

public RegionBSPTree2D 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 Iterable<LineConvexSubset> 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<Vector2D, RegionBSPTree2D.RegionNode2D>

Returns:

an Iterable for iterating over the boundaries of the region

See Also:

• AbstractRegionBSPTree.getBoundaries()

boundaryStream

public Stream<LineConvexSubset> boundaryStream()

Return a stream containing the boundaries for this instance.

Specified by:

boundaryStream in interface BoundarySource<LineConvexSubset>

Returns:

a stream containing the boundaries for this instance

getBoundaries

public List<LineConvexSubset> 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<Vector2D, RegionBSPTree2D.RegionNode2D>

Returns:

a list of the boundaries of the region

getBoundaryPaths

public List<LinePath> 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

public void add(ConvexArea area)

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

public List<ConvexArea> toConvex()

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

split

public Split<RegionBSPTree2D> split(Hyperplane<Vector2D> splitter)

Split this instance with the given hyperplane.

Specified by:

split in interface Splittable<Vector2D, HyperplaneBoundedRegion<Vector2D>>

Parameters:

splitter - the hyperplane to split this object with.

Returns:

result of the split operation

project

public Vector2D project(Vector2D 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<Vector2D>

Overrides:

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

public RegionBSPTree2D toTree()

Return the current instance.

Specified by:

toTree in interface BoundarySource2D

Returns:

a BSP tree constructed from the boundaries in this instance

See Also:

• partitionedRegionBuilder()

linecast

public List<LinecastPoint2D> 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. An empty list is returned if no intersections are discovered.

Specified by:

linecast in interface BoundarySource2D

Specified by:

linecast in interface Linecastable2D

Parameters:

subset - line subset to intersect

Returns:

a list of computed intersections in order of increasing position along the line

linecastFirst

public LinecastPoint2D 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.

Specified by:

linecastFirst in interface BoundarySource2D

Specified by:

linecastFirst in interface Linecastable2D

Parameters:

subset - line subset to intersect

Returns:

the first intersection found or null if no intersection is found

computeRegionSizeProperties

protected AbstractRegionBSPTree.RegionSizeProperties<Vector2D> computeRegionSizeProperties()

Compute the size-related properties of the region.

Specified by:

computeRegionSizeProperties in class AbstractRegionBSPTree<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 class AbstractRegionBSPTree<Vector2D, RegionBSPTree2D.RegionNode2D>

See Also:

• AbstractBSPTree.getVersion()

createNode

protected RegionBSPTree2D.RegionNode2D createNode()

Create a new node for this tree.

Specified by:

createNode in class AbstractBSPTree<Vector2D, RegionBSPTree2D.RegionNode2D>

Returns:

a new node for this tree

full

public static RegionBSPTree2D full()

Return a new RegionBSPTree2D instance containing the entire space.

Returns:

a new RegionBSPTree2D instance containing the entire space

empty

public static RegionBSPTree2D empty()

Return a new, empty RegionBSPTree2D instance.

Returns:

a new, empty RegionBSPTree2D instance

from

public static RegionBSPTree2D from(Iterable<? extends LineConvexSubset> 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 RegionBSPTree2D from(Iterable<? extends LineConvexSubset> 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 RegionBSPTree2D.PartitionedRegionBuilder2D partitionedRegionBuilder()

Create a new RegionBSPTree2D.PartitionedRegionBuilder2D instance which can be used to build balanced BSP trees from region boundaries.

Returns:

a new RegionBSPTree2D.PartitionedRegionBuilder2D instance