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    }