/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.math3.geometry.partitioning;

import java.util.ArrayList;
import java.util.List;

import org.apache.commons.math3.exception.MathIllegalStateException;
import org.apache.commons.math3.exception.MathInternalError;
import org.apache.commons.math3.exception.util.LocalizedFormats;
import org.apache.commons.math3.geometry.Point;
import org.apache.commons.math3.geometry.Space;
import org.apache.commons.math3.geometry.Vector;
import org.apache.commons.math3.util.FastMath;

This class represent a Binary Space Partition tree.
BSP trees are an efficient way to represent space partitions and
to associate attributes with each cell. Each node in a BSP tree
represents a convex region which is partitioned in two convex
sub-regions at each side of a cut hyperplane. The root tree
contains the complete space.
The main use of such partitions is to use a boolean attribute to
define an inside/outside property, hence representing arbitrary
polytopes (line segments in 1D, polygons in 2D and polyhedrons in
3D) and to operate on them.
Another example would be to represent Voronoi tesselations, the
attribute of each cell holding the defining point of the cell.
The application-defined attributes are shared among copied
instances and propagated to split parts. These attributes are not
used by the BSP-tree algorithms themselves, so the application can
use them for any purpose. Since the tree visiting method holds
internal and leaf nodes differently, it is possible to use
different classes for internal nodes attributes and leaf nodes
attributes. This should be used with care, though, because if the
tree is modified in any way after attributes have been set, some
internal nodes may become leaf nodes and some leaf nodes may become
internal nodes.
One of the main sources for the development of this package was
Bruce Naylor, John Amanatides and William Thibault paper Merging
BSP Trees Yields Polyhedral Set Operations Proc. Siggraph '90,
Computer Graphics 24(4), August 1990, pp 115-124, published by the
Association for Computing Machinery (ACM).
Type parameters:
<S> – Type of the space.
Since:
3.0/** This class represent a Binary Space Partition tree.

 * <p>BSP trees are an efficient way to represent space partitions and
 * to associate attributes with each cell. Each node in a BSP tree
 * represents a convex region which is partitioned in two convex
 * sub-regions at each side of a cut hyperplane. The root tree
 * contains the complete space.</p>

 * <p>The main use of such partitions is to use a boolean attribute to
 * define an inside/outside property, hence representing arbitrary
 * polytopes (line segments in 1D, polygons in 2D and polyhedrons in
 * 3D) and to operate on them.</p>

 * <p>Another example would be to represent Voronoi tesselations, the
 * attribute of each cell holding the defining point of the cell.</p>

 * <p>The application-defined attributes are shared among copied
 * instances and propagated to split parts. These attributes are not
 * used by the BSP-tree algorithms themselves, so the application can
 * use them for any purpose. Since the tree visiting method holds
 * internal and leaf nodes differently, it is possible to use
 * different classes for internal nodes attributes and leaf nodes
 * attributes. This should be used with care, though, because if the
 * tree is modified in any way after attributes have been set, some
 * internal nodes may become leaf nodes and some leaf nodes may become
 * internal nodes.</p>

 * <p>One of the main sources for the development of this package was
 * Bruce Naylor, John Amanatides and William Thibault paper <a
 * href="http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf">Merging
 * BSP Trees Yields Polyhedral Set Operations</a> Proc. Siggraph '90,
 * Computer Graphics 24(4), August 1990, pp 115-124, published by the
 * Association for Computing Machinery (ACM).</p>

 * @param <S> Type of the space.

 * @since 3.0
 */
