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    }