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 }