public class BSPTree<S extends Space> {

    
Cut sub-hyperplane. /** Cut sub-hyperplane. */
    private SubHyperplane<S> cut;

    
Tree at the plus side of the cut hyperplane. /** Tree at the plus side of the cut hyperplane. */
    private BSPTree<S> plus;

    
Tree at the minus side of the cut hyperplane. /** Tree at the minus side of the cut hyperplane. */
    private BSPTree<S> minus;

    
Parent tree. /** Parent tree. */
    private BSPTree<S> parent;

    
Application-defined attribute. /** Application-defined attribute. */
    private Object attribute;

    
Build a tree having only one root cell representing the whole space.
/** Build a tree having only one root cell representing the whole space.
     */
    public BSPTree() {
        cut       = null;
        plus      = null;
        minus     = null;
        parent    = null;
        attribute = null;
    }

    
Build a tree having only one root cell representing the whole space.
Params:
attribute – attribute of the tree (may be null)/** Build a tree having only one root cell representing the whole space.
     * @param attribute attribute of the tree (may be null)
     */
    public BSPTree(final Object attribute) {
        cut    = null;
        plus   = null;
        minus  = null;
        parent = null;
        this.attribute = attribute;
    }

    
Build a BSPTree from its underlying elements.
This method does not perform any verification on
consistency of its arguments, it should therefore be used only
when then caller knows what it is doing.
This method is mainly useful to build trees bottom-up. Building trees top-down is realized with the help of method insertCut.
Params:
cut – cut sub-hyperplane for the tree
plus – plus side sub-tree
minus – minus side sub-tree
attribute – attribute associated with the node (may be null)
See Also:
insertCut/** Build a BSPTree from its underlying elements.
     * <p>This method does <em>not</em> perform any verification on
     * consistency of its arguments, it should therefore be used only
     * when then caller knows what it is doing.</p>
     * <p>This method is mainly useful to build trees
     * bottom-up. Building trees top-down is realized with the help of
     * method {@link #insertCut insertCut}.</p>
     * @param cut cut sub-hyperplane for the tree
     * @param plus plus side sub-tree
     * @param minus minus side sub-tree
     * @param attribute attribute associated with the node (may be null)
     * @see #insertCut
     */
    public BSPTree(final SubHyperplane<S> cut, final BSPTree<S> plus, final BSPTree<S> minus,
                   final Object attribute) {
        this.cut       = cut;
        this.plus      = plus;
        this.minus     = minus;
        this.parent    = null;
        this.attribute = attribute;
        plus.parent    = this;
        minus.parent   = this;
    }

    
Insert a cut sub-hyperplane in a node.
The sub-tree starting at this node will be completely overwritten. The new cut sub-hyperplane will be built from the intersection of the provided hyperplane with the cell. If the hyperplane does intersect the cell, the cell will have two children cells with null attributes on each side of the inserted cut sub-hyperplane. If the hyperplane does not intersect the cell then no cut hyperplane will be
inserted and the cell will be changed to a leaf cell. The
attribute of the node is never changed.
This method is mainly useful when called on leaf nodes (i.e. nodes for which getCut returns null), in this case it provides a way to build a tree top-down (whereas the 4 arguments constructor is devoted to build trees bottom-up).
Params:
hyperplane – hyperplane to insert, it will be chopped in
order to fit in the cell defined by the parent nodes of the
instance
See Also:
BSPTree(SubHyperplane, BSPTree, BSPTree, Object)
Returns:
true if a cut sub-hyperplane has been inserted (i.e. if
the cell now has two leaf child nodes)/** Insert a cut sub-hyperplane in a node.
     * <p>The sub-tree starting at this node will be completely
     * overwritten. The new cut sub-hyperplane will be built from the
     * intersection of the provided hyperplane with the cell. If the
     * hyperplane does intersect the cell, the cell will have two
     * children cells with {@code null} attributes on each side of
     * the inserted cut sub-hyperplane. If the hyperplane does not
     * intersect the cell then <em>no</em> cut hyperplane will be
     * inserted and the cell will be changed to a leaf cell. The
     * attribute of the node is never changed.</p>
     * <p>This method is mainly useful when called on leaf nodes
     * (i.e. nodes for which {@link #getCut getCut} returns
     * {@code null}), in this case it provides a way to build a
     * tree top-down (whereas the {@link #BSPTree(SubHyperplane,
     * BSPTree, BSPTree, Object) 4 arguments constructor} is devoted to
     * build trees bottom-up).</p>
     * @param hyperplane hyperplane to insert, it will be chopped in
     * order to fit in the cell defined by the parent nodes of the
     * instance
     * @return true if a cut sub-hyperplane has been inserted (i.e. if
     * the cell now has two leaf child nodes)
     * @see #BSPTree(SubHyperplane, BSPTree, BSPTree, Object)
     */
    public boolean insertCut(final Hyperplane<S> hyperplane) {

        if (cut != null) {
            plus.parent  = null;
            minus.parent = null;
        }

        final SubHyperplane<S> chopped = fitToCell(hyperplane.wholeHyperplane());
        if (chopped == null || chopped.isEmpty()) {
            cut          = null;
            plus         = null;
            minus        = null;
            return false;
        }

        cut          = chopped;
        plus         = new BSPTree<S>();
        plus.parent  = this;
        minus        = new BSPTree<S>();
        minus.parent = this;
        return true;

    }

    
Copy the instance.
The instance created is completely independent of the original
one. A deep copy is used, none of the underlying objects are
shared (except for the nodes attributes and immutable
objects).
Returns:
a new tree, copy of the instance/** Copy the instance.
     * <p>The instance created is completely independent of the original
     * one. A deep copy is used, none of the underlying objects are
     * shared (except for the nodes attributes and immutable
     * objects).</p>
     * @return a new tree, copy of the instance
     */
    public BSPTree<S> copySelf() {

        if (cut == null) {
            return new BSPTree<S>(attribute);
        }

        return new BSPTree<S>(cut.copySelf(), plus.copySelf(), minus.copySelf(),
                           attribute);

    }

    
Get the cut sub-hyperplane.
Returns:
cut sub-hyperplane, null if this is a leaf tree/** Get the cut sub-hyperplane.
     * @return cut sub-hyperplane, null if this is a leaf tree
     */
    public SubHyperplane<S> getCut() {
        return cut;
    }

    
Get the tree on the plus side of the cut hyperplane.
Returns:
tree on the plus side of the cut hyperplane, null if this
is a leaf tree/** Get the tree on the plus side of the cut hyperplane.
     * @return tree on the plus side of the cut hyperplane, null if this
     * is a leaf tree
     */
    public BSPTree<S> getPlus() {
        return plus;
    }

    
Get the tree on the minus side of the cut hyperplane.
Returns:
tree on the minus side of the cut hyperplane, null if this
is a leaf tree/** Get the tree on the minus side of the cut hyperplane.
     * @return tree on the minus side of the cut hyperplane, null if this
     * is a leaf tree
     */
    public BSPTree<S> getMinus() {
        return minus;
    }

    
Get the parent node.
Returns:
parent node, null if the node has no parents/** Get the parent node.
     * @return parent node, null if the node has no parents
     */
    public BSPTree<S> getParent() {
        return parent;
    }

    
Associate an attribute with the instance.
Params:
attribute – attribute to associate with the node
See Also:
getAttribute/** Associate an attribute with the instance.
     * @param attribute attribute to associate with the node
     * @see #getAttribute
     */
    public void setAttribute(final Object attribute) {
        this.attribute = attribute;
    }

    
Get the attribute associated with the instance.
See Also:
setAttribute
Returns:
attribute associated with the node or null if no attribute has been explicitly set using the 
setAttribute method/** Get the attribute associated with the instance.
     * @return attribute associated with the node or null if no
     * attribute has been explicitly set using the {@link #setAttribute
     * setAttribute} method
     * @see #setAttribute
     */
    public Object getAttribute() {
        return attribute;
    }

    
Visit the BSP tree nodes.
Params:
visitor – object visiting the tree nodes/** Visit the BSP tree nodes.
     * @param visitor object visiting the tree nodes
     */
    public void visit(final BSPTreeVisitor<S> visitor) {
        if (cut == null) {
            visitor.visitLeafNode(this);
        } else {
            switch (visitor.visitOrder(this)) {
            case PLUS_MINUS_SUB:
                plus.visit(visitor);
                minus.visit(visitor);
                visitor.visitInternalNode(this);
                break;
            case PLUS_SUB_MINUS:
                plus.visit(visitor);
                visitor.visitInternalNode(this);
                minus.visit(visitor);
                break;
            case MINUS_PLUS_SUB:
                minus.visit(visitor);
                plus.visit(visitor);
                visitor.visitInternalNode(this);
                break;
            case MINUS_SUB_PLUS:
                minus.visit(visitor);
                visitor.visitInternalNode(this);
                plus.visit(visitor);
                break;
            case SUB_PLUS_MINUS:
                visitor.visitInternalNode(this);
                plus.visit(visitor);
                minus.visit(visitor);
                break;
            case SUB_MINUS_PLUS:
                visitor.visitInternalNode(this);
                minus.visit(visitor);
                plus.visit(visitor);
                break;
            default:
                throw new MathInternalError();
            }

        }
    }

    
Fit a sub-hyperplane inside the cell defined by the instance.
Fitting is done by chopping off the parts of the
sub-hyperplane that lie outside of the cell using the
cut-hyperplanes of the parent nodes of the instance.
Params:
sub – sub-hyperplane to fit
Returns:
a new sub-hyperplane, guaranteed to have no part outside
of the instance cell/** Fit a sub-hyperplane inside the cell defined by the instance.
     * <p>Fitting is done by chopping off the parts of the
     * sub-hyperplane that lie outside of the cell using the
     * cut-hyperplanes of the parent nodes of the instance.</p>
     * @param sub sub-hyperplane to fit
     * @return a new sub-hyperplane, guaranteed to have no part outside
     * of the instance cell
     */
    private SubHyperplane<S> fitToCell(final SubHyperplane<S> sub) {
        SubHyperplane<S> s = sub;
        for (BSPTree<S> tree = this; tree.parent != null && s != null; tree = tree.parent) {
            if (tree == tree.parent.plus) {
                s = s.split(tree.parent.cut.getHyperplane()).getPlus();
            } else {
                s = s.split(tree.parent.cut.getHyperplane()).getMinus();
            }
        }
        return s;
    }

    
Get the cell to which a point belongs.
If the returned cell is a leaf node the points belongs to the
interior of the node, if the cell is an internal node the points
belongs to the node cut sub-hyperplane.
Params:
point – point to check
Returns:
the tree cell to which the point belongs
Deprecated:
as of 3.3, replaced with getCell(Point, double)/** Get the cell to which a point belongs.
     * <p>If the returned cell is a leaf node the points belongs to the
     * interior of the node, if the cell is an internal node the points
     * belongs to the node cut sub-hyperplane.</p>
     * @param point point to check
     * @return the tree cell to which the point belongs
     * @deprecated as of 3.3, replaced with {@link #getCell(Point, double)}
     */
    @Deprecated
    public BSPTree<S> getCell(final Vector<S> point) {
        return getCell((Point<S>) point, 1.0e-10);
    }

    
Get the cell to which a point belongs.
If the returned cell is a leaf node the points belongs to the
interior of the node, if the cell is an internal node the points
belongs to the node cut sub-hyperplane.
Params:
point – point to check
tolerance – tolerance below which points close to a cut hyperplane
are considered to belong to the hyperplane itself
Returns:
the tree cell to which the point belongs/** Get the cell to which a point belongs.
     * <p>If the returned cell is a leaf node the points belongs to the
     * interior of the node, if the cell is an internal node the points
     * belongs to the node cut sub-hyperplane.</p>
     * @param point point to check
     * @param tolerance tolerance below which points close to a cut hyperplane
     * are considered to belong to the hyperplane itself
     * @return the tree cell to which the point belongs
     */
    public BSPTree<S> getCell(final Point<S> point, final double tolerance) {

        if (cut == null) {
            return this;
        }

        // position of the point with respect to the cut hyperplane
        final double offset = cut.getHyperplane().getOffset(point);

        if (FastMath.abs(offset) < tolerance) {
            return this;
        } else if (offset <= 0) {
            // point is on the minus side of the cut hyperplane
            return minus.getCell(point, tolerance);
        } else {
            // point is on the plus side of the cut hyperplane
            return plus.getCell(point, tolerance);
        }

    }

    
Get the cells whose cut sub-hyperplanes are close to the point.
Params:
point – point to check
maxOffset – offset below which a cut sub-hyperplane is considered
close to the point (in absolute value)
Returns:
close cells (may be empty if all cut sub-hyperplanes are farther
than maxOffset from the point)/** Get the cells whose cut sub-hyperplanes are close to the point.
     * @param point point to check
     * @param maxOffset offset below which a cut sub-hyperplane is considered
     * close to the point (in absolute value)
     * @return close cells (may be empty if all cut sub-hyperplanes are farther
     * than maxOffset from the point)
     */
    public List<BSPTree<S>> getCloseCuts(final Point<S> point, final double maxOffset) {
        final List<BSPTree<S>> close = new ArrayList<BSPTree<S>>();
        recurseCloseCuts(point, maxOffset, close);
        return close;
    }

    
Get the cells whose cut sub-hyperplanes are close to the point.
Params:
point – point to check
maxOffset – offset below which a cut sub-hyperplane is considered
close to the point (in absolute value)
close – list to fill/** Get the cells whose cut sub-hyperplanes are close to the point.
     * @param point point to check
     * @param maxOffset offset below which a cut sub-hyperplane is considered
     * close to the point (in absolute value)
     * @param close list to fill
     */
    private void recurseCloseCuts(final Point<S> point, final double maxOffset,
                                  final List<BSPTree<S>> close) {
        if (cut != null) {

            // position of the point with respect to the cut hyperplane
            final double offset = cut.getHyperplane().getOffset(point);

            if (offset < -maxOffset) {
                // point is on the minus side of the cut hyperplane
                minus.recurseCloseCuts(point, maxOffset, close);
            } else if (offset > maxOffset) {
                // point is on the plus side of the cut hyperplane
                plus.recurseCloseCuts(point, maxOffset, close);
            } else {
                // point is close to the cut hyperplane
                close.add(this);
                minus.recurseCloseCuts(point, maxOffset, close);
                plus.recurseCloseCuts(point, maxOffset, close);
            }

        }
    }

    
Perform condensation on a tree.
The condensation operation is not recursive, it must be called
explicitly from leaves to root.
/** Perform condensation on a tree.
     * <p>The condensation operation is not recursive, it must be called
     * explicitly from leaves to root.</p>
     */
    private void condense() {
        if ((cut != null) && (plus.cut == null) && (minus.cut == null) &&
            (((plus.attribute == null) && (minus.attribute == null)) ||
             ((plus.attribute != null) && plus.attribute.equals(minus.attribute)))) {
            attribute = (plus.attribute == null) ? minus.attribute : plus.attribute;
            cut       = null;
            plus      = null;
            minus     = null;
        }
    }

    
Merge a BSP tree with the instance.
All trees are modified (parts of them are reused in the new
tree), it is the responsibility of the caller to ensure a copy
has been done before if any of the former tree should be
preserved, no such copy is done here!
The algorithm used here is directly derived from the one
described in the Naylor, Amanatides and Thibault paper (section
III, Binary Partitioning of a BSP Tree).
Params:
tree – other tree to merge with the instance (will be
unusable after the operation, as well as the
instance itself)
leafMerger – object implementing the final merging phase
(this is where the semantic of the operation occurs, generally
depending on the attribute of the leaf node)
Returns:
a new tree, result of instance <op>
tree, this value can be ignored if parentTree is not null
since all connections have already been established/** Merge a BSP tree with the instance.
     * <p>All trees are modified (parts of them are reused in the new
     * tree), it is the responsibility of the caller to ensure a copy
     * has been done before if any of the former tree should be
     * preserved, <em>no</em> such copy is done here!</p>
     * <p>The algorithm used here is directly derived from the one
     * described in the Naylor, Amanatides and Thibault paper (section
     * III, Binary Partitioning of a BSP Tree).</p>
     * @param tree other tree to merge with the instance (will be
     * <em>unusable</em> after the operation, as well as the
     * instance itself)
     * @param leafMerger object implementing the final merging phase
     * (this is where the semantic of the operation occurs, generally
     * depending on the attribute of the leaf node)
     * @return a new tree, result of <code>instance &lt;op&gt;
     * tree</code>, this value can be ignored if parentTree is not null
     * since all connections have already been established
     */
    public BSPTree<S> merge(final BSPTree<S> tree, final LeafMerger<S> leafMerger) {
        return merge(tree, leafMerger, null, false);
    }

    
Merge a BSP tree with the instance.
Params:
tree – other tree to merge with the instance (will be
unusable after the operation, as well as the
instance itself)
leafMerger – object implementing the final merging phase
(this is where the semantic of the operation occurs, generally
depending on the attribute of the leaf node)
parentTree – parent tree to connect to (may be null)
isPlusChild – if true and if parentTree is not null, the
resulting tree should be the plus child of its parent, ignored if
parentTree is null
Returns:
a new tree, result of instance <op>
tree, this value can be ignored if parentTree is not null
since all connections have already been established/** Merge a BSP tree with the instance.
     * @param tree other tree to merge with the instance (will be
     * <em>unusable</em> after the operation, as well as the
     * instance itself)
     * @param leafMerger object implementing the final merging phase
     * (this is where the semantic of the operation occurs, generally
     * depending on the attribute of the leaf node)
     * @param parentTree parent tree to connect to (may be null)
     * @param isPlusChild if true and if parentTree is not null, the
     * resulting tree should be the plus child of its parent, ignored if
     * parentTree is null
     * @return a new tree, result of <code>instance &lt;op&gt;
     * tree</code>, this value can be ignored if parentTree is not null
     * since all connections have already been established
     */
    private BSPTree<S> merge(final BSPTree<S> tree, final LeafMerger<S> leafMerger,
                             final BSPTree<S> parentTree, final boolean isPlusChild) {
        if (cut == null) {
            // cell/tree operation
            return leafMerger.merge(this, tree, parentTree, isPlusChild, true);
        } else if (tree.cut == null) {
            // tree/cell operation
            return leafMerger.merge(tree, this, parentTree, isPlusChild, false);
        } else {
            // tree/tree operation
            final BSPTree<S> merged = tree.split(cut);
            if (parentTree != null) {
                merged.parent = parentTree;
                if (isPlusChild) {
                    parentTree.plus = merged;
                } else {
                    parentTree.minus = merged;
                }
            }

            // merging phase
            plus.merge(merged.plus, leafMerger, merged, true);
            minus.merge(merged.minus, leafMerger, merged, false);
            merged.condense();
            if (merged.cut != null) {
                merged.cut = merged.fitToCell(merged.cut.getHyperplane().wholeHyperplane());
            }

            return merged;

        }
    }

    
This interface gather the merging operations between a BSP tree
leaf and another BSP tree.
As explained in Bruce Naylor, John Amanatides and William
Thibault paper Merging
BSP Trees Yields Polyhedral Set Operations, the operations on BSP trees can be expressed as a generic recursive merging operation where only the final part, when one of the operand is a leaf, is specific to the real operation semantics. For example, a tree representing a region using a boolean attribute to identify inside cells and outside cells would use four different objects to implement the final merging phase of the four set operations union, intersection, difference and symmetric difference (exclusive or).
Type parameters:
<S> – Type of the space./** This interface gather the merging operations between a BSP tree
     * leaf and another BSP tree.
     * <p>As explained in Bruce Naylor, John Amanatides and William
     * Thibault paper <a
     * href="http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf">Merging
     * BSP Trees Yields Polyhedral Set Operations</a>,
     * the operations on {@link BSPTree BSP trees} can be expressed as a
     * generic recursive merging operation where only the final part,
     * when one of the operand is a leaf, is specific to the real
     * operation semantics. For example, a tree representing a region
     * using a boolean attribute to identify inside cells and outside
     * cells would use four different objects to implement the final
     * merging phase of the four set operations union, intersection,
     * difference and symmetric difference (exclusive or).</p>
     * @param <S> Type of the space.
     */
    public interface LeafMerger<S extends Space> {

        
Merge a leaf node and a tree node.
This method is called at the end of a recursive merging resulting from a tree1.merge(tree2, leafMerger) call, when one of the sub-trees involved is a leaf (i.e. when its cut-hyperplane is null). This is the only place where the precise semantics of the operation are required. For all upper level nodes in the tree, the merging operation is only a generic partitioning algorithm.
Since the final operation may be non-commutative, it is important to know if the leaf node comes from the instance tree (tree1) or the argument tree (tree2). The third argument of the method is devoted to this. It can be ignored for commutative operations.
The BSPTree.insertInTree method may be useful to implement this method.
Params:
leaf – leaf node (its cut hyperplane is guaranteed to be
null)
tree – tree node (its cut hyperplane may be null or not)
parentTree – parent tree to connect to (may be null)
isPlusChild – if true and if parentTree is not null, the
resulting tree should be the plus child of its parent, ignored if
parentTree is null
leafFromInstance – if true, the leaf node comes from the instance tree (tree1) and the tree node comes from the argument tree (tree2)
Returns:
the BSP tree resulting from the merging (may be one of
the arguments)/** Merge a leaf node and a tree node.
         * <p>This method is called at the end of a recursive merging
         * resulting from a {@code tree1.merge(tree2, leafMerger)}
         * call, when one of the sub-trees involved is a leaf (i.e. when
         * its cut-hyperplane is null). This is the only place where the
         * precise semantics of the operation are required. For all upper
         * level nodes in the tree, the merging operation is only a
         * generic partitioning algorithm.</p>
         * <p>Since the final operation may be non-commutative, it is
         * important to know if the leaf node comes from the instance tree
         * ({@code tree1}) or the argument tree
         * ({@code tree2}). The third argument of the method is
         * devoted to this. It can be ignored for commutative
         * operations.</p>
         * <p>The {@link BSPTree#insertInTree BSPTree.insertInTree} method
         * may be useful to implement this method.</p>
         * @param leaf leaf node (its cut hyperplane is guaranteed to be
         * null)
         * @param tree tree node (its cut hyperplane may be null or not)
         * @param parentTree parent tree to connect to (may be null)
         * @param isPlusChild if true and if parentTree is not null, the
         * resulting tree should be the plus child of its parent, ignored if
         * parentTree is null
         * @param leafFromInstance if true, the leaf node comes from the
         * instance tree ({@code tree1}) and the tree node comes from
         * the argument tree ({@code tree2})
         * @return the BSP tree resulting from the merging (may be one of
         * the arguments)
         */
        BSPTree<S> merge(BSPTree<S> leaf, BSPTree<S> tree, BSPTree<S> parentTree,
                         boolean isPlusChild, boolean leafFromInstance);

    }

    
This interface handles the corner cases when an internal node cut sub-hyperplane vanishes.

Such cases happens for example when a cut sub-hyperplane is inserted into
another tree (during a merge operation), and is split in several parts,
some of which becomes smaller than the tolerance. The corresponding node
as then no cut sub-hyperplane anymore, but does have children. This interface
specifies how to handle this situation.
setting

Type parameters:
<S> – Type of the space.
Since:
3.4/** This interface handles the corner cases when an internal node cut sub-hyperplane vanishes.
     * <p>
     * Such cases happens for example when a cut sub-hyperplane is inserted into
     * another tree (during a merge operation), and is split in several parts,
     * some of which becomes smaller than the tolerance. The corresponding node
     * as then no cut sub-hyperplane anymore, but does have children. This interface
     * specifies how to handle this situation.
     * setting
     * </p>
     * @param <S> Type of the space.
     * @since 3.4
     */
    public interface VanishingCutHandler<S extends Space> {

        
Fix a node with both vanished cut and children.
Params:
node – node to fix
Returns:
fixed node/** Fix a node with both vanished cut and children.
         * @param node node to fix
         * @return fixed node
         */
        BSPTree<S> fixNode(BSPTree<S> node);

    }

    
Split a BSP tree by an external sub-hyperplane.
Split a tree in two halves, on each side of the
sub-hyperplane. The instance is not modified.
The tree returned is not upward-consistent: despite all of its
sub-trees cut sub-hyperplanes (including its own cut
sub-hyperplane) are bounded to the current cell, it is not
attached to any parent tree yet. This tree is intended to be
later inserted into an higher level tree.
The algorithm used here is the one given in Naylor, Amanatides
and Thibault paper (section III, Binary Partitioning of a BSP
Tree).
Params:
sub – partitioning sub-hyperplane, must be already clipped
to the convex region represented by the instance, will be used as
the cut sub-hyperplane of the returned tree
Returns:
a tree having the specified sub-hyperplane as its cut
sub-hyperplane, the two parts of the split instance as its two
sub-trees and a null parent/** Split a BSP tree by an external sub-hyperplane.
     * <p>Split a tree in two halves, on each side of the
     * sub-hyperplane. The instance is not modified.</p>
     * <p>The tree returned is not upward-consistent: despite all of its
     * sub-trees cut sub-hyperplanes (including its own cut
     * sub-hyperplane) are bounded to the current cell, it is <em>not</em>
     * attached to any parent tree yet. This tree is intended to be
     * later inserted into an higher level tree.</p>
     * <p>The algorithm used here is the one given in Naylor, Amanatides
     * and Thibault paper (section III, Binary Partitioning of a BSP
     * Tree).</p>
     * @param sub partitioning sub-hyperplane, must be already clipped
     * to the convex region represented by the instance, will be used as
     * the cut sub-hyperplane of the returned tree
     * @return a tree having the specified sub-hyperplane as its cut
     * sub-hyperplane, the two parts of the split instance as its two
     * sub-trees and a null parent
     */
    public BSPTree<S> split(final SubHyperplane<S> sub) {

        if (cut == null) {
            return new BSPTree<S>(sub, copySelf(), new BSPTree<S>(attribute), null);
        }

        final Hyperplane<S> cHyperplane = cut.getHyperplane();
        final Hyperplane<S> sHyperplane = sub.getHyperplane();
        final SubHyperplane.SplitSubHyperplane<S> subParts = sub.split(cHyperplane);
        switch (subParts.getSide()) {
        case PLUS :
        { // the partitioning sub-hyperplane is entirely in the plus sub-tree
            final BSPTree<S> split = plus.split(sub);
            if (cut.split(sHyperplane).getSide() == Side.PLUS) {
                split.plus =
                    new BSPTree<S>(cut.copySelf(), split.plus, minus.copySelf(), attribute);
                split.plus.condense();
                split.plus.parent = split;
            } else {
                split.minus =
                    new BSPTree<S>(cut.copySelf(), split.minus, minus.copySelf(), attribute);
                split.minus.condense();
                split.minus.parent = split;
            }
            return split;
        }
        case MINUS :
        { // the partitioning sub-hyperplane is entirely in the minus sub-tree
            final BSPTree<S> split = minus.split(sub);
            if (cut.split(sHyperplane).getSide() == Side.PLUS) {
                split.plus =
                    new BSPTree<S>(cut.copySelf(), plus.copySelf(), split.plus, attribute);
                split.plus.condense();
                split.plus.parent = split;
            } else {
                split.minus =
                    new BSPTree<S>(cut.copySelf(), plus.copySelf(), split.minus, attribute);
                split.minus.condense();
                split.minus.parent = split;
            }
            return split;
        }
        case BOTH :
        {
            final SubHyperplane.SplitSubHyperplane<S> cutParts = cut.split(sHyperplane);
            final BSPTree<S> split =
                new BSPTree<S>(sub, plus.split(subParts.getPlus()), minus.split(subParts.getMinus()),
                               null);
            split.plus.cut          = cutParts.getPlus();
            split.minus.cut         = cutParts.getMinus();
            final BSPTree<S> tmp    = split.plus.minus;
            split.plus.minus        = split.minus.plus;
            split.plus.minus.parent = split.plus;
            split.minus.plus        = tmp;
            split.minus.plus.parent = split.minus;
            split.plus.condense();
            split.minus.condense();
            return split;
        }
        default :
            return cHyperplane.sameOrientationAs(sHyperplane) ?
                   new BSPTree<S>(sub, plus.copySelf(),  minus.copySelf(), attribute) :
                   new BSPTree<S>(sub, minus.copySelf(), plus.copySelf(),  attribute);
        }

    }

    
Insert the instance into another tree.
The instance itself is modified so its former parent should
not be used anymore.
Params:
parentTree – parent tree to connect to (may be null)
isPlusChild – if true and if parentTree is not null, the
resulting tree should be the plus child of its parent, ignored if
parentTree is null
See Also:
LeafMerger
Deprecated:
as of 3.4, replaced with insertInTree(BSPTree, boolean, VanishingCutHandler)/** Insert the instance into another tree.
     * <p>The instance itself is modified so its former parent should
     * not be used anymore.</p>
     * @param parentTree parent tree to connect to (may be null)
     * @param isPlusChild if true and if parentTree is not null, the
     * resulting tree should be the plus child of its parent, ignored if
     * parentTree is null
     * @see LeafMerger
     * @deprecated as of 3.4, replaced with {@link #insertInTree(BSPTree, boolean, VanishingCutHandler)}
     */
    @Deprecated
    public void insertInTree(final BSPTree<S> parentTree, final boolean isPlusChild) {
        insertInTree(parentTree, isPlusChild, new VanishingCutHandler<S>() {
            
{@inheritDoc} /** {@inheritDoc} */
            public BSPTree<S> fixNode(BSPTree<S> node) {
                // the cut should not be null
                throw new MathIllegalStateException(LocalizedFormats.NULL_NOT_ALLOWED);
            }
        });
    }

    
Insert the instance into another tree.
The instance itself is modified so its former parent should
not be used anymore.
Params:
parentTree – parent tree to connect to (may be null)
isPlusChild – if true and if parentTree is not null, the
resulting tree should be the plus child of its parent, ignored if
parentTree is null
vanishingHandler – handler to use for handling very rare corner
cases of vanishing cut sub-hyperplanes in internal nodes during merging
See Also:
LeafMerger
Since:
3.4/** Insert the instance into another tree.
     * <p>The instance itself is modified so its former parent should
     * not be used anymore.</p>
     * @param parentTree parent tree to connect to (may be null)
     * @param isPlusChild if true and if parentTree is not null, the
     * resulting tree should be the plus child of its parent, ignored if
     * parentTree is null
     * @param vanishingHandler handler to use for handling very rare corner
     * cases of vanishing cut sub-hyperplanes in internal nodes during merging
     * @see LeafMerger
     * @since 3.4
     */
    public void insertInTree(final BSPTree<S> parentTree, final boolean isPlusChild,
                             final VanishingCutHandler<S> vanishingHandler) {

        // set up parent/child links
        parent = parentTree;
        if (parentTree != null) {
            if (isPlusChild) {
                parentTree.plus = this;
            } else {
                parentTree.minus = this;
            }
        }

        // make sure the inserted tree lies in the cell defined by its parent nodes
        if (cut != null) {

            // explore the parent nodes from here towards tree root
            for (BSPTree<S> tree = this; tree.parent != null; tree = tree.parent) {

                // this is an hyperplane of some parent node
                final Hyperplane<S> hyperplane = tree.parent.cut.getHyperplane();

                // chop off the parts of the inserted tree that extend
                // on the wrong side of this parent hyperplane
                if (tree == tree.parent.plus) {
                    cut = cut.split(hyperplane).getPlus();
                    plus.chopOffMinus(hyperplane, vanishingHandler);
                    minus.chopOffMinus(hyperplane, vanishingHandler);
                } else {
                    cut = cut.split(hyperplane).getMinus();
                    plus.chopOffPlus(hyperplane, vanishingHandler);
                    minus.chopOffPlus(hyperplane, vanishingHandler);
                }

                if (cut == null) {
                    // the cut sub-hyperplane has vanished
                    final BSPTree<S> fixed = vanishingHandler.fixNode(this);
                    cut       = fixed.cut;
                    plus      = fixed.plus;
                    minus     = fixed.minus;
                    attribute = fixed.attribute;
                    if (cut == null) {
                        break;
                    }
                }

            }

            // since we may have drop some parts of the inserted tree,
            // perform a condensation pass to keep the tree structure simple
            condense();

        }

    }

    
Prune a tree around a cell.

This method can be used to extract a convex cell from a tree.
The original cell may either be a leaf node or an internal node.
If it is an internal node, it's subtree will be ignored (i.e. the
extracted cell will be a leaf node in all cases). The original
tree to which the original cell belongs is not touched at all,
a new independent tree will be built.

