    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     */
    017    package org.apache.commons.math3.geometry.partitioning;
    018
    019    import org.apache.commons.math3.exception.MathInternalError;
    020    import org.apache.commons.math3.geometry.Vector;
    021    import org.apache.commons.math3.geometry.Space;
    022    import org.apache.commons.math3.util.FastMath;
    023
    024    /** This class represent a Binary Space Partition tree.
    025
    026     * <p>BSP trees are an efficient way to represent space partitions and
    027     * to associate attributes with each cell. Each node in a BSP tree
    028     * represents a convex region which is partitioned in two convex
    029     * sub-regions at each side of a cut hyperplane. The root tree
    030     * contains the complete space.</p>
    031
    032     * <p>The main use of such partitions is to use a boolean attribute to
    033     * define an inside/outside property, hence representing arbitrary
    034     * polytopes (line segments in 1D, polygons in 2D and polyhedrons in
    035     * 3D) and to operate on them.</p>
    036
    037     * <p>Another example would be to represent Voronoi tesselations, the
    038     * attribute of each cell holding the defining point of the cell.</p>
    039
    040     * <p>The application-defined attributes are shared among copied
    041     * instances and propagated to split parts. These attributes are not
    042     * used by the BSP-tree algorithms themselves, so the application can
    043     * use them for any purpose. Since the tree visiting method holds
    044     * internal and leaf nodes differently, it is possible to use
    045     * different classes for internal nodes attributes and leaf nodes
    046     * attributes. This should be used with care, though, because if the
    047     * tree is modified in any way after attributes have been set, some
    048     * internal nodes may become leaf nodes and some leaf nodes may become
    049     * internal nodes.</p>
    050
    051     * <p>One of the main sources for the development of this package was
    052     * Bruce Naylor, John Amanatides and William Thibault paper <a
    053     * href="http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf">Merging
    054     * BSP Trees Yields Polyhedral Set Operations</a> Proc. Siggraph '90,
    055     * Computer Graphics 24(4), August 1990, pp 115-124, published by the
    056     * Association for Computing Machinery (ACM).</p>
    057
    058     * @param <S> Type of the space.
    059
    060     * @version $Id: BSPTree.java 1416643 2012-12-03 19:37:14Z tn $
    061     * @since 3.0
    062     */
    063    public class BSPTree<S extends Space> {
    064
    065        /** Cut sub-hyperplane. */
    066        private SubHyperplane<S> cut;
    067
    068        /** Tree at the plus side of the cut hyperplane. */
    069        private BSPTree<S> plus;
    070
    071        /** Tree at the minus side of the cut hyperplane. */
    072        private BSPTree<S> minus;
    073
    074        /** Parent tree. */
    075        private BSPTree<S> parent;
    076
    077        /** Application-defined attribute. */
    078        private Object attribute;
    079
    080        /** Build a tree having only one root cell representing the whole space.
    081         */
    082        public BSPTree() {
    083            cut       = null;
    084            plus      = null;
    085            minus     = null;
    086            parent    = null;
    087            attribute = null;
    088        }
    089
    090        /** Build a tree having only one root cell representing the whole space.
    091         * @param attribute attribute of the tree (may be null)
    092         */
    093        public BSPTree(final Object attribute) {
    094            cut    = null;
    095            plus   = null;
    096            minus  = null;
    097            parent = null;
    098            this.attribute = attribute;
    099        }
    100
    101        /** Build a BSPTree from its underlying elements.
    102         * <p>This method does <em>not</em> perform any verification on
    103         * consistency of its arguments, it should therefore be used only
    104         * when then caller knows what it is doing.</p>
    105         * <p>This method is mainly useful kto build trees
    106         * bottom-up. Building trees top-down is realized with the help of
    107         * method {@link #insertCut insertCut}.</p>
    108         * @param cut cut sub-hyperplane for the tree
    109         * @param plus plus side sub-tree
    110         * @param minus minus side sub-tree
    111         * @param attribute attribute associated with the node (may be null)
    112         * @see #insertCut
    113         */
    114        public BSPTree(final SubHyperplane<S> cut, final BSPTree<S> plus, final BSPTree<S> minus,
    115                       final Object attribute) {
    116            this.cut       = cut;
    117            this.plus      = plus;
    118            this.minus     = minus;
    119            this.parent    = null;
    120            this.attribute = attribute;
    121            plus.parent    = this;
    122            minus.parent   = this;
    123        }
    124
    125        /** Insert a cut sub-hyperplane in a node.
    126         * <p>The sub-tree starting at this node will be completely
    127         * overwritten. The new cut sub-hyperplane will be built from the
    128         * intersection of the provided hyperplane with the cell. If the
    129         * hyperplane does intersect the cell, the cell will have two
    130         * children cells with {@code null} attributes on each side of
    131         * the inserted cut sub-hyperplane. If the hyperplane does not
    132         * intersect the cell then <em>no</em> cut hyperplane will be
    133         * inserted and the cell will be changed to a leaf cell. The
    134         * attribute of the node is never changed.</p>
    135         * <p>This method is mainly useful when called on leaf nodes
    136         * (i.e. nodes for which {@link #getCut getCut} returns
    137         * {@code null}), in this case it provides a way to build a
    138         * tree top-down (whereas the {@link #BSPTree(SubHyperplane,
    139         * BSPTree, BSPTree, Object) 4 arguments constructor} is devoted to
    140         * build trees bottom-up).</p>
    141         * @param hyperplane hyperplane to insert, it will be chopped in
    142         * order to fit in the cell defined by the parent nodes of the
    143         * instance
    144         * @return true if a cut sub-hyperplane has been inserted (i.e. if
    145         * the cell now has two leaf child nodes)
    146         * @see #BSPTree(SubHyperplane, BSPTree, BSPTree, Object)
    147         */
    148        public boolean insertCut(final Hyperplane<S> hyperplane) {
    149
    150            if (cut != null) {
    151                plus.parent  = null;
    152                minus.parent = null;
    153            }
    154
    155            final SubHyperplane<S> chopped = fitToCell(hyperplane.wholeHyperplane());
    156            if (chopped == null || chopped.isEmpty()) {
    157                cut          = null;
    158                plus         = null;
    159                minus        = null;
    160                return false;
    161            }
    162
    163            cut          = chopped;
    164            plus         = new BSPTree<S>();
    165            plus.parent  = this;
    166            minus        = new BSPTree<S>();
    167            minus.parent = this;
    168            return true;
    169
    170        }
    171
    172        /** Copy the instance.
    173         * <p>The instance created is completely independant of the original
    174         * one. A deep copy is used, none of the underlying objects are
    175         * shared (except for the nodes attributes and immutable
    176         * objects).</p>
    177         * @return a new tree, copy of the instance
    178         */
    179        public BSPTree<S> copySelf() {
    180
    181            if (cut == null) {
    182                return new BSPTree<S>(attribute);
    183            }
    184
    185            return new BSPTree<S>(cut.copySelf(), plus.copySelf(), minus.copySelf(),
    186                               attribute);
    187
    188        }
    189
    190        /** Get the cut sub-hyperplane.
    191         * @return cut sub-hyperplane, null if this is a leaf tree
    192         */
    193        public SubHyperplane<S> getCut() {
    194            return cut;
    195        }
    196
    197        /** Get the tree on the plus side of the cut hyperplane.
    198         * @return tree on the plus side of the cut hyperplane, null if this
    199         * is a leaf tree
    200         */
    201        public BSPTree<S> getPlus() {
    202            return plus;
    203        }
    204
    205        /** Get the tree on the minus side of the cut hyperplane.
    206         * @return tree on the minus side of the cut hyperplane, null if this
    207         * is a leaf tree
    208         */
    209        public BSPTree<S> getMinus() {
    210            return minus;
    211        }
    212
    213        /** Get the parent node.
    214         * @return parent node, null if the node has no parents
    215         */
    216        public BSPTree<S> getParent() {
    217            return parent;
    218        }
    219
    220        /** Associate an attribute with the instance.
    221         * @param attribute attribute to associate with the node
    222         * @see #getAttribute
    223         */
    224        public void setAttribute(final Object attribute) {
    225            this.attribute = attribute;
    226        }
    227
    228        /** Get the attribute associated with the instance.
    229         * @return attribute associated with the node or null if no
    230         * attribute has been explicitly set using the {@link #setAttribute
    231         * setAttribute} method
    232         * @see #setAttribute
    233         */
    234        public Object getAttribute() {
    235            return attribute;
    236        }
    237
    238        /** Visit the BSP tree nodes.
    239         * @param visitor object visiting the tree nodes
    240         */
    241        public void visit(final BSPTreeVisitor<S> visitor) {
    242            if (cut == null) {
    243                visitor.visitLeafNode(this);
    244            } else {
    245                switch (visitor.visitOrder(this)) {
    246                case PLUS_MINUS_SUB:
    247                    plus.visit(visitor);
    248                    minus.visit(visitor);
    249                    visitor.visitInternalNode(this);
    250                    break;
    251                case PLUS_SUB_MINUS:
    252                    plus.visit(visitor);
    253                    visitor.visitInternalNode(this);
    254                    minus.visit(visitor);
    255                    break;
    256                case MINUS_PLUS_SUB:
    257                    minus.visit(visitor);
    258                    plus.visit(visitor);
    259                    visitor.visitInternalNode(this);
    260                    break;
    261                case MINUS_SUB_PLUS:
    262                    minus.visit(visitor);
    263                    visitor.visitInternalNode(this);
    264                    plus.visit(visitor);
    265                    break;
    266                case SUB_PLUS_MINUS:
    267                    visitor.visitInternalNode(this);
    268                    plus.visit(visitor);
    269                    minus.visit(visitor);
    270                    break;
    271                case SUB_MINUS_PLUS:
    272                    visitor.visitInternalNode(this);
    273                    minus.visit(visitor);
    274                    plus.visit(visitor);
    275                    break;
    276                default:
    277                    throw new MathInternalError();
    278                }
    279
    280            }
    281        }
    282
    283        /** Fit a sub-hyperplane inside the cell defined by the instance.
    284         * <p>Fitting is done by chopping off the parts of the
    285         * sub-hyperplane that lie outside of the cell using the
    286         * cut-hyperplanes of the parent nodes of the instance.</p>
    287         * @param sub sub-hyperplane to fit
    288         * @return a new sub-hyperplane, guaranteed to have no part outside
    289         * of the instance cell
    290         */
    291        private SubHyperplane<S> fitToCell(final SubHyperplane<S> sub) {
    292            SubHyperplane<S> s = sub;
    293            for (BSPTree<S> tree = this; tree.parent != null; tree = tree.parent) {
    294                if (tree == tree.parent.plus) {
    295                    s = s.split(tree.parent.cut.getHyperplane()).getPlus();
    296                } else {
    297                    s = s.split(tree.parent.cut.getHyperplane()).getMinus();
    298                }
    299            }
    300            return s;
    301        }
    302
    303        /** Get the cell to which a point belongs.
    304         * <p>If the returned cell is a leaf node the points belongs to the
    305         * interior of the node, if the cell is an internal node the points
    306         * belongs to the node cut sub-hyperplane.</p>
    307         * @param point point to check
    308         * @return the tree cell to which the point belongs (can be
    309         */
    310        public BSPTree<S> getCell(final Vector<S> point) {
    311
    312            if (cut == null) {
    313                return this;
    314            }
    315
    316            // position of the point with respect to the cut hyperplane
    317            final double offset = cut.getHyperplane().getOffset(point);
    318
    319            if (FastMath.abs(offset) < 1.0e-10) {
    320                return this;
    321            } else if (offset <= 0) {
    322                // point is on the minus side of the cut hyperplane
    323                return minus.getCell(point);
    324            } else {
    325                // point is on the plus side of the cut hyperplane
    326                return plus.getCell(point);
    327            }
    328
    329        }
    330
    331        /** Perform condensation on a tree.
    332         * <p>The condensation operation is not recursive, it must be called
    333         * explicitely from leaves to root.</p>
    334         */
    335        private void condense() {
    336            if ((cut != null) && (plus.cut == null) && (minus.cut == null) &&
    337                (((plus.attribute == null) && (minus.attribute == null)) ||
    338                 ((plus.attribute != null) && plus.attribute.equals(minus.attribute)))) {
    339                attribute = (plus.attribute == null) ? minus.attribute : plus.attribute;
    340                cut       = null;
    341                plus      = null;
    342                minus     = null;
    343            }
    344        }
    345
    346        /** Merge a BSP tree with the instance.
    347         * <p>All trees are modified (parts of them are reused in the new
    348         * tree), it is the responsibility of the caller to ensure a copy
    349         * has been done before if any of the former tree should be
    350         * preserved, <em>no</em> such copy is done here!</p>
    351         * <p>The algorithm used here is directly derived from the one
    352         * described in the Naylor, Amanatides and Thibault paper (section
    353         * III, Binary Partitioning of a BSP Tree).</p>
    354         * @param tree other tree to merge with the instance (will be
    355         * <em>unusable</em> after the operation, as well as the
    356         * instance itself)
    357         * @param leafMerger object implementing the final merging phase
    358         * (this is where the semantic of the operation occurs, generally
    359         * depending on the attribute of the leaf node)
    360         * @return a new tree, result of <code>instance &lt;op&gt;
    361         * tree</code>, this value can be ignored if parentTree is not null
    362         * since all connections have already been established
    363         */
    364        public BSPTree<S> merge(final BSPTree<S> tree, final LeafMerger<S> leafMerger) {
    365            return merge(tree, leafMerger, null, false);
    366        }
    367
    368        /** Merge a BSP tree with the instance.
    369         * @param tree other tree to merge with the instance (will be
    370         * <em>unusable</em> after the operation, as well as the
    371         * instance itself)
    372         * @param leafMerger object implementing the final merging phase
    373         * (this is where the semantic of the operation occurs, generally
    374         * depending on the attribute of the leaf node)
    375         * @param parentTree parent tree to connect to (may be null)
    376         * @param isPlusChild if true and if parentTree is not null, the
    377         * resulting tree should be the plus child of its parent, ignored if
    378         * parentTree is null
    379         * @return a new tree, result of <code>instance &lt;op&gt;
    380         * tree</code>, this value can be ignored if parentTree is not null
    381         * since all connections have already been established
    382         */
    383        private BSPTree<S> merge(final BSPTree<S> tree, final LeafMerger<S> leafMerger,
    384                                 final BSPTree<S> parentTree, final boolean isPlusChild) {
    385            if (cut == null) {
    386                // cell/tree operation
    387                return leafMerger.merge(this, tree, parentTree, isPlusChild, true);
    388            } else if (tree.cut == null) {
    389                // tree/cell operation
    390                return leafMerger.merge(tree, this, parentTree, isPlusChild, false);
    391            } else {
    392                // tree/tree operation
    393                final BSPTree<S> merged = tree.split(cut);
    394                if (parentTree != null) {
    395                    merged.parent = parentTree;
    396                    if (isPlusChild) {
    397                        parentTree.plus = merged;
    398                    } else {
    399                        parentTree.minus = merged;
    400                    }
    401                }
    402
    403                // merging phase
    404                plus.merge(merged.plus, leafMerger, merged, true);
    405                minus.merge(merged.minus, leafMerger, merged, false);
    406                merged.condense();
    407                if (merged.cut != null) {
    408                    merged.cut =
    409                        merged.fitToCell(merged.cut.getHyperplane().wholeHyperplane());
    410                }
    411
    412                return merged;
    413
    414            }
    415        }
    416
    417        /** This interface gather the merging operations between a BSP tree
    418         * leaf and another BSP tree.
    419         * <p>As explained in Bruce Naylor, John Amanatides and William
    420         * Thibault paper <a
    421         * href="http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf">Merging
    422         * BSP Trees Yields Polyhedral Set Operations</a>,
    423         * the operations on {@link BSPTree BSP trees} can be expressed as a
    424         * generic recursive merging operation where only the final part,
    425         * when one of the operand is a leaf, is specific to the real
    426         * operation semantics. For example, a tree representing a region
    427         * using a boolean attribute to identify inside cells and outside
    428         * cells would use four different objects to implement the final
    429         * merging phase of the four set operations union, intersection,
    430         * difference and symmetric difference (exclusive or).</p>
    431         * @param <S> Type of the space.
    432         */
    433        public interface LeafMerger<S extends Space> {
    434
    435            /** Merge a leaf node and a tree node.
    436             * <p>This method is called at the end of a recursive merging
    437             * resulting from a {@code tree1.merge(tree2, leafMerger)}
    438             * call, when one of the sub-trees involved is a leaf (i.e. when
    439             * its cut-hyperplane is null). This is the only place where the
    440             * precise semantics of the operation are required. For all upper
    441             * level nodes in the tree, the merging operation is only a
    442             * generic partitioning algorithm.</p>
    443             * <p>Since the final operation may be non-commutative, it is
    444             * important to know if the leaf node comes from the instance tree
    445             * ({@code tree1}) or the argument tree
    446             * ({@code tree2}). The third argument of the method is
    447             * devoted to this. It can be ignored for commutative
    448             * operations.</p>
    449             * <p>The {@link BSPTree#insertInTree BSPTree.insertInTree} method
    450             * may be useful to implement this method.</p>
    451             * @param leaf leaf node (its cut hyperplane is guaranteed to be
    452             * null)
    453             * @param tree tree node (its cut hyperplane may be null or not)
    454             * @param parentTree parent tree to connect to (may be null)
    455             * @param isPlusChild if true and if parentTree is not null, the
    456             * resulting tree should be the plus child of its parent, ignored if
    457             * parentTree is null
    458             * @param leafFromInstance if true, the leaf node comes from the
    459             * instance tree ({@code tree1}) and the tree node comes from
    460             * the argument tree ({@code tree2})
    461             * @return the BSP tree resulting from the merging (may be one of
    462             * the arguments)
    463             */
    464            BSPTree<S> merge(BSPTree<S> leaf, BSPTree<S> tree, BSPTree<S> parentTree,
    465                             boolean isPlusChild, boolean leafFromInstance);
    466
    467        }
    468
    469        /** Split a BSP tree by an external sub-hyperplane.
    470         * <p>Split a tree in two halves, on each side of the
    471         * sub-hyperplane. The instance is not modified.</p>
    472         * <p>The tree returned is not upward-consistent: despite all of its
    473         * sub-trees cut sub-hyperplanes (including its own cut
    474         * sub-hyperplane) are bounded to the current cell, it is <em>not</em>
    475         * attached to any parent tree yet. This tree is intended to be
    476         * later inserted into an higher level tree.</p>
    477         * <p>The algorithm used here is the one given in Naylor, Amanatides
    478         * and Thibault paper (section III, Binary Partitioning of a BSP
    479         * Tree).</p>
    480         * @param sub partitioning sub-hyperplane, must be already clipped
    481         * to the convex region represented by the instance, will be used as
    482         * the cut sub-hyperplane of the returned tree
    483         * @return a tree having the specified sub-hyperplane as its cut
    484         * sub-hyperplane, the two parts of the split instance as its two
    485         * sub-trees and a null parent
    486         */
    487        public BSPTree<S> split(final SubHyperplane<S> sub) {
    488
    489            if (cut == null) {
    490                return new BSPTree<S>(sub, copySelf(),
    491                        new BSPTree<S>(attribute), null);
    492            }
    493
    494            final Hyperplane<S> cHyperplane = cut.getHyperplane();
    495            final Hyperplane<S> sHyperplane = sub.getHyperplane();
    496            switch (sub.side(cHyperplane)) {
    497            case PLUS :
    498            { // the partitioning sub-hyperplane is entirely in the plus sub-tree
    499                final BSPTree<S> split = plus.split(sub);
    500                if (cut.side(sHyperplane) == Side.PLUS) {
    501                    split.plus =
    502                        new BSPTree<S>(cut.copySelf(), split.plus, minus.copySelf(), attribute);
    503                    split.plus.condense();
    504                    split.plus.parent = split;
    505                } else {
    506                    split.minus =
    507                        new BSPTree<S>(cut.copySelf(), split.minus, minus.copySelf(), attribute);
    508                    split.minus.condense();
    509                    split.minus.parent = split;
    510                }
    511                return split;
    512            }
    513            case MINUS :
    514            { // the partitioning sub-hyperplane is entirely in the minus sub-tree
    515                final BSPTree<S> split = minus.split(sub);
    516                if (cut.side(sHyperplane) == Side.PLUS) {
    517                    split.plus =
    518                        new BSPTree<S>(cut.copySelf(), plus.copySelf(), split.plus, attribute);
    519                    split.plus.condense();
    520                    split.plus.parent = split;
    521                } else {
    522                    split.minus =
    523                        new BSPTree<S>(cut.copySelf(), plus.copySelf(), split.minus, attribute);
    524                    split.minus.condense();
    525                    split.minus.parent = split;
    526                }
    527                return split;
    528            }
    529            case BOTH :
    530            {
    531                final SubHyperplane.SplitSubHyperplane<S> cutParts = cut.split(sHyperplane);
    532                final SubHyperplane.SplitSubHyperplane<S> subParts = sub.split(cHyperplane);
    533                final BSPTree<S> split =
    534                    new BSPTree<S>(sub, plus.split(subParts.getPlus()), minus.split(subParts.getMinus()),
    535                                   null);
    536                split.plus.cut          = cutParts.getPlus();
    537                split.minus.cut         = cutParts.getMinus();
    538                final BSPTree<S> tmp    = split.plus.minus;
    539                split.plus.minus        = split.minus.plus;
    540                split.plus.minus.parent = split.plus;
    541                split.minus.plus        = tmp;
    542                split.minus.plus.parent = split.minus;
    543                split.plus.condense();
    544                split.minus.condense();
    545                return split;
    546            }
    547            default :
    548                return cHyperplane.sameOrientationAs(sHyperplane) ?
    549                       new BSPTree<S>(sub, plus.copySelf(),  minus.copySelf(), attribute) :
    550                       new BSPTree<S>(sub, minus.copySelf(), plus.copySelf(),  attribute);
    551            }
    552
    553        }
    554
    555        /** Insert the instance into another tree.
    556         * <p>The instance itself is modified so its former parent should
    557         * not be used anymore.</p>
    558         * @param parentTree parent tree to connect to (may be null)
    559         * @param isPlusChild if true and if parentTree is not null, the
    560         * resulting tree should be the plus child of its parent, ignored if
    561         * parentTree is null
    562         * @see LeafMerger
    563         */
    564        public void insertInTree(final BSPTree<S> parentTree, final boolean isPlusChild) {
    565
    566            // set up parent/child links
    567            parent = parentTree;
    568            if (parentTree != null) {
    569                if (isPlusChild) {
    570                    parentTree.plus = this;
    571                } else {
    572                    parentTree.minus = this;
    573                }
    574            }
    575
    576            // make sure the inserted tree lies in the cell defined by its parent nodes
    577            if (cut != null) {
    578
    579                // explore the parent nodes from here towards tree root
    580                for (BSPTree<S> tree = this; tree.parent != null; tree = tree.parent) {
    581
    582                    // this is an hyperplane of some parent node
    583                    final Hyperplane<S> hyperplane = tree.parent.cut.getHyperplane();
    584
    585                    // chop off the parts of the inserted tree that extend
    586                    // on the wrong side of this parent hyperplane
    587                    if (tree == tree.parent.plus) {
    588                        cut = cut.split(hyperplane).getPlus();
    589                        plus.chopOffMinus(hyperplane);
    590                        minus.chopOffMinus(hyperplane);
    591                    } else {
    592                        cut = cut.split(hyperplane).getMinus();
    593                        plus.chopOffPlus(hyperplane);
    594                        minus.chopOffPlus(hyperplane);
    595                    }
    596
    597                }
    598
    599                // since we may have drop some parts of the inserted tree,
    600                // perform a condensation pass to keep the tree structure simple
    601                condense();
    602
    603            }
    604
    605        }
    606
    607        /** Chop off parts of the tree.
    608         * <p>The instance is modified in place, all the parts that are on
    609         * the minus side of the chopping hyperplane are discarded, only the
    610         * parts on the plus side remain.</p>
    611         * @param hyperplane chopping hyperplane
    612         */
    613        private void chopOffMinus(final Hyperplane<S> hyperplane) {
    614            if (cut != null) {
    615                cut = cut.split(hyperplane).getPlus();
    616                plus.chopOffMinus(hyperplane);
    617                minus.chopOffMinus(hyperplane);
    618            }
    619        }
    620
    621        /** Chop off parts of the tree.
    622         * <p>The instance is modified in place, all the parts that are on
    623         * the plus side of the chopping hyperplane are discarded, only the
    624         * parts on the minus side remain.</p>
    625         * @param hyperplane chopping hyperplane
    626         */
    627        private void chopOffPlus(final Hyperplane<S> hyperplane) {
    628            if (cut != null) {
    629                cut = cut.split(hyperplane).getMinus();
    630                plus.chopOffPlus(hyperplane);
    631                minus.chopOffPlus(hyperplane);
    632            }
    633        }
    634
    635    }