View Javadoc

    1   /*
    2    * Licensed to the Apache Software Foundation (ASF) under one or more
    3    * contributor license agreements.  See the NOTICE file distributed with
    4    * this work for additional information regarding copyright ownership.
    5    * The ASF licenses this file to You under the Apache License, Version 2.0
    6    * (the "License"); you may not use this file except in compliance with
    7    * the License.  You may obtain a copy of the License at
    8    *
    9    *      http://www.apache.org/licenses/LICENSE-2.0
    10   *
    11   * Unless required by applicable law or agreed to in writing, software
    12   * distributed under the License is distributed on an "AS IS" BASIS,
    13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    14   * See the License for the specific language governing permissions and
    15   * limitations under the License.
    16   */
    17  package org.apache.commons.geometry.core.partitioning.bsp;
    18
    19  import java.util.ArrayList;
    20  import java.util.Iterator;
    21  import java.util.List;
    22  import java.util.function.Function;
    23  import java.util.stream.Stream;
    24
    25  import org.apache.commons.geometry.core.Point;
    26  import org.apache.commons.geometry.core.RegionLocation;
    27  import org.apache.commons.geometry.core.internal.IteratorTransform;
    28  import org.apache.commons.geometry.core.partitioning.BoundarySource;
    29  import org.apache.commons.geometry.core.partitioning.Hyperplane;
    30  import org.apache.commons.geometry.core.partitioning.HyperplaneBoundedRegion;
    31  import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset;
    32  import org.apache.commons.geometry.core.partitioning.HyperplaneLocation;
    33  import org.apache.commons.geometry.core.partitioning.HyperplaneSubset;
    34  import org.apache.commons.geometry.core.partitioning.Split;
    35  import org.apache.commons.geometry.core.partitioning.SplitLocation;
    36  import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor.ClosestFirstVisitor;
    37
    38  /** Abstract {@link BSPTree} specialized for representing regions of space. For example,
    39   * this class can be used to represent polygons in Euclidean 2D space and polyhedrons
    40   * in Euclidean 3D space.
    41   *
    42   * <p>This class is not thread safe.</p>
    43   * @param <P> Point implementation type
    44   * @param <N> BSP tree node implementation type
    45   * @see HyperplaneBoundedRegion
    46   */
    47  public abstract class AbstractRegionBSPTree<
    48          P extends Point<P>,
    49          N extends AbstractRegionBSPTree.AbstractRegionNode<P, N>>
    50      extends AbstractBSPTree<P, N> implements HyperplaneBoundedRegion<P> {
    51
    52      /** The default {@link RegionCutRule}. */
    53      private static final RegionCutRule DEFAULT_REGION_CUT_RULE = RegionCutRule.MINUS_INSIDE;
    54
    55      /** Value used to indicate an unknown size. */
    56      private static final double UNKNOWN_SIZE = -1.0;
    57
    58      /** The region boundary size; this is computed when requested and then cached. */
    59      private double boundarySize = UNKNOWN_SIZE;
    60
    61      /** The current size properties for the region. */
    62      private RegionSizeProperties<P> regionSizeProperties;
    63
    64      /** Construct a new region will the given boolean determining whether or not the
    65       * region will be full (including the entire space) or empty (excluding the entire
    66       * space).
    67       * @param full if true, the region will cover the entire space, otherwise it will
    68       *      be empty
    69       */
    70      protected AbstractRegionBSPTree(final boolean full) {
    71          getRoot().setLocationValue(full ? RegionLocation.INSIDE : RegionLocation.OUTSIDE);
    72      }
    73
    74      /** {@inheritDoc} */
    75      @Override
    76      public boolean isEmpty() {
    77          return !hasNodeWithLocationRecursive(getRoot(), RegionLocation.INSIDE);
    78      }
    79
    80      /** {@inheritDoc} */
    81      @Override
    82      public boolean isFull() {
    83          return !hasNodeWithLocationRecursive(getRoot(), RegionLocation.OUTSIDE);
    84      }
    85
    86      /** Return true if any node in the subtree rooted at the given node has a location with the
    87       * given value.
    88       * @param node the node at the root of the subtree to search
    89       * @param location the location to find
    90       * @return true if any node in the subtree has the given location
    91       */
    92      private boolean hasNodeWithLocationRecursive(final AbstractRegionNode<P, N> node, final RegionLocation location) {
    93          if (node == null) {
    94              return false;
    95          }
    96
    97          return node.getLocation() == location ||
    98                  hasNodeWithLocationRecursive(node.getMinus(), location) ||
    99                  hasNodeWithLocationRecursive(node.getPlus(), location);
    100     }
    101
    102     /** Modify this instance so that it contains the entire space.
    103      * @see #isFull()
    104      */
    105     public void setFull() {
    106         final N root = getRoot();
    107
    108         root.clearCut();
    109         root.setLocationValue(RegionLocation.INSIDE);
    110     }
    111
    112     /** Modify this instance so that is is completely empty.
    113      * @see #isEmpty()
    114      */
    115     public void setEmpty() {
    116         final N root = getRoot();
    117
    118         root.clearCut();
    119         root.setLocationValue(RegionLocation.OUTSIDE);
    120     }
    121
    122     /** {@inheritDoc} */
    123     @Override
    124     public double getSize() {
    125         return getRegionSizeProperties().getSize();
    126     }
    127
    128     /** {@inheritDoc} */
    129     @Override
    130     public double getBoundarySize() {
    131         if (boundarySize < 0.0) {
    132             double sum = 0.0;
    133
    134             RegionCutBoundary<P> boundary;
    135             for (final AbstractRegionNode<P, N> node : nodes()) {
    136                 boundary = node.getCutBoundary();
    137                 if (boundary != null) {
    138                     sum += boundary.getSize();
    139                 }
    140             }
    141
    142             boundarySize = sum;
    143         }
    144
    145         return boundarySize;
    146     }
    147
    148     /** Insert a hyperplane subset into the tree, using the default {@link RegionCutRule} of
    149      * {@link RegionCutRule#MINUS_INSIDE MINUS_INSIDE}.
    150      * @param sub the hyperplane subset to insert into the tree
    151      */
    152     public void insert(final HyperplaneSubset<P> sub) {
    153         insert(sub, DEFAULT_REGION_CUT_RULE);
    154     }
    155
    156     /** Insert a hyperplane subset into the tree.
    157      * @param sub the hyperplane subset to insert into the tree
    158      * @param cutRule rule used to determine the region locations of new child nodes
    159      */
    160     public void insert(final HyperplaneSubset<P> sub, final RegionCutRule cutRule) {
    161         insert(sub.toConvex(), cutRule);
    162     }
    163
    164     /** Insert a hyperplane convex subset into the tree, using the default {@link RegionCutRule} of
    165      * {@link RegionCutRule#MINUS_INSIDE MINUS_INSIDE}.
    166      * @param convexSub the hyperplane convex subset to insert into the tree
    167      */
    168     public void insert(final HyperplaneConvexSubset<P> convexSub) {
    169         insert(convexSub, DEFAULT_REGION_CUT_RULE);
    170     }
    171
    172     /** Insert a hyperplane convex subset into the tree.
    173      * @param convexSub the hyperplane convex subset to insert into the tree
    174      * @param cutRule rule used to determine the region locations of new child nodes
    175      */
    176     public void insert(final HyperplaneConvexSubset<P> convexSub, final RegionCutRule cutRule) {
    177         insert(convexSub, getSubtreeInitializer(cutRule));
    178     }
    179
    180     /** Insert a set of hyperplane convex subsets into the tree, using the default {@link RegionCutRule} of
    181      * {@link RegionCutRule#MINUS_INSIDE MINUS_INSIDE}.
    182      * @param convexSubs iterable containing a collection of hyperplane convex subsets
    183      *      to insert into the tree
    184      */
    185     public void insert(final Iterable<? extends HyperplaneConvexSubset<P>> convexSubs) {
    186         insert(convexSubs, DEFAULT_REGION_CUT_RULE);
    187     }
    188
    189     /** Insert a set of hyperplane convex subsets into the tree.
    190      * @param convexSubs iterable containing a collection of hyperplane convex subsets
    191      *      to insert into the tree
    192      * @param cutRule rule used to determine the region locations of new child nodes
    193      */
    194     public void insert(final Iterable<? extends HyperplaneConvexSubset<P>> convexSubs, final RegionCutRule cutRule) {
    195         for (final HyperplaneConvexSubset<P> convexSub : convexSubs) {
    196             insert(convexSub, cutRule);
    197         }
    198     }
    199
    200     /** Insert all hyperplane convex subsets from the given source into the tree, using the default
    201      * {@link RegionCutRule} of {@link RegionCutRule#MINUS_INSIDE MINUS_INSIDE}.
    202      * @param boundarySrc source of boundary hyperplane subsets to insert
    203      *      into the tree
    204      */
    205     public void insert(final BoundarySource<? extends HyperplaneConvexSubset<P>> boundarySrc) {
    206         insert(boundarySrc, DEFAULT_REGION_CUT_RULE);
    207     }
    208
    209     /** Insert all hyperplane convex subsets from the given source into the tree.
    210      * @param boundarySrc source of boundary hyperplane subsets to insert
    211      *      into the tree
    212      * @param cutRule rule used to determine the region locations of new child nodes
    213      */
    214     public void insert(final BoundarySource<? extends HyperplaneConvexSubset<P>> boundarySrc,
    215             final RegionCutRule cutRule) {
    216         try (Stream<? extends HyperplaneConvexSubset<P>> stream = boundarySrc.boundaryStream()) {
    217             stream.forEach(c -> insert(c, cutRule));
    218         }
    219     }
    220
    221     /** Get the subtree initializer to use for the given region cut rule.
    222      * @param cutRule the cut rule to get an initializer for
    223      * @return the subtree initializer for the given region cut rule
    224      */
    225     protected SubtreeInitializer<N> getSubtreeInitializer(final RegionCutRule cutRule) {
    226         switch (cutRule) {
    227         case INHERIT:
    228             return root -> {
    229                 final RegionLocation rootLoc = root.getLocation();
    230
    231                 root.getMinus().setLocationValue(rootLoc);
    232                 root.getPlus().setLocationValue(rootLoc);
    233             };
    234         case PLUS_INSIDE:
    235             return root -> {
    236                 root.getMinus().setLocationValue(RegionLocation.OUTSIDE);
    237                 root.getPlus().setLocationValue(RegionLocation.INSIDE);
    238             };
    239         default:
    240             return root -> {
    241                 root.getMinus().setLocationValue(RegionLocation.INSIDE);
    242                 root.getPlus().setLocationValue(RegionLocation.OUTSIDE);
    243             };
    244         }
    245     }
    246
    247     /** Return an {@link Iterable} for iterating over the boundaries of the region.
    248      * Each boundary is oriented such that its plus side points to the outside of the
    249      * region. The exact ordering of the boundaries is determined by the internal structure
    250      * of the tree.
    251      * @return an {@link Iterable} for iterating over the boundaries of the region
    252      * @see #getBoundaries()
    253      */
    254     public Iterable<? extends HyperplaneConvexSubset<P>> boundaries() {
    255         return createBoundaryIterable(Function.identity());
    256     }
    257
    258     /** Internal method for creating the iterable instances used to iterate the region boundaries.
    259      * @param typeConverter function to convert the generic hyperplane subset type into
    260      *      the type specific for this tree
    261      * @param <C> HyperplaneConvexSubset implementation type
    262      * @return an iterable to iterating the region boundaries
    263      */
    264     protected <C extends HyperplaneConvexSubset<P>> Iterable<C> createBoundaryIterable(
    265             final Function<HyperplaneConvexSubset<P>, C> typeConverter) {
    266
    267         return () -> new RegionBoundaryIterator<>(
    268                 getRoot().nodes().iterator(),
    269                 typeConverter);
    270     }
    271
    272     /** Return a list containing the boundaries of the region. Each boundary is oriented such
    273      * that its plus side points to the outside of the region. The exact ordering of
    274      * the boundaries is determined by the internal structure of the tree.
    275      * @return a list of the boundaries of the region
    276      */
    277     public List<? extends HyperplaneConvexSubset<P>> getBoundaries() {
    278         return createBoundaryList(Function.identity());
    279     }
    280
    281     /** Internal method for creating a list of the region boundaries.
    282      * @param typeConverter function to convert the generic convex subset type into
    283      *      the type specific for this tree
    284      * @param <C> HyperplaneConvexSubset implementation type
    285      * @return a list of the region boundaries
    286      */
    287     protected <C extends HyperplaneConvexSubset<P>> List<C> createBoundaryList(
    288             final Function<HyperplaneConvexSubset<P>, C> typeConverter) {
    289
    290         final List<C> result = new ArrayList<>();
    291
    292         final RegionBoundaryIterator<P, C, N> it = new RegionBoundaryIterator<>(nodes().iterator(), typeConverter);
    293         it.forEachRemaining(result::add);
    294
    295         return result;
    296     }
    297
    298     /** {@inheritDoc} */
    299     @Override
    300     public P project(final P pt) {
    301         final BoundaryProjector<P, N> projector = new BoundaryProjector<>(pt);
    302         accept(projector);
    303
    304         return projector.getProjected();
    305     }
    306
    307     /** {@inheritDoc} */
    308     @Override
    309     public P getCentroid() {
    310         return getRegionSizeProperties().getCentroid();
    311     }
    312
    313     /** Helper method implementing the algorithm for splitting a tree by a hyperplane. Subclasses
    314      * should call this method with two instantiated trees of the correct type.
    315      * @param splitter splitting hyperplane
    316      * @param minus tree that will contain the minus side of the split result
    317      * @param plus tree that will contain the plus side of the split result
    318      * @param <T> Tree implementation type
    319      * @return result of splitting this tree with the given hyperplane
    320      */
    321     protected <T extends AbstractRegionBSPTree<P, N>> Split<T> split(final Hyperplane<P> splitter,
    322             final T minus, final T plus) {
    323
    324         splitIntoTrees(splitter, minus, plus);
    325
    326         T splitMinus = null;
    327         T splitPlus = null;
    328
    329         if (minus != null) {
    330             minus.getRoot().getPlus().setLocationValue(RegionLocation.OUTSIDE);
    331             minus.condense();
    332
    333             splitMinus = minus.isEmpty() ? null : minus;
    334         }
    335         if (plus != null) {
    336             plus.getRoot().getMinus().setLocationValue(RegionLocation.OUTSIDE);
    337             plus.condense();
    338
    339             splitPlus = plus.isEmpty() ? null : plus;
    340         }
    341
    342         return new Split<>(splitMinus, splitPlus);
    343     }
    344
    345     /** Get the size-related properties for the region. The value is computed
    346      * lazily and cached.
    347      * @return the size-related properties for the region
    348      */
    349     protected RegionSizeProperties<P> getRegionSizeProperties() {
    350         if (regionSizeProperties == null) {
    351             regionSizeProperties = computeRegionSizeProperties();
    352         }
    353
    354         return regionSizeProperties;
    355     }
    356
    357     /** Compute the size-related properties of the region.
    358      * @return object containing size properties for the region
    359      */
    360     protected abstract RegionSizeProperties<P> computeRegionSizeProperties();
    361
    362     /** {@inheritDoc}
    363      *
    364      * <p>If the point is {@link org.apache.commons.geometry.core.Spatial#isNaN() NaN}, then
    365      * {@link RegionLocation#OUTSIDE} is returned.</p>
    366      */
    367     @Override
    368     public RegionLocation classify(final P point) {
    369         if (point.isNaN()) {
    370             return RegionLocation.OUTSIDE;
    371         }
    372
    373         return classifyRecursive(getRoot(), point);
    374     }
    375
    376     /** Recursively classify a point with respect to the region.
    377      * @param node the node to classify against
    378      * @param point the point to classify
    379      * @return the classification of the point with respect to the region rooted
    380      *      at the given node
    381      */
    382     private RegionLocation classifyRecursive(final AbstractRegionNode<P, N> node, final P point) {
    383         if (node.isLeaf()) {
    384             // the point is in a leaf, so the classification is just the leaf location
    385             return node.getLocation();
    386         } else {
    387             final HyperplaneLocation cutLoc = node.getCutHyperplane().classify(point);
    388
    389             if (cutLoc == HyperplaneLocation.MINUS) {
    390                 return classifyRecursive(node.getMinus(), point);
    391             } else if (cutLoc == HyperplaneLocation.PLUS) {
    392                 return classifyRecursive(node.getPlus(), point);
    393             } else {
    394                 // the point is on the cut boundary; classify against both child
    395                 // subtrees and see if we end up with the same result or not
    396                 final RegionLocation minusLoc = classifyRecursive(node.getMinus(), point);
    397                 final RegionLocation plusLoc = classifyRecursive(node.getPlus(), point);
    398
    399                 if (minusLoc == plusLoc) {
    400                     return minusLoc;
    401                 }
    402                 return RegionLocation.BOUNDARY;
    403             }
    404         }
    405     }
    406
    407     /** Change this region into its complement. All inside nodes become outside
    408      * nodes and vice versa. The orientations of the node cuts are not modified.
    409      */
    410     public void complement() {
    411         complementRecursive(getRoot());
    412     }
    413
    414     /** Set this instance to be the complement of the given tree. The argument
    415      * is not modified.
    416      * @param tree the tree to become the complement of
    417      */
    418     public void complement(final AbstractRegionBSPTree<P, N> tree) {
    419         copySubtree(tree.getRoot(), getRoot());
    420         complementRecursive(getRoot());
    421     }
    422
    423     /** Recursively switch all inside nodes to outside nodes and vice versa.
    424      * @param node the node at the root of the subtree to switch
    425      */
    426     private void complementRecursive(final AbstractRegionNode<P, N> node) {
    427         if (node != null) {
    428             final RegionLocation newLoc = (node.getLocation() == RegionLocation.INSIDE) ?
    429                     RegionLocation.OUTSIDE :
    430                     RegionLocation.INSIDE;
    431
    432             node.setLocationValue(newLoc);
    433
    434             complementRecursive(node.getMinus());
    435             complementRecursive(node.getPlus());
    436         }
    437     }
    438
    439     /** Compute the union of this instance and the given region, storing the result back in
    440      * this instance. The argument is not modified.
    441      * @param other the tree to compute the union with
    442      */
    443     public void union(final AbstractRegionBSPTree<P, N> other) {
    444         new UnionOperator<P, N>().apply(this, other, this);
    445     }
    446
    447     /** Compute the union of the two regions passed as arguments and store the result in
    448      * this instance. Any nodes currently existing in this instance are removed.
    449      * @param a first argument to the union operation
    450      * @param b second argument to the union operation
    451      */
    452     public void union(final AbstractRegionBSPTree<P, N> a, final AbstractRegionBSPTree<P, N> b) {
    453         new UnionOperator<P, N>().apply(a, b, this);
    454     }
    455
    456     /** Compute the intersection of this instance and the given region, storing the result back in
    457      * this instance. The argument is not modified.
    458      * @param other the tree to compute the intersection with
    459      */
    460     public void intersection(final AbstractRegionBSPTree<P, N> other) {
    461         new IntersectionOperator<P, N>().apply(this, other, this);
    462     }
    463
    464     /** Compute the intersection of the two regions passed as arguments and store the result in
    465      * this instance. Any nodes currently existing in this instance are removed.
    466      * @param a first argument to the intersection operation
    467      * @param b second argument to the intersection operation
    468      */
    469     public void intersection(final AbstractRegionBSPTree<P, N> a, final AbstractRegionBSPTree<P, N> b) {
    470         new IntersectionOperator<P, N>().apply(a, b, this);
    471     }
    472
    473     /** Compute the difference of this instance and the given region, storing the result back in
    474      * this instance. The argument is not modified.
    475      * @param other the tree to compute the difference with
    476      */
    477     public void difference(final AbstractRegionBSPTree<P, N> other) {
    478         new DifferenceOperator<P, N>().apply(this, other, this);
    479     }
    480
    481     /** Compute the difference of the two regions passed as arguments and store the result in
    482      * this instance. Any nodes currently existing in this instance are removed.
    483      * @param a first argument to the difference operation
    484      * @param b second argument to the difference operation
    485      */
    486     public void difference(final AbstractRegionBSPTree<P, N> a, final AbstractRegionBSPTree<P, N> b) {
    487         new DifferenceOperator<P, N>().apply(a, b, this);
    488     }
    489
    490     /** Compute the symmetric difference (xor) of this instance and the given region, storing the result back in
    491      * this instance. The argument is not modified.
    492      * @param other the tree to compute the symmetric difference with
    493      */
    494     public void xor(final AbstractRegionBSPTree<P, N> other) {
    495         new XorOperator<P, N>().apply(this, other, this);
    496     }
    497
    498     /** Compute the symmetric difference (xor) of the two regions passed as arguments and store the result in
    499      * this instance. Any nodes currently existing in this instance are removed.
    500      * @param a first argument to the symmetric difference operation
    501      * @param b second argument to the symmetric difference operation
    502      */
    503     public void xor(final AbstractRegionBSPTree<P, N> a, final AbstractRegionBSPTree<P, N> b) {
    504         new XorOperator<P, N>().apply(a, b, this);
    505     }
    506
    507     /** Condense this tree by removing redundant subtrees, returning true if the
    508      * tree structure was modified.
    509      *
    510      * <p>This operation can be used to reduce the total number of nodes in the
    511      * tree after performing node manipulations. For example, if two sibling leaf
    512      * nodes both represent the same {@link RegionLocation}, then there is no reason
    513      * from the perspective of the geometric region to retain both nodes. They are
    514      * therefore both merged into their parent node. This method performs this
    515      * simplification process.
    516      * </p>
    517      * @return true if the tree structure was modified, otherwise false
    518      */
    519     public boolean condense() {
    520         return new Condenser<P, N>().condense(getRoot());
    521     }
    522
    523     /** {@inheritDoc} */
    524     @Override
    525     protected void copyNodeProperties(final N src, final N dst) {
    526         dst.setLocationValue(src.getLocation());
    527     }
    528
    529     /** {@inheritDoc} */
    530     @Override
    531     protected void invalidate() {
    532         super.invalidate();
    533
    534         // clear cached region properties
    535         boundarySize = UNKNOWN_SIZE;
    536         regionSizeProperties = null;
    537     }
    538
    539     /** {@link BSPTree.Node} implementation for use with {@link AbstractRegionBSPTree}s.
    540      * @param <P> Point implementation type
    541      * @param <N> BSP tree node implementation type
    542      */
    543     public abstract static class AbstractRegionNode<P extends Point<P>, N extends AbstractRegionNode<P, N>>
    544         extends AbstractBSPTree.AbstractNode<P, N> {
    545         /** The location for the node. This will only be set on leaf nodes. */
    546         private RegionLocation location;
    547
    548         /** Object representing the part of the node cut hyperplane subset that lies on the
    549          * region boundary. This is calculated lazily and is only present on internal nodes.
    550          */
    551         private RegionCutBoundary<P> cutBoundary;
    552
    553         /** Simple constructor.
    554          * @param tree owning tree instance
    555          */
    556         protected AbstractRegionNode(final AbstractBSPTree<P, N> tree) {
    557             super(tree);
    558         }
    559
    560         /** {@inheritDoc} */
    561         @Override
    562         public AbstractRegionBSPTree<P, N> getTree() {
    563             // cast to our parent tree type
    564             return (AbstractRegionBSPTree<P, N>) super.getTree();
    565         }
    566
    567         /** Get the location property of the node. Only the locations of leaf nodes are meaningful
    568          * as they relate to the region represented by the BSP tree. For example, changing
    569          * the location of an internal node will only affect the geometric properties
    570          * of the region if the node later becomes a leaf node.
    571          * @return the location of the node
    572          */
    573         public RegionLocation getLocation() {
    574             return location;
    575         }
    576
    577         /** Set the location property for the node. If the location is changed, the tree is
    578          * invalidated.
    579          *
    580          * <p>Only the locations of leaf nodes are meaningful
    581          * as they relate to the region represented by the BSP tree. For example, changing
    582          * the location of an internal node will only affect the geometric properties
    583          * of the region if the node later becomes a leaf node.</p>
    584          * @param location the location for the node
    585          * @throws IllegalArgumentException if {@code location} is not one of
    586          *      {@link RegionLocation#INSIDE INSIDE} or {@link RegionLocation#OUTSIDE OUTSIDE}
    587          */
    588         public void setLocation(final RegionLocation location) {
    589             if (location != RegionLocation.INSIDE && location != RegionLocation.OUTSIDE) {
    590                 throw new IllegalArgumentException("Invalid node location: " + location);
    591             }
    592             if (this.location != location) {
    593                 this.location = location;
    594
    595                 getTree().invalidate();
    596             }
    597         }
    598
    599         /** True if the node is a leaf node and has a location of {@link RegionLocation#INSIDE}.
    600          * @return true if the node is a leaf node and has a location of
    601          *      {@link RegionLocation#INSIDE}
    602          */
    603         public boolean isInside() {
    604             return isLeaf() && getLocation() == RegionLocation.INSIDE;
    605         }
    606
    607         /** True if the node is a leaf node and has a location of {@link RegionLocation#OUTSIDE}.
    608          * @return true if the node is a leaf node and has a location of
    609          *      {@link RegionLocation#OUTSIDE}
    610          */
    611         public boolean isOutside() {
    612             return isLeaf() && getLocation() == RegionLocation.OUTSIDE;
    613         }
    614
    615         /** Insert a cut into this node, using the default region cut rule of
    616          * {@link RegionCutRule#MINUS_INSIDE}.
    617          * @param cutter the hyperplane to cut the node's region with
    618          * @return true if the cutting hyperplane intersected the node's region, resulting
    619          *      in the creation of new child nodes
    620          * @see #insertCut(Hyperplane, RegionCutRule)
    621          */
    622         public boolean insertCut(final Hyperplane<P> cutter) {
    623             return insertCut(cutter, DEFAULT_REGION_CUT_RULE);
    624         }
    625
    626         /** Insert a cut into this node. If the given hyperplane intersects
    627          * this node's region, then the node's cut is set to the {@link HyperplaneConvexSubset}
    628          * representing the intersection, new plus and minus child leaf nodes
    629          * are assigned, and true is returned. If the hyperplane does not intersect
    630          * the node's region, then the node's cut and plus and minus child references
    631          * are all set to null (ie, it becomes a leaf node) and false is returned. In
    632          * either case, any existing cut and/or child nodes are removed by this method.
    633          * @param cutter the hyperplane to cut the node's region with
    634          * @param cutRule rule used to determine the region locations of newly created
    635          *      child nodes
    636          * @return true if the cutting hyperplane intersected the node's region, resulting
    637          *      in the creation of new child nodes
    638          */
    639         public boolean insertCut(final Hyperplane<P> cutter, final RegionCutRule cutRule) {
    640             final AbstractRegionBSPTree<P, N> tree = getTree();
    641             return tree.cutNode(getSelf(), cutter, tree.getSubtreeInitializer(cutRule));
    642         }
    643
    644         /** Remove the cut from this node. Returns true if the node previously had a cut.
    645          * @return true if the node had a cut before the call to this method
    646          */
    647         public boolean clearCut() {
    648             return getTree().removeNodeCut(getSelf());
    649         }
    650
    651         /** Cut this node with the given hyperplane. The same node is returned, regardless of
    652          * the outcome of the cut operation. If the operation succeeded, then the node will
    653          * have plus and minus child nodes.
    654          * @param cutter the hyperplane to cut the node's region with
    655          * @return this node
    656          * @see #insertCut(Hyperplane)
    657          */
    658         public N cut(final Hyperplane<P> cutter) {
    659             return cut(cutter, DEFAULT_REGION_CUT_RULE);
    660         }
    661
    662         /** Cut this node with the given hyperplane, using {@code cutRule} to determine the region
    663          * locations of any new child nodes. The same node is returned, regardless of
    664          * the outcome of the cut operation. If the operation succeeded, then the node will
    665          * have plus and minus child nodes.
    666          * @param cutter the hyperplane to cut the node's region with
    667          * @param cutRule rule used to determine the region locations of newly created
    668          *      child nodes
    669          * @return this node
    670          * @see #insertCut(Hyperplane, RegionCutRule)
    671          */
    672         public N cut(final Hyperplane<P> cutter, final RegionCutRule cutRule) {
    673             this.insertCut(cutter, cutRule);
    674
    675             return getSelf();
    676         }
    677
    678         /** Get the portion of the node's cut that lies on the boundary of the region.
    679          * @return the portion of the node's cut that lies on the boundary of
    680          *      the region
    681          */
    682         public RegionCutBoundary<P> getCutBoundary() {
    683             if (!isLeaf()) {
    684                 checkValid();
    685
    686                 if (cutBoundary == null) {
    687                     cutBoundary = computeBoundary();
    688                 }
    689             }
    690
    691             return cutBoundary;
    692         }
    693
    694         /** Compute the portion of the node's cut that lies on the boundary of the region.
    695          * This method must only be called on internal nodes.
    696          * @return object representing the portions of the node's cut that lie on the region's boundary
    697          */
    698         private RegionCutBoundary<P> computeBoundary() {
    699             final HyperplaneConvexSubset<P> sub = getCut();
    700
    701             // find the portions of the node cut hyperplane subset that touch inside and
    702             // outside cells in the minus sub-tree
    703             final List<HyperplaneConvexSubset<P>> minusIn = new ArrayList<>();
    704             final List<HyperplaneConvexSubset<P>> minusOut = new ArrayList<>();
    705
    706             characterizeHyperplaneSubset(sub, getMinus(), minusIn, minusOut);
    707
    708             final ArrayList<HyperplaneConvexSubset<P>> insideFacing = new ArrayList<>();
    709             final ArrayList<HyperplaneConvexSubset<P>> outsideFacing = new ArrayList<>();
    710
    711             if (!minusIn.isEmpty()) {
    712                 // Add to the boundary anything that touches an inside cell in the minus sub-tree
    713                 // and an outside cell in the plus sub-tree. These portions are oriented with their
    714                 // plus side pointing to the outside of the region.
    715                 for (final HyperplaneConvexSubset<P> minusInFragment : minusIn) {
    716                     characterizeHyperplaneSubset(minusInFragment, getPlus(), null, outsideFacing);
    717                 }
    718             }
    719
    720             if (!minusOut.isEmpty()) {
    721                 // Add to the boundary anything that touches an outside cell in the minus sub-tree
    722                 // and an inside cell in the plus sub-tree. These portions are oriented with their
    723                 // plus side pointing to the inside of the region.
    724                 for (final HyperplaneConvexSubset<P> minusOutFragment : minusOut) {
    725                     characterizeHyperplaneSubset(minusOutFragment, getPlus(), insideFacing, null);
    726                 }
    727             }
    728
    729             insideFacing.trimToSize();
    730             outsideFacing.trimToSize();
    731
    732             return new RegionCutBoundary<>(
    733                     insideFacing.isEmpty() ? null : insideFacing,
    734                     outsideFacing.isEmpty() ? null : outsideFacing);
    735         }
    736
    737         /** Recursive method to characterize a hyperplane convex subset with respect to the region's
    738          * boundaries.
    739          * @param sub the hyperplane convex subset to characterize
    740          * @param node the node to characterize the hyperplane convex subset against
    741          * @param in list that will receive the portions of the subset that lie in the inside
    742          *      of the region; may be null
    743          * @param out list that will receive the portions of the subset that lie on the outside
    744          *      of the region; may be null
    745          */
    746         private void characterizeHyperplaneSubset(final HyperplaneConvexSubset<P> sub,
    747                 final AbstractRegionNode<P, N> node, final List<HyperplaneConvexSubset<P>> in,
    748                 final List<HyperplaneConvexSubset<P>> out) {
    749
    750             if (sub != null) {
    751                 if (node.isLeaf()) {
    752                     if (node.isInside() && in != null) {
    753                         in.add(sub);
    754                     } else if (node.isOutside() && out != null) {
    755                         out.add(sub);
    756                     }
    757                 } else {
    758                     final Split<? extends HyperplaneConvexSubset<P>> split = sub.split(node.getCutHyperplane());
    759
    760                     // Continue further on down the subtree with the same subset if the
    761                     // subset lies directly on the current node's cut
    762                     if (split.getLocation() == SplitLocation.NEITHER) {
    763                         characterizeHyperplaneSubset(sub, node.getPlus(), in, out);
    764                         characterizeHyperplaneSubset(sub, node.getMinus(), in, out);
    765                     } else {
    766                         characterizeHyperplaneSubset(split.getPlus(), node.getPlus(), in, out);
    767                         characterizeHyperplaneSubset(split.getMinus(), node.getMinus(), in, out);
    768                     }
    769                 }
    770             }
    771         }
    772
    773         /** {@inheritDoc} */
    774         @Override
    775         public String toString() {
    776             final StringBuilder sb = new StringBuilder();
    777             sb.append(this.getClass().getSimpleName())
    778                 .append("[cut= ")
    779                 .append(getCut())
    780                 .append(", location= ")
    781                 .append(getLocation())
    782                 .append("]");
    783
    784             return sb.toString();
    785         }
    786
    787         /** {@inheritDoc} */
    788         @Override
    789         protected void nodeInvalidated() {
    790             super.nodeInvalidated();
    791
    792             // null any computed boundary value since it is no longer valid
    793             cutBoundary = null;
    794         }
    795
    796         /** Directly set the value of the location property for the node. No input validation
    797          * is performed and the tree is not invalidated.
    798          * @param locationValue the new location value for the node
    799          * @see #setLocation(RegionLocation)
    800          */
    801         protected void setLocationValue(final RegionLocation locationValue) {
    802             this.location = locationValue;
    803         }
    804     }
    805
    806     /** Class used to compute the point on the region's boundary that is closest to a target point.
    807      * @param <P> Point implementation type
    808      * @param <N> BSP tree node implementation type
    809      */
    810     protected static class BoundaryProjector<P extends Point<P>, N extends AbstractRegionNode<P, N>>
    811         extends ClosestFirstVisitor<P, N> {
    812         /** The projected point. */
    813         private P projected;
    814
    815         /** The current closest distance to the boundary found. */
    816         private double minDist = -1.0;
    817
    818         /** Simple constructor.
    819          * @param point the point to project onto the region's boundary
    820          */
    821         public BoundaryProjector(final P point) {
    822             super(point);
    823         }
    824
    825         /** {@inheritDoc} */
    826         @Override
    827         public Result visit(final N node) {
    828             final P point = getTarget();
    829
    830             if (node.isInternal() && (minDist < 0.0 || isPossibleClosestCut(node.getCut(), point, minDist))) {
    831                 final RegionCutBoundary<P> boundary = node.getCutBoundary();
    832                 final P boundaryPt = boundary.closest(point);
    833
    834                 final double dist = boundaryPt.distance(point);
    835                 final int cmp = Double.compare(dist, minDist);
    836
    837                 if (minDist < 0.0 || cmp < 0) {
    838                     projected = boundaryPt;
    839                     minDist = dist;
    840                 } else if (cmp == 0) {
    841                     // the two points are the _exact_ same distance from the reference point, so use
    842                     // a separate method to disambiguate them
    843                     projected = disambiguateClosestPoint(point, projected, boundaryPt);
    844                 }
    845             }
    846
    847             return Result.CONTINUE;
    848         }
    849
    850         /** Return true if the given node cut is a possible candidate for containing the closest region
    851          * boundary point to the target.
    852          * @param cut the node cut to test
    853          * @param target the target point being projected
    854          * @param currentMinDist the smallest distance found so far to a region boundary; this value is guaranteed
    855          *      to be non-negative
    856          * @return true if the cut is a possible candidate for containing the closest region
    857          *      boundary point to the target
    858          */
    859         protected boolean isPossibleClosestCut(final HyperplaneSubset<P> cut, final P target,
    860                 final double currentMinDist) {
    861             return Math.abs(cut.getHyperplane().offset(target)) <= currentMinDist;
    862         }
    863
    864         /** Method used to determine which of points {@code a} and {@code b} should be considered
    865          * as the "closest" point to {@code target} when the points are exactly equidistant.
    866          * @param target the target point
    867          * @param a first point to consider
    868          * @param b second point to consider
    869          * @return which of {@code a} or {@code b} should be considered as the one closest to
    870          *      {@code target}
    871          */
    872         protected P disambiguateClosestPoint(final P target, final P a, final P b) {
    873             return a;
    874         }
    875
    876         /** Get the projected point on the region's boundary, or null if no point could be found.
    877          * @return the projected point on the region's boundary
    878          */
    879         public P getProjected() {
    880             return projected;
    881         }
    882     }
    883
    884     /** Class containing the primary size-related properties of a region. These properties
    885      * are typically computed at the same time, so this class serves to encapsulate the result
    886      * of the combined computation.
    887      * @param <P> Point implementation type
    888      */
    889     protected static class RegionSizeProperties<P extends Point<P>> {
    890         /** The size of the region. */
    891         private final double size;
    892
    893         /** The centroid of the region. */
    894         private final P centroid;
    895
    896         /** Simple constructor.
    897          * @param size the region size
    898          * @param centroid the region centroid
    899          */
    900         public RegionSizeProperties(final double size, final P centroid) {
    901             this.size = size;
    902             this.centroid = centroid;
    903         }
    904
    905         /** Get the size of the region.
    906          * @return the size of the region
    907          */
    908         public double getSize() {
    909             return size;
    910         }
    911
    912         /** Get the centroid of the region.
    913          * @return the centroid of the region
    914          */
    915         public P getCentroid() {
    916             return centroid;
    917         }
    918     }
    919
    920     /** Class containing the basic algorithm for merging region BSP trees.
    921      * @param <P> Point implementation type
    922      * @param <N> BSP tree node implementation type
    923      */
    924     private abstract static class RegionMergeOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>>
    925         extends AbstractBSPTreeMergeOperator<P, N> {
    926
    927         /** Merge two input trees, storing the output in the third. The output tree can be one of the
    928          * input trees. The output tree is condensed before the method returns.
    929          * @param inputTree1 first input tree
    930          * @param inputTree2 second input tree
    931          * @param outputTree the tree that will contain the result of the merge; may be one
    932          *      of the input trees
    933          */
    934         public void apply(final AbstractRegionBSPTree<P, N> inputTree1, final AbstractRegionBSPTree<P, N> inputTree2,
    935                 final AbstractRegionBSPTree<P, N> outputTree) {
    936
    937             this.performMerge(inputTree1, inputTree2, outputTree);
    938
    939             outputTree.condense();
    940         }
    941     }
    942
    943     /** Class for performing boolean union operations on region trees.
    944      * @param <P> Point implementation type
    945      * @param <N> BSP tree node implementation type
    946      */
    947     private static final class UnionOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>>
    948         extends RegionMergeOperator<P, N> {
    949
    950         /** {@inheritDoc} */
    951         @Override
    952         protected N mergeLeaf(final N node1, final N node2) {
    953             if (node1.isLeaf()) {
    954                 return node1.isInside() ? node1 : node2;
    955             }
    956
    957             // call again with flipped arguments
    958             return mergeLeaf(node2, node1);
    959         }
    960     }
    961
    962     /** Class for performing boolean intersection operations on region trees.
    963      * @param <P> Point implementation type
    964      * @param <N> BSP tree node implementation type
    965      */
    966     private static final class IntersectionOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>>
    967         extends RegionMergeOperator<P, N> {
    968
    969         /** {@inheritDoc} */
    970         @Override
    971         protected N mergeLeaf(final N node1, final N node2) {
    972             if (node1.isLeaf()) {
    973                 return node1.isInside() ? node2 : node1;
    974             }
    975
    976             // call again with flipped arguments
    977             return mergeLeaf(node2, node1);
    978         }
    979     }
    980
    981     /** Class for performing boolean difference operations on region trees.
    982      * @param <P> Point implementation type
    983      * @param <N> BSP tree node implementation type
    984      */
    985     private static final class DifferenceOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>>
    986         extends RegionMergeOperator<P, N> {
    987
    988         /** {@inheritDoc} */
    989         @Override
    990         protected N mergeLeaf(final N node1, final N node2) {
    991             // a region is included if it belongs in tree1 and is not in tree2
    992
    993             if (node1.isInside()) {
    994                 // this region is inside of tree1, so only include subregions that are
    995                 // not in tree2, ie include everything in node2's complement
    996                 final N output = outputSubtree(node2);
    997                 output.getTree().complementRecursive(output);
    998
    999                 return output;
    1000             } else if (node2.isInside()) {
    1001                 // this region is inside of tree2 and so cannot be in the result region
    1002                 final N output = outputNode();
    1003                 output.setLocationValue(RegionLocation.OUTSIDE);
    1004
    1005                 return output;
    1006             }
    1007
    1008             // this region is not in tree2, so we can include everything in tree1
    1009             return node1;
    1010         }
    1011     }
    1012
    1013     /** Class for performing boolean symmetric difference (xor) operations on region trees.
    1014      * @param <P> Point implementation type
    1015      * @param <N> BSP tree node implementation type
    1016      */
    1017     private static final class XorOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>>
    1018         extends RegionMergeOperator<P, N> {
    1019
    1020         /** {@inheritDoc} */
    1021         @Override
    1022         protected N mergeLeaf(final N node1, final N node2) {
    1023             // a region is included if it belongs in tree1 and is not in tree2 OR
    1024             // it belongs in tree2 and is not in tree1
    1025
    1026             if (node1.isLeaf()) {
    1027                 if (node1.isInside()) {
    1028                     // this region is inside node1, so only include subregions that are
    1029                     // not in node2, ie include everything in node2's complement
    1030                     final N output = outputSubtree(node2);
    1031                     output.getTree().complementRecursive(output);
    1032
    1033                     return output;
    1034                 } else {
    1035                     // this region is not in node1, so only include subregions that
    1036                     // in node2
    1037                     return node2;
    1038                 }
    1039             }
    1040
    1041             // the operation is symmetric, so perform the same operation but with the
    1042             // nodes flipped
    1043             return mergeLeaf(node2, node1);
    1044         }
    1045     }
    1046
    1047     /** Internal class used to perform tree condense operations.
    1048      * @param <P> Point implementation type
    1049      * @param <N> BSP tree node implementation type
    1050      */
    1051     private static final class Condenser<P extends Point<P>, N extends AbstractRegionNode<P, N>> {
    1052         /** Flag set to true if the tree was modified during the operation. */
    1053         private boolean modifiedTree;
    1054
    1055         /** Condense the nodes in the subtree rooted at the given node. Redundant child nodes are
    1056          * removed. The tree is invalidated if the tree structure was modified.
    1057          * @param node the root node of the subtree to condense
    1058          * @return true if the tree was modified.
    1059          */
    1060         boolean condense(final N node) {
    1061             modifiedTree = false;
    1062
    1063             condenseRecursive(node);
    1064
    1065             return modifiedTree;
    1066         }
    1067
    1068         /** Recursively condense nodes that have children with homogenous location attributes
    1069          * (eg, both inside, both outside) into single nodes.
    1070          * @param node the root of the subtree to condense
    1071          * @return the location of the successfully condensed subtree or null if no condensing was
    1072          *      able to be performed
    1073          */
    1074         private RegionLocation condenseRecursive(final N node) {
    1075             if (node.isLeaf()) {
    1076                 return node.getLocation();
    1077             }
    1078
    1079             final RegionLocation minusLocation = condenseRecursive(node.getMinus());
    1080             final RegionLocation plusLocation = condenseRecursive(node.getPlus());
    1081
    1082             if (minusLocation == plusLocation && minusLocation != null) {
    1083                 node.setLocationValue(minusLocation);
    1084                 node.clearCut();
    1085
    1086                 modifiedTree = true;
    1087
    1088                 return minusLocation;
    1089             }
    1090
    1091             return null;
    1092         }
    1093     }
    1094
    1095     /** Class that iterates over the boundary hyperplane convex subsets from a set of region nodes.
    1096      * @param <P> Point implementation type
    1097      * @param <C> Boundary hyperplane convex subset implementation type
    1098      * @param <N> BSP tree node implementation type
    1099      */
    1100     private static final class RegionBoundaryIterator<
    1101             P extends Point<P>,
    1102             C extends HyperplaneConvexSubset<P>,
    1103             N extends AbstractRegionNode<P, N>>
    1104         extends IteratorTransform<N, C> {
    1105
    1106         /** Function that converts from the convex subset type to the output type. */
    1107         private final Function<HyperplaneConvexSubset<P>, C> typeConverter;
    1108
    1109         /** Simple constructor.
    1110          * @param inputIterator iterator that will provide all nodes in the tree
    1111          * @param typeConverter function that converts from the convex subset type to the output type
    1112          */
    1113         RegionBoundaryIterator(final Iterator<N> inputIterator,
    1114                 final Function<HyperplaneConvexSubset<P>, C> typeConverter) {
    1115             super(inputIterator);
    1116
    1117             this.typeConverter = typeConverter;
    1118         }
    1119
    1120         /** {@inheritDoc} */
    1121         @Override
    1122         protected void acceptInput(final N input) {
    1123             if (input.isInternal()) {
    1124                 final RegionCutBoundary<P> cutBoundary = input.getCutBoundary();
    1125
    1126                 for (final HyperplaneConvexSubset<P> boundary : cutBoundary.getOutsideFacing()) {
    1127                     addOutput(typeConverter.apply(boundary));
    1128                 }
    1129
    1130                 for (final HyperplaneConvexSubset<P> boundary : cutBoundary.getInsideFacing()) {
    1131                     final HyperplaneConvexSubset<P> reversed = boundary.reverse();
    1132
    1133                     addOutput(typeConverter.apply(reversed));
    1134                 }
    1135             }
    1136         }
    1137     }
    1138 }