AbstractBSPTreeMergeOperator.java

  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. import org.apache.commons.geometry.core.Point;
  19. import org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree.AbstractNode;

  20. /** Class containing the basic algorithm for merging two {@link AbstractBSPTree}
  21.  * instances. Subclasses must override the
  22.  * {@link #mergeLeaf(AbstractBSPTree.AbstractNode, AbstractBSPTree.AbstractNode)} method
  23.  * to implement the merging logic for their particular use case. The remainder of the
  24.  * algorithm is independent of the use case.
  25.  *
  26.  * <p>This class does not expose any public methods so that subclasses can present their own
  27.  * public API, tailored to the specific types being worked with. In particular, most subclasses
  28.  * will want to restrict the tree types used with the algorithm, which is difficult to implement
  29.  * cleanly at this level.</p>
  30.  *
  31.  * <p>This class maintains state during the merging process and is therefore
  32.  * <em>not</em> thread-safe.</p>
  33.  * @param <P> Point implementation type
  34.  * @param <N> BSP tree node implementation type
  35.  */
  36. public abstract class AbstractBSPTreeMergeOperator<P extends Point<P>, N extends AbstractNode<P, N>> {

  37.     /** The tree that the merge operation output will be written to. All existing content
  38.      * in this tree is overwritten.
  39.      */
  40.     private AbstractBSPTree<P, N> outputTree;

  41.     /** Set the tree used as output for this instance.
  42.      * @param outputTree the tree used as output for this instance
  43.      */
  44.     protected void setOutputTree(final AbstractBSPTree<P, N> outputTree) {
  45.         this.outputTree = outputTree;
  46.     }

  47.     /** Get the tree used as output for this instance.
  48.      * @return the tree used as output for this instance
  49.      */
  50.     protected AbstractBSPTree<P, N> getOutputTree() {
  51.         return outputTree;
  52.     }

  53.     /** Perform a merge operation with the two input trees and store the result in the output tree. The
  54.      * output tree may be one of the input trees, in which case, the tree is modified in place.
  55.      * @param input1 first input tree
  56.      * @param input2 second input tree
  57.      * @param output output tree all previous content in this tree is overwritten
  58.      */
  59.     protected void performMerge(final AbstractBSPTree<P, N> input1, final AbstractBSPTree<P, N> input2,
  60.             final AbstractBSPTree<P, N> output) {

  61.         setOutputTree(output);

  62.         final N root1 = input1.getRoot();
  63.         final N root2 = input2.getRoot();

  64.         final N outputRoot = performMergeRecursive(root1, root2);

  65.         getOutputTree().setRoot(outputRoot);
  66.     }

  67.     /** Recursively merge two nodes.
  68.      * @param node1 node from the first input tree
  69.      * @param node2 node from the second input tree
  70.      * @return a merged node
  71.      */
  72.     private N performMergeRecursive(final N node1, final N node2) {

  73.         if (node1.isLeaf() || node2.isLeaf()) {
  74.             // delegate to the mergeLeaf method if we can no longer continue
  75.             // merging recursively
  76.             final N merged = mergeLeaf(node1, node2);

  77.             // copy the merged node to the output if needed (in case mergeLeaf
  78.             // returned one of the input nodes directly)
  79.             return outputTree.importSubtree(merged);
  80.         } else {
  81.             final N partitioned = outputTree.splitSubtree(node2, node1.getCut());

  82.             final N minus = performMergeRecursive(node1.getMinus(), partitioned.getMinus());

  83.             final N plus = performMergeRecursive(node1.getPlus(), partitioned.getPlus());

  84.             final N outputNode = outputTree.copyNode(node1);
  85.             outputNode.setSubtree(node1.getCut(), minus, plus);

  86.             return outputNode;
  87.         }
  88.     }

  89.     /** Create a new node in the output tree. The node is associated with the output tree but
  90.      * is not attached to a parent node.
  91.      * @return a new node associated with the output tree but not yet attached to a parent
  92.      */
  93.     protected N outputNode() {
  94.         return outputTree.createNode();
  95.     }

  96.     /** Place the subtree rooted at the given input node into the output tree. The subtree
  97.      * is copied if needed.
  98.      * @param node the root of the subtree to copy
  99.      * @return a subtree in the output tree
  100.      */
  101.     protected N outputSubtree(final N node) {
  102.         return outputTree.importSubtree(node);
  103.     }

  104.     /** Merge a leaf node from one input with a subtree from another.
  105.      * <p>When this method is called, one or both of the given nodes will be a leaf node.
  106.      * This method is expected to return a node representing the merger of the two given
  107.      * nodes. The way that the returned node is determined defines the overall behavior of
  108.      * the merge operation.
  109.      * </p>
  110.      * <p>The return value can be one of the two input nodes or a completely different one.</p>
  111.      * @param node1 node from the first input tree
  112.      * @param node2 node from the second input tree
  113.      * @return node representing the merger of the two input nodes
  114.      */
  115.     protected abstract N mergeLeaf(N node1, N node2);
  116. }