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.geometry.core.partitioning.bsp; 018 019import java.util.Deque; 020import java.util.Iterator; 021import java.util.LinkedList; 022import java.util.NoSuchElementException; 023 024import org.apache.commons.geometry.core.Point; 025import org.apache.commons.geometry.core.Transform; 026import org.apache.commons.geometry.core.partitioning.Hyperplane; 027import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset; 028import org.apache.commons.geometry.core.partitioning.HyperplaneLocation; 029import org.apache.commons.geometry.core.partitioning.Split; 030import org.apache.commons.geometry.core.partitioning.SplitLocation; 031 032/** Abstract class for Binary Space Partitioning (BSP) tree implementations. This 033 * class contains basic structures and algorithms that should be common 034 * to all BSP tree implementations, regardless of the end use cases for the tree 035 * (eg, whether the tree is intended to represent polytopes, hold attributes like 036 * a map, etc). 037 * 038 * <h2>Implementation Notes</h2> 039 * <ul> 040 * <li>The {@link AbstractBSPTree} class is designed to work closely with its nested node type, 041 * {@link AbstractNode}. The tree class handles all tree manipulation operations while the node type 042 * is primarily a simple data type and delegates tree operations to internal methods within its 043 * parent tree. This allows for easier overriding of tree behavior in subclasses.</li> 044 * <li>Each time the structure of the tree is modified, a {@link #getVersion() version number} is 045 * incremented in the tree. This allows certain tree properties to be computed lazily and then 046 * cached. The tree version number is incremented with the {@link #invalidate() invalidate} method. Properties 047 * can be cached directly on nodes using the {@link AbstractBSPTree.AbstractNode#checkValid() checkValid} 048 * and {@link AbstractBSPTree.AbstractNode#nodeInvalidated() nodeInvalidated} methods.</li> 049 * <li>Since the methods used to construct and modify trees can vary by use case, no public API is provided 050 * for manipulating the tree. Subclasses are expected to use the protected methods of this class to 051 * create their own. For tree construction, subclasses are expected to pass their own {@link SubtreeInitializer} 052 * instances to {@link #insert(HyperplaneConvexSubset, SubtreeInitializer) insert} and 053 * {@link #cutNode(AbstractNode, Hyperplane, SubtreeInitializer) cutNode} in order to set the correct properties on 054 * tree nodes. To support tree copying, subclasses must also override 055 * {@link #copyNodeProperties(AbstractNode, AbstractNode) copyNodeProperties}.</li> 056 * <li>This class is not thread safe.</li> 057 * </ul> 058 * 059 * @param <P> Point implementation type 060 * @param <N> BSP tree node implementation type 061 * @see BSPTree 062 */ 063public abstract class AbstractBSPTree<P extends Point<P>, N extends AbstractBSPTree.AbstractNode<P, N>> 064 implements BSPTree<P, N> { 065 066 /** Interface used to initialize newly created BSP subtrees, consisting of a single parent 067 * node and two child nodes. 068 * @param <N> BSP tree node implementation type 069 */ 070 @FunctionalInterface 071 public interface SubtreeInitializer<N extends AbstractBSPTree.AbstractNode<?, ?>> { 072 073 /** Initialize the given newly-created subtree. The subtree consists of a single root node and two 074 * child nodes. 075 * @param root the root node of the new subtree 076 */ 077 void initSubtree(N root); 078 } 079 080 /** The default number of levels to print when creating a string representation of the tree. */ 081 private static final int DEFAULT_TREE_STRING_MAX_DEPTH = 8; 082 083 /** Integer value set on various node fields when a value is unknown. */ 084 private static final int UNKNOWN_VALUE = -1; 085 086 /** The root node for the tree. */ 087 private N root; 088 089 /** The current modification version for the tree structure. This is incremented each time 090 * a structural change occurs in the tree and is used to determine when cached values 091 * must be recomputed. 092 */ 093 private int version; 094 095 /** {@inheritDoc} */ 096 @Override 097 public N getRoot() { 098 if (root == null) { 099 setRoot(createNode()); 100 } 101 return root; 102 } 103 104 /** Set the root node for the tree. Cached tree properties are invalidated 105 * with {@link #invalidate()}. 106 * @param root new root node for the tree 107 */ 108 protected void setRoot(final N root) { 109 this.root = root; 110 111 this.root.makeRoot(); 112 113 invalidate(); 114 } 115 116 /** {@inheritDoc} */ 117 @Override 118 public int count() { 119 return getRoot().count(); 120 } 121 122 /** {@inheritDoc} */ 123 @Override 124 public int height() { 125 return getRoot().height(); 126 } 127 128 /** {@inheritDoc} */ 129 @Override 130 public void accept(final BSPTreeVisitor<P, N> visitor) { 131 accept(getRoot(), visitor); 132 } 133 134 /** {@inheritDoc} */ 135 @Override 136 public N findNode(final P pt, final FindNodeCutRule cutBehavior) { 137 return findNode(getRoot(), pt, cutBehavior); 138 } 139 140 /** {@inheritDoc} */ 141 @Override 142 public Iterable<N> nodes() { 143 return () -> new NodeIterator<>(getRoot()); 144 } 145 146 /** {@inheritDoc} */ 147 @Override 148 public void copy(final BSPTree<P, N> src) { 149 copySubtree(src.getRoot(), getRoot()); 150 } 151 152 /** {@inheritDoc} */ 153 @Override 154 public void extract(final N node) { 155 // copy downward 156 final N extracted = importSubtree(node); 157 158 // extract upward 159 final N newRoot = extractParentPath(node, extracted); 160 161 // set the root of this tree 162 setRoot(newRoot); 163 } 164 165 /** {@inheritDoc} */ 166 @Override 167 public void transform(final Transform<P> transform) { 168 final boolean swapChildren = swapsInsideOutside(transform); 169 transformRecursive(getRoot(), transform, swapChildren); 170 171 invalidate(); 172 } 173 174 /** Get a simple string representation of the tree structure. The returned string contains 175 * the tree structure down to the default max depth of {@value #DEFAULT_TREE_STRING_MAX_DEPTH}. 176 * @return a string representation of the tree 177 */ 178 public String treeString() { 179 return treeString(DEFAULT_TREE_STRING_MAX_DEPTH); 180 } 181 182 /** Get a simple string representation of the tree structure. The returned string contains 183 * the tree structure down to {@code maxDepth}. 184 * @param maxDepth the maximum depth in the tree to print; nodes below this depth are skipped 185 * @return a string representation of the tree 186 */ 187 public String treeString(final int maxDepth) { 188 final BSPTreePrinter<P, N> printer = new BSPTreePrinter<>(maxDepth); 189 accept(printer); 190 191 return printer.toString(); 192 } 193 194 /** {@inheritDoc} */ 195 @Override 196 public String toString() { 197 return new StringBuilder() 198 .append(getClass().getSimpleName()) 199 .append("[count= ") 200 .append(count()) 201 .append(", height= ") 202 .append(height()) 203 .append(']') 204 .toString(); 205 } 206 207 /** Create a new node for this tree. 208 * @return a new node for this tree 209 */ 210 protected abstract N createNode(); 211 212 /** Copy non-structural node properties from {@code src} to {@code dst}. 213 * Non-structural properties are those properties not directly related 214 * to the structure of the BSP tree, i.e. properties other than parent/child 215 * connections and cuts. Subclasses should override this method to copy additional 216 * properties stored on nodes. 217 * @param src source node 218 * @param dst destination node 219 */ 220 protected abstract void copyNodeProperties(N src, N dst); 221 222 /** Create a non-structural copy of the given node. Properties such as parent/child 223 * connections and cuts are <em>not</em> copied. 224 * @param src the node to copy; does not need to belong to the current tree 225 * @return the copied node 226 * @see AbstractBSPTree#copyNodeProperties(AbstractNode, AbstractNode) 227 */ 228 protected N copyNode(final N src) { 229 final N copy = createNode(); 230 copyNodeProperties(src, copy); 231 232 return copy; 233 } 234 235 /** Recursively copy a subtree. The returned node is not attached to the current tree. 236 * Structural <em>and</em> non-structural properties are copied from the source subtree 237 * to the destination subtree. This method does nothing if {@code src} and {@code dst} 238 * reference the same node. 239 * @param src the node representing the source subtree; does not need to belong to the 240 * current tree 241 * @param dst the node representing the destination subtree 242 * @return the copied node, ie {@code dst} 243 */ 244 protected N copySubtree(final N src, final N dst) { 245 // only copy if we're actually switching nodes 246 if (src != dst) { 247 // copy non-structural properties 248 copyNodeProperties(src, dst); 249 250 // copy the subtree structure 251 HyperplaneConvexSubset<P> cut = null; 252 N minus = null; 253 N plus = null; 254 255 if (!src.isLeaf()) { 256 final AbstractBSPTree<P, N> dstTree = dst.getTree(); 257 258 cut = src.getCut(); 259 minus = copySubtree(src.getMinus(), dstTree.createNode()); 260 plus = copySubtree(src.getPlus(), dstTree.createNode()); 261 } 262 263 dst.setSubtree(cut, minus, plus); 264 } 265 266 return dst; 267 } 268 269 /** Import the subtree represented by the given node into this tree. If the given node 270 * already belongs to this tree, then the node is returned directly without modification. 271 * If the node does <em>not</em> belong to this tree, a new node is created and the src node 272 * subtree is copied into it. 273 * 274 * <p>This method does not modify the current structure of the tree.</p> 275 * @param src node to import 276 * @return the given node if it belongs to this tree, otherwise a new node containing 277 * a copy of the given node's subtree 278 * @see #copySubtree(AbstractNode, AbstractNode) 279 */ 280 protected N importSubtree(final N src) { 281 // create a copy of the node if it's not already in this tree 282 if (src.getTree() != this) { 283 return copySubtree(src, createNode()); 284 } 285 286 return src; 287 } 288 289 /** Extract the path from {@code src} to the root of its tree and 290 * set it as the parent path of {@code dst}. Leaf nodes created during 291 * the extraction are given the same node properties as their counterparts 292 * in the source tree but without the cuts and child nodes. The properties 293 * of {@code dst} are not modified, with the exception of its parent node 294 * reference. 295 * @param src the source node to copy the parent path from 296 * @param dst the destination node to place under the extracted path 297 * @return the root node of the extracted path 298 */ 299 protected N extractParentPath(final N src, final N dst) { 300 N dstParent = dst; 301 N dstChild; 302 303 N srcChild = src; 304 N srcParent = srcChild.getParent(); 305 306 while (srcParent != null) { 307 dstChild = dstParent; 308 dstParent = copyNode(srcParent); 309 310 if (srcChild.isMinus()) { 311 dstParent.setSubtree( 312 srcParent.getCut(), 313 dstChild, 314 copyNode(srcParent.getPlus())); 315 } else { 316 dstParent.setSubtree( 317 srcParent.getCut(), 318 copyNode(srcParent.getMinus()), 319 dstChild); 320 } 321 322 srcChild = srcParent; 323 srcParent = srcChild.getParent(); 324 } 325 326 return dstParent; 327 } 328 329 /** Find the smallest node in the tree containing the point, starting 330 * at the given node. 331 * @param start the node to begin the search with 332 * @param pt the point to check 333 * @param cutRule value determining the search behavior when the test point 334 * lies directly on the cut of an internal node 335 * @return the smallest node in the tree containing the point 336 */ 337 protected N findNode(final N start, final P pt, final FindNodeCutRule cutRule) { 338 final Hyperplane<P> cutHyper = start.getCutHyperplane(); 339 if (cutHyper != null) { 340 final HyperplaneLocation cutLoc = cutHyper.classify(pt); 341 342 final boolean onPlusSide = cutLoc == HyperplaneLocation.PLUS; 343 final boolean onMinusSide = cutLoc == HyperplaneLocation.MINUS; 344 final boolean onCut = !onPlusSide && !onMinusSide; 345 346 if (onMinusSide || (onCut && cutRule == FindNodeCutRule.MINUS)) { 347 return findNode(start.getMinus(), pt, cutRule); 348 } else if (onPlusSide || cutRule == FindNodeCutRule.PLUS) { 349 return findNode(start.getPlus(), pt, cutRule); 350 } 351 } 352 return start; 353 } 354 355 /** Visit the nodes in a subtree. 356 * @param node the node to begin the visit process 357 * @param visitor the visitor to pass nodes to 358 */ 359 protected void accept(final N node, final BSPTreeVisitor<P, N> visitor) { 360 acceptRecursive(node, visitor); 361 } 362 363 /** Recursively visit the nodes in the subtree rooted at the given node. 364 * @param node the node located at the root of the subtree to visit 365 * @param visitor the visitor to pass nodes to 366 * @return true if the visit operation should continue 367 */ 368 private boolean acceptRecursive(final N node, final BSPTreeVisitor<P, N> visitor) { 369 if (node.isLeaf()) { 370 return shouldContinueVisit(visitor.visit(node)); 371 } else { 372 final BSPTreeVisitor.Order order = visitor.visitOrder(node); 373 374 if (order != null) { 375 376 switch (order) { 377 case PLUS_MINUS_NODE: 378 return acceptRecursive(node.getPlus(), visitor) && 379 acceptRecursive(node.getMinus(), visitor) && 380 shouldContinueVisit(visitor.visit(node)); 381 case PLUS_NODE_MINUS: 382 return acceptRecursive(node.getPlus(), visitor) && 383 shouldContinueVisit(visitor.visit(node)) && 384 acceptRecursive(node.getMinus(), visitor); 385 case MINUS_PLUS_NODE: 386 return acceptRecursive(node.getMinus(), visitor) && 387 acceptRecursive(node.getPlus(), visitor) && 388 shouldContinueVisit(visitor.visit(node)); 389 case MINUS_NODE_PLUS: 390 return acceptRecursive(node.getMinus(), visitor) && 391 shouldContinueVisit(visitor.visit(node)) && 392 acceptRecursive(node.getPlus(), visitor); 393 case NODE_PLUS_MINUS: 394 return shouldContinueVisit(visitor.visit(node)) && 395 acceptRecursive(node.getPlus(), visitor) && 396 acceptRecursive(node.getMinus(), visitor); 397 case NODE_MINUS_PLUS: 398 return shouldContinueVisit(visitor.visit(node)) && 399 acceptRecursive(node.getMinus(), visitor) && 400 acceptRecursive(node.getPlus(), visitor); 401 default: // NONE 402 break; 403 } 404 } 405 406 return true; 407 } 408 } 409 410 /** Return true if the given BSP tree visit result indicates that the current visit 411 * operation should continue. 412 * @param result visit result from BSP tree node visit operation 413 * @return true if the visit operation should continue with remaining nodes in the 414 * BSP tree 415 */ 416 private boolean shouldContinueVisit(final BSPTreeVisitor.Result result) { 417 return result == BSPTreeVisitor.Result.CONTINUE; 418 } 419 420 /** Cut a node with a hyperplane. The algorithm proceeds as follows: 421 * <ol> 422 * <li>The hyperplane is trimmed by splitting it with each cut hyperplane on the 423 * path from the given node to the root of the tree.</li> 424 * <li>If the remaining portion of the hyperplane is <em>not</em> empty, then 425 * <ul> 426 * <li>the remaining portion becomes the cut hyperplane subset for the node,</li> 427 * <li>two new child nodes are created and initialized with 428 * {@code subtreeInitializer}, and</li> 429 * <li>true is returned.</li> 430 * </ul> 431 * </li> 432 * <li>If the remaining portion of the hyperplane <em>is</em> empty (ie, the 433 * cutting hyperplane does not intersect the node's region), then 434 * <ul> 435 * <li>the node is converted to a leaf node (meaning that previous 436 * child nodes are lost), and</li> 437 * <li>false is returned.</li> 438 * </ul> 439 * </li> 440 * </ol> 441 * 442 * <p>It is important to note that since this method uses the path from given node 443 * to the tree root, it must only be used on nodes that are already inserted into 444 * the tree.</p> 445 * 446 * <p>This method calls {@link #invalidate()} to invalidate cached tree properties if the tree 447 * structure is changed.</p> 448 * 449 * @param node the node to cut 450 * @param cutter the hyperplane to cut the node with 451 * @param subtreeInitializer object used to initialize any newly-created subtrees 452 * @return true if the node was cut and two new child nodes were created; 453 * otherwise false 454 * @see #trimToNode(AbstractNode, HyperplaneConvexSubset) 455 * @see #setNodeCut(AbstractNode, HyperplaneConvexSubset, SubtreeInitializer) 456 * @see #removeNodeCut(AbstractNode) 457 * @see #invalidate() 458 */ 459 protected boolean cutNode(final N node, final Hyperplane<P> cutter, 460 final SubtreeInitializer<N> subtreeInitializer) { 461 462 // cut the hyperplane using all hyperplanes from this node up 463 // to the root 464 final HyperplaneConvexSubset<P> cut = trimToNode(node, cutter.span()); 465 if (cut == null || cut.isEmpty()) { 466 // insertion failed; the node was not cut 467 removeNodeCut(node); 468 return false; 469 } 470 471 setNodeCut(node, cut, subtreeInitializer); 472 return true; 473 } 474 475 /** Trim the given hyperplane convex subset to the region defined by the given node. This method 476 * cuts the subset with the cut hyperplanes (binary partitioners) of all parent nodes up to the 477 * root and returns the trimmed subset or {@code null} if the subset lies outside of the region 478 * defined by the node. 479 * 480 * <p>If the subset is directly coincident with a binary partitioner of a parent node, 481 * then the relative orientations of the associated hyperplanes are used to determine the behavior, 482 * as described below. 483 * <ul> 484 * <li>If the orientations are <strong>similar</strong>, then the subset is determined to 485 * lie <em>outside</em> of the node's region and {@code null} is returned.</li> 486 * <li>If the orientations are <strong>different</strong> (ie, opposite), then the subset 487 * is determined to lie <em>inside</em> of the node's region and the fit operation continues 488 * with the remaining parent nodes.</li> 489 * </ul> 490 * These rules are designed to allow the creation of trees with node regions that are the thickness 491 * of a single hyperplane. For example, in two dimensions, a tree could be constructed with an internal 492 * node containing a cut along the x-axis in the positive direction and with a child node containing a 493 * cut along the x-axis in the opposite direction. If the nodes in the tree are given inside and outside 494 * attributes, then this tree could be used to represent a region consisting of a single line or a region 495 * consisting of the entire space except for the single line. This would not be possible if nodes were not 496 * able to have cut hyperplanes that were coincident with parent cuts but in opposite directions. 497 * 498 * <p> 499 * Another way of looking at the rules above is that inserting a hyperplane into the tree that exactly 500 * matches the hyperplane of a parent node does not add any information to the tree. However, adding a 501 * hyperplane to the tree that is coincident with a parent node but with the opposite orientation, 502 * <em>does</em> add information to the tree. 503 * 504 * @param node the node representing the region to fit the hyperplane subset to 505 * @param sub the hyperplane subset to trim to the node's region 506 * @return the trimmed hyperplane subset or null if the given hyperplane subset does not intersect 507 * the node's region 508 */ 509 protected HyperplaneConvexSubset<P> trimToNode(final N node, final HyperplaneConvexSubset<P> sub) { 510 511 HyperplaneConvexSubset<P> result = sub; 512 513 N parentNode = node.getParent(); 514 N currentNode = node; 515 516 while (parentNode != null && result != null) { 517 final Split<? extends HyperplaneConvexSubset<P>> split = result.split(parentNode.getCutHyperplane()); 518 519 if (split.getLocation() == SplitLocation.NEITHER) { 520 // if we're directly on the splitter and have the same orientation, then 521 // we say the subset does not lie in the node's region (no new information 522 // is added to the tree in this case) 523 if (result.getHyperplane().similarOrientation(parentNode.getCutHyperplane())) { 524 result = null; 525 } 526 } else { 527 result = currentNode.isPlus() ? split.getPlus() : split.getMinus(); 528 } 529 530 currentNode = parentNode; 531 parentNode = parentNode.getParent(); 532 } 533 534 return result; 535 } 536 537 /** Remove the cut from the given node. Returns true if the node had a cut before 538 * the call to this method. Any previous child nodes are lost. 539 * 540 * <p>This method calls {@link #invalidate()} to invalidate cached tree properties if the tree 541 * structure changed.</p> 542 * @param node the node to remove the cut from 543 * @return true if the node previously had a cut 544 */ 545 protected boolean removeNodeCut(final N node) { 546 if (node.getCut() != null) { 547 node.setSubtree(null, null, null); 548 549 invalidate(); 550 551 return true; 552 } 553 554 return false; 555 } 556 557 /** Set the cut hyperplane subset for the given node. Two new child nodes are created for the 558 * node and the new subtree is initialized with {@code subtreeInitializer}. 559 * 560 * <p>This method performs absolutely <em>no</em> validation on the given cut 561 * hyperplane subset. It is the responsibility of the caller to ensure that the 562 * hyperplane subset fits the region represented by the node.</p> 563 * 564 * <p>This method always calls {@link #invalidate()} to invalidate cached tree properties.</p> 565 * @param node the node to cut 566 * @param cut the hyperplane convex subset to set as the node cut 567 * @param subtreeInitializer object used to initialize the newly-created subtree 568 */ 569 protected void setNodeCut(final N node, final HyperplaneConvexSubset<P> cut, 570 final SubtreeInitializer<N> subtreeInitializer) { 571 572 node.setSubtree(cut, createNode(), createNode()); 573 574 subtreeInitializer.initSubtree(node); 575 576 invalidate(); 577 } 578 579 /** Insert the given hyperplane convex subset into the tree, starting at the root node. Any subtrees 580 * created are initialized with {@code subtreeInit}. 581 * @param convexSub hyperplane convex subset to insert into the tree 582 * @param subtreeInit object used to initialize newly created subtrees 583 */ 584 protected void insert(final HyperplaneConvexSubset<P> convexSub, final SubtreeInitializer<N> subtreeInit) { 585 insertRecursive(getRoot(), convexSub, 586 convexSub.getHyperplane().span(), subtreeInit); 587 } 588 589 /** Recursively insert a hyperplane convex subset into the tree at the given node. 590 * @param node the node to begin insertion with 591 * @param insert the hyperplane subset to insert 592 * @param trimmed hyperplane subset containing the result of splitting the entire 593 * space with each hyperplane from this node to the root 594 * @param subtreeInit object used to initialize newly created subtrees 595 */ 596 private void insertRecursive(final N node, final HyperplaneConvexSubset<P> insert, 597 final HyperplaneConvexSubset<P> trimmed, final SubtreeInitializer<N> subtreeInit) { 598 if (node.isLeaf()) { 599 setNodeCut(node, trimmed, subtreeInit); 600 } else { 601 final Split<? extends HyperplaneConvexSubset<P>> insertSplit = insert.split(node.getCutHyperplane()); 602 603 final HyperplaneConvexSubset<P> minus = insertSplit.getMinus(); 604 final HyperplaneConvexSubset<P> plus = insertSplit.getPlus(); 605 606 if (minus != null || plus != null) { 607 final Split<? extends HyperplaneConvexSubset<P>> trimmedSplit = trimmed.split(node.getCutHyperplane()); 608 609 if (minus != null) { 610 insertRecursive(node.getMinus(), minus, trimmedSplit.getMinus(), subtreeInit); 611 } 612 if (plus != null) { 613 insertRecursive(node.getPlus(), plus, trimmedSplit.getPlus(), subtreeInit); 614 } 615 } 616 } 617 } 618 619 /** Return true if the given transform swaps the inside and outside of 620 * the region. 621 * 622 * <p>The default behavior of this method is to return true if the transform 623 * does not preserve spatial orientation (ie, {@link Transform#preservesOrientation()} 624 * is false). Subclasses may need to override this method to implement the correct 625 * behavior for their space and dimension.</p> 626 * @param transform transform to check 627 * @return true if the given transform swaps the interior and exterior of 628 * the region 629 */ 630 protected boolean swapsInsideOutside(final Transform<P> transform) { 631 return !transform.preservesOrientation(); 632 } 633 634 /** Transform the subtree rooted as {@code node} recursively. 635 * @param node the root node of the subtree to transform 636 * @param t the transform to apply 637 * @param swapChildren if true, the plus and minus child nodes of each internal node 638 * will be swapped; this should be the case when the transform is a reflection 639 */ 640 private void transformRecursive(final N node, final Transform<P> t, final boolean swapChildren) { 641 if (node.isInternal()) { 642 // transform our cut 643 final HyperplaneConvexSubset<P> transformedCut = node.getCut().transform(t); 644 645 // transform our children 646 transformRecursive(node.getMinus(), t, swapChildren); 647 transformRecursive(node.getPlus(), t, swapChildren); 648 649 final N transformedMinus = swapChildren ? node.getPlus() : node.getMinus(); 650 final N transformedPlus = swapChildren ? node.getMinus() : node.getPlus(); 651 652 // set our new state 653 node.setSubtree(transformedCut, transformedMinus, transformedPlus); 654 } 655 } 656 657 /** Split this tree with the given hyperplane, placing the split contents into the given 658 * target trees. One of the given trees may be null, in which case that portion of the split 659 * will not be exported. The current tree is not modified. 660 * @param splitter splitting hyperplane 661 * @param minus tree that will contain the portion of the tree on the minus side of the splitter 662 * @param plus tree that will contain the portion of the tree on the plus side of the splitter 663 */ 664 protected void splitIntoTrees(final Hyperplane<P> splitter, 665 final AbstractBSPTree<P, N> minus, final AbstractBSPTree<P, N> plus) { 666 667 final AbstractBSPTree<P, N> temp = (minus != null) ? minus : plus; 668 669 final N splitRoot = temp.splitSubtree(this.getRoot(), splitter.span()); 670 671 if (minus != null) { 672 if (plus != null) { 673 plus.extract(splitRoot.getPlus()); 674 } 675 minus.extract(splitRoot.getMinus()); 676 } else { 677 plus.extract(splitRoot.getPlus()); 678 } 679 } 680 681 /** Split the subtree rooted at the given node by a partitioning convex subset defined 682 * on the same region as the node. The subtree rooted at {@code node} is imported into 683 * this tree, meaning that if it comes from a different tree, the other tree is not 684 * modified. 685 * @param node the root node of the subtree to split; may come from a different tree, 686 * in which case the other tree is not modified 687 * @param partitioner partitioning convex subset 688 * @return node containing the split subtree 689 */ 690 protected N splitSubtree(final N node, final HyperplaneConvexSubset<P> partitioner) { 691 if (node.isLeaf()) { 692 return splitLeafNode(node, partitioner); 693 } 694 return splitInternalNode(node, partitioner); 695 } 696 697 /** Split the given leaf node by a partitioning convex subset defined on the 698 * same region and import it into this tree. 699 * @param node the leaf node to split 700 * @param partitioner partitioning convex subset 701 * @return node containing the split subtree 702 */ 703 private N splitLeafNode(final N node, final HyperplaneConvexSubset<P> partitioner) { 704 // in this case, we just create a new parent node with the partitioner as its 705 // cut and two copies of the original node as children 706 final N parent = createNode(); 707 parent.setSubtree(partitioner, copyNode(node), copyNode(node)); 708 709 return parent; 710 } 711 712 /** Split the given internal node by a partitioning convex subset defined on the same region 713 * as the node and import it into this tree. 714 * @param node the internal node to split 715 * @param partitioner partitioning convex subset 716 * @return node containing the split subtree 717 */ 718 private N splitInternalNode(final N node, final HyperplaneConvexSubset<P> partitioner) { 719 // split the partitioner and node cut with each other's hyperplanes to determine their relative positions 720 final Split<? extends HyperplaneConvexSubset<P>> partitionerSplit = partitioner.split(node.getCutHyperplane()); 721 final Split<? extends HyperplaneConvexSubset<P>> nodeCutSplit = 722 node.getCut().split(partitioner.getHyperplane()); 723 724 final SplitLocation partitionerSplitSide = partitionerSplit.getLocation(); 725 final SplitLocation nodeCutSplitSide = nodeCutSplit.getLocation(); 726 727 final N result = createNode(); 728 729 final N resultMinus; 730 final N resultPlus; 731 732 if (partitionerSplitSide == SplitLocation.PLUS) { 733 if (nodeCutSplitSide == SplitLocation.PLUS) { 734 // partitioner is on node cut plus side, node cut is on partitioner plus side 735 final N nodePlusSplit = splitSubtree(node.getPlus(), partitioner); 736 737 resultMinus = nodePlusSplit.getMinus(); 738 739 resultPlus = copyNode(node); 740 resultPlus.setSubtree(node.getCut(), importSubtree(node.getMinus()), nodePlusSplit.getPlus()); 741 } else { 742 // partitioner is on node cut plus side, node cut is on partitioner minus side 743 final N nodePlusSplit = splitSubtree(node.getPlus(), partitioner); 744 745 resultMinus = copyNode(node); 746 resultMinus.setSubtree(node.getCut(), importSubtree(node.getMinus()), nodePlusSplit.getMinus()); 747 748 resultPlus = nodePlusSplit.getPlus(); 749 } 750 } else if (partitionerSplitSide == SplitLocation.MINUS) { 751 if (nodeCutSplitSide == SplitLocation.MINUS) { 752 // partitioner is on node cut minus side, node cut is on partitioner minus side 753 final N nodeMinusSplit = splitSubtree(node.getMinus(), partitioner); 754 755 resultMinus = copyNode(node); 756 resultMinus.setSubtree(node.getCut(), nodeMinusSplit.getMinus(), importSubtree(node.getPlus())); 757 758 resultPlus = nodeMinusSplit.getPlus(); 759 } else { 760 // partitioner is on node cut minus side, node cut is on partitioner plus side 761 final N nodeMinusSplit = splitSubtree(node.getMinus(), partitioner); 762 763 resultMinus = nodeMinusSplit.getMinus(); 764 765 resultPlus = copyNode(node); 766 resultPlus.setSubtree(node.getCut(), nodeMinusSplit.getPlus(), importSubtree(node.getPlus())); 767 } 768 } else if (partitionerSplitSide == SplitLocation.BOTH) { 769 // partitioner and node cut split each other 770 final N nodeMinusSplit = splitSubtree(node.getMinus(), partitionerSplit.getMinus()); 771 final N nodePlusSplit = splitSubtree(node.getPlus(), partitionerSplit.getPlus()); 772 773 resultMinus = copyNode(node); 774 resultMinus.setSubtree(nodeCutSplit.getMinus(), nodeMinusSplit.getMinus(), nodePlusSplit.getMinus()); 775 776 resultPlus = copyNode(node); 777 resultPlus.setSubtree(nodeCutSplit.getPlus(), nodeMinusSplit.getPlus(), nodePlusSplit.getPlus()); 778 } else { 779 // partitioner and node cut are parallel or anti-parallel 780 final boolean sameOrientation = partitioner.getHyperplane().similarOrientation(node.getCutHyperplane()); 781 782 resultMinus = importSubtree(sameOrientation ? node.getMinus() : node.getPlus()); 783 resultPlus = importSubtree(sameOrientation ? node.getPlus() : node.getMinus()); 784 } 785 786 result.setSubtree(partitioner, resultMinus, resultPlus); 787 788 return result; 789 } 790 791 /** Invalidate any previously computed properties that rely on the internal structure of the tree. 792 * This method must be called any time the tree's internal structure changes in order to force cacheable 793 * tree and node properties to be recomputed the next time they are requested. 794 * 795 * <p>This method increments the tree's {@link #version} property.</p> 796 * @see #getVersion() 797 */ 798 protected void invalidate() { 799 version = Math.max(0, version + 1); // positive values only 800 } 801 802 /** Get the current structural version of the tree. This is incremented each time the 803 * tree structure is changes and can be used by nodes to allow caching of computed values. 804 * @return the current version of the tree structure 805 * @see #invalidate() 806 */ 807 protected int getVersion() { 808 return version; 809 } 810 811 /** Abstract implementation of {@link BSPTree.Node}. This class is intended for use with 812 * {@link AbstractBSPTree} and delegates tree mutation methods back to the parent tree object. 813 * @param <P> Point implementation type 814 * @param <N> BSP tree node implementation type 815 */ 816 public abstract static class AbstractNode<P extends Point<P>, N extends AbstractNode<P, N>> 817 implements BSPTree.Node<P, N> { 818 /** The owning tree instance. */ 819 private final AbstractBSPTree<P, N> tree; 820 821 /** The parent node; this will be null for the tree root node. */ 822 private N parent; 823 824 /** The hyperplane convex subset cutting the node's region; this will be null for leaf nodes. */ 825 private HyperplaneConvexSubset<P> cut; 826 827 /** The node lying on the minus side of the cut hyperplane; this will be null 828 * for leaf nodes. 829 */ 830 private N minus; 831 832 /** The node lying on the plus side of the cut hyperplane; this will be null 833 * for leaf nodes. 834 */ 835 private N plus; 836 837 /** The current version of the node. This is set to track the tree's version 838 * and is used to detect when certain values need to be recomputed due to 839 * structural changes in the tree. 840 */ 841 private int nodeVersion = -1; 842 843 /** The depth of this node in the tree. This will be zero for the root node and 844 * {@link AbstractBSPTree#UNKNOWN_VALUE} when the value needs to be computed. 845 */ 846 private int depth = UNKNOWN_VALUE; 847 848 /** The total number of nodes in the subtree rooted at this node. This will be 849 * set to {@link AbstractBSPTree#UNKNOWN_VALUE} when the value needs 850 * to be computed. 851 */ 852 private int count = UNKNOWN_VALUE; 853 854 /** The height of the subtree rooted at this node. This will 855 * be set to {@link AbstractBSPTree#UNKNOWN_VALUE} when the value needs 856 * to be computed. 857 */ 858 private int height = UNKNOWN_VALUE; 859 860 /** Simple constructor. 861 * @param tree the tree instance that owns this node 862 */ 863 protected AbstractNode(final AbstractBSPTree<P, N> tree) { 864 this.tree = tree; 865 } 866 867 /** {@inheritDoc} */ 868 @Override 869 public AbstractBSPTree<P, N> getTree() { 870 return tree; 871 } 872 873 /** {@inheritDoc} */ 874 @Override 875 public int depth() { 876 // Calculate our depth based on our parent's depth, if possible. 877 if (depth == UNKNOWN_VALUE && 878 parent != null) { 879 final int parentDepth = parent.depth(); 880 if (parentDepth != UNKNOWN_VALUE) { 881 depth = parentDepth + 1; 882 } 883 } 884 return depth; 885 } 886 887 /** {@inheritDoc} */ 888 @Override 889 public int height() { 890 checkValid(); 891 892 if (height == UNKNOWN_VALUE) { 893 if (isLeaf()) { 894 height = 0; 895 } else { 896 height = Math.max(getMinus().height(), getPlus().height()) + 1; 897 } 898 } 899 900 return height; 901 } 902 903 /** {@inheritDoc} */ 904 @Override 905 public int count() { 906 checkValid(); 907 908 if (count == UNKNOWN_VALUE) { 909 count = 1; 910 911 if (!isLeaf()) { 912 count += minus.count() + plus.count(); 913 } 914 } 915 916 return count; 917 } 918 919 /** {@inheritDoc} */ 920 @Override 921 public Iterable<N> nodes() { 922 return () -> new NodeIterator<>(getSelf()); 923 } 924 925 /** {@inheritDoc} */ 926 @Override 927 public void accept(final BSPTreeVisitor<P, N> visitor) { 928 tree.accept(getSelf(), visitor); 929 } 930 931 /** {@inheritDoc} */ 932 @Override 933 public N getParent() { 934 return parent; 935 } 936 937 /** {@inheritDoc} */ 938 @Override 939 public boolean isLeaf() { 940 return cut == null; 941 } 942 943 /** {@inheritDoc} */ 944 @Override 945 public boolean isInternal() { 946 return cut != null; 947 } 948 949 /** {@inheritDoc} */ 950 @Override 951 public boolean isPlus() { 952 return parent != null && parent.getPlus() == this; 953 } 954 955 /** {@inheritDoc} */ 956 @Override 957 public boolean isMinus() { 958 return parent != null && parent.getMinus() == this; 959 } 960 961 /** {@inheritDoc} */ 962 @Override 963 public HyperplaneConvexSubset<P> getCut() { 964 return cut; 965 } 966 967 /** {@inheritDoc} */ 968 @Override 969 public Hyperplane<P> getCutHyperplane() { 970 return (cut != null) ? cut.getHyperplane() : null; 971 } 972 973 /** {@inheritDoc} */ 974 @Override 975 public N getPlus() { 976 return plus; 977 } 978 979 /** {@inheritDoc} */ 980 @Override 981 public N getMinus() { 982 return minus; 983 } 984 985 /** {@inheritDoc} */ 986 @Override 987 public HyperplaneConvexSubset<P> trim(final HyperplaneConvexSubset<P> sub) { 988 return getTree().trimToNode(getSelf(), sub); 989 } 990 991 /** {@inheritDoc} */ 992 @Override 993 public String toString() { 994 final StringBuilder sb = new StringBuilder(); 995 sb.append(this.getClass().getSimpleName()) 996 .append("[cut= ") 997 .append(getCut()) 998 .append(']'); 999 1000 return sb.toString(); 1001 } 1002 1003 /** Set the parameters for the subtree rooted at this node. The arguments should either be 1004 * all null (representing a leaf node) or all non-null (representing an internal node). 1005 * 1006 * <p>Absolutely no validation is performed on the arguments. Callers are responsible for 1007 * ensuring that any given hyperplane subset fits the region defined by the node and that 1008 * any child nodes belong to this tree and are correctly initialized.</p> 1009 * 1010 * @param newCut the new cut hyperplane subset for the node 1011 * @param newMinus the new minus child for the node 1012 * @param newPlus the new plus child for the node 1013 */ 1014 protected void setSubtree(final HyperplaneConvexSubset<P> newCut, final N newMinus, final N newPlus) { 1015 this.cut = newCut; 1016 1017 final N self = getSelf(); 1018 1019 // cast for access to private member 1020 final AbstractNode<P, N> minusNode = newMinus; 1021 final AbstractNode<P, N> plusNode = newPlus; 1022 1023 // get the child depth now if we know it offhand, otherwise set it to the unknown value 1024 // and have the child pull it when needed 1025 final int childDepth = (depth != UNKNOWN_VALUE) ? depth + 1 : UNKNOWN_VALUE; 1026 1027 if (newMinus != null) { 1028 minusNode.parent = self; 1029 minusNode.depth = childDepth; 1030 } 1031 this.minus = newMinus; 1032 1033 if (newPlus != null) { 1034 plusNode.parent = self; 1035 plusNode.depth = childDepth; 1036 } 1037 this.plus = newPlus; 1038 } 1039 1040 /** 1041 * Make this node a root node, detaching it from its parent and settings its depth to zero. 1042 * Any previous parent node will be left in an invalid state since one of its children now 1043 * does not have a reference back to it. 1044 */ 1045 protected void makeRoot() { 1046 parent = null; 1047 depth = 0; 1048 } 1049 1050 /** Check if cached node properties are valid, meaning that no structural updates have 1051 * occurred in the tree since the last call to this method. If updates have occurred, the 1052 * {@link #nodeInvalidated()} method is called to clear the cached properties. This method 1053 * should be called at the beginning of any method that fetches cacheable properties 1054 * to ensure that no stale values are returned. 1055 */ 1056 protected void checkValid() { 1057 final int treeVersion = tree.getVersion(); 1058 1059 if (nodeVersion != treeVersion) { 1060 // the tree structure changed somewhere 1061 nodeInvalidated(); 1062 1063 // store the current version 1064 nodeVersion = treeVersion; 1065 } 1066 } 1067 1068 /** Method called from {@link #checkValid()} when updates 1069 * are detected in the tree. This method should clear out any 1070 * computed properties that rely on the structure of the tree 1071 * and prepare them for recalculation. 1072 */ 1073 protected void nodeInvalidated() { 1074 count = UNKNOWN_VALUE; 1075 height = UNKNOWN_VALUE; 1076 } 1077 1078 /** Get a reference to the current instance, cast to type N. 1079 * @return a reference to the current instance, as type N. 1080 */ 1081 protected abstract N getSelf(); 1082 } 1083 1084 /** Class for iterating through the nodes in a BSP subtree. 1085 * @param <P> Point implementation type 1086 * @param <N> Node implementation type 1087 */ 1088 private static final class NodeIterator<P extends Point<P>, N extends AbstractNode<P, N>> implements Iterator<N> { 1089 1090 /** The current node stack. */ 1091 private final Deque<N> stack = new LinkedList<>(); 1092 1093 /** Create a new instance for iterating over the nodes in the given subtree. 1094 * @param subtreeRoot the root node of the subtree to iterate 1095 */ 1096 NodeIterator(final N subtreeRoot) { 1097 stack.push(subtreeRoot); 1098 } 1099 1100 /** {@inheritDoc} */ 1101 @Override 1102 public boolean hasNext() { 1103 return !stack.isEmpty(); 1104 } 1105 1106 /** {@inheritDoc} */ 1107 @Override 1108 public N next() { 1109 if (stack.isEmpty()) { 1110 throw new NoSuchElementException(); 1111 } 1112 1113 final N result = stack.pop(); 1114 1115 if (result != null && !result.isLeaf()) { 1116 stack.push(result.getPlus()); 1117 stack.push(result.getMinus()); 1118 } 1119 1120 return result; 1121 } 1122 } 1123}