Params:
cellAttribute – attribute to set for the leaf node
corresponding to the initial instance cell
otherLeafsAttributes – attribute to set for the other leaf
nodes
internalAttributes – attribute to set for the internal nodes
Returns:
a new tree (the original tree is left untouched) containing
a single branch with the cell as a leaf node, and other leaf nodes
as the remnants of the pruned branches
Since:
3.3/** Prune a tree around a cell.
     * <p>
     * This method can be used to extract a convex cell from a tree.
     * The original cell may either be a leaf node or an internal node.
     * If it is an internal node, it's subtree will be ignored (i.e. the
     * extracted cell will be a leaf node in all cases). The original
     * tree to which the original cell belongs is not touched at all,
     * a new independent tree will be built.
     * </p>
     * @param cellAttribute attribute to set for the leaf node
     * corresponding to the initial instance cell
     * @param otherLeafsAttributes attribute to set for the other leaf
     * nodes
     * @param internalAttributes attribute to set for the internal nodes
     * @return a new tree (the original tree is left untouched) containing
     * a single branch with the cell as a leaf node, and other leaf nodes
     * as the remnants of the pruned branches
     * @since 3.3
     */
    public BSPTree<S> pruneAroundConvexCell(final Object cellAttribute,
                                            final Object otherLeafsAttributes,
                                            final Object internalAttributes) {

        // build the current cell leaf
        BSPTree<S> tree = new BSPTree<S>(cellAttribute);

        // build the pruned tree bottom-up
        for (BSPTree<S> current = this; current.parent != null; current = current.parent) {
            final SubHyperplane<S> parentCut = current.parent.cut.copySelf();
            final BSPTree<S>       sibling   = new BSPTree<S>(otherLeafsAttributes);
            if (current == current.parent.plus) {
                tree = new BSPTree<S>(parentCut, tree, sibling, internalAttributes);
            } else {
                tree = new BSPTree<S>(parentCut, sibling, tree, internalAttributes);
            }
        }

        return tree;

    }

    
