Package org.apache.commons.geometry.core.partitioning.bsp

Class AbstractRegionBSPTree<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>>

java.lang.Object
org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree<P,N>
org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree<P,N>
Type Parameters:
P - Point implementation type
N - BSP tree node implementation type
All Implemented Interfaces:
BSPSubtree<P,N>, BSPTree<P,N>, HyperplaneBoundedRegion<P>, Splittable<P,HyperplaneBoundedRegion<P>>, Region<P>, Sized
Direct Known Subclasses:
RegionBSPTree1D, RegionBSPTree1S, RegionBSPTree2D, RegionBSPTree2S, RegionBSPTree3D
public abstract class AbstractRegionBSPTree<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>> extends AbstractBSPTree<P,N> implements HyperplaneBoundedRegion<P>
Abstract 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.

See Also:

  • Field Details

    • DEFAULT_REGION_CUT_RULE

      private static final RegionCutRule DEFAULT_REGION_CUT_RULE
      The default RegionCutRule.

    • UNKNOWN_SIZE

      private static final double UNKNOWN_SIZE
      Value used to indicate an unknown size.
      See Also:

    • boundarySize

      private double boundarySize
      The region boundary size; this is computed when requested and then cached.

    • regionSizeProperties

      private AbstractRegionBSPTree.RegionSizeProperties<P extends Point<P>> regionSizeProperties
      The current size properties for the region.

  • Constructor Details

    • AbstractRegionBSPTree

      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).
      Parameters:
      full - if true, the region will cover the entire space, otherwise it will be empty

  • Method Details

    • isEmpty

      public boolean isEmpty()
      Return true if the region is completely empty, ie all points in the space are classified as outside.
      Specified by:
      isEmpty in interface Region<P extends Point<P>>
      Returns:
      true if the region is empty

    • isFull

      public boolean isFull()
      Return true if the region spans the entire space. In other words, a region is full if no points in the space are classified as outside.
      Specified by:
      isFull in interface Region<P extends Point<P>>
      Returns:
      true if the region spans the entire space

    • hasNodeWithLocationRecursive

      private boolean hasNodeWithLocationRecursive(AbstractRegionBSPTree.AbstractRegionNode<P,N> node, RegionLocation location)
      Return true if any node in the subtree rooted at the given node has a location with the given value.
      Parameters:
      node - the node at the root of the subtree to search
      location - the location to find
      Returns:
      true if any node in the subtree has the given location

    • setFull

      public void setFull()
      Modify this instance so that it contains the entire space.
      See Also:

    • setEmpty

      public void setEmpty()
      Modify this instance so that is is completely empty.
      See Also:

    • getSize

      public double getSize()
      Get the size of the instance.
      Specified by:
      getSize in interface Sized
      Returns:
      the size of the instance

    • getBoundarySize

      public double getBoundarySize()
      Get the size of the boundary of the region. The size is a value in the d-1 dimension space. For example, in Euclidean space, this will be a length in 2D and an area in 3D.
      Specified by:
      getBoundarySize in interface Region<P extends Point<P>>
      Returns:
      the size of the boundary of the region

    • insert

      public void insert(HyperplaneSubset<P> sub)
      Insert a hyperplane subset into the tree, using the default RegionCutRule of MINUS_INSIDE.
      Parameters:
      sub - the hyperplane subset to insert into the tree

    • insert

      public void insert(HyperplaneSubset<P> sub, RegionCutRule cutRule)
      Insert a hyperplane subset into the tree.
      Parameters:
      sub - the hyperplane subset to insert into the tree
      cutRule - rule used to determine the region locations of new child nodes

    • insert

      public void insert(HyperplaneConvexSubset<P> convexSub)
      Insert a hyperplane convex subset into the tree, using the default RegionCutRule of MINUS_INSIDE.
      Parameters:
      convexSub - the hyperplane convex subset to insert into the tree

    • insert

      public void insert(HyperplaneConvexSubset<P> convexSub, RegionCutRule cutRule)
      Insert a hyperplane convex subset into the tree.
      Parameters:
      convexSub - the hyperplane convex subset to insert into the tree
      cutRule - rule used to determine the region locations of new child nodes

    • insert

      public void insert(Iterable<? extends HyperplaneConvexSubset<P>> convexSubs)
      Insert a set of hyperplane convex subsets into the tree, using the default RegionCutRule of MINUS_INSIDE.
      Parameters:
      convexSubs - iterable containing a collection of hyperplane convex subsets to insert into the tree

    • insert

      public void insert(Iterable<? extends HyperplaneConvexSubset<P>> convexSubs, RegionCutRule cutRule)
      Insert a set of hyperplane convex subsets into the tree.
      Parameters:
      convexSubs - iterable containing a collection of hyperplane convex subsets to insert into the tree
      cutRule - rule used to determine the region locations of new child nodes

    • insert

      public 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.
      Parameters:
      boundarySrc - source of boundary hyperplane subsets to insert into the tree

    • insert

      public void insert(BoundarySource<? extends HyperplaneConvexSubset<P>> boundarySrc, RegionCutRule cutRule)
      Insert all hyperplane convex subsets from the given source into the tree.
      Parameters:
      boundarySrc - source of boundary hyperplane subsets to insert into the tree
      cutRule - rule used to determine the region locations of new child nodes

    • getSubtreeInitializer

      protected AbstractBSPTree.SubtreeInitializer<N> getSubtreeInitializer(RegionCutRule cutRule)
      Get the subtree initializer to use for the given region cut rule.
      Parameters:
      cutRule - the cut rule to get an initializer for
      Returns:
      the subtree initializer for the given region cut rule

    • boundaries

      public Iterable<? extends HyperplaneConvexSubset<P>> 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.
      Returns:
      an Iterable for iterating over the boundaries of the region
      See Also:

    • createBoundaryIterable

      protected <C extends HyperplaneConvexSubset<P>> Iterable<C> createBoundaryIterable(Function<HyperplaneConvexSubset<P>,C> typeConverter)
      Internal method for creating the iterable instances used to iterate the region boundaries.
      Type Parameters:
      C - HyperplaneConvexSubset implementation type
      Parameters:
      typeConverter - function to convert the generic hyperplane subset type into the type specific for this tree
      Returns:
      an iterable to iterating the region boundaries

    • getBoundaries

      public List<? extends HyperplaneConvexSubset<P>> 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.
      Returns:
      a list of the boundaries of the region

    • createBoundaryList

      protected <C extends HyperplaneConvexSubset<P>> List<C> createBoundaryList(Function<HyperplaneConvexSubset<P>,C> typeConverter)
      Internal method for creating a list of the region boundaries.
      Type Parameters:
      C - HyperplaneConvexSubset implementation type
      Parameters:
      typeConverter - function to convert the generic convex subset type into the type specific for this tree
      Returns:
      a list of the region boundaries

    • project

      public P project(P 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<P extends Point<P>>
      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

    • getCentroid

      public P getCentroid()
      Get the centroid, or geometric center, of the region or null if no centroid exists or one exists but is not unique. A centroid will not exist for empty or infinite regions.

      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.

      Specified by:
      getCentroid in interface Region<P extends Point<P>>
      Returns:
      the centroid of the region or null if no unique centroid exists
      See Also:

    • split

      protected <T extends AbstractRegionBSPTree<P, N>> Split<T> split(Hyperplane<P> splitter, T minus, T plus)
      Helper method implementing the algorithm for splitting a tree by a hyperplane. Subclasses should call this method with two instantiated trees of the correct type.
      Type Parameters:
      T - Tree implementation type
      Parameters:
      splitter - splitting hyperplane
      minus - tree that will contain the minus side of the split result
      plus - tree that will contain the plus side of the split result
      Returns:
      result of splitting this tree with the given hyperplane

    • getRegionSizeProperties

      protected AbstractRegionBSPTree.RegionSizeProperties<P> getRegionSizeProperties()
      Get the size-related properties for the region. The value is computed lazily and cached.
      Returns:
      the size-related properties for the region

    • computeRegionSizeProperties

      protected abstract AbstractRegionBSPTree.RegionSizeProperties<P> computeRegionSizeProperties()
      Compute the size-related properties of the region.
      Returns:
      object containing size properties for the region

    • classify

      public RegionLocation classify(P point)
      Classify the given point with respect to the region.

      If the point is NaN, then RegionLocation.OUTSIDE is returned.

      Specified by:
      classify in interface Region<P extends Point<P>>
      Parameters:
      point - the point to classify
      Returns:
      the location of the point with respect to the region

    • classifyRecursive

      private RegionLocation classifyRecursive(AbstractRegionBSPTree.AbstractRegionNode<P,N> node, P point)
      Recursively classify a point with respect to the region.
      Parameters:
      node - the node to classify against
      point - the point to classify
      Returns:
      the classification of the point with respect to the region rooted at the given node

    • complement

      public void complement()
      Change this region into its complement. All inside nodes become outside nodes and vice versa. The orientations of the node cuts are not modified.

    • complement

      public void complement(AbstractRegionBSPTree<P,N> tree)
      Set this instance to be the complement of the given tree. The argument is not modified.
      Parameters:
      tree - the tree to become the complement of

    • complementRecursive

      private void complementRecursive(AbstractRegionBSPTree.AbstractRegionNode<P,N> node)
      Recursively switch all inside nodes to outside nodes and vice versa.
      Parameters:
      node - the node at the root of the subtree to switch

    • union

      public void union(AbstractRegionBSPTree<P,N> other)
      Compute the union of this instance and the given region, storing the result back in this instance. The argument is not modified.
      Parameters:
      other - the tree to compute the union with

    • union

      public 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. Any nodes currently existing in this instance are removed.
      Parameters:
      a - first argument to the union operation
      b - second argument to the union operation

    • intersection

      public void intersection(AbstractRegionBSPTree<P,N> other)
      Compute the intersection of this instance and the given region, storing the result back in this instance. The argument is not modified.
      Parameters:
      other - the tree to compute the intersection with

    • intersection

      public 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. Any nodes currently existing in this instance are removed.
      Parameters:
      a - first argument to the intersection operation
      b - second argument to the intersection operation

    • difference

      public void difference(AbstractRegionBSPTree<P,N> other)
      Compute the difference of this instance and the given region, storing the result back in this instance. The argument is not modified.
      Parameters:
      other - the tree to compute the difference with

    • difference

      public 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. Any nodes currently existing in this instance are removed.
      Parameters:
      a - first argument to the difference operation
      b - second argument to the difference operation

    • xor

      public 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. The argument is not modified.
      Parameters:
      other - the tree to compute the symmetric difference with

    • xor

      public 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. Any nodes currently existing in this instance are removed.
      Parameters:
      a - first argument to the symmetric difference operation
      b - second argument to the symmetric difference operation

    • condense

      public boolean condense()
      Condense this tree by removing redundant subtrees, returning true if the tree structure was modified.

      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.

      Returns:
      true if the tree structure was modified, otherwise false

    • copyNodeProperties

      protected void copyNodeProperties(N src, N dst)
      Copy non-structural node properties from 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.
      Specified by:
      copyNodeProperties in class AbstractBSPTree<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>>
      Parameters:
      src - source node
      dst - destination node

    • 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 AbstractBSPTree<P extends Point<P>,N extends AbstractRegionBSPTree.AbstractRegionNode<P,N>>
      See Also: