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.Deque;
    20  import java.util.Iterator;
    21  import java.util.LinkedList;
    22  import java.util.NoSuchElementException;
    23
    24  import org.apache.commons.geometry.core.Point;
    25  import org.apache.commons.geometry.core.Transform;
    26  import org.apache.commons.geometry.core.partitioning.Hyperplane;
    27  import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset;
    28  import org.apache.commons.geometry.core.partitioning.HyperplaneLocation;
    29  import org.apache.commons.geometry.core.partitioning.Split;
    30  import org.apache.commons.geometry.core.partitioning.SplitLocation;
    31
    32  /** Abstract class for Binary Space Partitioning (BSP) tree implementations. This
    33   * class contains basic structures and algorithms that should be common
    34   * to all BSP tree implementations, regardless of the end use cases for the tree
    35   * (eg, whether the tree is intended to represent polytopes, hold attributes like
    36   * a map, etc).
    37   *
    38   * <h2>Implementation Notes</h2>
    39   * <ul>
    40   *      <li>The {@link AbstractBSPTree} class is designed to work closely with its nested node type,
    41   *      {@link AbstractNode}. The tree class handles all tree manipulation operations while the node type
    42   *      is primarily a simple data type and delegates tree operations to internal methods within its
    43   *      parent tree. This allows for easier overriding of tree behavior in subclasses.</li>
    44   *      <li>Each time the structure of the tree is modified, a {@link #getVersion() version number} is
    45   *      incremented in the tree. This allows certain tree properties to be computed lazily and then
    46   *      cached. The tree version number is incremented with the {@link #invalidate() invalidate} method. Properties
    47   *      can be cached directly on nodes using the {@link AbstractBSPTree.AbstractNode#checkValid() checkValid}
    48   *      and {@link AbstractBSPTree.AbstractNode#nodeInvalidated() nodeInvalidated} methods.</li>
    49   *      <li>Since the methods used to construct and modify trees can vary by use case, no public API is provided
    50   *      for manipulating the tree. Subclasses are expected to use the protected methods of this class to
    51   *      create their own. For tree construction, subclasses are expected to pass their own {@link SubtreeInitializer}
    52   *      instances to {@link #insert(HyperplaneConvexSubset, SubtreeInitializer) insert} and
    53   *      {@link #cutNode(AbstractNode, Hyperplane, SubtreeInitializer) cutNode} in order to set the correct properties on
    54   *      tree nodes. To support tree copying, subclasses must also override
    55   *      {@link #copyNodeProperties(AbstractNode, AbstractNode) copyNodeProperties}.</li>
    56   *      <li>This class is not thread safe.</li>
    57   * </ul>
    58   *
    59   * @param <P> Point implementation type
    60   * @param <N> BSP tree node implementation type
    61   * @see BSPTree
    62   */
    63  public abstract class AbstractBSPTree<P extends Point<P>, N extends AbstractBSPTree.AbstractNode<P, N>>
    64      implements BSPTree<P, N> {
    65
    66      /** Interface used to initialize newly created BSP subtrees, consisting of a single parent
    67       * node and two child nodes.
    68       * @param <N> BSP tree node implementation type
    69       */
    70      @FunctionalInterface
    71      public interface SubtreeInitializer<N extends AbstractBSPTree.AbstractNode<?, ?>> {
    72
    73          /** Initialize the given newly-created subtree. The subtree consists of a single root node and two
    74           * child nodes.
    75           * @param root the root node of the new subtree
    76           */
    77          void initSubtree(N root);
    78      }
    79
    80      /** The default number of levels to print when creating a string representation of the tree. */
    81      private static final int DEFAULT_TREE_STRING_MAX_DEPTH = 8;
    82
    83      /** Integer value set on various node fields when a value is unknown. */
    84      private static final int UNKNOWN_VALUE = -1;
    85
    86      /** The root node for the tree. */
    87      private N root;
    88
    89      /** The current modification version for the tree structure. This is incremented each time
    90       * a structural change occurs in the tree and is used to determine when cached values
    91       * must be recomputed.
    92       */
    93      private int version;
    94
    95      /** {@inheritDoc} */
    96      @Override
    97      public N getRoot() {
    98          if (root == null) {
    99              setRoot(createNode());
    100         }
    101         return root;
    102     }
    103
    104     /** Set the root node for the tree. Cached tree properties are invalidated
    105      * with {@link #invalidate()}.
    106      * @param root new root node for the tree
    107      */
    108     protected void setRoot(final N root) {
    109         this.root = root;
    110
    111         this.root.makeRoot();
    112
    113         invalidate();
    114     }
    115
    116     /** {@inheritDoc} */
    117     @Override
    118     public int count() {
    119         return getRoot().count();
    120     }
    121
    122     /** {@inheritDoc} */
    123     @Override
    124     public int height() {
    125         return getRoot().height();
    126     }
    127
    128     /** {@inheritDoc} */
    129     @Override
    130     public void accept(final BSPTreeVisitor<P, N> visitor) {
    131         accept(getRoot(), visitor);
    132     }
    133
    134     /** {@inheritDoc} */
    135     @Override
    136     public N findNode(final P pt, final FindNodeCutRule cutBehavior) {
    137         return findNode(getRoot(), pt, cutBehavior);
    138     }
    139
    140     /** {@inheritDoc} */
    141     @Override
    142     public Iterable<N> nodes() {
    143         return () -> new NodeIterator<>(getRoot());
    144     }
    145
    146     /** {@inheritDoc} */
    147     @Override
    148     public void copy(final BSPTree<P, N> src) {
    149         copySubtree(src.getRoot(), getRoot());
    150     }
    151
    152     /** {@inheritDoc} */
    153     @Override
    154     public void extract(final N node) {
    155         // copy downward
    156         final N extracted = importSubtree(node);
    157
    158         // extract upward
    159         final N newRoot = extractParentPath(node, extracted);
    160
    161         // set the root of this tree
    162         setRoot(newRoot);
    163     }
    164
    165     /** {@inheritDoc} */
    166     @Override
    167     public void transform(final Transform<P> transform) {
    168         final boolean swapChildren = swapsInsideOutside(transform);
    169         transformRecursive(getRoot(), transform, swapChildren);
    170
    171         invalidate();
    172     }
    173
    174     /** Get a simple string representation of the tree structure. The returned string contains
    175      * the tree structure down to the default max depth of {@value #DEFAULT_TREE_STRING_MAX_DEPTH}.
    176      * @return a string representation of the tree
    177      */
    178     public String treeString() {
    179         return treeString(DEFAULT_TREE_STRING_MAX_DEPTH);
    180     }
    181
    182     /** Get a simple string representation of the tree structure. The returned string contains
    183      * the tree structure down to {@code maxDepth}.
    184      * @param maxDepth the maximum depth in the tree to print; nodes below this depth are skipped
    185      * @return a string representation of the tree
    186      */
    187     public String treeString(final int maxDepth) {
    188         final BSPTreePrinter<P, N> printer = new BSPTreePrinter<>(maxDepth);
    189         accept(printer);
    190
    191         return printer.toString();
    192     }
    193
    194     /** {@inheritDoc} */
    195     @Override
    196     public String toString() {
    197         return new StringBuilder()
    198                 .append(getClass().getSimpleName())
    199                 .append("[count= ")
    200                 .append(count())
    201                 .append(", height= ")
    202                 .append(height())
    203                 .append("]")
    204                 .toString();
    205     }
    206
    207     /** Create a new node for this tree.
    208      * @return a new node for this tree
    209      */
    210     protected abstract N createNode();
    211
    212     /** Copy non-structural node properties from {@code src} to {@code dst}.
    213      * Non-structural properties are those properties not directly related
    214      * to the structure of the BSP tree, i.e. properties other than parent/child
    215      * connections and cuts. Subclasses should override this method to copy additional
    216      * properties stored on nodes.
    217      * @param src source node
    218      * @param dst destination node
    219      */
    220     protected abstract void copyNodeProperties(N src, N dst);
    221
    222     /** Create a non-structural copy of the given node. Properties such as parent/child
    223      * connections and cuts are <em>not</em> copied.
    224      * @param src the node to copy; does not need to belong to the current tree
    225      * @return the copied node
    226      * @see AbstractBSPTree#copyNodeProperties(AbstractNode, AbstractNode)
    227      */
    228     protected N copyNode(final N src) {
    229         final N copy = createNode();
    230         copyNodeProperties(src, copy);
    231
    232         return copy;
    233     }
    234
    235     /** Recursively copy a subtree. The returned node is not attached to the current tree.
    236      * Structural <em>and</em> non-structural properties are copied from the source subtree
    237      * to the destination subtree. This method does nothing if {@code src} and {@code dst}
    238      * reference the same node.
    239      * @param src the node representing the source subtree; does not need to belong to the
    240      *      current tree
    241      * @param dst the node representing the destination subtree
    242      * @return the copied node, ie {@code dst}
    243      */
    244     protected N copySubtree(final N src, final N dst) {
    245         // only copy if we're actually switching nodes
    246         if (src != dst) {
    247             // copy non-structural properties
    248             copyNodeProperties(src, dst);
    249
    250             // copy the subtree structure
    251             HyperplaneConvexSubset<P> cut = null;
    252             N minus = null;
    253             N plus = null;
    254
    255             if (!src.isLeaf()) {
    256                 final AbstractBSPTree<P, N> dstTree = dst.getTree();
    257
    258                 cut = src.getCut();
    259                 minus = copySubtree(src.getMinus(), dstTree.createNode());
    260                 plus = copySubtree(src.getPlus(), dstTree.createNode());
    261             }
    262
    263             dst.setSubtree(cut, minus, plus);
    264         }
    265
    266         return dst;
    267     }
    268
    269     /** Import the subtree represented by the given node into this tree. If the given node
    270      * already belongs to this tree, then the node is returned directly without modification.
    271      * If the node does <em>not</em> belong to this tree, a new node is created and the src node
    272      * subtree is copied into it.
    273      *
    274      * <p>This method does not modify the current structure of the tree.</p>
    275      * @param src node to import
    276      * @return the given node if it belongs to this tree, otherwise a new node containing
    277      *      a copy of the given node's subtree
    278      * @see #copySubtree(AbstractNode, AbstractNode)
    279      */
    280     protected N importSubtree(final N src) {
    281         // create a copy of the node if it's not already in this tree
    282         if (src.getTree() != this) {
    283             return copySubtree(src, createNode());
    284         }
    285
    286         return src;
    287     }
    288
    289     /** Extract the path from {@code src} to the root of its tree and
    290      * set it as the parent path of {@code dst}. Leaf nodes created during
    291      * the extraction are given the same node properties as their counterparts
    292      * in the source tree but without the cuts and child nodes. The properties
    293      * of {@code dst} are not modified, with the exception of its parent node
    294      * reference.
    295      * @param src the source node to copy the parent path from
    296      * @param dst the destination node to place under the extracted path
    297      * @return the root node of the extracted path
    298      */
    299     protected N extractParentPath(final N src, final N dst) {
    300         N dstParent = dst;
    301         N dstChild;
    302
    303         N srcChild = src;
    304         N srcParent = srcChild.getParent();
    305
    306         while (srcParent != null) {
    307             dstChild = dstParent;
    308             dstParent = copyNode(srcParent);
    309
    310             if (srcChild.isMinus()) {
    311                 dstParent.setSubtree(
    312                         srcParent.getCut(),
    313                         dstChild,
    314                         copyNode(srcParent.getPlus()));
    315             } else {
    316                 dstParent.setSubtree(
    317                         srcParent.getCut(),
    318                         copyNode(srcParent.getMinus()),
    319                         dstChild);
    320             }
    321
    322             srcChild = srcParent;
    323             srcParent = srcChild.getParent();
    324         }
    325
    326         return dstParent;
    327     }
    328
    329     /** Find the smallest node in the tree containing the point, starting
    330      * at the given node.
    331      * @param start the node to begin the search with
    332      * @param pt the point to check
    333      * @param cutRule value determining the search behavior when the test point
    334      *      lies directly on the cut of an internal node
    335      * @return the smallest node in the tree containing the point
    336      */
    337     protected N findNode(final N start, final P pt, final FindNodeCutRule cutRule) {
    338         final Hyperplane<P> cutHyper = start.getCutHyperplane();
    339         if (cutHyper != null) {
    340             final HyperplaneLocation cutLoc = cutHyper.classify(pt);
    341
    342             final boolean onPlusSide = cutLoc == HyperplaneLocation.PLUS;
    343             final boolean onMinusSide = cutLoc == HyperplaneLocation.MINUS;
    344             final boolean onCut = !onPlusSide && !onMinusSide;
    345
    346             if (onMinusSide || (onCut && cutRule == FindNodeCutRule.MINUS)) {
    347                 return findNode(start.getMinus(), pt, cutRule);
    348             } else if (onPlusSide || cutRule == FindNodeCutRule.PLUS) {
    349                 return findNode(start.getPlus(), pt, cutRule);
    350             }
    351         }
    352         return start;
    353     }
    354
    355     /** Visit the nodes in a subtree.
    356      * @param node the node to begin the visit process
    357      * @param visitor the visitor to pass nodes to
    358      */
    359     protected void accept(final N node, final BSPTreeVisitor<P, N> visitor) {
    360         acceptRecursive(node, visitor);
    361     }
    362
    363     /** Recursively visit the nodes in the subtree rooted at the given node.
    364      * @param node the node located at the root of the subtree to visit
    365      * @param visitor the visitor to pass nodes to
    366      * @return true if the visit operation should continue
    367      */
    368     private boolean acceptRecursive(final N node, final BSPTreeVisitor<P, N> visitor) {
    369         if (node.isLeaf()) {
    370             return shouldContinueVisit(visitor.visit(node));
    371         } else {
    372             final BSPTreeVisitor.Order order = visitor.visitOrder(node);
    373
    374             if (order != null) {
    375
    376                 switch (order) {
    377                 case PLUS_MINUS_NODE:
    378                     return acceptRecursive(node.getPlus(), visitor) &&
    379                             acceptRecursive(node.getMinus(), visitor) &&
    380                             shouldContinueVisit(visitor.visit(node));
    381                 case PLUS_NODE_MINUS:
    382                     return acceptRecursive(node.getPlus(), visitor) &&
    383                             shouldContinueVisit(visitor.visit(node)) &&
    384                             acceptRecursive(node.getMinus(), visitor);
    385                 case MINUS_PLUS_NODE:
    386                     return acceptRecursive(node.getMinus(), visitor) &&
    387                             acceptRecursive(node.getPlus(), visitor) &&
    388                             shouldContinueVisit(visitor.visit(node));
    389                 case MINUS_NODE_PLUS:
    390                     return acceptRecursive(node.getMinus(), visitor) &&
    391                             shouldContinueVisit(visitor.visit(node)) &&
    392                             acceptRecursive(node.getPlus(), visitor);
    393                 case NODE_PLUS_MINUS:
    394                     return shouldContinueVisit(visitor.visit(node)) &&
    395                             acceptRecursive(node.getPlus(), visitor) &&
    396                             acceptRecursive(node.getMinus(), visitor);
    397                 case  NODE_MINUS_PLUS:
    398                     return shouldContinueVisit(visitor.visit(node)) &&
    399                             acceptRecursive(node.getMinus(), visitor) &&
    400                             acceptRecursive(node.getPlus(), visitor);
    401                 default: // NONE
    402                     break;
    403                 }
    404             }
    405
    406             return true;
    407         }
    408     }
    409
    410     /** Return true if the given BSP tree visit result indicates that the current visit
    411      * operation should continue.
    412      * @param result visit result from BSP tree node visit operation
    413      * @return true if the visit operation should continue with remaining nodes in the
    414      *      BSP tree
    415      */
    416     private boolean shouldContinueVisit(final BSPTreeVisitor.Result result) {
    417         return result == BSPTreeVisitor.Result.CONTINUE;
    418     }
    419
    420     /** Cut a node with a hyperplane. The algorithm proceeds as follows:
    421      * <ol>
    422      *      <li>The hyperplane is trimmed by splitting it with each cut hyperplane on the
    423      *      path from the given node to the root of the tree.</li>
    424      *      <li>If the remaining portion of the hyperplane is <em>not</em> empty, then
    425      *          <ul>
    426      *              <li>the remaining portion becomes the cut hyperplane subset for the node,</li>
    427      *              <li>two new child nodes are created and initialized with
    428      *              {@code subtreeInitializer}, and</li>
    429      *              <li>true is returned.</li>
    430      *          </ul>
    431      *      </li>
    432      *      <li>If the remaining portion of the hyperplane <em>is</em> empty (ie, the
    433      *      cutting hyperplane does not intersect the node's region), then
    434      *          <ul>
    435      *              <li>the node is converted to a leaf node (meaning that previous
    436      *              child nodes are lost), and</li>
    437      *              <li>false is returned.</li>
    438      *          </ul>
    439      *      </li>
    440      * </ol>
    441      *
    442      * <p>It is important to note that since this method uses the path from given node
    443      * to the tree root, it must only be used on nodes that are already inserted into
    444      * the tree.</p>
    445      *
    446      * <p>This method calls {@link #invalidate()} to invalidate cached tree properties if the tree
    447      * structure is changed.</p>
    448      *
    449      * @param node the node to cut
    450      * @param cutter the hyperplane to cut the node with
    451      * @param subtreeInitializer object used to initialize any newly-created subtrees
    452      * @return true if the node was cut and two new child nodes were created;
    453      *      otherwise false
    454      * @see #trimToNode(AbstractNode, HyperplaneConvexSubset)
    455      * @see #setNodeCut(AbstractNode, HyperplaneConvexSubset, SubtreeInitializer)
    456      * @see #removeNodeCut(AbstractNode)
    457      * @see #invalidate()
    458      */
    459     protected boolean cutNode(final N node, final Hyperplane<P> cutter,
    460             final SubtreeInitializer<N> subtreeInitializer) {
    461
    462         // cut the hyperplane using all hyperplanes from this node up
    463         // to the root
    464         final HyperplaneConvexSubset<P> cut = trimToNode(node, cutter.span());
    465         if (cut == null || cut.isEmpty()) {
    466             // insertion failed; the node was not cut
    467             removeNodeCut(node);
    468             return false;
    469         }
    470
    471         setNodeCut(node, cut, subtreeInitializer);
    472         return true;
    473     }
    474
    475     /** Trim the given hyperplane convex subset to the region defined by the given node. This method
    476      * cuts the subset with the cut hyperplanes (binary partitioners) of all parent nodes up to the
    477      * root and returns the trimmed subset or {@code null} if the subset lies outside of the region
    478      * defined by the node.
    479      *
    480      * <p>If the subset is directly coincident with a binary partitioner of a parent node,
    481      * then the relative orientations of the associated hyperplanes are used to determine the behavior,
    482      * as described below.
    483      * <ul>
    484      *      <li>If the orientations are <strong>similar</strong>, then the subset is determined to
    485      *      lie <em>outside</em> of the node's region and {@code null} is returned.</li>
    486      *      <li>If the orientations are <strong>different</strong> (ie, opposite), then the subset
    487      *      is determined to lie <em>inside</em> of the node's region and the fit operation continues
    488      *      with the remaining parent nodes.</li>
    489      * </ul>
    490      * These rules are designed to allow the creation of trees with node regions that are the thickness
    491      * of a single hyperplane. For example, in two dimensions, a tree could be constructed with an internal
    492      * node containing a cut along the x-axis in the positive direction and with a child node containing a
    493      * cut along the x-axis in the opposite direction. If the nodes in the tree are given inside and outside
    494      * attributes, then this tree could be used to represent a region consisting of a single line or a region
    495      * consisting of the entire space except for the single line. This would not be possible if nodes were not
    496      * able to have cut hyperplanes that were coincident with parent cuts but in opposite directions.
    497      *
    498      * <p>
    499      * Another way of looking at the rules above is that inserting a hyperplane into the tree that exactly
    500      * matches the hyperplane of a parent node does not add any information to the tree. However, adding a
    501      * hyperplane to the tree that is coincident with a parent node but with the opposite orientation,
    502      * <em>does</em> add information to the tree.
    503      *
    504      * @param node the node representing the region to fit the hyperplane subset to
    505      * @param sub the hyperplane subset to trim to the node's region
    506      * @return the trimmed hyperplane subset or null if the given hyperplane subset does not intersect
    507      *      the node's region
    508      */
    509     protected HyperplaneConvexSubset<P> trimToNode(final N node, final HyperplaneConvexSubset<P> sub) {
    510
    511         HyperplaneConvexSubset<P> result = sub;
    512
    513         N parentNode = node.getParent();
    514         N currentNode = node;
    515
    516         while (parentNode != null && result != null) {
    517             final Split<? extends HyperplaneConvexSubset<P>> split = result.split(parentNode.getCutHyperplane());
    518
    519             if (split.getLocation() == SplitLocation.NEITHER) {
    520                 // if we're directly on the splitter and have the same orientation, then
    521                 // we say the subset does not lie in the node's region (no new information
    522                 // is added to the tree in this case)
    523                 if (result.getHyperplane().similarOrientation(parentNode.getCutHyperplane())) {
    524                     result = null;
    525                 }
    526             } else {
    527                 result = currentNode.isPlus() ? split.getPlus() : split.getMinus();
    528             }
    529
    530             currentNode = parentNode;
    531             parentNode = parentNode.getParent();
    532         }
    533
    534         return result;
    535     }
    536
    537     /** Remove the cut from the given node. Returns true if the node had a cut before
    538      * the call to this method. Any previous child nodes are lost.
    539      *
    540      * <p>This method calls {@link #invalidate()} to invalidate cached tree properties if the tree
    541      * structure changed.</p>
    542      * @param node the node to remove the cut from
    543      * @return true if the node previously had a cut
    544      */
    545     protected boolean removeNodeCut(final N node) {
    546         if (node.getCut() != null) {
    547             node.setSubtree(null, null, null);
    548
    549             invalidate();
    550
    551             return true;
    552         }
    553
    554         return false;
    555     }
    556
    557     /** Set the cut hyperplane subset for the given node. Two new child nodes are created for the
    558      * node and the new subtree is initialized with {@code subtreeInitializer}.
    559      *
    560      * <p>This method performs absolutely <em>no</em> validation on the given cut
    561      * hyperplane subset. It is the responsibility of the caller to ensure that the
    562      * hyperplane subset fits the region represented by the node.</p>
    563      *
    564      * <p>This method always calls {@link #invalidate()} to invalidate cached tree properties.</p>
    565      * @param node the node to cut
    566      * @param cut the hyperplane convex subset to set as the node cut
    567      * @param subtreeInitializer object used to initialize the newly-created subtree
    568      */
    569     protected void setNodeCut(final N node, final HyperplaneConvexSubset<P> cut,
    570             final SubtreeInitializer<N> subtreeInitializer) {
    571
    572         node.setSubtree(cut, createNode(), createNode());
    573
    574         subtreeInitializer.initSubtree(node);
    575
    576         invalidate();
    577     }
    578
    579     /** Insert the given hyperplane convex subset into the tree, starting at the root node. Any subtrees
    580      * created are initialized with {@code subtreeInit}.
    581      * @param convexSub hyperplane convex subset to insert into the tree
    582      * @param subtreeInit object used to initialize newly created subtrees
    583      */
    584     protected void insert(final HyperplaneConvexSubset<P> convexSub, final SubtreeInitializer<N> subtreeInit) {
    585         insertRecursive(getRoot(), convexSub,
    586                 convexSub.getHyperplane().span(), subtreeInit);
    587     }
    588
    589     /** Recursively insert a hyperplane convex subset into the tree at the given node.
    590      * @param node the node to begin insertion with
    591      * @param insert the hyperplane subset to insert
    592      * @param trimmed hyperplane subset containing the result of splitting the entire
    593      *      space with each hyperplane from this node to the root
    594      * @param subtreeInit object used to initialize newly created subtrees
    595      */
    596     private void insertRecursive(final N node, final HyperplaneConvexSubset<P> insert,
    597             final HyperplaneConvexSubset<P> trimmed, final SubtreeInitializer<N> subtreeInit) {
    598         if (node.isLeaf()) {
    599             setNodeCut(node, trimmed, subtreeInit);
    600         } else {
    601             final Split<? extends HyperplaneConvexSubset<P>> insertSplit = insert.split(node.getCutHyperplane());
    602
    603             final HyperplaneConvexSubset<P> minus = insertSplit.getMinus();
    604             final HyperplaneConvexSubset<P> plus = insertSplit.getPlus();
    605
    606             if (minus != null || plus != null) {
    607                 final Split<? extends HyperplaneConvexSubset<P>> trimmedSplit = trimmed.split(node.getCutHyperplane());
    608
    609                 if (minus != null) {
    610                     insertRecursive(node.getMinus(), minus, trimmedSplit.getMinus(), subtreeInit);
    611                 }
    612                 if (plus != null) {
    613                     insertRecursive(node.getPlus(), plus, trimmedSplit.getPlus(), subtreeInit);
    614                 }
    615             }
    616         }
    617     }
    618
    619     /** Return true if the given transform swaps the inside and outside of
    620      * the region.
    621      *
    622      * <p>The default behavior of this method is to return true if the transform
    623      * does not preserve spatial orientation (ie, {@link Transform#preservesOrientation()}
    624      * is false). Subclasses may need to override this method to implement the correct
    625      * behavior for their space and dimension.</p>
    626      * @param transform transform to check
    627      * @return true if the given transform swaps the interior and exterior of
    628      *      the region
    629      */
    630     protected boolean swapsInsideOutside(final Transform<P> transform) {
    631         return !transform.preservesOrientation();
    632     }
    633
    634     /** Transform the subtree rooted as {@code node} recursively.
    635      * @param node the root node of the subtree to transform
    636      * @param t the transform to apply
    637      * @param swapChildren if true, the plus and minus child nodes of each internal node
    638      *      will be swapped; this should be the case when the transform is a reflection
    639      */
    640     private void transformRecursive(final N node, final Transform<P> t, final boolean swapChildren) {
    641         if (node.isInternal()) {
    642             // transform our cut
    643             final HyperplaneConvexSubset<P> transformedCut = node.getCut().transform(t);
    644
    645             // transform our children
    646             transformRecursive(node.getMinus(), t, swapChildren);
    647             transformRecursive(node.getPlus(), t, swapChildren);
    648
    649             final N transformedMinus = swapChildren ? node.getPlus() : node.getMinus();
    650             final N transformedPlus = swapChildren ? node.getMinus() : node.getPlus();
    651
    652             // set our new state
    653             node.setSubtree(transformedCut, transformedMinus, transformedPlus);
    654         }
    655     }
    656
    657     /** Split this tree with the given hyperplane, placing the split contents into the given
    658      * target trees. One of the given trees may be null, in which case that portion of the split
    659      * will not be exported. The current tree is not modified.
    660      * @param splitter splitting hyperplane
    661      * @param minus tree that will contain the portion of the tree on the minus side of the splitter
    662      * @param plus tree that will contain the portion of the tree on the plus side of the splitter
    663      */
    664     protected void splitIntoTrees(final Hyperplane<P> splitter,
    665             final AbstractBSPTree<P, N> minus, final AbstractBSPTree<P, N> plus) {
    666
    667         final AbstractBSPTree<P, N> temp = (minus != null) ? minus : plus;
    668
    669         final N splitRoot = temp.splitSubtree(this.getRoot(), splitter.span());
    670
    671         if (minus != null) {
    672             if (plus != null) {
    673                 plus.extract(splitRoot.getPlus());
    674             }
    675             minus.extract(splitRoot.getMinus());
    676         } else {
    677             plus.extract(splitRoot.getPlus());
    678         }
    679     }
    680
    681     /** Split the subtree rooted at the given node by a partitioning convex subset defined
    682      * on the same region as the node. The subtree rooted at {@code node} is imported into
    683      * this tree, meaning that if it comes from a different tree, the other tree is not
    684      * modified.
    685      * @param node the root node of the subtree to split; may come from a different tree,
    686      *      in which case the other tree is not modified
    687      * @param partitioner partitioning convex subset
    688      * @return node containing the split subtree
    689      */
    690     protected N splitSubtree(final N node, final HyperplaneConvexSubset<P> partitioner) {
    691         if (node.isLeaf()) {
    692             return splitLeafNode(node, partitioner);
    693         }
    694         return splitInternalNode(node, partitioner);
    695     }
    696
    697     /** Split the given leaf node by a partitioning convex subset defined on the
    698      * same region and import it into this tree.
    699      * @param node the leaf node to split
    700      * @param partitioner partitioning convex subset
    701      * @return node containing the split subtree
    702      */
    703     private N splitLeafNode(final N node, final HyperplaneConvexSubset<P> partitioner) {
    704         // in this case, we just create a new parent node with the partitioner as its
    705         // cut and two copies of the original node as children
    706         final N parent = createNode();
    707         parent.setSubtree(partitioner, copyNode(node), copyNode(node));
    708
    709         return parent;
    710     }
    711
    712     /** Split the given internal node by a partitioning convex subset defined on the same region
    713      * as the node and import it into this tree.
    714      * @param node the internal node to split
    715      * @param partitioner partitioning convex subset
    716      * @return node containing the split subtree
    717      */
    718     private N splitInternalNode(final N node, final HyperplaneConvexSubset<P> partitioner) {
    719         // split the partitioner and node cut with each other's hyperplanes to determine their relative positions
    720         final Split<? extends HyperplaneConvexSubset<P>> partitionerSplit = partitioner.split(node.getCutHyperplane());
    721         final Split<? extends HyperplaneConvexSubset<P>> nodeCutSplit =
    722                 node.getCut().split(partitioner.getHyperplane());
    723
    724         final SplitLocation partitionerSplitSide = partitionerSplit.getLocation();
    725         final SplitLocation nodeCutSplitSide = nodeCutSplit.getLocation();
    726
    727         final N result = createNode();
    728
    729         final N resultMinus;
    730         final N resultPlus;
    731
    732         if (partitionerSplitSide == SplitLocation.PLUS) {
    733             if (nodeCutSplitSide == SplitLocation.PLUS) {
    734                 // partitioner is on node cut plus side, node cut is on partitioner plus side
    735                 final N nodePlusSplit = splitSubtree(node.getPlus(), partitioner);
    736
    737                 resultMinus = nodePlusSplit.getMinus();
    738
    739                 resultPlus = copyNode(node);
    740                 resultPlus.setSubtree(node.getCut(), importSubtree(node.getMinus()), nodePlusSplit.getPlus());
    741             } else {
    742                 // partitioner is on node cut plus side, node cut is on partitioner minus side
    743                 final N nodePlusSplit = splitSubtree(node.getPlus(), partitioner);
    744
    745                 resultMinus = copyNode(node);
    746                 resultMinus.setSubtree(node.getCut(), importSubtree(node.getMinus()), nodePlusSplit.getMinus());
    747
    748                 resultPlus = nodePlusSplit.getPlus();
    749             }
    750         } else if (partitionerSplitSide == SplitLocation.MINUS) {
    751             if (nodeCutSplitSide == SplitLocation.MINUS) {
    752                 // partitioner is on node cut minus side, node cut is on partitioner minus side
    753                 final N nodeMinusSplit = splitSubtree(node.getMinus(), partitioner);
    754
    755                 resultMinus = copyNode(node);
    756                 resultMinus.setSubtree(node.getCut(), nodeMinusSplit.getMinus(), importSubtree(node.getPlus()));
    757
    758                 resultPlus = nodeMinusSplit.getPlus();
    759             } else {
    760                 // partitioner is on node cut minus side, node cut is on partitioner plus side
    761                 final N nodeMinusSplit = splitSubtree(node.getMinus(), partitioner);
    762
    763                 resultMinus = nodeMinusSplit.getMinus();
    764
    765                 resultPlus = copyNode(node);
    766                 resultPlus.setSubtree(node.getCut(), nodeMinusSplit.getPlus(), importSubtree(node.getPlus()));
    767             }
    768         } else if (partitionerSplitSide == SplitLocation.BOTH) {
    769             // partitioner and node cut split each other
    770             final N nodeMinusSplit = splitSubtree(node.getMinus(), partitionerSplit.getMinus());
    771             final N nodePlusSplit = splitSubtree(node.getPlus(), partitionerSplit.getPlus());
    772
    773             resultMinus = copyNode(node);
    774             resultMinus.setSubtree(nodeCutSplit.getMinus(), nodeMinusSplit.getMinus(), nodePlusSplit.getMinus());
    775
    776             resultPlus = copyNode(node);
    777             resultPlus.setSubtree(nodeCutSplit.getPlus(), nodeMinusSplit.getPlus(), nodePlusSplit.getPlus());
    778         } else {
    779             // partitioner and node cut are parallel or anti-parallel
    780             final boolean sameOrientation = partitioner.getHyperplane().similarOrientation(node.getCutHyperplane());
    781
    782             resultMinus = importSubtree(sameOrientation ? node.getMinus() : node.getPlus());
    783             resultPlus = importSubtree(sameOrientation ? node.getPlus() : node.getMinus());
    784         }
    785
    786         result.setSubtree(partitioner, resultMinus, resultPlus);
    787
    788         return result;
    789     }
    790
    791     /** Invalidate any previously computed properties that rely on the internal structure of the tree.
    792      * This method must be called any time the tree's internal structure changes in order to force cacheable
    793      * tree and node properties to be recomputed the next time they are requested.
    794      *
    795      * <p>This method increments the tree's {@link #version} property.</p>
    796      * @see #getVersion()
    797      */
    798     protected void invalidate() {
    799         version = Math.max(0, version + 1); // positive values only
    800     }
    801
    802     /** Get the current structural version of the tree. This is incremented each time the
    803      * tree structure is changes and can be used by nodes to allow caching of computed values.
    804      * @return the current version of the tree structure
    805      * @see #invalidate()
    806      */
    807     protected int getVersion() {
    808         return version;
    809     }
    810
    811     /** Abstract implementation of {@link BSPTree.Node}. This class is intended for use with
    812      * {@link AbstractBSPTree} and delegates tree mutation methods back to the parent tree object.
    813      * @param <P> Point implementation type
    814      * @param <N> BSP tree node implementation type
    815      */
    816     public abstract static class AbstractNode<P extends Point<P>, N extends AbstractNode<P, N>>
    817         implements BSPTree.Node<P, N> {
    818         /** The owning tree instance. */
    819         private final AbstractBSPTree<P, N> tree;
    820
    821         /** The parent node; this will be null for the tree root node. */
    822         private N parent;
    823
    824         /** The hyperplane convex subset cutting the node's region; this will be null for leaf nodes. */
    825         private HyperplaneConvexSubset<P> cut;
    826
    827         /** The node lying on the minus side of the cut hyperplane; this will be null
    828          * for leaf nodes.
    829          */
    830         private N minus;
    831
    832         /** The node lying on the plus side of the cut hyperplane; this will be null
    833          * for leaf nodes.
    834          */
    835         private N plus;
    836
    837         /** The current version of the node. This is set to track the tree's version
    838          * and is used to detect when certain values need to be recomputed due to
    839          * structural changes in the tree.
    840          */
    841         private int nodeVersion = -1;
    842
    843         /** The depth of this node in the tree. This will be zero for the root node and
    844          * {@link AbstractBSPTree#UNKNOWN_VALUE} when the value needs to be computed.
    845          */
    846         private int depth = UNKNOWN_VALUE;
    847
    848         /** The total number of nodes in the subtree rooted at this node. This will be
    849          * set to {@link AbstractBSPTree#UNKNOWN_VALUE} when the value needs
    850          * to be computed.
    851          */
    852         private int count = UNKNOWN_VALUE;
    853
    854         /** The height of the subtree rooted at this node. This will
    855          * be set to {@link AbstractBSPTree#UNKNOWN_VALUE} when the value needs
    856          * to be computed.
    857          */
    858         private int height = UNKNOWN_VALUE;
    859
    860         /** Simple constructor.
    861          * @param tree the tree instance that owns this node
    862          */
    863         protected AbstractNode(final AbstractBSPTree<P, N> tree) {
    864             this.tree = tree;
    865         }
    866
    867         /** {@inheritDoc} */
    868         @Override
    869         public AbstractBSPTree<P, N> getTree() {
    870             return tree;
    871         }
    872
    873         /** {@inheritDoc} */
    874         @Override
    875         public int depth() {
    876             // Calculate our depth based on our parent's depth, if possible.
    877             if (depth == UNKNOWN_VALUE &&
    878                 parent != null) {
    879                 final int parentDepth = parent.depth();
    880                 if (parentDepth != UNKNOWN_VALUE) {
    881                     depth = parentDepth + 1;
    882                 }
    883             }
    884             return depth;
    885         }
    886
    887         /** {@inheritDoc} */
    888         @Override
    889         public int height() {
    890             checkValid();
    891
    892             if (height == UNKNOWN_VALUE) {
    893                 if (isLeaf()) {
    894                     height = 0;
    895                 } else {
    896                     height = Math.max(getMinus().height(), getPlus().height()) + 1;
    897                 }
    898             }
    899
    900             return height;
    901         }
    902
    903         /** {@inheritDoc} */
    904         @Override
    905         public int count() {
    906             checkValid();
    907
    908             if (count == UNKNOWN_VALUE) {
    909                 count = 1;
    910
    911                 if (!isLeaf()) {
    912                     count += minus.count() + plus.count();
    913                 }
    914             }
    915
    916             return count;
    917         }
    918
    919         /** {@inheritDoc} */
    920         @Override
    921         public Iterable<N> nodes() {
    922             return () -> new NodeIterator<>(getSelf());
    923         }
    924
    925         /** {@inheritDoc} */
    926         @Override
    927         public void accept(final BSPTreeVisitor<P, N> visitor) {
    928             tree.accept(getSelf(), visitor);
    929         }
    930
    931         /** {@inheritDoc} */
    932         @Override
    933         public N getParent() {
    934             return parent;
    935         }
    936
    937         /** {@inheritDoc} */
    938         @Override
    939         public boolean isLeaf() {
    940             return cut == null;
    941         }
    942
    943         /** {@inheritDoc} */
    944         @Override
    945         public boolean isInternal() {
    946             return cut != null;
    947         }
    948
    949         /** {@inheritDoc} */
    950         @Override
    951         public boolean isPlus() {
    952             return parent != null && parent.getPlus() == this;
    953         }
    954
    955         /** {@inheritDoc} */
    956         @Override
    957         public boolean isMinus() {
    958             return parent != null && parent.getMinus() == this;
    959         }
    960
    961         /** {@inheritDoc} */
    962         @Override
    963         public HyperplaneConvexSubset<P> getCut() {
    964             return cut;
    965         }
    966
    967         /** {@inheritDoc} */
    968         @Override
    969         public Hyperplane<P> getCutHyperplane() {
    970             return (cut != null) ? cut.getHyperplane() : null;
    971         }
    972
    973         /** {@inheritDoc} */
    974         @Override
    975         public N getPlus() {
    976             return plus;
    977         }
    978
    979         /** {@inheritDoc} */
    980         @Override
    981         public N getMinus() {
    982             return minus;
    983         }
    984
    985         /** {@inheritDoc} */
    986         @Override
    987         public HyperplaneConvexSubset<P> trim(final HyperplaneConvexSubset<P> sub) {
    988             return getTree().trimToNode(getSelf(), sub);
    989         }
    990
    991         /** {@inheritDoc} */
    992         @Override
    993         public String toString() {
    994             final StringBuilder sb = new StringBuilder();
    995             sb.append(this.getClass().getSimpleName())
    996                 .append("[cut= ")
    997                 .append(getCut())
    998                 .append(']');
    999
    1000             return sb.toString();
    1001         }
    1002
    1003         /** Set the parameters for the subtree rooted at this node. The arguments should either be
    1004          * all null (representing a leaf node) or all non-null (representing an internal node).
    1005          *
    1006          * <p>Absolutely no validation is performed on the arguments. Callers are responsible for
    1007          * ensuring that any given hyperplane subset fits the region defined by the node and that
    1008          * any child nodes belong to this tree and are correctly initialized.</p>
    1009          *
    1010          * @param newCut the new cut hyperplane subset for the node
    1011          * @param newMinus the new minus child for the node
    1012          * @param newPlus the new plus child for the node
    1013          */
    1014         protected void setSubtree(final HyperplaneConvexSubset<P> newCut, final N newMinus, final N newPlus) {
    1015             this.cut = newCut;
    1016
    1017             final N self = getSelf();
    1018
    1019             // cast for access to private member
    1020             final AbstractNode<P, N> minusNode = newMinus;
    1021             final AbstractNode<P, N> plusNode = newPlus;
    1022
    1023             // get the child depth now if we know it offhand, otherwise set it to the unknown value
    1024             // and have the child pull it when needed
    1025             final int childDepth = (depth != UNKNOWN_VALUE) ? depth + 1 : UNKNOWN_VALUE;
    1026
    1027             if (newMinus != null) {
    1028                 minusNode.parent = self;
    1029                 minusNode.depth = childDepth;
    1030             }
    1031             this.minus = newMinus;
    1032
    1033             if (newPlus != null) {
    1034                 plusNode.parent = self;
    1035                 plusNode.depth = childDepth;
    1036             }
    1037             this.plus = newPlus;
    1038         }
    1039
    1040         /**
    1041          * Make this node a root node, detaching it from its parent and settings its depth to zero.
    1042          * Any previous parent node will be left in an invalid state since one of its children now
    1043          * does not have a reference back to it.
    1044          */
    1045         protected void makeRoot() {
    1046             parent = null;
    1047             depth = 0;
    1048         }
    1049
    1050         /** Check if cached node properties are valid, meaning that no structural updates have
    1051          * occurred in the tree since the last call to this method. If updates have occurred, the
    1052          * {@link #nodeInvalidated()} method is called to clear the cached properties. This method
    1053          * should be called at the beginning of any method that fetches cacheable properties
    1054          * to ensure that no stale values are returned.
    1055          */
    1056         protected void checkValid() {
    1057             final int treeVersion = tree.getVersion();
    1058
    1059             if (nodeVersion != treeVersion) {
    1060                 // the tree structure changed somewhere
    1061                 nodeInvalidated();
    1062
    1063                 // store the current version
    1064                 nodeVersion = treeVersion;
    1065             }
    1066         }
    1067
    1068         /** Method called from {@link #checkValid()} when updates
    1069          * are detected in the tree. This method should clear out any
    1070          * computed properties that rely on the structure of the tree
    1071          * and prepare them for recalculation.
    1072          */
    1073         protected void nodeInvalidated() {
    1074             count = UNKNOWN_VALUE;
    1075             height = UNKNOWN_VALUE;
    1076         }
    1077
    1078         /** Get a reference to the current instance, cast to type N.
    1079          * @return a reference to the current instance, as type N.
    1080          */
    1081         protected abstract N getSelf();
    1082     }
    1083
    1084     /** Class for iterating through the nodes in a BSP subtree.
    1085      * @param <P> Point implementation type
    1086      * @param <N> Node implementation type
    1087      */
    1088     private static final class NodeIterator<P extends Point<P>, N extends AbstractNode<P, N>> implements Iterator<N> {
    1089
    1090         /** The current node stack. */
    1091         private final Deque<N> stack = new LinkedList<>();
    1092
    1093         /** Create a new instance for iterating over the nodes in the given subtree.
    1094          * @param subtreeRoot the root node of the subtree to iterate
    1095          */
    1096         NodeIterator(final N subtreeRoot) {
    1097             stack.push(subtreeRoot);
    1098         }
    1099
    1100         /** {@inheritDoc} */
    1101         @Override
    1102         public boolean hasNext() {
    1103             return !stack.isEmpty();
    1104         }
    1105
    1106         /** {@inheritDoc} */
    1107         @Override
    1108         public N next() {
    1109             if (stack.isEmpty()) {
    1110                 throw new NoSuchElementException();
    1111             }
    1112
    1113             final N result = stack.pop();
    1114
    1115             if (result != null && !result.isLeaf()) {
    1116                 stack.push(result.getPlus());
    1117                 stack.push(result.getMinus());
    1118             }
    1119
    1120             return result;
    1121         }
    1122     }
    1123 }