Chop off parts of the tree.
The instance is modified in place, all the parts that are on
the minus side of the chopping hyperplane are discarded, only the
parts on the plus side remain.
Params:
hyperplane – chopping hyperplane
vanishingHandler – handler to use for handling very rare corner
cases of vanishing cut sub-hyperplanes in internal nodes during merging/** Chop off parts of the tree.
     * <p>The instance is modified in place, all the parts that are on
     * the minus side of the chopping hyperplane are discarded, only the
     * parts on the plus side remain.</p>
     * @param hyperplane chopping hyperplane
     * @param vanishingHandler handler to use for handling very rare corner
     * cases of vanishing cut sub-hyperplanes in internal nodes during merging
     */
    private void chopOffMinus(final Hyperplane<S> hyperplane, final VanishingCutHandler<S> vanishingHandler) {
        if (cut != null) {

            cut = cut.split(hyperplane).getPlus();
            plus.chopOffMinus(hyperplane, vanishingHandler);
            minus.chopOffMinus(hyperplane, vanishingHandler);

            if (cut == null) {
                // the cut sub-hyperplane has vanished
                final BSPTree<S> fixed = vanishingHandler.fixNode(this);
                cut       = fixed.cut;
                plus      = fixed.plus;
                minus     = fixed.minus;
                attribute = fixed.attribute;
            }

        }
    }

    
