001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.math3.geometry.partitioning;
018
019import org.apache.commons.math3.exception.MathInternalError;
020import org.apache.commons.math3.geometry.Vector;
021import org.apache.commons.math3.geometry.Space;
022import 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 */
063public 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}