1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 package org.apache.commons.math3.geometry.partitioning; 18 19 import java.util.ArrayList; 20 import java.util.List; 21 22 import org.apache.commons.math3.exception.MathIllegalStateException; 23 import org.apache.commons.math3.exception.MathInternalError; 24 import org.apache.commons.math3.exception.util.LocalizedFormats; 25 import org.apache.commons.math3.geometry.Point; 26 import org.apache.commons.math3.geometry.Space; 27 import org.apache.commons.math3.geometry.Vector; 28 import org.apache.commons.math3.util.FastMath; 29 30 /** This class represent a Binary Space Partition tree. 31 32 * <p>BSP trees are an efficient way to represent space partitions and 33 * to associate attributes with each cell. Each node in a BSP tree 34 * represents a convex region which is partitioned in two convex 35 * sub-regions at each side of a cut hyperplane. The root tree 36 * contains the complete space.</p> 37 38 * <p>The main use of such partitions is to use a boolean attribute to 39 * define an inside/outside property, hence representing arbitrary 40 * polytopes (line segments in 1D, polygons in 2D and polyhedrons in 41 * 3D) and to operate on them.</p> 42 43 * <p>Another example would be to represent Voronoi tesselations, the 44 * attribute of each cell holding the defining point of the cell.</p> 45 46 * <p>The application-defined attributes are shared among copied 47 * instances and propagated to split parts. These attributes are not 48 * used by the BSP-tree algorithms themselves, so the application can 49 * use them for any purpose. Since the tree visiting method holds 50 * internal and leaf nodes differently, it is possible to use 51 * different classes for internal nodes attributes and leaf nodes 52 * attributes. This should be used with care, though, because if the 53 * tree is modified in any way after attributes have been set, some 54 * internal nodes may become leaf nodes and some leaf nodes may become 55 * internal nodes.</p> 56 57 * <p>One of the main sources for the development of this package was 58 * Bruce Naylor, John Amanatides and William Thibault paper <a 59 * href="http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf">Merging 60 * BSP Trees Yields Polyhedral Set Operations</a> Proc. Siggraph '90, 61 * Computer Graphics 24(4), August 1990, pp 115-124, published by the 62 * Association for Computing Machinery (ACM).</p> 63 64 * @param <S> Type of the space. 65 66 * @since 3.0 67 */ 68 public class BSPTree<S extends Space> { 69 70 /** Cut sub-hyperplane. */ 71 private SubHyperplane<S> cut; 72 73 /** Tree at the plus side of the cut hyperplane. */ 74 private BSPTree<S> plus; 75 76 /** Tree at the minus side of the cut hyperplane. */ 77 private BSPTree<S> minus; 78 79 /** Parent tree. */ 80 private BSPTree<S> parent; 81 82 /** Application-defined attribute. */ 83 private Object attribute; 84 85 /** Build a tree having only one root cell representing the whole space. 86 */ BSPTree()87 public BSPTree() { 88 cut = null; 89 plus = null; 90 minus = null; 91 parent = null; 92 attribute = null; 93 } 94 95 /** Build a tree having only one root cell representing the whole space. 96 * @param attribute attribute of the tree (may be null) 97 */ BSPTree(final Object attribute)98 public BSPTree(final Object attribute) { 99 cut = null; 100 plus = null; 101 minus = null; 102 parent = null; 103 this.attribute = attribute; 104 } 105 106 /** Build a BSPTree from its underlying elements. 107 * <p>This method does <em>not</em> perform any verification on 108 * consistency of its arguments, it should therefore be used only 109 * when then caller knows what it is doing.</p> 110 * <p>This method is mainly useful to build trees 111 * bottom-up. Building trees top-down is realized with the help of 112 * method {@link #insertCut insertCut}.</p> 113 * @param cut cut sub-hyperplane for the tree 114 * @param plus plus side sub-tree 115 * @param minus minus side sub-tree 116 * @param attribute attribute associated with the node (may be null) 117 * @see #insertCut 118 */ BSPTree(final SubHyperplane<S> cut, final BSPTree<S> plus, final BSPTree<S> minus, final Object attribute)119 public BSPTree(final SubHyperplane<S> cut, final BSPTree<S> plus, final BSPTree<S> minus, 120 final Object attribute) { 121 this.cut = cut; 122 this.plus = plus; 123 this.minus = minus; 124 this.parent = null; 125 this.attribute = attribute; 126 plus.parent = this; 127 minus.parent = this; 128 } 129 130 /** Insert a cut sub-hyperplane in a node. 131 * <p>The sub-tree starting at this node will be completely 132 * overwritten. The new cut sub-hyperplane will be built from the 133 * intersection of the provided hyperplane with the cell. If the 134 * hyperplane does intersect the cell, the cell will have two 135 * children cells with {@code null} attributes on each side of 136 * the inserted cut sub-hyperplane. If the hyperplane does not 137 * intersect the cell then <em>no</em> cut hyperplane will be 138 * inserted and the cell will be changed to a leaf cell. The 139 * attribute of the node is never changed.</p> 140 * <p>This method is mainly useful when called on leaf nodes 141 * (i.e. nodes for which {@link #getCut getCut} returns 142 * {@code null}), in this case it provides a way to build a 143 * tree top-down (whereas the {@link #BSPTree(SubHyperplane, 144 * BSPTree, BSPTree, Object) 4 arguments constructor} is devoted to 145 * build trees bottom-up).</p> 146 * @param hyperplane hyperplane to insert, it will be chopped in 147 * order to fit in the cell defined by the parent nodes of the 148 * instance 149 * @return true if a cut sub-hyperplane has been inserted (i.e. if 150 * the cell now has two leaf child nodes) 151 * @see #BSPTree(SubHyperplane, BSPTree, BSPTree, Object) 152 */ insertCut(final Hyperplane<S> hyperplane)153 public boolean insertCut(final Hyperplane<S> hyperplane) { 154 155 if (cut != null) { 156 plus.parent = null; 157 minus.parent = null; 158 } 159 160 final SubHyperplane<S> chopped = fitToCell(hyperplane.wholeHyperplane()); 161 if (chopped == null || chopped.isEmpty()) { 162 cut = null; 163 plus = null; 164 minus = null; 165 return false; 166 } 167 168 cut = chopped; 169 plus = new BSPTree<S>(); 170 plus.parent = this; 171 minus = new BSPTree<S>(); 172 minus.parent = this; 173 return true; 174 175 } 176 177 /** Copy the instance. 178 * <p>The instance created is completely independent of the original 179 * one. A deep copy is used, none of the underlying objects are 180 * shared (except for the nodes attributes and immutable 181 * objects).</p> 182 * @return a new tree, copy of the instance 183 */ copySelf()184 public BSPTree<S> copySelf() { 185 186 if (cut == null) { 187 return new BSPTree<S>(attribute); 188 } 189 190 return new BSPTree<S>(cut.copySelf(), plus.copySelf(), minus.copySelf(), 191 attribute); 192 193 } 194 195 /** Get the cut sub-hyperplane. 196 * @return cut sub-hyperplane, null if this is a leaf tree 197 */ getCut()198 public SubHyperplane<S> getCut() { 199 return cut; 200 } 201 202 /** Get the tree on the plus side of the cut hyperplane. 203 * @return tree on the plus side of the cut hyperplane, null if this 204 * is a leaf tree 205 */ getPlus()206 public BSPTree<S> getPlus() { 207 return plus; 208 } 209 210 /** Get the tree on the minus side of the cut hyperplane. 211 * @return tree on the minus side of the cut hyperplane, null if this 212 * is a leaf tree 213 */ getMinus()214 public BSPTree<S> getMinus() { 215 return minus; 216 } 217 218 /** Get the parent node. 219 * @return parent node, null if the node has no parents 220 */ getParent()221 public BSPTree<S> getParent() { 222 return parent; 223 } 224 225 /** Associate an attribute with the instance. 226 * @param attribute attribute to associate with the node 227 * @see #getAttribute 228 */ setAttribute(final Object attribute)229 public void setAttribute(final Object attribute) { 230 this.attribute = attribute; 231 } 232 233 /** Get the attribute associated with the instance. 234 * @return attribute associated with the node or null if no 235 * attribute has been explicitly set using the {@link #setAttribute 236 * setAttribute} method 237 * @see #setAttribute 238 */ getAttribute()239 public Object getAttribute() { 240 return attribute; 241 } 242 243 /** Visit the BSP tree nodes. 244 * @param visitor object visiting the tree nodes 245 */ visit(final BSPTreeVisitor<S> visitor)246 public void visit(final BSPTreeVisitor<S> visitor) { 247 if (cut == null) { 248 visitor.visitLeafNode(this); 249 } else { 250 switch (visitor.visitOrder(this)) { 251 case PLUS_MINUS_SUB: 252 plus.visit(visitor); 253 minus.visit(visitor); 254 visitor.visitInternalNode(this); 255 break; 256 case PLUS_SUB_MINUS: 257 plus.visit(visitor); 258 visitor.visitInternalNode(this); 259 minus.visit(visitor); 260 break; 261 case MINUS_PLUS_SUB: 262 minus.visit(visitor); 263 plus.visit(visitor); 264 visitor.visitInternalNode(this); 265 break; 266 case MINUS_SUB_PLUS: 267 minus.visit(visitor); 268 visitor.visitInternalNode(this); 269 plus.visit(visitor); 270 break; 271 case SUB_PLUS_MINUS: 272 visitor.visitInternalNode(this); 273 plus.visit(visitor); 274 minus.visit(visitor); 275 break; 276 case SUB_MINUS_PLUS: 277 visitor.visitInternalNode(this); 278 minus.visit(visitor); 279 plus.visit(visitor); 280 break; 281 default: 282 throw new MathInternalError(); 283 } 284 285 } 286 } 287 288 /** Fit a sub-hyperplane inside the cell defined by the instance. 289 * <p>Fitting is done by chopping off the parts of the 290 * sub-hyperplane that lie outside of the cell using the 291 * cut-hyperplanes of the parent nodes of the instance.</p> 292 * @param sub sub-hyperplane to fit 293 * @return a new sub-hyperplane, guaranteed to have no part outside 294 * of the instance cell 295 */ fitToCell(final SubHyperplane<S> sub)296 private SubHyperplane<S> fitToCell(final SubHyperplane<S> sub) { 297 SubHyperplane<S> s = sub; 298 for (BSPTree<S> tree = this; tree.parent != null && s != null; tree = tree.parent) { 299 if (tree == tree.parent.plus) { 300 s = s.split(tree.parent.cut.getHyperplane()).getPlus(); 301 } else { 302 s = s.split(tree.parent.cut.getHyperplane()).getMinus(); 303 } 304 } 305 return s; 306 } 307 308 /** Get the cell to which a point belongs. 309 * <p>If the returned cell is a leaf node the points belongs to the 310 * interior of the node, if the cell is an internal node the points 311 * belongs to the node cut sub-hyperplane.</p> 312 * @param point point to check 313 * @return the tree cell to which the point belongs 314 * @deprecated as of 3.3, replaced with {@link #getCell(Point, double)} 315 */ 316 @Deprecated getCell(final Vector<S> point)317 public BSPTree<S> getCell(final Vector<S> point) { 318 return getCell((Point<S>) point, 1.0e-10); 319 } 320 321 /** Get the cell to which a point belongs. 322 * <p>If the returned cell is a leaf node the points belongs to the 323 * interior of the node, if the cell is an internal node the points 324 * belongs to the node cut sub-hyperplane.</p> 325 * @param point point to check 326 * @param tolerance tolerance below which points close to a cut hyperplane 327 * are considered to belong to the hyperplane itself 328 * @return the tree cell to which the point belongs 329 */ getCell(final Point<S> point, final double tolerance)330 public BSPTree<S> getCell(final Point<S> point, final double tolerance) { 331 332 if (cut == null) { 333 return this; 334 } 335 336 // position of the point with respect to the cut hyperplane 337 final double offset = cut.getHyperplane().getOffset(point); 338 339 if (FastMath.abs(offset) < tolerance) { 340 return this; 341 } else if (offset <= 0) { 342 // point is on the minus side of the cut hyperplane 343 return minus.getCell(point, tolerance); 344 } else { 345 // point is on the plus side of the cut hyperplane 346 return plus.getCell(point, tolerance); 347 } 348 349 } 350 351 /** Get the cells whose cut sub-hyperplanes are close to the point. 352 * @param point point to check 353 * @param maxOffset offset below which a cut sub-hyperplane is considered 354 * close to the point (in absolute value) 355 * @return close cells (may be empty if all cut sub-hyperplanes are farther 356 * than maxOffset from the point) 357 */ getCloseCuts(final Point<S> point, final double maxOffset)358 public List<BSPTree<S>> getCloseCuts(final Point<S> point, final double maxOffset) { 359 final List<BSPTree<S>> close = new ArrayList<BSPTree<S>>(); 360 recurseCloseCuts(point, maxOffset, close); 361 return close; 362 } 363 364 /** Get the cells whose cut sub-hyperplanes are close to the point. 365 * @param point point to check 366 * @param maxOffset offset below which a cut sub-hyperplane is considered 367 * close to the point (in absolute value) 368 * @param close list to fill 369 */ recurseCloseCuts(final Point<S> point, final double maxOffset, final List<BSPTree<S>> close)370 private void recurseCloseCuts(final Point<S> point, final double maxOffset, 371 final List<BSPTree<S>> close) { 372 if (cut != null) { 373 374 // position of the point with respect to the cut hyperplane 375 final double offset = cut.getHyperplane().getOffset(point); 376 377 if (offset < -maxOffset) { 378 // point is on the minus side of the cut hyperplane 379 minus.recurseCloseCuts(point, maxOffset, close); 380 } else if (offset > maxOffset) { 381 // point is on the plus side of the cut hyperplane 382 plus.recurseCloseCuts(point, maxOffset, close); 383 } else { 384 // point is close to the cut hyperplane 385 close.add(this); 386 minus.recurseCloseCuts(point, maxOffset, close); 387 plus.recurseCloseCuts(point, maxOffset, close); 388 } 389 390 } 391 } 392 393 /** Perform condensation on a tree. 394 * <p>The condensation operation is not recursive, it must be called 395 * explicitly from leaves to root.</p> 396 */ condense()397 private void condense() { 398 if ((cut != null) && (plus.cut == null) && (minus.cut == null) && 399 (((plus.attribute == null) && (minus.attribute == null)) || 400 ((plus.attribute != null) && plus.attribute.equals(minus.attribute)))) { 401 attribute = (plus.attribute == null) ? minus.attribute : plus.attribute; 402 cut = null; 403 plus = null; 404 minus = null; 405 } 406 } 407 408 /** Merge a BSP tree with the instance. 409 * <p>All trees are modified (parts of them are reused in the new 410 * tree), it is the responsibility of the caller to ensure a copy 411 * has been done before if any of the former tree should be 412 * preserved, <em>no</em> such copy is done here!</p> 413 * <p>The algorithm used here is directly derived from the one 414 * described in the Naylor, Amanatides and Thibault paper (section 415 * III, Binary Partitioning of a BSP Tree).</p> 416 * @param tree other tree to merge with the instance (will be 417 * <em>unusable</em> after the operation, as well as the 418 * instance itself) 419 * @param leafMerger object implementing the final merging phase 420 * (this is where the semantic of the operation occurs, generally 421 * depending on the attribute of the leaf node) 422 * @return a new tree, result of <code>instance <op> 423 * tree</code>, this value can be ignored if parentTree is not null 424 * since all connections have already been established 425 */ merge(final BSPTree<S> tree, final LeafMerger<S> leafMerger)426 public BSPTree<S> merge(final BSPTree<S> tree, final LeafMerger<S> leafMerger) { 427 return merge(tree, leafMerger, null, false); 428 } 429 430 /** Merge a BSP tree with the instance. 431 * @param tree other tree to merge with the instance (will be 432 * <em>unusable</em> after the operation, as well as the 433 * instance itself) 434 * @param leafMerger object implementing the final merging phase 435 * (this is where the semantic of the operation occurs, generally 436 * depending on the attribute of the leaf node) 437 * @param parentTree parent tree to connect to (may be null) 438 * @param isPlusChild if true and if parentTree is not null, the 439 * resulting tree should be the plus child of its parent, ignored if 440 * parentTree is null 441 * @return a new tree, result of <code>instance <op> 442 * tree</code>, this value can be ignored if parentTree is not null 443 * since all connections have already been established 444 */ merge(final BSPTree<S> tree, final LeafMerger<S> leafMerger, final BSPTree<S> parentTree, final boolean isPlusChild)445 private BSPTree<S> merge(final BSPTree<S> tree, final LeafMerger<S> leafMerger, 446 final BSPTree<S> parentTree, final boolean isPlusChild) { 447 if (cut == null) { 448 // cell/tree operation 449 return leafMerger.merge(this, tree, parentTree, isPlusChild, true); 450 } else if (tree.cut == null) { 451 // tree/cell operation 452 return leafMerger.merge(tree, this, parentTree, isPlusChild, false); 453 } else { 454 // tree/tree operation 455 final BSPTree<S> merged = tree.split(cut); 456 if (parentTree != null) { 457 merged.parent = parentTree; 458 if (isPlusChild) { 459 parentTree.plus = merged; 460 } else { 461 parentTree.minus = merged; 462 } 463 } 464 465 // merging phase 466 plus.merge(merged.plus, leafMerger, merged, true); 467 minus.merge(merged.minus, leafMerger, merged, false); 468 merged.condense(); 469 if (merged.cut != null) { 470 merged.cut = merged.fitToCell(merged.cut.getHyperplane().wholeHyperplane()); 471 } 472 473 return merged; 474 475 } 476 } 477 478 /** This interface gather the merging operations between a BSP tree 479 * leaf and another BSP tree. 480 * <p>As explained in Bruce Naylor, John Amanatides and William 481 * Thibault paper <a 482 * href="http://www.cs.yorku.ca/~amana/research/bsptSetOp.pdf">Merging 483 * BSP Trees Yields Polyhedral Set Operations</a>, 484 * the operations on {@link BSPTree BSP trees} can be expressed as a 485 * generic recursive merging operation where only the final part, 486 * when one of the operand is a leaf, is specific to the real 487 * operation semantics. For example, a tree representing a region 488 * using a boolean attribute to identify inside cells and outside 489 * cells would use four different objects to implement the final 490 * merging phase of the four set operations union, intersection, 491 * difference and symmetric difference (exclusive or).</p> 492 * @param <S> Type of the space. 493 */ 494 public interface LeafMerger<S extends Space> { 495 496 /** Merge a leaf node and a tree node. 497 * <p>This method is called at the end of a recursive merging 498 * resulting from a {@code tree1.merge(tree2, leafMerger)} 499 * call, when one of the sub-trees involved is a leaf (i.e. when 500 * its cut-hyperplane is null). This is the only place where the 501 * precise semantics of the operation are required. For all upper 502 * level nodes in the tree, the merging operation is only a 503 * generic partitioning algorithm.</p> 504 * <p>Since the final operation may be non-commutative, it is 505 * important to know if the leaf node comes from the instance tree 506 * ({@code tree1}) or the argument tree 507 * ({@code tree2}). The third argument of the method is 508 * devoted to this. It can be ignored for commutative 509 * operations.</p> 510 * <p>The {@link BSPTree#insertInTree BSPTree.insertInTree} method 511 * may be useful to implement this method.</p> 512 * @param leaf leaf node (its cut hyperplane is guaranteed to be 513 * null) 514 * @param tree tree node (its cut hyperplane may be null or not) 515 * @param parentTree parent tree to connect to (may be null) 516 * @param isPlusChild if true and if parentTree is not null, the 517 * resulting tree should be the plus child of its parent, ignored if 518 * parentTree is null 519 * @param leafFromInstance if true, the leaf node comes from the 520 * instance tree ({@code tree1}) and the tree node comes from 521 * the argument tree ({@code tree2}) 522 * @return the BSP tree resulting from the merging (may be one of 523 * the arguments) 524 */ merge(BSPTree<S> leaf, BSPTree<S> tree, BSPTree<S> parentTree, boolean isPlusChild, boolean leafFromInstance)525 BSPTree<S> merge(BSPTree<S> leaf, BSPTree<S> tree, BSPTree<S> parentTree, 526 boolean isPlusChild, boolean leafFromInstance); 527 528 } 529 530 /** This interface handles the corner cases when an internal node cut sub-hyperplane vanishes. 531 * <p> 532 * Such cases happens for example when a cut sub-hyperplane is inserted into 533 * another tree (during a merge operation), and is split in several parts, 534 * some of which becomes smaller than the tolerance. The corresponding node 535 * as then no cut sub-hyperplane anymore, but does have children. This interface 536 * specifies how to handle this situation. 537 * setting 538 * </p> 539 * @param <S> Type of the space. 540 * @since 3.4 541 */ 542 public interface VanishingCutHandler<S extends Space> { 543 544 /** Fix a node with both vanished cut and children. 545 * @param node node to fix 546 * @return fixed node 547 */ fixNode(BSPTree<S> node)548 BSPTree<S> fixNode(BSPTree<S> node); 549 550 } 551 552 /** Split a BSP tree by an external sub-hyperplane. 553 * <p>Split a tree in two halves, on each side of the 554 * sub-hyperplane. The instance is not modified.</p> 555 * <p>The tree returned is not upward-consistent: despite all of its 556 * sub-trees cut sub-hyperplanes (including its own cut 557 * sub-hyperplane) are bounded to the current cell, it is <em>not</em> 558 * attached to any parent tree yet. This tree is intended to be 559 * later inserted into an higher level tree.</p> 560 * <p>The algorithm used here is the one given in Naylor, Amanatides 561 * and Thibault paper (section III, Binary Partitioning of a BSP 562 * Tree).</p> 563 * @param sub partitioning sub-hyperplane, must be already clipped 564 * to the convex region represented by the instance, will be used as 565 * the cut sub-hyperplane of the returned tree 566 * @return a tree having the specified sub-hyperplane as its cut 567 * sub-hyperplane, the two parts of the split instance as its two 568 * sub-trees and a null parent 569 */ split(final SubHyperplane<S> sub)570 public BSPTree<S> split(final SubHyperplane<S> sub) { 571 572 if (cut == null) { 573 return new BSPTree<S>(sub, copySelf(), new BSPTree<S>(attribute), null); 574 } 575 576 final Hyperplane<S> cHyperplane = cut.getHyperplane(); 577 final Hyperplane<S> sHyperplane = sub.getHyperplane(); 578 final SubHyperplane.SplitSubHyperplane<S> subParts = sub.split(cHyperplane); 579 switch (subParts.getSide()) { 580 case PLUS : 581 { // the partitioning sub-hyperplane is entirely in the plus sub-tree 582 final BSPTree<S> split = plus.split(sub); 583 if (cut.split(sHyperplane).getSide() == Side.PLUS) { 584 split.plus = 585 new BSPTree<S>(cut.copySelf(), split.plus, minus.copySelf(), attribute); 586 split.plus.condense(); 587 split.plus.parent = split; 588 } else { 589 split.minus = 590 new BSPTree<S>(cut.copySelf(), split.minus, minus.copySelf(), attribute); 591 split.minus.condense(); 592 split.minus.parent = split; 593 } 594 return split; 595 } 596 case MINUS : 597 { // the partitioning sub-hyperplane is entirely in the minus sub-tree 598 final BSPTree<S> split = minus.split(sub); 599 if (cut.split(sHyperplane).getSide() == Side.PLUS) { 600 split.plus = 601 new BSPTree<S>(cut.copySelf(), plus.copySelf(), split.plus, attribute); 602 split.plus.condense(); 603 split.plus.parent = split; 604 } else { 605 split.minus = 606 new BSPTree<S>(cut.copySelf(), plus.copySelf(), split.minus, attribute); 607 split.minus.condense(); 608 split.minus.parent = split; 609 } 610 return split; 611 } 612 case BOTH : 613 { 614 final SubHyperplane.SplitSubHyperplane<S> cutParts = cut.split(sHyperplane); 615 final BSPTree<S> split = 616 new BSPTree<S>(sub, plus.split(subParts.getPlus()), minus.split(subParts.getMinus()), 617 null); 618 split.plus.cut = cutParts.getPlus(); 619 split.minus.cut = cutParts.getMinus(); 620 final BSPTree<S> tmp = split.plus.minus; 621 split.plus.minus = split.minus.plus; 622 split.plus.minus.parent = split.plus; 623 split.minus.plus = tmp; 624 split.minus.plus.parent = split.minus; 625 split.plus.condense(); 626 split.minus.condense(); 627 return split; 628 } 629 default : 630 return cHyperplane.sameOrientationAs(sHyperplane) ? 631 new BSPTree<S>(sub, plus.copySelf(), minus.copySelf(), attribute) : 632 new BSPTree<S>(sub, minus.copySelf(), plus.copySelf(), attribute); 633 } 634 635 } 636 637 /** Insert the instance into another tree. 638 * <p>The instance itself is modified so its former parent should 639 * not be used anymore.</p> 640 * @param parentTree parent tree to connect to (may be null) 641 * @param isPlusChild if true and if parentTree is not null, the 642 * resulting tree should be the plus child of its parent, ignored if 643 * parentTree is null 644 * @see LeafMerger 645 * @deprecated as of 3.4, replaced with {@link #insertInTree(BSPTree, boolean, VanishingCutHandler)} 646 */ 647 @Deprecated insertInTree(final BSPTree<S> parentTree, final boolean isPlusChild)648 public void insertInTree(final BSPTree<S> parentTree, final boolean isPlusChild) { 649 insertInTree(parentTree, isPlusChild, new VanishingCutHandler<S>() { 650 /** {@inheritDoc} */ 651 public BSPTree<S> fixNode(BSPTree<S> node) { 652 // the cut should not be null 653 throw new MathIllegalStateException(LocalizedFormats.NULL_NOT_ALLOWED); 654 } 655 }); 656 } 657 658 /** Insert the instance into another tree. 659 * <p>The instance itself is modified so its former parent should 660 * not be used anymore.</p> 661 * @param parentTree parent tree to connect to (may be null) 662 * @param isPlusChild if true and if parentTree is not null, the 663 * resulting tree should be the plus child of its parent, ignored if 664 * parentTree is null 665 * @param vanishingHandler handler to use for handling very rare corner 666 * cases of vanishing cut sub-hyperplanes in internal nodes during merging 667 * @see LeafMerger 668 * @since 3.4 669 */ insertInTree(final BSPTree<S> parentTree, final boolean isPlusChild, final VanishingCutHandler<S> vanishingHandler)670 public void insertInTree(final BSPTree<S> parentTree, final boolean isPlusChild, 671 final VanishingCutHandler<S> vanishingHandler) { 672 673 // set up parent/child links 674 parent = parentTree; 675 if (parentTree != null) { 676 if (isPlusChild) { 677 parentTree.plus = this; 678 } else { 679 parentTree.minus = this; 680 } 681 } 682 683 // make sure the inserted tree lies in the cell defined by its parent nodes 684 if (cut != null) { 685 686 // explore the parent nodes from here towards tree root 687 for (BSPTree<S> tree = this; tree.parent != null; tree = tree.parent) { 688 689 // this is an hyperplane of some parent node 690 final Hyperplane<S> hyperplane = tree.parent.cut.getHyperplane(); 691 692 // chop off the parts of the inserted tree that extend 693 // on the wrong side of this parent hyperplane 694 if (tree == tree.parent.plus) { 695 cut = cut.split(hyperplane).getPlus(); 696 plus.chopOffMinus(hyperplane, vanishingHandler); 697 minus.chopOffMinus(hyperplane, vanishingHandler); 698 } else { 699 cut = cut.split(hyperplane).getMinus(); 700 plus.chopOffPlus(hyperplane, vanishingHandler); 701 minus.chopOffPlus(hyperplane, vanishingHandler); 702 } 703 704 if (cut == null) { 705 // the cut sub-hyperplane has vanished 706 final BSPTree<S> fixed = vanishingHandler.fixNode(this); 707 cut = fixed.cut; 708 plus = fixed.plus; 709 minus = fixed.minus; 710 attribute = fixed.attribute; 711 if (cut == null) { 712 break; 713 } 714 } 715 716 } 717 718 // since we may have drop some parts of the inserted tree, 719 // perform a condensation pass to keep the tree structure simple 720 condense(); 721 722 } 723 724 } 725 726 /** Prune a tree around a cell. 727 * <p> 728 * This method can be used to extract a convex cell from a tree. 729 * The original cell may either be a leaf node or an internal node. 730 * If it is an internal node, it's subtree will be ignored (i.e. the 731 * extracted cell will be a leaf node in all cases). The original 732 * tree to which the original cell belongs is not touched at all, 733 * a new independent tree will be built. 734 * </p> 735 * @param cellAttribute attribute to set for the leaf node 736 * corresponding to the initial instance cell 737 * @param otherLeafsAttributes attribute to set for the other leaf 738 * nodes 739 * @param internalAttributes attribute to set for the internal nodes 740 * @return a new tree (the original tree is left untouched) containing 741 * a single branch with the cell as a leaf node, and other leaf nodes 742 * as the remnants of the pruned branches 743 * @since 3.3 744 */ pruneAroundConvexCell(final Object cellAttribute, final Object otherLeafsAttributes, final Object internalAttributes)745 public BSPTree<S> pruneAroundConvexCell(final Object cellAttribute, 746 final Object otherLeafsAttributes, 747 final Object internalAttributes) { 748 749 // build the current cell leaf 750 BSPTree<S> tree = new BSPTree<S>(cellAttribute); 751 752 // build the pruned tree bottom-up 753 for (BSPTree<S> current = this; current.parent != null; current = current.parent) { 754 final SubHyperplane<S> parentCut = current.parent.cut.copySelf(); 755 final BSPTree<S> sibling = new BSPTree<S>(otherLeafsAttributes); 756 if (current == current.parent.plus) { 757 tree = new BSPTree<S>(parentCut, tree, sibling, internalAttributes); 758 } else { 759 tree = new BSPTree<S>(parentCut, sibling, tree, internalAttributes); 760 } 761 } 762 763 return tree; 764 765 } 766 767 /** Chop off parts of the tree. 768 * <p>The instance is modified in place, all the parts that are on 769 * the minus side of the chopping hyperplane are discarded, only the 770 * parts on the plus side remain.</p> 771 * @param hyperplane chopping hyperplane 772 * @param vanishingHandler handler to use for handling very rare corner 773 * cases of vanishing cut sub-hyperplanes in internal nodes during merging 774 */ chopOffMinus(final Hyperplane<S> hyperplane, final VanishingCutHandler<S> vanishingHandler)775 private void chopOffMinus(final Hyperplane<S> hyperplane, final VanishingCutHandler<S> vanishingHandler) { 776 if (cut != null) { 777 778 cut = cut.split(hyperplane).getPlus(); 779 plus.chopOffMinus(hyperplane, vanishingHandler); 780 minus.chopOffMinus(hyperplane, vanishingHandler); 781 782 if (cut == null) { 783 // the cut sub-hyperplane has vanished 784 final BSPTree<S> fixed = vanishingHandler.fixNode(this); 785 cut = fixed.cut; 786 plus = fixed.plus; 787 minus = fixed.minus; 788 attribute = fixed.attribute; 789 } 790 791 } 792 } 793 794 /** Chop off parts of the tree. 795 * <p>The instance is modified in place, all the parts that are on 796 * the plus side of the chopping hyperplane are discarded, only the 797 * parts on the minus side remain.</p> 798 * @param hyperplane chopping hyperplane 799 * @param vanishingHandler handler to use for handling very rare corner 800 * cases of vanishing cut sub-hyperplanes in internal nodes during merging 801 */ chopOffPlus(final Hyperplane<S> hyperplane, final VanishingCutHandler<S> vanishingHandler)802 private void chopOffPlus(final Hyperplane<S> hyperplane, final VanishingCutHandler<S> vanishingHandler) { 803 if (cut != null) { 804 805 cut = cut.split(hyperplane).getMinus(); 806 plus.chopOffPlus(hyperplane, vanishingHandler); 807 minus.chopOffPlus(hyperplane, vanishingHandler); 808 809 if (cut == null) { 810 // the cut sub-hyperplane has vanished 811 final BSPTree<S> fixed = vanishingHandler.fixNode(this); 812 cut = fixed.cut; 813 plus = fixed.plus; 814 minus = fixed.minus; 815 attribute = fixed.attribute; 816 } 817 818 } 819 } 820 821 } 822