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 <op>
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 <op>
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 }