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 org.apache.commons.geometry.core.Point;
    20  import org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree.AbstractNode;
    21
    22  /** Class containing the basic algorithm for merging two {@link AbstractBSPTree}
    23   * instances. Subclasses must override the
    24   * {@link #mergeLeaf(AbstractBSPTree.AbstractNode, AbstractBSPTree.AbstractNode)} method
    25   * to implement the merging logic for their particular use case. The remainder of the
    26   * algorithm is independent of the use case.
    27   *
    28   * <p>This class does not expose any public methods so that subclasses can present their own
    29   * public API, tailored to the specific types being worked with. In particular, most subclasses
    30   * will want to restrict the tree types used with the algorithm, which is difficult to implement
    31   * cleanly at this level.</p>
    32   *
    33   * <p>This class maintains state during the merging process and is therefore
    34   * <em>not</em> thread-safe.</p>
    35   * @param <P> Point implementation type
    36   * @param <N> BSP tree node implementation type
    37   */
    38  public abstract class AbstractBSPTreeMergeOperator<P extends Point<P>, N extends AbstractNode<P, N>> {
    39
    40      /** The tree that the merge operation output will be written to. All existing content
    41       * in this tree is overwritten.
    42       */
    43      private AbstractBSPTree<P, N> outputTree;
    44
    45      /** Set the tree used as output for this instance.
    46       * @param outputTree the tree used as output for this instance
    47       */
    48      protected void setOutputTree(final AbstractBSPTree<P, N> outputTree) {
    49          this.outputTree = outputTree;
    50      }
    51
    52      /** Get the tree used as output for this instance.
    53       * @return the tree used as output for this instance
    54       */
    55      protected AbstractBSPTree<P, N> getOutputTree() {
    56          return outputTree;
    57      }
    58
    59      /** Perform a merge operation with the two input trees and store the result in the output tree. The
    60       * output tree may be one of the input trees, in which case, the tree is modified in place.
    61       * @param input1 first input tree
    62       * @param input2 second input tree
    63       * @param output output tree all previous content in this tree is overwritten
    64       */
    65      protected void performMerge(final AbstractBSPTree<P, N> input1, final AbstractBSPTree<P, N> input2,
    66              final AbstractBSPTree<P, N> output) {
    67
    68          setOutputTree(output);
    69
    70          final N root1 = input1.getRoot();
    71          final N root2 = input2.getRoot();
    72
    73          final N outputRoot = performMergeRecursive(root1, root2);
    74
    75          getOutputTree().setRoot(outputRoot);
    76      }
    77
    78      /** Recursively merge two nodes.
    79       * @param node1 node from the first input tree
    80       * @param node2 node from the second input tree
    81       * @return a merged node
    82       */
    83      private N performMergeRecursive(final N node1, final N node2) {
    84
    85          if (node1.isLeaf() || node2.isLeaf()) {
    86              // delegate to the mergeLeaf method if we can no longer continue
    87              // merging recursively
    88              final N merged = mergeLeaf(node1, node2);
    89
    90              // copy the merged node to the output if needed (in case mergeLeaf
    91              // returned one of the input nodes directly)
    92              return outputTree.importSubtree(merged);
    93          } else {
    94              final N partitioned = outputTree.splitSubtree(node2, node1.getCut());
    95
    96              final N minus = performMergeRecursive(node1.getMinus(), partitioned.getMinus());
    97
    98              final N plus = performMergeRecursive(node1.getPlus(), partitioned.getPlus());
    99
    100             final N outputNode = outputTree.copyNode(node1);
    101             outputNode.setSubtree(node1.getCut(), minus, plus);
    102
    103             return outputNode;
    104         }
    105     }
    106
    107     /** Create a new node in the output tree. The node is associated with the output tree but
    108      * is not attached to a parent node.
    109      * @return a new node associated with the output tree but not yet attached to a parent
    110      */
    111     protected N outputNode() {
    112         return outputTree.createNode();
    113     }
    114
    115     /** Place the subtree rooted at the given input node into the output tree. The subtree
    116      * is copied if needed.
    117      * @param node the root of the subtree to copy
    118      * @return a subtree in the output tree
    119      */
    120     protected N outputSubtree(final N node) {
    121         return outputTree.importSubtree(node);
    122     }
    123
    124     /** Merge a leaf node from one input with a subtree from another.
    125      * <p>When this method is called, one or both of the given nodes will be a leaf node.
    126      * This method is expected to return a node representing the merger of the two given
    127      * nodes. The way that the returned node is determined defines the overall behavior of
    128      * the merge operation.
    129      * </p>
    130      * <p>The return value can be one of the two input nodes or a completely different one.</p>
    131      * @param node1 node from the first input tree
    132      * @param node2 node from the second input tree
    133      * @return node representing the merger of the two input nodes
    134      */
    135     protected abstract N mergeLeaf(N node1, N node2);
    136 }