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.Comparator;
    21  import java.util.HashSet;
    22  import java.util.List;
    23  import java.util.Set;
    24  import java.util.function.BiConsumer;
    25
    26  import org.apache.commons.geometry.core.Point;
    27  import org.apache.commons.geometry.core.RegionLocation;
    28  import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset;
    29  import org.apache.commons.geometry.core.partitioning.Split;
    30  import org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree.SubtreeInitializer;
    31  import org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree.AbstractRegionNode;
    32
    33  /** Class encapsulating logic for building regions by inserting boundaries into a BSP
    34   * tree containing structural cuts, i.e. cuts where both sides of the cut have the same region
    35   * location. This technique only produces accurate results when the inserted boundaries define
    36   * the entire surface of the region. However, for valid input boundaries, significant performance
    37   * improvements can be achieved due to the reduced height of the tree, especially where large
    38   * numbers of boundaries are involved and/or the defined region is convex.
    39   *
    40   * <h2>Implementation Notes</h2>
    41   *
    42   * <p>This class constructs regions in two phases: (1) <em>partition insertion</em> and (2) <em>boundary insertion</em>.
    43   * Instances begin in the <em>partition insertion</em> phase. Here, partitions can be inserted into the empty tree
    44   * using the standard BSP insertion logic. The {@link RegionCutRule#INHERIT INHERIT} cut rule is used so that the
    45   * represented region remains empty even as partitions are inserted.
    46   * </p>
    47   *
    48   * <p>The instance moves into the <em>boundary insertion</em> phase when the caller inserts the first region boundary.
    49   * Attempting to insert a partition after this point results in an {@code IllegalStateException}. This ensures that
    50   * partitioning cuts are always located higher up the tree than boundary cuts.</p>
    51   *
    52   * <p>After all boundaries are inserted, the tree undergoes final processing to ensure that the region is consistent
    53   * and that unnecessary nodes are removed.</p>
    54   *
    55   * <p>This class does not expose any public methods so that subclasses can present their own
    56   * public API, tailored to the specific types being worked with. In particular, most subclasses
    57   * will want to restrict the tree types used with the algorithm, which is difficult to implement
    58   * cleanly at this level.</p>
    59   * @param <P> Point implementation type
    60   * @param <N> BSP tree node implementation type
    61   */
    62  public abstract class AbstractPartitionedRegionBuilder<
    63      P extends Point<P>,
    64      N extends AbstractRegionNode<P, N>> {
    65
    66      /** Comparator for sorting nodes with the deepest nodes first. */
    67      private static final Comparator<BSPTree.Node<?, ?>> DEEPEST_FIRST_ORDER =
    68          (a, b) -> Integer.compare(b.depth(), a.depth());
    69
    70      /** Tree being constructed. */
    71      private final AbstractRegionBSPTree<P, N> tree;
    72
    73      /** Subtree initializer for inserted boundaries. */
    74      private final SubtreeInitializer<N> subtreeInit;
    75
    76      /** Flag indicating whether or not partitions may still be inserted into the tree. */
    77      private boolean insertingPartitions = true;
    78
    79      /** Set of all internal nodes used as partitioning nodes. */
    80      private final Set<N> partitionNodes = new HashSet<>();
    81
    82      /** Construct a new instance that builds a partitioned region in the given tree. The tree must
    83       * be empty.
    84       * @param tree tree to build the region in; must be empty
    85       * @throws IllegalArgumentException if the tree is not empty
    86       */
    87      protected AbstractPartitionedRegionBuilder(final AbstractRegionBSPTree<P, N> tree) {
    88          if (!tree.isEmpty()) {
    89              throw new IllegalArgumentException("Tree must be empty");
    90          }
    91
    92          this.tree = tree;
    93          this.subtreeInit = tree.getSubtreeInitializer(RegionCutRule.MINUS_INSIDE);
    94      }
    95
    96      /** Internal method to build and return the tree representing the final partitioned region.
    97       * @return the partitioned region
    98       */
    99      protected AbstractRegionBSPTree<P, N> buildInternal() {
    100         // condense to combine homogenous leaf nodes
    101         tree.condense();
    102
    103         // propagate region interiors to partitioned nodes that have not received
    104         // a boundary
    105         if (propagateRegionInterior()) {
    106             // condense again since some leaf nodes changed
    107             tree.condense();
    108         }
    109
    110         return tree;
    111     }
    112
    113     /** Internal method to insert a partition into the tree.
    114      * @param partition partition to insert
    115      * @throws IllegalStateException if a boundary has previously been inserted
    116      */
    117     protected void insertPartitionInternal(final HyperplaneConvexSubset<P> partition) {
    118         ensureInsertingPartitions();
    119
    120         tree.insert(partition, RegionCutRule.INHERIT);
    121     }
    122
    123     /** Internal method to insert a region boundary into the tree.
    124      * @param boundary boundary to insert
    125      */
    126     protected void insertBoundaryInternal(final HyperplaneConvexSubset<P> boundary) {
    127         if (insertingPartitions) {
    128             // switch to inserting boundaries; place all current internal nodes into
    129             // a set for easy identification
    130             for (final N node : tree.nodes()) {
    131                 if (node.isInternal()) {
    132                     partitionNodes.add(node);
    133                 }
    134             }
    135
    136             insertingPartitions = false;
    137         }
    138
    139         insertBoundaryRecursive(tree.getRoot(), boundary, boundary.getHyperplane().span(),
    140             (leaf, cut) -> tree.setNodeCut(leaf, cut, subtreeInit));
    141     }
    142
    143     /** Insert a region boundary into the tree.
    144      * @param node node to insert into
    145      * @param insert the hyperplane convex subset to insert
    146      * @param trimmed version of the hyperplane convex subset filling the entire space of {@code node}
    147      * @param leafFn function to apply to leaf nodes
    148      */
    149     private void insertBoundaryRecursive(final N node, final HyperplaneConvexSubset<P> insert,
    150             final HyperplaneConvexSubset<P> trimmed, final BiConsumer<N, HyperplaneConvexSubset<P>> leafFn) {
    151         if (node.isLeaf()) {
    152             leafFn.accept(node, trimmed);
    153         } else {
    154             insertBoundaryRecursiveInternalNode(node, insert, trimmed, leafFn);
    155         }
    156     }
    157
    158     /** Recursive boundary insertion method for internal nodes.
    159      * @param node node to insert into
    160      * @param insert the hyperplane convex subset to insert
    161      * @param trimmed version of the hyperplane convex subset filling the entire space of {@code node}
    162      * @param leafFn function to apply to leaf nodes
    163      * @see #insertBoundaryRecursive(AbstractRegionNode, HyperplaneConvexSubset, HyperplaneConvexSubset, BiConsumer)
    164      */
    165     private void insertBoundaryRecursiveInternalNode(final N node, final HyperplaneConvexSubset<P> insert,
    166             final HyperplaneConvexSubset<P> trimmed, final BiConsumer<N, HyperplaneConvexSubset<P>> leafFn) {
    167
    168         final Split<? extends HyperplaneConvexSubset<P>> insertSplit =
    169                 insert.split(node.getCutHyperplane());
    170
    171         final HyperplaneConvexSubset<P> minus = insertSplit.getMinus();
    172         final HyperplaneConvexSubset<P> plus = insertSplit.getPlus();
    173
    174         if (minus == null && plus == null && isPartitionNode(node)) {
    175             // the inserted boundary lies directly on a partition; proceed down the tree with the
    176             // rest of the insertion algorithm but instead of cutting the final leaf nodes, just
    177             // set the location
    178
    179             // remove this node from the set of partition nodes since this is now a boundary cut
    180             partitionNodes.remove(node);
    181
    182             final boolean sameOrientation = node.getCutHyperplane().similarOrientation(insert.getHyperplane());
    183             final N insertMinus = sameOrientation ? node.getMinus() : node.getPlus();
    184             final N insertPlus = sameOrientation ? node.getPlus() : node.getMinus();
    185
    186             insertBoundaryRecursive(insertMinus, insert, trimmed,
    187                 (leaf, cut) -> leaf.setLocation(RegionLocation.INSIDE));
    188
    189             insertBoundaryRecursive(insertPlus, insert, trimmed,
    190                 (leaf, cut) -> leaf.setLocation(RegionLocation.OUTSIDE));
    191
    192         } else if (minus != null || plus != null) {
    193             final Split<? extends HyperplaneConvexSubset<P>> trimmedSplit =
    194                     trimmed.split(node.getCutHyperplane());
    195
    196             final HyperplaneConvexSubset<P> trimmedMinus = trimmedSplit.getMinus();
    197             final HyperplaneConvexSubset<P> trimmedPlus = trimmedSplit.getPlus();
    198
    199             if (minus != null) {
    200                 insertBoundaryRecursive(node.getMinus(), minus, trimmedMinus, leafFn);
    201             }
    202             if (plus != null) {
    203                 insertBoundaryRecursive(node.getPlus(), plus, trimmedPlus, leafFn);
    204             }
    205         }
    206     }
    207
    208     /** Propagate the region interior to partitioned leaf nodes that have not had a boundary
    209      * inserted.
    210      * @return true if any nodes were changed
    211      */
    212     private boolean propagateRegionInterior() {
    213         final List<N> outsidePartitionedLeaves = getOutsidePartitionedLeaves();
    214         outsidePartitionedLeaves.sort(DEEPEST_FIRST_ORDER);
    215
    216         int changeCount = 0;
    217
    218         N parent;
    219         N sibling;
    220         for (final N leaf : outsidePartitionedLeaves) {
    221             parent = leaf.getParent();
    222
    223             // check if the parent cut touches the inside anywhere on the side opposite of
    224             // this leaf; if so, then this node should also be inside
    225             sibling = leaf.isMinus() ?
    226                     parent.getPlus() :
    227                     parent.getMinus();
    228
    229             if (touchesInside(parent.getCut(), sibling)) {
    230                 leaf.setLocation(RegionLocation.INSIDE);
    231
    232                 ++changeCount;
    233             }
    234         }
    235
    236         return changeCount > 0;
    237     }
    238
    239     /** Return a list containing all outside leaf nodes that have a parent marked as a partition node.
    240      * @return a list containing all outside leaf nodes that have a parent marked as a partition node
    241      */
    242     private List<N> getOutsidePartitionedLeaves() {
    243         final List<N> result = new ArrayList<>();
    244
    245         final N root = tree.getRoot();
    246         collectOutsidePartitionedLeavesRecursive(root, false, result);
    247
    248         return result;
    249     }
    250
    251    /** Recursively collect all outside leaf nodes that have a parent marked as a partition node.
    252     * @param node root of the subtree to collect nodes from
    253     * @param parentIsPartitionNode true if the parent of {@code node} is a partition node
    254     * @param result list of accumulated results
    255     */
    256     private void collectOutsidePartitionedLeavesRecursive(final N node, final boolean parentIsPartitionNode,
    257             final List<N> result) {
    258         if (node != null) {
    259             if (parentIsPartitionNode && node.isOutside()) {
    260                 result.add(node);
    261             }
    262
    263             final boolean partitionNode = isPartitionNode(node);
    264
    265             collectOutsidePartitionedLeavesRecursive(node.getMinus(), partitionNode, result);
    266             collectOutsidePartitionedLeavesRecursive(node.getPlus(), partitionNode, result);
    267         }
    268     }
    269
    270     /** Return true if {@code sub} touches an inside leaf node anywhere in the subtree rooted at {@code node}.
    271      * @param sub convex subset to check
    272      * @param node root node of the subtree to test against
    273      * @return true if {@code sub} touches an inside leaf node anywhere in the subtree rooted at {@code node}
    274      */
    275     private boolean touchesInside(final HyperplaneConvexSubset<P> sub, final N node) {
    276         if (sub != null) {
    277             if (node.isLeaf()) {
    278                 return node.isInside();
    279             } else {
    280                 final Split<? extends HyperplaneConvexSubset<P>> split = sub.split(node.getCutHyperplane());
    281
    282                 return touchesInside(split.getMinus(), node.getMinus()) ||
    283                         touchesInside(split.getPlus(), node.getPlus());
    284
    285             }
    286         }
    287
    288         return false;
    289     }
    290
    291     /** Return true if the given node is marked as a partition node.
    292      * @param node node to check
    293      * @return true if the given node is marked as a partition node
    294      */
    295     private boolean isPartitionNode(final N node) {
    296         return partitionNodes.contains(node);
    297     }
    298
    299     /** Throw an exception if the instance is no longer accepting partitions.
    300      * @throws IllegalStateException if the instance is no longer accepting partitions
    301      */
    302     private void ensureInsertingPartitions() {
    303         if (!insertingPartitions) {
    304             throw new IllegalStateException("Cannot insert partitions after boundaries have been inserted");
    305         }
    306     }
    307 }