Chop off parts of the tree.
The instance is modified in place, all the parts that are on
the plus side of the chopping hyperplane are discarded, only the
parts on the minus side remain.
Params:
hyperplane – chopping hyperplane
vanishingHandler – handler to use for handling very rare corner
cases of vanishing cut sub-hyperplanes in internal nodes during merging/** Chop off parts of the tree.
     * <p>The instance is modified in place, all the parts that are on
     * the plus side of the chopping hyperplane are discarded, only the
     * parts on the minus side remain.</p>
     * @param hyperplane chopping hyperplane
     * @param vanishingHandler handler to use for handling very rare corner
     * cases of vanishing cut sub-hyperplanes in internal nodes during merging
     */
    private void chopOffPlus(final Hyperplane<S> hyperplane, final VanishingCutHandler<S> vanishingHandler) {
        if (cut != null) {

            cut = cut.split(hyperplane).getMinus();
            plus.chopOffPlus(hyperplane, vanishingHandler);
            minus.chopOffPlus(hyperplane, vanishingHandler);

            if (cut == null) {
                // the cut sub-hyperplane has vanished
                final BSPTree<S> fixed = vanishingHandler.fixNode(this);
                cut       = fixed.cut;
                plus      = fixed.plus;
                minus     = fixed.minus;
                attribute = fixed.attribute;
            }

        }
    }

}