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