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.MathInternalError;
023import org.apache.commons.math3.geometry.Point;
024import org.apache.commons.math3.geometry.Space;
025import org.apache.commons.math3.geometry.Vector;
026import org.apache.commons.math3.util.FastMath;
027
028/** This class represent a Binary Space Partition tree.
029
030 * <p>BSP trees are an efficient way to represent space partitions and
031 * to associate attributes with each cell. Each node in a BSP tree
032 * represents a convex region which is partitioned in two convex
033 * sub-regions at each side of a cut hyperplane. The root tree
034 * contains the complete space.</p>
035
036 * <p>The main use of such partitions is to use a boolean attribute to
037 * define an inside/outside property, hence representing arbitrary
038 * polytopes (line segments in 1D, polygons in 2D and polyhedrons in
039 * 3D) and to operate on them.</p>
040
041 * <p>Another example would be to represent Voronoi tesselations, the
042 * attribute of each cell holding the defining point of the cell.</p>
043
044 * <p>The application-defined attributes are shared among copied
045 * instances and propagated to split parts. These attributes are not
046 * used by the BSP-tree algorithms themselves, so the application can
047 * use them for any purpose. Since the tree visiting method holds
048 * internal and leaf nodes differently, it is possible to use
049 * different classes for internal nodes attributes and leaf nodes
050 * attributes. This should be used with care, though, because if the
051 * tree is modified in any way after attributes have been set, some
052 * internal nodes may become leaf nodes and some leaf nodes may become
053 * internal nodes.</p>
054
055 * <p>One of the main sources for the development of this package was
056 * Bruce Naylor, John Amanatides and William Thibault paper <a
057 * href="http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf">Merging
058 * BSP Trees Yields Polyhedral Set Operations</a> Proc. Siggraph '90,
059 * Computer Graphics 24(4), August 1990, pp 115-124, published by the
060 * Association for Computing Machinery (ACM).</p>
061
062 * @param <S> Type of the space.
063
064 * @version $Id: BSPTree.java 1560115 2014-01-21 17:49:13Z luc $
065 * @since 3.0
066 */
067public class BSPTree<S extends Space> {
068
069    /** Cut sub-hyperplane. */
070    private SubHyperplane<S> cut;
071
072    /** Tree at the plus side of the cut hyperplane. */
073    private BSPTree<S> plus;
074
075    /** Tree at the minus side of the cut hyperplane. */
076    private BSPTree<S> minus;
077
078    /** Parent tree. */
079    private BSPTree<S> parent;
080
081    /** Application-defined attribute. */
082    private Object attribute;
083
084    /** Build a tree having only one root cell representing the whole space.
085     */
086    public BSPTree() {
087        cut       = null;
088        plus      = null;
089        minus     = null;
090        parent    = null;
091        attribute = null;
092    }
093
094    /** Build a tree having only one root cell representing the whole space.
095     * @param attribute attribute of the tree (may be null)
096     */
097    public BSPTree(final Object attribute) {
098        cut    = null;
099        plus   = null;
100        minus  = null;
101        parent = null;
102        this.attribute = attribute;
103    }
104
105    /** Build a BSPTree from its underlying elements.
106     * <p>This method does <em>not</em> perform any verification on
107     * consistency of its arguments, it should therefore be used only
108     * when then caller knows what it is doing.</p>
109     * <p>This method is mainly useful to build trees
110     * bottom-up. Building trees top-down is realized with the help of
111     * method {@link #insertCut insertCut}.</p>
112     * @param cut cut sub-hyperplane for the tree
113     * @param plus plus side sub-tree
114     * @param minus minus side sub-tree
115     * @param attribute attribute associated with the node (may be null)
116     * @see #insertCut
117     */
118    public BSPTree(final SubHyperplane<S> cut, final BSPTree<S> plus, final BSPTree<S> minus,
119                   final Object attribute) {
120        this.cut       = cut;
121        this.plus      = plus;
122        this.minus     = minus;
123        this.parent    = null;
124        this.attribute = attribute;
125        plus.parent    = this;
126        minus.parent   = this;
127    }
128
129    /** Insert a cut sub-hyperplane in a node.
130     * <p>The sub-tree starting at this node will be completely
131     * overwritten. The new cut sub-hyperplane will be built from the
132     * intersection of the provided hyperplane with the cell. If the
133     * hyperplane does intersect the cell, the cell will have two
134     * children cells with {@code null} attributes on each side of
135     * the inserted cut sub-hyperplane. If the hyperplane does not
136     * intersect the cell then <em>no</em> cut hyperplane will be
137     * inserted and the cell will be changed to a leaf cell. The
138     * attribute of the node is never changed.</p>
139     * <p>This method is mainly useful when called on leaf nodes
140     * (i.e. nodes for which {@link #getCut getCut} returns
141     * {@code null}), in this case it provides a way to build a
142     * tree top-down (whereas the {@link #BSPTree(SubHyperplane,
143     * BSPTree, BSPTree, Object) 4 arguments constructor} is devoted to
144     * build trees bottom-up).</p>
145     * @param hyperplane hyperplane to insert, it will be chopped in
146     * order to fit in the cell defined by the parent nodes of the
147     * instance
148     * @return true if a cut sub-hyperplane has been inserted (i.e. if
149     * the cell now has two leaf child nodes)
150     * @see #BSPTree(SubHyperplane, BSPTree, BSPTree, Object)
151     */
152    public boolean insertCut(final Hyperplane<S> hyperplane) {
153
154        if (cut != null) {
155            plus.parent  = null;
156            minus.parent = null;
157        }
158
159        final SubHyperplane<S> chopped = fitToCell(hyperplane.wholeHyperplane());
160        if (chopped == null || chopped.isEmpty()) {
161            cut          = null;
162            plus         = null;
163            minus        = null;
164            return false;
165        }
166
167        cut          = chopped;
168        plus         = new BSPTree<S>();
169        plus.parent  = this;
170        minus        = new BSPTree<S>();
171        minus.parent = this;
172        return true;
173
174    }
175
176    /** Copy the instance.
177     * <p>The instance created is completely independent of the original
178     * one. A deep copy is used, none of the underlying objects are
179     * shared (except for the nodes attributes and immutable
180     * objects).</p>
181     * @return a new tree, copy of the instance
182     */
183    public BSPTree<S> copySelf() {
184
185        if (cut == null) {
186            return new BSPTree<S>(attribute);
187        }
188
189        return new BSPTree<S>(cut.copySelf(), plus.copySelf(), minus.copySelf(),
190                           attribute);
191
192    }
193
194    /** Get the cut sub-hyperplane.
195     * @return cut sub-hyperplane, null if this is a leaf tree
196     */
197    public SubHyperplane<S> getCut() {
198        return cut;
199    }
200
201    /** Get the tree on the plus side of the cut hyperplane.
202     * @return tree on the plus side of the cut hyperplane, null if this
203     * is a leaf tree
204     */
205    public BSPTree<S> getPlus() {
206        return plus;
207    }
208
209    /** Get the tree on the minus side of the cut hyperplane.
210     * @return tree on the minus side of the cut hyperplane, null if this
211     * is a leaf tree
212     */
213    public BSPTree<S> getMinus() {
214        return minus;
215    }
216
217    /** Get the parent node.
218     * @return parent node, null if the node has no parents
219     */
220    public BSPTree<S> getParent() {
221        return parent;
222    }
223
224    /** Associate an attribute with the instance.
225     * @param attribute attribute to associate with the node
226     * @see #getAttribute
227     */
228    public void setAttribute(final Object attribute) {
229        this.attribute = attribute;
230    }
231
232    /** Get the attribute associated with the instance.
233     * @return attribute associated with the node or null if no
234     * attribute has been explicitly set using the {@link #setAttribute
235     * setAttribute} method
236     * @see #setAttribute
237     */
238    public Object getAttribute() {
239        return attribute;
240    }
241
242    /** Visit the BSP tree nodes.
243     * @param visitor object visiting the tree nodes
244     */
245    public void visit(final BSPTreeVisitor<S> visitor) {
246        if (cut == null) {
247            visitor.visitLeafNode(this);
248        } else {
249            switch (visitor.visitOrder(this)) {
250            case PLUS_MINUS_SUB:
251                plus.visit(visitor);
252                minus.visit(visitor);
253                visitor.visitInternalNode(this);
254                break;
255            case PLUS_SUB_MINUS:
256                plus.visit(visitor);
257                visitor.visitInternalNode(this);
258                minus.visit(visitor);
259                break;
260            case MINUS_PLUS_SUB:
261                minus.visit(visitor);
262                plus.visit(visitor);
263                visitor.visitInternalNode(this);
264                break;
265            case MINUS_SUB_PLUS:
266                minus.visit(visitor);
267                visitor.visitInternalNode(this);
268                plus.visit(visitor);
269                break;
270            case SUB_PLUS_MINUS:
271                visitor.visitInternalNode(this);
272                plus.visit(visitor);
273                minus.visit(visitor);
274                break;
275            case SUB_MINUS_PLUS:
276                visitor.visitInternalNode(this);
277                minus.visit(visitor);
278                plus.visit(visitor);
279                break;
280            default:
281                throw new MathInternalError();
282            }
283
284        }
285    }
286
287    /** Fit a sub-hyperplane inside the cell defined by the instance.
288     * <p>Fitting is done by chopping off the parts of the
289     * sub-hyperplane that lie outside of the cell using the
290     * cut-hyperplanes of the parent nodes of the instance.</p>
291     * @param sub sub-hyperplane to fit
292     * @return a new sub-hyperplane, guaranteed to have no part outside
293     * of the instance cell
294     */
295    private SubHyperplane<S> fitToCell(final SubHyperplane<S> sub) {
296        SubHyperplane<S> s = sub;
297        for (BSPTree<S> tree = this; tree.parent != null; tree = tree.parent) {
298            if (tree == tree.parent.plus) {
299                s = s.split(tree.parent.cut.getHyperplane()).getPlus();
300            } else {
301                s = s.split(tree.parent.cut.getHyperplane()).getMinus();
302            }
303        }
304        return s;
305    }
306
307    /** Get the cell to which a point belongs.
308     * <p>If the returned cell is a leaf node the points belongs to the
309     * interior of the node, if the cell is an internal node the points
310     * belongs to the node cut sub-hyperplane.</p>
311     * @param point point to check
312     * @return the tree cell to which the point belongs
313     * @deprecated as of 3.3, replaced with {@link #getCell(Point, double)}
314     */
315    @Deprecated
316    public BSPTree<S> getCell(final Vector<S> point) {
317        return getCell((Point<S>) point, 1.0e-10);
318    }
319
320    /** Get the cell to which a point belongs.
321     * <p>If the returned cell is a leaf node the points belongs to the
322     * interior of the node, if the cell is an internal node the points
323     * belongs to the node cut sub-hyperplane.</p>
324     * @param point point to check
325     * @param tolerance tolerance below which points close to a cut hyperplane
326     * are considered to belong to the hyperplane itself
327     * @return the tree cell to which the point belongs
328     */
329    public BSPTree<S> getCell(final Point<S> point, final double tolerance) {
330
331        if (cut == null) {
332            return this;
333        }
334
335        // position of the point with respect to the cut hyperplane
336        final double offset = cut.getHyperplane().getOffset(point);
337
338        if (FastMath.abs(offset) < tolerance) {
339            return this;
340        } else if (offset <= 0) {
341            // point is on the minus side of the cut hyperplane
342            return minus.getCell(point, tolerance);
343        } else {
344            // point is on the plus side of the cut hyperplane
345            return plus.getCell(point, tolerance);
346        }
347
348    }
349
350    /** Get the cells whose cut sub-hyperplanes are close to the point.
351     * @param point point to check
352     * @param maxOffset offset below which a cut sub-hyperplane is considered
353     * close to the point (in absolute value)
354     * @return close cells (may be empty if all cut sub-hyperplanes are farther
355     * than maxOffset from the point)
356     */
357    public List<BSPTree<S>> getCloseCuts(final Point<S> point, final double maxOffset) {
358        final List<BSPTree<S>> close = new ArrayList<BSPTree<S>>();
359        recurseCloseCuts(point, maxOffset, close);
360        return close;
361    }
362
363    /** Get the cells whose cut sub-hyperplanes are close to the point.
364     * @param point point to check
365     * @param maxOffset offset below which a cut sub-hyperplane is considered
366     * close to the point (in absolute value)
367     * @param close list to fill
368     */
369    private void recurseCloseCuts(final Point<S> point, final double maxOffset,
370                                  final List<BSPTree<S>> close) {
371        if (cut != null) {
372
373            // position of the point with respect to the cut hyperplane
374            final double offset = cut.getHyperplane().getOffset(point);
375
376            if (offset < -maxOffset) {
377                // point is on the minus side of the cut hyperplane
378                minus.recurseCloseCuts(point, maxOffset, close);
379            } else if (offset > maxOffset) {
380                // point is on the plus side of the cut hyperplane
381                plus.recurseCloseCuts(point, maxOffset, close);
382            } else {
383                // point is close to the cut hyperplane
384                close.add(this);
385                minus.recurseCloseCuts(point, maxOffset, close);
386                plus.recurseCloseCuts(point, maxOffset, close);
387            }
388
389        }
390    }
391
392    /** Perform condensation on a tree.
393     * <p>The condensation operation is not recursive, it must be called
394     * explicitly from leaves to root.</p>
395     */
396    private void condense() {
397        if ((cut != null) && (plus.cut == null) && (minus.cut == null) &&
398            (((plus.attribute == null) && (minus.attribute == null)) ||
399             ((plus.attribute != null) && plus.attribute.equals(minus.attribute)))) {
400            attribute = (plus.attribute == null) ? minus.attribute : plus.attribute;
401            cut       = null;
402            plus      = null;
403            minus     = null;
404        }
405    }
406
407    /** Merge a BSP tree with the instance.
408     * <p>All trees are modified (parts of them are reused in the new
409     * tree), it is the responsibility of the caller to ensure a copy
410     * has been done before if any of the former tree should be
411     * preserved, <em>no</em> such copy is done here!</p>
412     * <p>The algorithm used here is directly derived from the one
413     * described in the Naylor, Amanatides and Thibault paper (section
414     * III, Binary Partitioning of a BSP Tree).</p>
415     * @param tree other tree to merge with the instance (will be
416     * <em>unusable</em> after the operation, as well as the
417     * instance itself)
418     * @param leafMerger object implementing the final merging phase
419     * (this is where the semantic of the operation occurs, generally
420     * depending on the attribute of the leaf node)
421     * @return a new tree, result of <code>instance &lt;op&gt;
422     * tree</code>, this value can be ignored if parentTree is not null
423     * since all connections have already been established
424     */
425    public BSPTree<S> merge(final BSPTree<S> tree, final LeafMerger<S> leafMerger) {
426        return merge(tree, leafMerger, null, false);
427    }
428
429    /** Merge a BSP tree with the instance.
430     * @param tree other tree to merge with the instance (will be
431     * <em>unusable</em> after the operation, as well as the
432     * instance itself)
433     * @param leafMerger object implementing the final merging phase
434     * (this is where the semantic of the operation occurs, generally
435     * depending on the attribute of the leaf node)
436     * @param parentTree parent tree to connect to (may be null)
437     * @param isPlusChild if true and if parentTree is not null, the
438     * resulting tree should be the plus child of its parent, ignored if
439     * parentTree is null
440     * @return a new tree, result of <code>instance &lt;op&gt;
441     * tree</code>, this value can be ignored if parentTree is not null
442     * since all connections have already been established
443     */
444    private BSPTree<S> merge(final BSPTree<S> tree, final LeafMerger<S> leafMerger,
445                             final BSPTree<S> parentTree, final boolean isPlusChild) {
446        if (cut == null) {
447            // cell/tree operation
448            return leafMerger.merge(this, tree, parentTree, isPlusChild, true);
449        } else if (tree.cut == null) {
450            // tree/cell operation
451            return leafMerger.merge(tree, this, parentTree, isPlusChild, false);
452        } else {
453            // tree/tree operation
454            final BSPTree<S> merged = tree.split(cut);
455            if (parentTree != null) {
456                merged.parent = parentTree;
457                if (isPlusChild) {
458                    parentTree.plus = merged;
459                } else {
460                    parentTree.minus = merged;
461                }
462            }
463
464            // merging phase
465            plus.merge(merged.plus, leafMerger, merged, true);
466            minus.merge(merged.minus, leafMerger, merged, false);
467            merged.condense();
468            if (merged.cut != null) {
469                merged.cut =
470                    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    /** Split a BSP tree by an external sub-hyperplane.
531     * <p>Split a tree in two halves, on each side of the
532     * sub-hyperplane. The instance is not modified.</p>
533     * <p>The tree returned is not upward-consistent: despite all of its
534     * sub-trees cut sub-hyperplanes (including its own cut
535     * sub-hyperplane) are bounded to the current cell, it is <em>not</em>
536     * attached to any parent tree yet. This tree is intended to be
537     * later inserted into an higher level tree.</p>
538     * <p>The algorithm used here is the one given in Naylor, Amanatides
539     * and Thibault paper (section III, Binary Partitioning of a BSP
540     * Tree).</p>
541     * @param sub partitioning sub-hyperplane, must be already clipped
542     * to the convex region represented by the instance, will be used as
543     * the cut sub-hyperplane of the returned tree
544     * @return a tree having the specified sub-hyperplane as its cut
545     * sub-hyperplane, the two parts of the split instance as its two
546     * sub-trees and a null parent
547     */
548    public BSPTree<S> split(final SubHyperplane<S> sub) {
549
550        if (cut == null) {
551            return new BSPTree<S>(sub, copySelf(),
552                    new BSPTree<S>(attribute), null);
553        }
554
555        final Hyperplane<S> cHyperplane = cut.getHyperplane();
556        final Hyperplane<S> sHyperplane = sub.getHyperplane();
557        switch (sub.side(cHyperplane)) {
558        case PLUS :
559        { // the partitioning sub-hyperplane is entirely in the plus sub-tree
560            final BSPTree<S> split = plus.split(sub);
561            if (cut.side(sHyperplane) == Side.PLUS) {
562                split.plus =
563                    new BSPTree<S>(cut.copySelf(), split.plus, minus.copySelf(), attribute);
564                split.plus.condense();
565                split.plus.parent = split;
566            } else {
567                split.minus =
568                    new BSPTree<S>(cut.copySelf(), split.minus, minus.copySelf(), attribute);
569                split.minus.condense();
570                split.minus.parent = split;
571            }
572            return split;
573        }
574        case MINUS :
575        { // the partitioning sub-hyperplane is entirely in the minus sub-tree
576            final BSPTree<S> split = minus.split(sub);
577            if (cut.side(sHyperplane) == Side.PLUS) {
578                split.plus =
579                    new BSPTree<S>(cut.copySelf(), plus.copySelf(), split.plus, attribute);
580                split.plus.condense();
581                split.plus.parent = split;
582            } else {
583                split.minus =
584                    new BSPTree<S>(cut.copySelf(), plus.copySelf(), split.minus, attribute);
585                split.minus.condense();
586                split.minus.parent = split;
587            }
588            return split;
589        }
590        case BOTH :
591        {
592            final SubHyperplane.SplitSubHyperplane<S> cutParts = cut.split(sHyperplane);
593            final SubHyperplane.SplitSubHyperplane<S> subParts = sub.split(cHyperplane);
594            final BSPTree<S> split =
595                new BSPTree<S>(sub, plus.split(subParts.getPlus()), minus.split(subParts.getMinus()),
596                               null);
597            split.plus.cut          = cutParts.getPlus();
598            split.minus.cut         = cutParts.getMinus();
599            final BSPTree<S> tmp    = split.plus.minus;
600            split.plus.minus        = split.minus.plus;
601            split.plus.minus.parent = split.plus;
602            split.minus.plus        = tmp;
603            split.minus.plus.parent = split.minus;
604            split.plus.condense();
605            split.minus.condense();
606            return split;
607        }
608        default :
609            return cHyperplane.sameOrientationAs(sHyperplane) ?
610                   new BSPTree<S>(sub, plus.copySelf(),  minus.copySelf(), attribute) :
611                   new BSPTree<S>(sub, minus.copySelf(), plus.copySelf(),  attribute);
612        }
613
614    }
615
616    /** Insert the instance into another tree.
617     * <p>The instance itself is modified so its former parent should
618     * not be used anymore.</p>
619     * @param parentTree parent tree to connect to (may be null)
620     * @param isPlusChild if true and if parentTree is not null, the
621     * resulting tree should be the plus child of its parent, ignored if
622     * parentTree is null
623     * @see LeafMerger
624     */
625    public void insertInTree(final BSPTree<S> parentTree, final boolean isPlusChild) {
626
627        // set up parent/child links
628        parent = parentTree;
629        if (parentTree != null) {
630            if (isPlusChild) {
631                parentTree.plus = this;
632            } else {
633                parentTree.minus = this;
634            }
635        }
636
637        // make sure the inserted tree lies in the cell defined by its parent nodes
638        if (cut != null) {
639
640            // explore the parent nodes from here towards tree root
641            for (BSPTree<S> tree = this; tree.parent != null; tree = tree.parent) {
642
643                // this is an hyperplane of some parent node
644                final Hyperplane<S> hyperplane = tree.parent.cut.getHyperplane();
645
646                // chop off the parts of the inserted tree that extend
647                // on the wrong side of this parent hyperplane
648                if (tree == tree.parent.plus) {
649                    cut = cut.split(hyperplane).getPlus();
650                    plus.chopOffMinus(hyperplane);
651                    minus.chopOffMinus(hyperplane);
652                } else {
653                    cut = cut.split(hyperplane).getMinus();
654                    plus.chopOffPlus(hyperplane);
655                    minus.chopOffPlus(hyperplane);
656                }
657
658            }
659
660            // since we may have drop some parts of the inserted tree,
661            // perform a condensation pass to keep the tree structure simple
662            condense();
663
664        }
665
666    }
667
668    /** Prune a tree around a cell.
669     * <p>
670     * This method can be used to extract a convex cell from a tree.
671     * The original cell may either be a leaf node or an internal node.
672     * If it is an internal node, it's subtree will be ignored (i.e. the
673     * extracted cell will be a leaf node in all cases). The original
674     * tree to which the original cell belongs is not touched at all,
675     * a new independent tree will be built.
676     * </p>
677     * @param cellAttribute attribute to set for the leaf node
678     * corresponding to the initial instance cell
679     * @param otherLeafsAttributes attribute to set for the other leaf
680     * nodes
681     * @param internalAttributes attribute to set for the internal nodes
682     * @return a new tree (the original tree is left untouched) containing
683     * a single branch with the cell as a leaf node, and other leaf nodes
684     * as the remnants of the pruned branches
685     * @since 3.3
686     */
687    public BSPTree<S> pruneAroundConvexCell(final Object cellAttribute,
688                                            final Object otherLeafsAttributes,
689                                            final Object internalAttributes) {
690
691        // build the current cell leaf
692        BSPTree<S> tree = new BSPTree<S>(cellAttribute);
693
694        // build the pruned tree bottom-up
695        for (BSPTree<S> current = this; current.parent != null; current = current.parent) {
696            final SubHyperplane<S> parentCut = current.parent.cut.copySelf();
697            final BSPTree<S>       sibling   = new BSPTree<S>(otherLeafsAttributes);
698            if (current == current.parent.plus) {
699                tree = new BSPTree<S>(parentCut, tree, sibling, internalAttributes);
700            } else {
701                tree = new BSPTree<S>(parentCut, sibling, tree, internalAttributes);
702            }
703        }
704
705        return tree;
706
707    }
708
709    /** Chop off parts of the tree.
710     * <p>The instance is modified in place, all the parts that are on
711     * the minus side of the chopping hyperplane are discarded, only the
712     * parts on the plus side remain.</p>
713     * @param hyperplane chopping hyperplane
714     */
715    private void chopOffMinus(final Hyperplane<S> hyperplane) {
716        if (cut != null) {
717            cut = cut.split(hyperplane).getPlus();
718            plus.chopOffMinus(hyperplane);
719            minus.chopOffMinus(hyperplane);
720        }
721    }
722
723    /** Chop off parts of the tree.
724     * <p>The instance is modified in place, all the parts that are on
725     * the plus side of the chopping hyperplane are discarded, only the
726     * parts on the minus side remain.</p>
727     * @param hyperplane chopping hyperplane
728     */
729    private void chopOffPlus(final Hyperplane<S> hyperplane) {
730        if (cut != null) {
731            cut = cut.split(hyperplane).getMinus();
732            plus.chopOffPlus(hyperplane);
733            minus.chopOffPlus(hyperplane);
734        }
735    }
736
737}