001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.math3.geometry.partitioning;
018
019import java.util.ArrayList;
020import java.util.List;
021
022import org.apache.commons.math3.exception.MathIllegalStateException;
023import org.apache.commons.math3.exception.MathInternalError;
024import org.apache.commons.math3.exception.util.LocalizedFormats;
025import org.apache.commons.math3.geometry.Point;
026import org.apache.commons.math3.geometry.Space;
027import org.apache.commons.math3.geometry.Vector;
028import org.apache.commons.math3.util.FastMath;
029
030/** This class represent a Binary Space Partition tree.
031
032 * <p>BSP trees are an efficient way to represent space partitions and
033 * to associate attributes with each cell. Each node in a BSP tree
034 * represents a convex region which is partitioned in two convex
035 * sub-regions at each side of a cut hyperplane. The root tree
036 * contains the complete space.</p>
037
038 * <p>The main use of such partitions is to use a boolean attribute to
039 * define an inside/outside property, hence representing arbitrary
040 * polytopes (line segments in 1D, polygons in 2D and polyhedrons in
041 * 3D) and to operate on them.</p>
042
043 * <p>Another example would be to represent Voronoi tesselations, the
044 * attribute of each cell holding the defining point of the cell.</p>
045
046 * <p>The application-defined attributes are shared among copied
047 * instances and propagated to split parts. These attributes are not
048 * used by the BSP-tree algorithms themselves, so the application can
049 * use them for any purpose. Since the tree visiting method holds
050 * internal and leaf nodes differently, it is possible to use
051 * different classes for internal nodes attributes and leaf nodes
052 * attributes. This should be used with care, though, because if the
053 * tree is modified in any way after attributes have been set, some
054 * internal nodes may become leaf nodes and some leaf nodes may become
055 * internal nodes.</p>
056
057 * <p>One of the main sources for the development of this package was
058 * Bruce Naylor, John Amanatides and William Thibault paper <a
059 * href="http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf">Merging
060 * BSP Trees Yields Polyhedral Set Operations</a> Proc. Siggraph '90,
061 * Computer Graphics 24(4), August 1990, pp 115-124, published by the
062 * Association for Computing Machinery (ACM).</p>
063
064 * @param <S> Type of the space.
065
066 * @since 3.0
067 */
068public class BSPTree<S extends Space> {
069
070    /** Cut sub-hyperplane. */
071    private SubHyperplane<S> cut;
072
073    /** Tree at the plus side of the cut hyperplane. */
074    private BSPTree<S> plus;
075
076    /** Tree at the minus side of the cut hyperplane. */
077    private BSPTree<S> minus;
078
079    /** Parent tree. */
080    private BSPTree<S> parent;
081
082    /** Application-defined attribute. */
083    private Object attribute;
084
085    /** Build a tree having only one root cell representing the whole space.
086     */
087    public BSPTree() {
088        cut       = null;
089        plus      = null;
090        minus     = null;
091        parent    = null;
092        attribute = null;
093    }
094
095    /** Build a tree having only one root cell representing the whole space.
096     * @param attribute attribute of the tree (may be null)
097     */
098    public BSPTree(final Object attribute) {
099        cut    = null;
100        plus   = null;
101        minus  = null;
102        parent = null;
103        this.attribute = attribute;
104    }
105
106    /** Build a BSPTree from its underlying elements.
107     * <p>This method does <em>not</em> perform any verification on
108     * consistency of its arguments, it should therefore be used only
109     * when then caller knows what it is doing.</p>
110     * <p>This method is mainly useful to build trees
111     * bottom-up. Building trees top-down is realized with the help of
112     * method {@link #insertCut insertCut}.</p>
113     * @param cut cut sub-hyperplane for the tree
114     * @param plus plus side sub-tree
115     * @param minus minus side sub-tree
116     * @param attribute attribute associated with the node (may be null)
117     * @see #insertCut
118     */
119    public BSPTree(final SubHyperplane<S> cut, final BSPTree<S> plus, final BSPTree<S> minus,
120                   final Object attribute) {
121        this.cut       = cut;
122        this.plus      = plus;
123        this.minus     = minus;
124        this.parent    = null;
125        this.attribute = attribute;
126        plus.parent    = this;
127        minus.parent   = this;
128    }
129
130    /** Insert a cut sub-hyperplane in a node.
131     * <p>The sub-tree starting at this node will be completely
132     * overwritten. The new cut sub-hyperplane will be built from the
133     * intersection of the provided hyperplane with the cell. If the
134     * hyperplane does intersect the cell, the cell will have two
135     * children cells with {@code null} attributes on each side of
136     * the inserted cut sub-hyperplane. If the hyperplane does not
137     * intersect the cell then <em>no</em> cut hyperplane will be
138     * inserted and the cell will be changed to a leaf cell. The
139     * attribute of the node is never changed.</p>
140     * <p>This method is mainly useful when called on leaf nodes
141     * (i.e. nodes for which {@link #getCut getCut} returns
142     * {@code null}), in this case it provides a way to build a
143     * tree top-down (whereas the {@link #BSPTree(SubHyperplane,
144     * BSPTree, BSPTree, Object) 4 arguments constructor} is devoted to
145     * build trees bottom-up).</p>
146     * @param hyperplane hyperplane to insert, it will be chopped in
147     * order to fit in the cell defined by the parent nodes of the
148     * instance
149     * @return true if a cut sub-hyperplane has been inserted (i.e. if
150     * the cell now has two leaf child nodes)
151     * @see #BSPTree(SubHyperplane, BSPTree, BSPTree, Object)
152     */
153    public boolean insertCut(final Hyperplane<S> hyperplane) {
154
155        if (cut != null) {
156            plus.parent  = null;
157            minus.parent = null;
158        }
159
160        final SubHyperplane<S> chopped = fitToCell(hyperplane.wholeHyperplane());
161        if (chopped == null || chopped.isEmpty()) {
162            cut          = null;
163            plus         = null;
164            minus        = null;
165            return false;
166        }
167
168        cut          = chopped;
169        plus         = new BSPTree<S>();
170        plus.parent  = this;
171        minus        = new BSPTree<S>();
172        minus.parent = this;
173        return true;
174
175    }
176
177    /** Copy the instance.
178     * <p>The instance created is completely independent of the original
179     * one. A deep copy is used, none of the underlying objects are
180     * shared (except for the nodes attributes and immutable
181     * objects).</p>
182     * @return a new tree, copy of the instance
183     */
184    public BSPTree<S> copySelf() {
185
186        if (cut == null) {
187            return new BSPTree<S>(attribute);
188        }
189
190        return new BSPTree<S>(cut.copySelf(), plus.copySelf(), minus.copySelf(),
191                           attribute);
192
193    }
194
195    /** Get the cut sub-hyperplane.
196     * @return cut sub-hyperplane, null if this is a leaf tree
197     */
198    public SubHyperplane<S> getCut() {
199        return cut;
200    }
201
202    /** Get the tree on the plus side of the cut hyperplane.
203     * @return tree on the plus side of the cut hyperplane, null if this
204     * is a leaf tree
205     */
206    public BSPTree<S> getPlus() {
207        return plus;
208    }
209
210    /** Get the tree on the minus side of the cut hyperplane.
211     * @return tree on the minus side of the cut hyperplane, null if this
212     * is a leaf tree
213     */
214    public BSPTree<S> getMinus() {
215        return minus;
216    }
217
218    /** Get the parent node.
219     * @return parent node, null if the node has no parents
220     */
221    public BSPTree<S> getParent() {
222        return parent;
223    }
224
225    /** Associate an attribute with the instance.
226     * @param attribute attribute to associate with the node
227     * @see #getAttribute
228     */
229    public void setAttribute(final Object attribute) {
230        this.attribute = attribute;
231    }
232
233    /** Get the attribute associated with the instance.
234     * @return attribute associated with the node or null if no
235     * attribute has been explicitly set using the {@link #setAttribute
236     * setAttribute} method
237     * @see #setAttribute
238     */
239    public Object getAttribute() {
240        return attribute;
241    }
242
243    /** Visit the BSP tree nodes.
244     * @param visitor object visiting the tree nodes
245     */
246    public void visit(final BSPTreeVisitor<S> visitor) {
247        if (cut == null) {
248            visitor.visitLeafNode(this);
249        } else {
250            switch (visitor.visitOrder(this)) {
251            case PLUS_MINUS_SUB:
252                plus.visit(visitor);
253                minus.visit(visitor);
254                visitor.visitInternalNode(this);
255                break;
256            case PLUS_SUB_MINUS:
257                plus.visit(visitor);
258                visitor.visitInternalNode(this);
259                minus.visit(visitor);
260                break;
261            case MINUS_PLUS_SUB:
262                minus.visit(visitor);
263                plus.visit(visitor);
264                visitor.visitInternalNode(this);
265                break;
266            case MINUS_SUB_PLUS:
267                minus.visit(visitor);
268                visitor.visitInternalNode(this);
269                plus.visit(visitor);
270                break;
271            case SUB_PLUS_MINUS:
272                visitor.visitInternalNode(this);
273                plus.visit(visitor);
274                minus.visit(visitor);
275                break;
276            case SUB_MINUS_PLUS:
277                visitor.visitInternalNode(this);
278                minus.visit(visitor);
279                plus.visit(visitor);
280                break;
281            default:
282                throw new MathInternalError();
283            }
284
285        }
286    }
287
288    /** Fit a sub-hyperplane inside the cell defined by the instance.
289     * <p>Fitting is done by chopping off the parts of the
290     * sub-hyperplane that lie outside of the cell using the
291     * cut-hyperplanes of the parent nodes of the instance.</p>
292     * @param sub sub-hyperplane to fit
293     * @return a new sub-hyperplane, guaranteed to have no part outside
294     * of the instance cell
295     */
296    private SubHyperplane<S> fitToCell(final SubHyperplane<S> sub) {
297        SubHyperplane<S> s = sub;
298        for (BSPTree<S> tree = this; tree.parent != null && s != null; tree = tree.parent) {
299            if (tree == tree.parent.plus) {
300                s = s.split(tree.parent.cut.getHyperplane()).getPlus();
301            } else {
302                s = s.split(tree.parent.cut.getHyperplane()).getMinus();
303            }
304        }
305        return s;
306    }
307
308    /** Get the cell to which a point belongs.
309     * <p>If the returned cell is a leaf node the points belongs to the
310     * interior of the node, if the cell is an internal node the points
311     * belongs to the node cut sub-hyperplane.</p>
312     * @param point point to check
313     * @return the tree cell to which the point belongs
314     * @deprecated as of 3.3, replaced with {@link #getCell(Point, double)}
315     */
316    @Deprecated
317    public BSPTree<S> getCell(final Vector<S> point) {
318        return getCell((Point<S>) point, 1.0e-10);
319    }
320
321    /** Get the cell to which a point belongs.
322     * <p>If the returned cell is a leaf node the points belongs to the
323     * interior of the node, if the cell is an internal node the points
324     * belongs to the node cut sub-hyperplane.</p>
325     * @param point point to check
326     * @param tolerance tolerance below which points close to a cut hyperplane
327     * are considered to belong to the hyperplane itself
328     * @return the tree cell to which the point belongs
329     */
330    public BSPTree<S> getCell(final Point<S> point, final double tolerance) {
331
332        if (cut == null) {
333            return this;
334        }
335
336        // position of the point with respect to the cut hyperplane
337        final double offset = cut.getHyperplane().getOffset(point);
338
339        if (FastMath.abs(offset) < tolerance) {
340            return this;
341        } else if (offset <= 0) {
342            // point is on the minus side of the cut hyperplane
343            return minus.getCell(point, tolerance);
344        } else {
345            // point is on the plus side of the cut hyperplane
346            return plus.getCell(point, tolerance);
347        }
348
349    }
350
351    /** Get the cells whose cut sub-hyperplanes are close to the point.
352     * @param point point to check
353     * @param maxOffset offset below which a cut sub-hyperplane is considered
354     * close to the point (in absolute value)
355     * @return close cells (may be empty if all cut sub-hyperplanes are farther
356     * than maxOffset from the point)
357     */
358    public List<BSPTree<S>> getCloseCuts(final Point<S> point, final double maxOffset) {
359        final List<BSPTree<S>> close = new ArrayList<BSPTree<S>>();
360        recurseCloseCuts(point, maxOffset, close);
361        return close;
362    }
363
364    /** Get the cells whose cut sub-hyperplanes are close to the point.
365     * @param point point to check
366     * @param maxOffset offset below which a cut sub-hyperplane is considered
367     * close to the point (in absolute value)
368     * @param close list to fill
369     */
370    private void recurseCloseCuts(final Point<S> point, final double maxOffset,
371                                  final List<BSPTree<S>> close) {
372        if (cut != null) {
373
374            // position of the point with respect to the cut hyperplane
375            final double offset = cut.getHyperplane().getOffset(point);
376
377            if (offset < -maxOffset) {
378                // point is on the minus side of the cut hyperplane
379                minus.recurseCloseCuts(point, maxOffset, close);
380            } else if (offset > maxOffset) {
381                // point is on the plus side of the cut hyperplane
382                plus.recurseCloseCuts(point, maxOffset, close);
383            } else {
384                // point is close to the cut hyperplane
385                close.add(this);
386                minus.recurseCloseCuts(point, maxOffset, close);
387                plus.recurseCloseCuts(point, maxOffset, close);
388            }
389
390        }
391    }
392
393    /** Perform condensation on a tree.
394     * <p>The condensation operation is not recursive, it must be called
395     * explicitly from leaves to root.</p>
396     */
397    private void condense() {
398        if ((cut != null) && (plus.cut == null) && (minus.cut == null) &&
399            (((plus.attribute == null) && (minus.attribute == null)) ||
400             ((plus.attribute != null) && plus.attribute.equals(minus.attribute)))) {
401            attribute = (plus.attribute == null) ? minus.attribute : plus.attribute;
402            cut       = null;
403            plus      = null;
404            minus     = null;
405        }
406    }
407
408    /** Merge a BSP tree with the instance.
409     * <p>All trees are modified (parts of them are reused in the new
410     * tree), it is the responsibility of the caller to ensure a copy
411     * has been done before if any of the former tree should be
412     * preserved, <em>no</em> such copy is done here!</p>
413     * <p>The algorithm used here is directly derived from the one
414     * described in the Naylor, Amanatides and Thibault paper (section
415     * III, Binary Partitioning of a BSP Tree).</p>
416     * @param tree other tree to merge with the instance (will be
417     * <em>unusable</em> after the operation, as well as the
418     * instance itself)
419     * @param leafMerger object implementing the final merging phase
420     * (this is where the semantic of the operation occurs, generally
421     * depending on the attribute of the leaf node)
422     * @return a new tree, result of <code>instance &lt;op&gt;
423     * tree</code>, this value can be ignored if parentTree is not null
424     * since all connections have already been established
425     */
426    public BSPTree<S> merge(final BSPTree<S> tree, final LeafMerger<S> leafMerger) {
427        return merge(tree, leafMerger, null, false);
428    }
429
430    /** Merge a BSP tree with the instance.
431     * @param tree other tree to merge with the instance (will be
432     * <em>unusable</em> after the operation, as well as the
433     * instance itself)
434     * @param leafMerger object implementing the final merging phase
435     * (this is where the semantic of the operation occurs, generally
436     * depending on the attribute of the leaf node)
437     * @param parentTree parent tree to connect to (may be null)
438     * @param isPlusChild if true and if parentTree is not null, the
439     * resulting tree should be the plus child of its parent, ignored if
440     * parentTree is null
441     * @return a new tree, result of <code>instance &lt;op&gt;
442     * tree</code>, this value can be ignored if parentTree is not null
443     * since all connections have already been established
444     */
445    private BSPTree<S> merge(final BSPTree<S> tree, final LeafMerger<S> leafMerger,
446                             final BSPTree<S> parentTree, final boolean isPlusChild) {
447        if (cut == null) {
448            // cell/tree operation
449            return leafMerger.merge(this, tree, parentTree, isPlusChild, true);
450        } else if (tree.cut == null) {
451            // tree/cell operation
452            return leafMerger.merge(tree, this, parentTree, isPlusChild, false);
453        } else {
454            // tree/tree operation
455            final BSPTree<S> merged = tree.split(cut);
456            if (parentTree != null) {
457                merged.parent = parentTree;
458                if (isPlusChild) {
459                    parentTree.plus = merged;
460                } else {
461                    parentTree.minus = merged;
462                }
463            }
464
465            // merging phase
466            plus.merge(merged.plus, leafMerger, merged, true);
467            minus.merge(merged.minus, leafMerger, merged, false);
468            merged.condense();
469            if (merged.cut != null) {
470                merged.cut = merged.fitToCell(merged.cut.getHyperplane().wholeHyperplane());
471            }
472
473            return merged;
474
475        }
476    }
477
478    /** This interface gather the merging operations between a BSP tree
479     * leaf and another BSP tree.
480     * <p>As explained in Bruce Naylor, John Amanatides and William
481     * Thibault paper <a
482     * href="http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf">Merging
483     * BSP Trees Yields Polyhedral Set Operations</a>,
484     * the operations on {@link BSPTree BSP trees} can be expressed as a
485     * generic recursive merging operation where only the final part,
486     * when one of the operand is a leaf, is specific to the real
487     * operation semantics. For example, a tree representing a region
488     * using a boolean attribute to identify inside cells and outside
489     * cells would use four different objects to implement the final
490     * merging phase of the four set operations union, intersection,
491     * difference and symmetric difference (exclusive or).</p>
492     * @param <S> Type of the space.
493     */
494    public interface LeafMerger<S extends Space> {
495
496        /** Merge a leaf node and a tree node.
497         * <p>This method is called at the end of a recursive merging
498         * resulting from a {@code tree1.merge(tree2, leafMerger)}
499         * call, when one of the sub-trees involved is a leaf (i.e. when
500         * its cut-hyperplane is null). This is the only place where the
501         * precise semantics of the operation are required. For all upper
502         * level nodes in the tree, the merging operation is only a
503         * generic partitioning algorithm.</p>
504         * <p>Since the final operation may be non-commutative, it is
505         * important to know if the leaf node comes from the instance tree
506         * ({@code tree1}) or the argument tree
507         * ({@code tree2}). The third argument of the method is
508         * devoted to this. It can be ignored for commutative
509         * operations.</p>
510         * <p>The {@link BSPTree#insertInTree BSPTree.insertInTree} method
511         * may be useful to implement this method.</p>
512         * @param leaf leaf node (its cut hyperplane is guaranteed to be
513         * null)
514         * @param tree tree node (its cut hyperplane may be null or not)
515         * @param parentTree parent tree to connect to (may be null)
516         * @param isPlusChild if true and if parentTree is not null, the
517         * resulting tree should be the plus child of its parent, ignored if
518         * parentTree is null
519         * @param leafFromInstance if true, the leaf node comes from the
520         * instance tree ({@code tree1}) and the tree node comes from
521         * the argument tree ({@code tree2})
522         * @return the BSP tree resulting from the merging (may be one of
523         * the arguments)
524         */
525        BSPTree<S> merge(BSPTree<S> leaf, BSPTree<S> tree, BSPTree<S> parentTree,
526                         boolean isPlusChild, boolean leafFromInstance);
527
528    }
529
530    /** This interface handles the corner cases when an internal node cut sub-hyperplane vanishes.
531     * <p>
532     * Such cases happens for example when a cut sub-hyperplane is inserted into
533     * another tree (during a merge operation), and is split in several parts,
534     * some of which becomes smaller than the tolerance. The corresponding node
535     * as then no cut sub-hyperplane anymore, but does have children. This interface
536     * specifies how to handle this situation.
537     * setting
538     * </p>
539     * @since 3.4
540     */
541    public interface VanishingCutHandler<S extends Space> {
542
543        /** Fix a node with both vanished cut and children.
544         * @param node node to fix
545         * @return fixed node
546         */
547        BSPTree<S> fixNode(BSPTree<S> node);
548
549    }
550
551    /** Split a BSP tree by an external sub-hyperplane.
552     * <p>Split a tree in two halves, on each side of the
553     * sub-hyperplane. The instance is not modified.</p>
554     * <p>The tree returned is not upward-consistent: despite all of its
555     * sub-trees cut sub-hyperplanes (including its own cut
556     * sub-hyperplane) are bounded to the current cell, it is <em>not</em>
557     * attached to any parent tree yet. This tree is intended to be
558     * later inserted into an higher level tree.</p>
559     * <p>The algorithm used here is the one given in Naylor, Amanatides
560     * and Thibault paper (section III, Binary Partitioning of a BSP
561     * Tree).</p>
562     * @param sub partitioning sub-hyperplane, must be already clipped
563     * to the convex region represented by the instance, will be used as
564     * the cut sub-hyperplane of the returned tree
565     * @return a tree having the specified sub-hyperplane as its cut
566     * sub-hyperplane, the two parts of the split instance as its two
567     * sub-trees and a null parent
568     */
569    public BSPTree<S> split(final SubHyperplane<S> sub) {
570
571        if (cut == null) {
572            return new BSPTree<S>(sub, copySelf(), new BSPTree<S>(attribute), null);
573        }
574
575        final Hyperplane<S> cHyperplane = cut.getHyperplane();
576        final Hyperplane<S> sHyperplane = sub.getHyperplane();
577        switch (sub.side(cHyperplane)) {
578        case PLUS :
579        { // the partitioning sub-hyperplane is entirely in the plus sub-tree
580            final BSPTree<S> split = plus.split(sub);
581            if (cut.side(sHyperplane) == Side.PLUS) {
582                split.plus =
583                    new BSPTree<S>(cut.copySelf(), split.plus, minus.copySelf(), attribute);
584                split.plus.condense();
585                split.plus.parent = split;
586            } else {
587                split.minus =
588                    new BSPTree<S>(cut.copySelf(), split.minus, minus.copySelf(), attribute);
589                split.minus.condense();
590                split.minus.parent = split;
591            }
592            return split;
593        }
594        case MINUS :
595        { // the partitioning sub-hyperplane is entirely in the minus sub-tree
596            final BSPTree<S> split = minus.split(sub);
597            if (cut.side(sHyperplane) == Side.PLUS) {
598                split.plus =
599                    new BSPTree<S>(cut.copySelf(), plus.copySelf(), split.plus, attribute);
600                split.plus.condense();
601                split.plus.parent = split;
602            } else {
603                split.minus =
604                    new BSPTree<S>(cut.copySelf(), plus.copySelf(), split.minus, attribute);
605                split.minus.condense();
606                split.minus.parent = split;
607            }
608            return split;
609        }
610        case BOTH :
611        {
612            final SubHyperplane.SplitSubHyperplane<S> cutParts = cut.split(sHyperplane);
613            final SubHyperplane.SplitSubHyperplane<S> subParts = sub.split(cHyperplane);
614            final BSPTree<S> split =
615                new BSPTree<S>(sub, plus.split(subParts.getPlus()), minus.split(subParts.getMinus()),
616                               null);
617            split.plus.cut          = cutParts.getPlus();
618            split.minus.cut         = cutParts.getMinus();
619            final BSPTree<S> tmp    = split.plus.minus;
620            split.plus.minus        = split.minus.plus;
621            split.plus.minus.parent = split.plus;
622            split.minus.plus        = tmp;
623            split.minus.plus.parent = split.minus;
624            split.plus.condense();
625            split.minus.condense();
626            return split;
627        }
628        default :
629            return cHyperplane.sameOrientationAs(sHyperplane) ?
630                   new BSPTree<S>(sub, plus.copySelf(),  minus.copySelf(), attribute) :
631                   new BSPTree<S>(sub, minus.copySelf(), plus.copySelf(),  attribute);
632        }
633
634    }
635
636    /** Insert the instance into another tree.
637     * <p>The instance itself is modified so its former parent should
638     * not be used anymore.</p>
639     * @param parentTree parent tree to connect to (may be null)
640     * @param isPlusChild if true and if parentTree is not null, the
641     * resulting tree should be the plus child of its parent, ignored if
642     * parentTree is null
643     * @see LeafMerger
644     * @deprecated as of 3.4, replaced with {@link #insertInTree(BSPTree, boolean, VanishingCutHandler)}
645     */
646    @Deprecated
647    public void insertInTree(final BSPTree<S> parentTree, final boolean isPlusChild) {
648        insertInTree(parentTree, isPlusChild, new VanishingCutHandler<S>() {
649            /** {@inheritDoc} */
650            public BSPTree<S> fixNode(BSPTree<S> node) {
651                // the cut should not be null
652                throw new MathIllegalStateException(LocalizedFormats.NULL_NOT_ALLOWED);
653            }
654        });
655    }
656
657    /** Insert the instance into another tree.
658     * <p>The instance itself is modified so its former parent should
659     * not be used anymore.</p>
660     * @param parentTree parent tree to connect to (may be null)
661     * @param isPlusChild if true and if parentTree is not null, the
662     * resulting tree should be the plus child of its parent, ignored if
663     * parentTree is null
664     * @param vanishingHandler handler to use for handling very rare corner
665     * cases of vanishing cut sub-hyperplanes in internal nodes during merging
666     * @see LeafMerger
667     * @since 3.4
668     */
669    public void insertInTree(final BSPTree<S> parentTree, final boolean isPlusChild,
670                             final VanishingCutHandler<S> vanishingHandler) {
671
672        // set up parent/child links
673        parent = parentTree;
674        if (parentTree != null) {
675            if (isPlusChild) {
676                parentTree.plus = this;
677            } else {
678                parentTree.minus = this;
679            }
680        }
681
682        // make sure the inserted tree lies in the cell defined by its parent nodes
683        if (cut != null) {
684
685            // explore the parent nodes from here towards tree root
686            for (BSPTree<S> tree = this; tree.parent != null; tree = tree.parent) {
687
688                // this is an hyperplane of some parent node
689                final Hyperplane<S> hyperplane = tree.parent.cut.getHyperplane();
690
691                // chop off the parts of the inserted tree that extend
692                // on the wrong side of this parent hyperplane
693                if (tree == tree.parent.plus) {
694                    cut = cut.split(hyperplane).getPlus();
695                    plus.chopOffMinus(hyperplane, vanishingHandler);
696                    minus.chopOffMinus(hyperplane, vanishingHandler);
697                } else {
698                    cut = cut.split(hyperplane).getMinus();
699                    plus.chopOffPlus(hyperplane, vanishingHandler);
700                    minus.chopOffPlus(hyperplane, vanishingHandler);
701                }
702
703                if (cut == null) {
704                    // the cut sub-hyperplane has vanished
705                    final BSPTree<S> fixed = vanishingHandler.fixNode(this);
706                    cut       = fixed.cut;
707                    plus      = fixed.plus;
708                    minus     = fixed.minus;
709                    attribute = fixed.attribute;
710                }
711
712            }
713
714            // since we may have drop some parts of the inserted tree,
715            // perform a condensation pass to keep the tree structure simple
716            condense();
717
718        }
719
720    }
721
722    /** Prune a tree around a cell.
723     * <p>
724     * This method can be used to extract a convex cell from a tree.
725     * The original cell may either be a leaf node or an internal node.
726     * If it is an internal node, it's subtree will be ignored (i.e. the
727     * extracted cell will be a leaf node in all cases). The original
728     * tree to which the original cell belongs is not touched at all,
729     * a new independent tree will be built.
730     * </p>
731     * @param cellAttribute attribute to set for the leaf node
732     * corresponding to the initial instance cell
733     * @param otherLeafsAttributes attribute to set for the other leaf
734     * nodes
735     * @param internalAttributes attribute to set for the internal nodes
736     * @return a new tree (the original tree is left untouched) containing
737     * a single branch with the cell as a leaf node, and other leaf nodes
738     * as the remnants of the pruned branches
739     * @since 3.3
740     */
741    public BSPTree<S> pruneAroundConvexCell(final Object cellAttribute,
742                                            final Object otherLeafsAttributes,
743                                            final Object internalAttributes) {
744
745        // build the current cell leaf
746        BSPTree<S> tree = new BSPTree<S>(cellAttribute);
747
748        // build the pruned tree bottom-up
749        for (BSPTree<S> current = this; current.parent != null; current = current.parent) {
750            final SubHyperplane<S> parentCut = current.parent.cut.copySelf();
751            final BSPTree<S>       sibling   = new BSPTree<S>(otherLeafsAttributes);
752            if (current == current.parent.plus) {
753                tree = new BSPTree<S>(parentCut, tree, sibling, internalAttributes);
754            } else {
755                tree = new BSPTree<S>(parentCut, sibling, tree, internalAttributes);
756            }
757        }
758
759        return tree;
760
761    }
762
763    /** Chop off parts of the tree.
764     * <p>The instance is modified in place, all the parts that are on
765     * the minus side of the chopping hyperplane are discarded, only the
766     * parts on the plus side remain.</p>
767     * @param hyperplane chopping hyperplane
768     * @param vanishingHandler handler to use for handling very rare corner
769     * cases of vanishing cut sub-hyperplanes in internal nodes during merging
770     */
771    private void chopOffMinus(final Hyperplane<S> hyperplane, final VanishingCutHandler<S> vanishingHandler) {
772        if (cut != null) {
773
774            cut = cut.split(hyperplane).getPlus();
775            plus.chopOffMinus(hyperplane, vanishingHandler);
776            minus.chopOffMinus(hyperplane, vanishingHandler);
777
778            if (cut == null) {
779                // the cut sub-hyperplane has vanished
780                final BSPTree<S> fixed = vanishingHandler.fixNode(this);
781                cut       = fixed.cut;
782                plus      = fixed.plus;
783                minus     = fixed.minus;
784                attribute = fixed.attribute;
785            }
786
787        }
788    }
789
790    /** Chop off parts of the tree.
791     * <p>The instance is modified in place, all the parts that are on
792     * the plus side of the chopping hyperplane are discarded, only the
793     * parts on the minus side remain.</p>
794     * @param hyperplane chopping hyperplane
795     * @param vanishingHandler handler to use for handling very rare corner
796     * cases of vanishing cut sub-hyperplanes in internal nodes during merging
797     */
798    private void chopOffPlus(final Hyperplane<S> hyperplane, final VanishingCutHandler<S> vanishingHandler) {
799        if (cut != null) {
800
801            cut = cut.split(hyperplane).getMinus();
802            plus.chopOffPlus(hyperplane, vanishingHandler);
803            minus.chopOffPlus(hyperplane, vanishingHandler);
804
805            if (cut == null) {
806                // the cut sub-hyperplane has vanished
807                final BSPTree<S> fixed = vanishingHandler.fixNode(this);
808                cut       = fixed.cut;
809                plus      = fixed.plus;
810                minus     = fixed.minus;
811                attribute = fixed.attribute;
812            }
813
814        }
815    }
816
817}