    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 java.lang.reflect.Array;
    020    import java.util.ArrayList;
    021    import java.util.Collection;
    022    import java.util.Comparator;
    023    import java.util.Iterator;
    024    import java.util.TreeSet;
    025
    026    import org.apache.commons.math3.exception.MathInternalError;
    027    import org.apache.commons.math3.geometry.Space;
    028    import org.apache.commons.math3.geometry.Vector;
    029
    030    /** Abstract class for all regions, independently of geometry type or dimension.
    031
    032     * @param <S> Type of the space.
    033     * @param <T> Type of the sub-space.
    034
    035     * @version $Id: AbstractRegion.java 1416643 2012-12-03 19:37:14Z tn $
    036     * @since 3.0
    037     */
    038    public abstract class AbstractRegion<S extends Space, T extends Space> implements Region<S> {
    039
    040        /** Inside/Outside BSP tree. */
    041        private BSPTree<S> tree;
    042
    043        /** Size of the instance. */
    044        private double size;
    045
    046        /** Barycenter. */
    047        private Vector<S> barycenter;
    048
    049        /** Build a region representing the whole space.
    050         */
    051        protected AbstractRegion() {
    052            tree = new BSPTree<S>(Boolean.TRUE);
    053        }
    054
    055        /** Build a region from an inside/outside BSP tree.
    056         * <p>The leaf nodes of the BSP tree <em>must</em> have a
    057         * {@code Boolean} attribute representing the inside status of
    058         * the corresponding cell (true for inside cells, false for outside
    059         * cells). In order to avoid building too many small objects, it is
    060         * recommended to use the predefined constants
    061         * {@code Boolean.TRUE} and {@code Boolean.FALSE}. The
    062         * tree also <em>must</em> have either null internal nodes or
    063         * internal nodes representing the boundary as specified in the
    064         * {@link #getTree getTree} method).</p>
    065         * @param tree inside/outside BSP tree representing the region
    066         */
    067        protected AbstractRegion(final BSPTree<S> tree) {
    068            this.tree = tree;
    069        }
    070
    071        /** Build a Region from a Boundary REPresentation (B-rep).
    072         * <p>The boundary is provided as a collection of {@link
    073         * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the
    074         * interior part of the region on its minus side and the exterior on
    075         * its plus side.</p>
    076         * <p>The boundary elements can be in any order, and can form
    077         * several non-connected sets (like for example polygons with holes
    078         * or a set of disjoints polyhedrons considered as a whole). In
    079         * fact, the elements do not even need to be connected together
    080         * (their topological connections are not used here). However, if the
    081         * boundary does not really separate an inside open from an outside
    082         * open (open having here its topological meaning), then subsequent
    083         * calls to the {@link #checkPoint(Vector) checkPoint} method will not be
    084         * meaningful anymore.</p>
    085         * <p>If the boundary is empty, the region will represent the whole
    086         * space.</p>
    087         * @param boundary collection of boundary elements, as a
    088         * collection of {@link SubHyperplane SubHyperplane} objects
    089         */
    090        protected AbstractRegion(final Collection<SubHyperplane<S>> boundary) {
    091
    092            if (boundary.size() == 0) {
    093
    094                // the tree represents the whole space
    095                tree = new BSPTree<S>(Boolean.TRUE);
    096
    097            } else {
    098
    099                // sort the boundary elements in decreasing size order
    100                // (we don't want equal size elements to be removed, so
    101                // we use a trick to fool the TreeSet)
    102                final TreeSet<SubHyperplane<S>> ordered = new TreeSet<SubHyperplane<S>>(new Comparator<SubHyperplane<S>>() {
    103                    public int compare(final SubHyperplane<S> o1, final SubHyperplane<S> o2) {
    104                        final double size1 = o1.getSize();
    105                        final double size2 = o2.getSize();
    106                        return (size2 < size1) ? -1 : ((o1 == o2) ? 0 : +1);
    107                    }
    108                });
    109                ordered.addAll(boundary);
    110
    111                // build the tree top-down
    112                tree = new BSPTree<S>();
    113                insertCuts(tree, ordered);
    114
    115                // set up the inside/outside flags
    116                tree.visit(new BSPTreeVisitor<S>() {
    117
    118                    /** {@inheritDoc} */
    119                    public Order visitOrder(final BSPTree<S> node) {
    120                        return Order.PLUS_SUB_MINUS;
    121                    }
    122
    123                    /** {@inheritDoc} */
    124                    public void visitInternalNode(final BSPTree<S> node) {
    125                    }
    126
    127                    /** {@inheritDoc} */
    128                    public void visitLeafNode(final BSPTree<S> node) {
    129                        node.setAttribute((node == node.getParent().getPlus()) ?
    130                                                                                Boolean.FALSE : Boolean.TRUE);
    131                    }
    132                });
    133
    134            }
    135
    136        }
    137
    138        /** Build a convex region from an array of bounding hyperplanes.
    139         * @param hyperplanes array of bounding hyperplanes (if null, an
    140         * empty region will be built)
    141         */
    142        public AbstractRegion(final Hyperplane<S>[] hyperplanes) {
    143            if ((hyperplanes == null) || (hyperplanes.length == 0)) {
    144                tree = new BSPTree<S>(Boolean.FALSE);
    145            } else {
    146
    147                // use the first hyperplane to build the right class
    148                tree = hyperplanes[0].wholeSpace().getTree(false);
    149
    150                // chop off parts of the space
    151                BSPTree<S> node = tree;
    152                node.setAttribute(Boolean.TRUE);
    153                for (final Hyperplane<S> hyperplane : hyperplanes) {
    154                    if (node.insertCut(hyperplane)) {
    155                        node.setAttribute(null);
    156                        node.getPlus().setAttribute(Boolean.FALSE);
    157                        node = node.getMinus();
    158                        node.setAttribute(Boolean.TRUE);
    159                    }
    160                }
    161
    162            }
    163
    164        }
    165
    166        /** {@inheritDoc} */
    167        public abstract AbstractRegion<S, T> buildNew(BSPTree<S> newTree);
    168
    169        /** Recursively build a tree by inserting cut sub-hyperplanes.
    170         * @param node current tree node (it is a leaf node at the beginning
    171         * of the call)
    172         * @param boundary collection of edges belonging to the cell defined
    173         * by the node
    174         */
    175        private void insertCuts(final BSPTree<S> node, final Collection<SubHyperplane<S>> boundary) {
    176
    177            final Iterator<SubHyperplane<S>> iterator = boundary.iterator();
    178
    179            // build the current level
    180            Hyperplane<S> inserted = null;
    181            while ((inserted == null) && iterator.hasNext()) {
    182                inserted = iterator.next().getHyperplane();
    183                if (!node.insertCut(inserted.copySelf())) {
    184                    inserted = null;
    185                }
    186            }
    187
    188            if (!iterator.hasNext()) {
    189                return;
    190            }
    191
    192            // distribute the remaining edges in the two sub-trees
    193            final ArrayList<SubHyperplane<S>> plusList  = new ArrayList<SubHyperplane<S>>();
    194            final ArrayList<SubHyperplane<S>> minusList = new ArrayList<SubHyperplane<S>>();
    195            while (iterator.hasNext()) {
    196                final SubHyperplane<S> other = iterator.next();
    197                switch (other.side(inserted)) {
    198                case PLUS:
    199                    plusList.add(other);
    200                    break;
    201                case MINUS:
    202                    minusList.add(other);
    203                    break;
    204                case BOTH:
    205                    final SubHyperplane.SplitSubHyperplane<S> split = other.split(inserted);
    206                    plusList.add(split.getPlus());
    207                    minusList.add(split.getMinus());
    208                    break;
    209                default:
    210                    // ignore the sub-hyperplanes belonging to the cut hyperplane
    211                }
    212            }
    213
    214            // recurse through lower levels
    215            insertCuts(node.getPlus(),  plusList);
    216            insertCuts(node.getMinus(), minusList);
    217
    218        }
    219
    220        /** {@inheritDoc} */
    221        public AbstractRegion<S, T> copySelf() {
    222            return buildNew(tree.copySelf());
    223        }
    224
    225        /** {@inheritDoc} */
    226        public boolean isEmpty() {
    227            return isEmpty(tree);
    228        }
    229
    230        /** {@inheritDoc} */
    231        public boolean isEmpty(final BSPTree<S> node) {
    232
    233            // we use a recursive function rather than the BSPTreeVisitor
    234            // interface because we can stop visiting the tree as soon as we
    235            // have found an inside cell
    236
    237            if (node.getCut() == null) {
    238                // if we find an inside node, the region is not empty
    239                return !((Boolean) node.getAttribute());
    240            }
    241
    242            // check both sides of the sub-tree
    243            return isEmpty(node.getMinus()) && isEmpty(node.getPlus());
    244
    245        }
    246
    247        /** {@inheritDoc} */
    248        public boolean contains(final Region<S> region) {
    249            return new RegionFactory<S>().difference(region, this).isEmpty();
    250        }
    251
    252        /** {@inheritDoc} */
    253        public Location checkPoint(final Vector<S> point) {
    254            return checkPoint(tree, point);
    255        }
    256
    257        /** Check a point with respect to the region starting at a given node.
    258         * @param node root node of the region
    259         * @param point point to check
    260         * @return a code representing the point status: either {@link
    261         * Region.Location#INSIDE INSIDE}, {@link Region.Location#OUTSIDE
    262         * OUTSIDE} or {@link Region.Location#BOUNDARY BOUNDARY}
    263         */
    264        protected Location checkPoint(final BSPTree<S> node, final Vector<S> point) {
    265            final BSPTree<S> cell = node.getCell(point);
    266            if (cell.getCut() == null) {
    267                // the point is in the interior of a cell, just check the attribute
    268                return ((Boolean) cell.getAttribute()) ? Location.INSIDE : Location.OUTSIDE;
    269            }
    270
    271            // the point is on a cut-sub-hyperplane, is it on a boundary ?
    272            final Location minusCode = checkPoint(cell.getMinus(), point);
    273            final Location plusCode  = checkPoint(cell.getPlus(),  point);
    274            return (minusCode == plusCode) ? minusCode : Location.BOUNDARY;
    275
    276        }
    277
    278        /** {@inheritDoc} */
    279        public BSPTree<S> getTree(final boolean includeBoundaryAttributes) {
    280            if (includeBoundaryAttributes && (tree.getCut() != null) && (tree.getAttribute() == null)) {
    281                // we need to compute the boundary attributes
    282                tree.visit(new BoundaryBuilder<S>());
    283            }
    284            return tree;
    285        }
    286
    287        /** Visitor building boundary shell tree.
    288         * <p>
    289         * The boundary shell is represented as {@link BoundaryAttribute boundary attributes}
    290         * at each internal node.
    291         * </p>
    292         */
    293        private static class BoundaryBuilder<S extends Space> implements BSPTreeVisitor<S> {
    294
    295            /** {@inheritDoc} */
    296            public Order visitOrder(BSPTree<S> node) {
    297                return Order.PLUS_MINUS_SUB;
    298            }
    299
    300            /** {@inheritDoc} */
    301            public void visitInternalNode(BSPTree<S> node) {
    302
    303                SubHyperplane<S> plusOutside = null;
    304                SubHyperplane<S> plusInside  = null;
    305
    306                // characterize the cut sub-hyperplane,
    307                // first with respect to the plus sub-tree
    308                @SuppressWarnings("unchecked")
    309                final SubHyperplane<S>[] plusChar = (SubHyperplane<S>[]) Array.newInstance(SubHyperplane.class, 2);
    310                characterize(node.getPlus(), node.getCut().copySelf(), plusChar);
    311
    312                if (plusChar[0] != null && !plusChar[0].isEmpty()) {
    313                    // plusChar[0] corresponds to a subset of the cut sub-hyperplane known to have
    314                    // outside cells on its plus side, we want to check if parts of this subset
    315                    // do have inside cells on their minus side
    316                    @SuppressWarnings("unchecked")
    317                    final SubHyperplane<S>[] minusChar = (SubHyperplane<S>[]) Array.newInstance(SubHyperplane.class, 2);
    318                    characterize(node.getMinus(), plusChar[0], minusChar);
    319                    if (minusChar[1] != null && !minusChar[1].isEmpty()) {
    320                        // this part belongs to the boundary,
    321                        // it has the outside on its plus side and the inside on its minus side
    322                        plusOutside = minusChar[1];
    323                    }
    324                }
    325
    326                if (plusChar[1] != null && !plusChar[1].isEmpty()) {
    327                    // plusChar[1] corresponds to a subset of the cut sub-hyperplane known to have
    328                    // inside cells on its plus side, we want to check if parts of this subset
    329                    // do have outside cells on their minus side
    330                    @SuppressWarnings("unchecked")
    331                    final SubHyperplane<S>[] minusChar = (SubHyperplane<S>[]) Array.newInstance(SubHyperplane.class, 2);
    332                    characterize(node.getMinus(), plusChar[1], minusChar);
    333                    if (minusChar[0] != null && !minusChar[0].isEmpty()) {
    334                        // this part belongs to the boundary,
    335                        // it has the inside on its plus side and the outside on its minus side
    336                        plusInside = minusChar[0];
    337                    }
    338                }
    339
    340                // set the boundary attribute at non-leaf nodes
    341                node.setAttribute(new BoundaryAttribute<S>(plusOutside, plusInside));
    342
    343            }
    344
    345            /** {@inheritDoc} */
    346            public void visitLeafNode(BSPTree<S> node) {
    347            }
    348
    349            /** Filter the parts of an hyperplane belonging to the boundary.
    350             * <p>The filtering consist in splitting the specified
    351             * sub-hyperplane into several parts lying in inside and outside
    352             * cells of the tree. The principle is to call this method twice for
    353             * each cut sub-hyperplane in the tree, once one the plus node and
    354             * once on the minus node. The parts that have the same flag
    355             * (inside/inside or outside/outside) do not belong to the boundary
    356             * while parts that have different flags (inside/outside or
    357             * outside/inside) do belong to the boundary.</p>
    358             * @param node current BSP tree node
    359             * @param sub sub-hyperplane to characterize
    360             * @param characterization placeholder where to put the characterized parts
    361             */
    362            private void characterize(final BSPTree<S> node, final SubHyperplane<S> sub,
    363                                      final SubHyperplane<S>[] characterization) {
    364                if (node.getCut() == null) {
    365                    // we have reached a leaf node
    366                    final boolean inside = (Boolean) node.getAttribute();
    367                    if (inside) {
    368                        if (characterization[1] == null) {
    369                            characterization[1] = sub;
    370                        } else {
    371                            characterization[1] = characterization[1].reunite(sub);
    372                        }
    373                    } else {
    374                        if (characterization[0] == null) {
    375                            characterization[0] = sub;
    376                        } else {
    377                            characterization[0] = characterization[0].reunite(sub);
    378                        }
    379                    }
    380                } else {
    381                    final Hyperplane<S> hyperplane = node.getCut().getHyperplane();
    382                    switch (sub.side(hyperplane)) {
    383                    case PLUS:
    384                        characterize(node.getPlus(), sub, characterization);
    385                        break;
    386                    case MINUS:
    387                        characterize(node.getMinus(), sub, characterization);
    388                        break;
    389                    case BOTH:
    390                        final SubHyperplane.SplitSubHyperplane<S> split = sub.split(hyperplane);
    391                        characterize(node.getPlus(),  split.getPlus(),  characterization);
    392                        characterize(node.getMinus(), split.getMinus(), characterization);
    393                        break;
    394                    default:
    395                        // this should not happen
    396                        throw new MathInternalError();
    397                    }
    398                }
    399            }
    400
    401        }
    402
    403        /** {@inheritDoc} */
    404        public double getBoundarySize() {
    405            final BoundarySizeVisitor<S> visitor = new BoundarySizeVisitor<S>();
    406            getTree(true).visit(visitor);
    407            return visitor.getSize();
    408        }
    409
    410        /** {@inheritDoc} */
    411        public double getSize() {
    412            if (barycenter == null) {
    413                computeGeometricalProperties();
    414            }
    415            return size;
    416        }
    417
    418        /** Set the size of the instance.
    419         * @param size size of the instance
    420         */
    421        protected void setSize(final double size) {
    422            this.size = size;
    423        }
    424
    425        /** {@inheritDoc} */
    426        public Vector<S> getBarycenter() {
    427            if (barycenter == null) {
    428                computeGeometricalProperties();
    429            }
    430            return barycenter;
    431        }
    432
    433        /** Set the barycenter of the instance.
    434         * @param barycenter barycenter of the instance
    435         */
    436        protected void setBarycenter(final Vector<S> barycenter) {
    437            this.barycenter = barycenter;
    438        }
    439
    440        /** Compute some geometrical properties.
    441         * <p>The properties to compute are the barycenter and the size.</p>
    442         */
    443        protected abstract void computeGeometricalProperties();
    444
    445        /** {@inheritDoc} */
    446        public Side side(final Hyperplane<S> hyperplane) {
    447            final Sides sides = new Sides();
    448            recurseSides(tree, hyperplane.wholeHyperplane(), sides);
    449            return sides.plusFound() ?
    450                  (sides.minusFound() ? Side.BOTH  : Side.PLUS) :
    451                  (sides.minusFound() ? Side.MINUS : Side.HYPER);
    452        }
    453
    454        /** Search recursively for inside leaf nodes on each side of the given hyperplane.
    455
    456         * <p>The algorithm used here is directly derived from the one
    457         * described in section III (<i>Binary Partitioning of a BSP
    458         * Tree</i>) of the Bruce Naylor, John Amanatides and William
    459         * Thibault paper <a
    460         * href="http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf">Merging
    461         * BSP Trees Yields Polyhedral Set Operations</a> Proc. Siggraph
    462         * '90, Computer Graphics 24(4), August 1990, pp 115-124, published
    463         * by the Association for Computing Machinery (ACM)..</p>
    464
    465         * @param node current BSP tree node
    466         * @param sub sub-hyperplane
    467         * @param sides object holding the sides found
    468         */
    469        private void recurseSides(final BSPTree<S> node, final SubHyperplane<S> sub, final Sides sides) {
    470
    471            if (node.getCut() == null) {
    472                if ((Boolean) node.getAttribute()) {
    473                    // this is an inside cell expanding across the hyperplane
    474                    sides.rememberPlusFound();
    475                    sides.rememberMinusFound();
    476                }
    477                return;
    478            }
    479
    480            final Hyperplane<S> hyperplane = node.getCut().getHyperplane();
    481            switch (sub.side(hyperplane)) {
    482            case PLUS :
    483                // the sub-hyperplane is entirely in the plus sub-tree
    484                if (node.getCut().side(sub.getHyperplane()) == Side.PLUS) {
    485                    if (!isEmpty(node.getMinus())) {
    486                        sides.rememberPlusFound();
    487                    }
    488                } else {
    489                    if (!isEmpty(node.getMinus())) {
    490                        sides.rememberMinusFound();
    491                    }
    492                }
    493                if (!(sides.plusFound() && sides.minusFound())) {
    494                    recurseSides(node.getPlus(), sub, sides);
    495                }
    496                break;
    497            case MINUS :
    498                // the sub-hyperplane is entirely in the minus sub-tree
    499                if (node.getCut().side(sub.getHyperplane()) == Side.PLUS) {
    500                    if (!isEmpty(node.getPlus())) {
    501                        sides.rememberPlusFound();
    502                    }
    503                } else {
    504                    if (!isEmpty(node.getPlus())) {
    505                        sides.rememberMinusFound();
    506                    }
    507                }
    508                if (!(sides.plusFound() && sides.minusFound())) {
    509                    recurseSides(node.getMinus(), sub, sides);
    510                }
    511                break;
    512            case BOTH :
    513                // the sub-hyperplane extends in both sub-trees
    514                final SubHyperplane.SplitSubHyperplane<S> split = sub.split(hyperplane);
    515
    516                // explore first the plus sub-tree
    517                recurseSides(node.getPlus(), split.getPlus(), sides);
    518
    519                // if needed, explore the minus sub-tree
    520                if (!(sides.plusFound() && sides.minusFound())) {
    521                    recurseSides(node.getMinus(), split.getMinus(), sides);
    522                }
    523                break;
    524            default :
    525                // the sub-hyperplane and the cut sub-hyperplane share the same hyperplane
    526                if (node.getCut().getHyperplane().sameOrientationAs(sub.getHyperplane())) {
    527                    if ((node.getPlus().getCut() != null) || ((Boolean) node.getPlus().getAttribute())) {
    528                        sides.rememberPlusFound();
    529                    }
    530                    if ((node.getMinus().getCut() != null) || ((Boolean) node.getMinus().getAttribute())) {
    531                        sides.rememberMinusFound();
    532                    }
    533                } else {
    534                    if ((node.getPlus().getCut() != null) || ((Boolean) node.getPlus().getAttribute())) {
    535                        sides.rememberMinusFound();
    536                    }
    537                    if ((node.getMinus().getCut() != null) || ((Boolean) node.getMinus().getAttribute())) {
    538                        sides.rememberPlusFound();
    539                    }
    540                }
    541            }
    542
    543        }
    544
    545        /** Utility class holding the already found sides. */
    546        private static final class Sides {
    547
    548            /** Indicator of inside leaf nodes found on the plus side. */
    549            private boolean plusFound;
    550
    551            /** Indicator of inside leaf nodes found on the plus side. */
    552            private boolean minusFound;
    553
    554            /** Simple constructor.
    555             */
    556            public Sides() {
    557                plusFound  = false;
    558                minusFound = false;
    559            }
    560
    561            /** Remember the fact that inside leaf nodes have been found on the plus side.
    562             */
    563            public void rememberPlusFound() {
    564                plusFound = true;
    565            }
    566
    567            /** Check if inside leaf nodes have been found on the plus side.
    568             * @return true if inside leaf nodes have been found on the plus side
    569             */
    570            public boolean plusFound() {
    571                return plusFound;
    572            }
    573
    574            /** Remember the fact that inside leaf nodes have been found on the minus side.
    575             */
    576            public void rememberMinusFound() {
    577                minusFound = true;
    578            }
    579
    580            /** Check if inside leaf nodes have been found on the minus side.
    581             * @return true if inside leaf nodes have been found on the minus side
    582             */
    583            public boolean minusFound() {
    584                return minusFound;
    585            }
    586
    587        }
    588
    589        /** {@inheritDoc} */
    590        public SubHyperplane<S> intersection(final SubHyperplane<S> sub) {
    591            return recurseIntersection(tree, sub);
    592        }
    593
    594        /** Recursively compute the parts of a sub-hyperplane that are
    595         * contained in the region.
    596         * @param node current BSP tree node
    597         * @param sub sub-hyperplane traversing the region
    598         * @return filtered sub-hyperplane
    599         */
    600        private SubHyperplane<S> recurseIntersection(final BSPTree<S> node, final SubHyperplane<S> sub) {
    601
    602            if (node.getCut() == null) {
    603                return (Boolean) node.getAttribute() ? sub.copySelf() : null;
    604            }
    605
    606            final Hyperplane<S> hyperplane = node.getCut().getHyperplane();
    607            switch (sub.side(hyperplane)) {
    608            case PLUS :
    609                return recurseIntersection(node.getPlus(), sub);
    610            case MINUS :
    611                return recurseIntersection(node.getMinus(), sub);
    612            case BOTH :
    613                final SubHyperplane.SplitSubHyperplane<S> split = sub.split(hyperplane);
    614                final SubHyperplane<S> plus  = recurseIntersection(node.getPlus(),  split.getPlus());
    615                final SubHyperplane<S> minus = recurseIntersection(node.getMinus(), split.getMinus());
    616                if (plus == null) {
    617                    return minus;
    618                } else if (minus == null) {
    619                    return plus;
    620                } else {
    621                    return plus.reunite(minus);
    622                }
    623            default :
    624                return recurseIntersection(node.getPlus(),
    625                                           recurseIntersection(node.getMinus(), sub));
    626            }
    627
    628        }
    629
    630        /** Transform a region.
    631         * <p>Applying a transform to a region consist in applying the
    632         * transform to all the hyperplanes of the underlying BSP tree and
    633         * of the boundary (and also to the sub-hyperplanes embedded in
    634         * these hyperplanes) and to the barycenter. The instance is not
    635         * modified, a new instance is built.</p>
    636         * @param transform transform to apply
    637         * @return a new region, resulting from the application of the
    638         * transform to the instance
    639         */
    640        public AbstractRegion<S, T> applyTransform(final Transform<S, T> transform) {
    641            return buildNew(recurseTransform(getTree(false), transform));
    642        }
    643
    644        /** Recursively transform an inside/outside BSP-tree.
    645         * @param node current BSP tree node
    646         * @param transform transform to apply
    647         * @return a new tree
    648         */
    649        @SuppressWarnings("unchecked")
    650        private BSPTree<S> recurseTransform(final BSPTree<S> node, final Transform<S, T> transform) {
    651
    652            if (node.getCut() == null) {
    653                return new BSPTree<S>(node.getAttribute());
    654            }
    655
    656            final SubHyperplane<S>  sub = node.getCut();
    657            final SubHyperplane<S> tSub = ((AbstractSubHyperplane<S, T>) sub).applyTransform(transform);
    658            BoundaryAttribute<S> attribute = (BoundaryAttribute<S>) node.getAttribute();
    659            if (attribute != null) {
    660                final SubHyperplane<S> tPO = (attribute.getPlusOutside() == null) ?
    661                    null : ((AbstractSubHyperplane<S, T>) attribute.getPlusOutside()).applyTransform(transform);
    662                final SubHyperplane<S> tPI = (attribute.getPlusInside()  == null) ?
    663                    null  : ((AbstractSubHyperplane<S, T>) attribute.getPlusInside()).applyTransform(transform);
    664                attribute = new BoundaryAttribute<S>(tPO, tPI);
    665            }
    666
    667            return new BSPTree<S>(tSub,
    668                                        recurseTransform(node.getPlus(),  transform),
    669                                        recurseTransform(node.getMinus(), transform),
    670                                        attribute);
    671
    672        }
    673
    674    }