Class AbstractBSPTreeMergeOperator<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>>

java.lang.Object
org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTreeMergeOperator<P,N>
Type Parameters:
P - Point implementation type
N - BSP tree node implementation type
Direct Known Subclasses:
AbstractRegionBSPTree.RegionMergeOperator

public abstract class AbstractBSPTreeMergeOperator<P extends Point<P>,N extends AbstractBSPTree.AbstractNode<P,N>> extends Object
Class containing the basic algorithm for merging two AbstractBSPTree instances. Subclasses must override the mergeLeaf(AbstractBSPTree.AbstractNode, AbstractBSPTree.AbstractNode) method to implement the merging logic for their particular use case. The remainder of the algorithm is independent of the use case.

This class does not expose any public methods so that subclasses can present their own public API, tailored to the specific types being worked with. In particular, most subclasses will want to restrict the tree types used with the algorithm, which is difficult to implement cleanly at this level.

This class maintains state during the merging process and is therefore not thread-safe.

  • Field Details

  • Constructor Details

    • AbstractBSPTreeMergeOperator

      public AbstractBSPTreeMergeOperator()
  • Method Details

    • setOutputTree

      protected void setOutputTree(AbstractBSPTree<P,N> outputTree)
      Set the tree used as output for this instance.
      Parameters:
      outputTree - the tree used as output for this instance
    • getOutputTree

      protected AbstractBSPTree<P,N> getOutputTree()
      Get the tree used as output for this instance.
      Returns:
      the tree used as output for this instance
    • performMerge

      protected void performMerge(AbstractBSPTree<P,N> input1, AbstractBSPTree<P,N> input2, AbstractBSPTree<P,N> output)
      Perform a merge operation with the two input trees and store the result in the output tree. The output tree may be one of the input trees, in which case, the tree is modified in place.
      Parameters:
      input1 - first input tree
      input2 - second input tree
      output - output tree all previous content in this tree is overwritten
    • performMergeRecursive

      private N performMergeRecursive(N node1, N node2)
      Recursively merge two nodes.
      Parameters:
      node1 - node from the first input tree
      node2 - node from the second input tree
      Returns:
      a merged node
    • outputNode

      protected N outputNode()
      Create a new node in the output tree. The node is associated with the output tree but is not attached to a parent node.
      Returns:
      a new node associated with the output tree but not yet attached to a parent
    • outputSubtree

      protected N outputSubtree(N node)
      Place the subtree rooted at the given input node into the output tree. The subtree is copied if needed.
      Parameters:
      node - the root of the subtree to copy
      Returns:
      a subtree in the output tree
    • mergeLeaf

      protected abstract N mergeLeaf(N node1, N node2)
      Merge a leaf node from one input with a subtree from another.

      When this method is called, one or both of the given nodes will be a leaf node. This method is expected to return a node representing the merger of the two given nodes. The way that the returned node is determined defines the overall behavior of the merge operation.

      The return value can be one of the two input nodes or a completely different one.

      Parameters:
      node1 - node from the first input tree
      node2 - node from the second input tree
      Returns:
      node representing the merger of the two input nodes