org.apache.commons.geometry.euclidean.twod

Class RegionBSPTree2D

java.lang.Object

org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree<P,N>

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 and Description
static class	RegionBSPTree2D.PartitionedRegionBuilder2D Class used to build regions in Euclidean 2D space by inserting boundaries into a BSP tree containing "partitions", i.e.
static class	RegionBSPTree2D.RegionNode2D BSP tree node for two dimensional Euclidean space.

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 and Description
RegionBSPTree2D() Create a new, empty region.
RegionBSPTree2D(boolean full) Create a new region.

Method Summary

Modifier and Type	Method and Description
void	add(ConvexArea area) Add a convex area to this region.
Iterable<LineConvexSubset>	boundaries()
Stream<LineConvexSubset>	boundaryStream()
protected AbstractRegionBSPTree.RegionSizeProperties<Vector2D>	computeRegionSizeProperties()
RegionBSPTree2D	copy() Return a deep copy of this instance.
protected RegionBSPTree2D.RegionNode2D	createNode()
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()
List<LinePath>	getBoundaryPaths() Get the boundary of the region as a list of connected line subset paths.
protected void	invalidate()
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)
Split<RegionBSPTree2D>	split(Hyperplane<Vector2D> splitter)
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 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, 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.twod.BoundarySource2D

getBounds, of, of, toList

Methods inherited from interface org.apache.commons.geometry.euclidean.twod.Linecastable2D

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

Methods inherited from interface org.apache.commons.geometry.core.partitioning.bsp.BSPTree

findNode

Constructor Detail

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 Detail

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()

Overrides:

boundaries in class AbstractRegionBSPTree<Vector2D,RegionBSPTree2D.RegionNode2D>

boundaryStream

public Stream<LineConvexSubset> boundaryStream()

Specified by:

boundaryStream in interface BoundarySource<LineConvexSubset>

getBoundaries

public List<LineConvexSubset> getBoundaries()

Overrides:

getBoundaries in class AbstractRegionBSPTree<Vector2D,RegionBSPTree2D.RegionNode2D>

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)

Specified by:

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

project

public Vector2D project(Vector2D pt)

Specified by:

project in interface Region<Vector2D>

Overrides:

project in class AbstractRegionBSPTree<Vector2D,RegionBSPTree2D.RegionNode2D>

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()

Specified by:

computeRegionSizeProperties in class AbstractRegionBSPTree<Vector2D,RegionBSPTree2D.RegionNode2D>

invalidate

protected void invalidate()

Overrides:

invalidate in class AbstractRegionBSPTree<Vector2D,RegionBSPTree2D.RegionNode2D>

createNode

protected RegionBSPTree2D.RegionNode2D createNode()

Specified by:

createNode in class AbstractBSPTree<Vector2D,RegionBSPTree2D.RegionNode2D>

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