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.ArrayList; 020import java.util.Iterator; 021import java.util.List; 022import java.util.function.Function; 023import java.util.stream.Stream; 024 025import org.apache.commons.geometry.core.Point; 026import org.apache.commons.geometry.core.RegionLocation; 027import org.apache.commons.geometry.core.internal.IteratorTransform; 028import org.apache.commons.geometry.core.partitioning.BoundarySource; 029import org.apache.commons.geometry.core.partitioning.Hyperplane; 030import org.apache.commons.geometry.core.partitioning.HyperplaneBoundedRegion; 031import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset; 032import org.apache.commons.geometry.core.partitioning.HyperplaneLocation; 033import org.apache.commons.geometry.core.partitioning.HyperplaneSubset; 034import org.apache.commons.geometry.core.partitioning.Split; 035import org.apache.commons.geometry.core.partitioning.SplitLocation; 036import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor.ClosestFirstVisitor; 037 038/** Abstract {@link BSPTree} specialized for representing regions of space. For example, 039 * this class can be used to represent polygons in Euclidean 2D space and polyhedrons 040 * in Euclidean 3D space. 041 * 042 * <p>This class is not thread safe.</p> 043 * @param <P> Point implementation type 044 * @param <N> BSP tree node implementation type 045 * @see HyperplaneBoundedRegion 046 */ 047public abstract class AbstractRegionBSPTree< 048 P extends Point<P>, 049 N extends AbstractRegionBSPTree.AbstractRegionNode<P, N>> 050 extends AbstractBSPTree<P, N> implements HyperplaneBoundedRegion<P> { 051 052 /** The default {@link RegionCutRule}. */ 053 private static final RegionCutRule DEFAULT_REGION_CUT_RULE = RegionCutRule.MINUS_INSIDE; 054 055 /** Value used to indicate an unknown size. */ 056 private static final double UNKNOWN_SIZE = -1.0; 057 058 /** The region boundary size; this is computed when requested and then cached. */ 059 private double boundarySize = UNKNOWN_SIZE; 060 061 /** The current size properties for the region. */ 062 private RegionSizeProperties<P> regionSizeProperties; 063 064 /** Construct a new region will the given boolean determining whether or not the 065 * region will be full (including the entire space) or empty (excluding the entire 066 * space). 067 * @param full if true, the region will cover the entire space, otherwise it will 068 * be empty 069 */ 070 protected AbstractRegionBSPTree(final boolean full) { 071 getRoot().setLocationValue(full ? RegionLocation.INSIDE : RegionLocation.OUTSIDE); 072 } 073 074 /** {@inheritDoc} */ 075 @Override 076 public boolean isEmpty() { 077 return !hasNodeWithLocationRecursive(getRoot(), RegionLocation.INSIDE); 078 } 079 080 /** {@inheritDoc} */ 081 @Override 082 public boolean isFull() { 083 return !hasNodeWithLocationRecursive(getRoot(), RegionLocation.OUTSIDE); 084 } 085 086 /** Return true if any node in the subtree rooted at the given node has a location with the 087 * given value. 088 * @param node the node at the root of the subtree to search 089 * @param location the location to find 090 * @return true if any node in the subtree has the given location 091 */ 092 private boolean hasNodeWithLocationRecursive(final AbstractRegionNode<P, N> node, final RegionLocation location) { 093 if (node == null) { 094 return false; 095 } 096 097 return node.getLocation() == location || 098 hasNodeWithLocationRecursive(node.getMinus(), location) || 099 hasNodeWithLocationRecursive(node.getPlus(), location); 100 } 101 102 /** Modify this instance so that it contains the entire space. 103 * @see #isFull() 104 */ 105 public void setFull() { 106 final N root = getRoot(); 107 108 root.clearCut(); 109 root.setLocationValue(RegionLocation.INSIDE); 110 } 111 112 /** Modify this instance so that is is completely empty. 113 * @see #isEmpty() 114 */ 115 public void setEmpty() { 116 final N root = getRoot(); 117 118 root.clearCut(); 119 root.setLocationValue(RegionLocation.OUTSIDE); 120 } 121 122 /** {@inheritDoc} */ 123 @Override 124 public double getSize() { 125 return getRegionSizeProperties().getSize(); 126 } 127 128 /** {@inheritDoc} */ 129 @Override 130 public double getBoundarySize() { 131 if (boundarySize < 0) { 132 double sum = 0.0; 133 134 RegionCutBoundary<P> boundary; 135 for (final AbstractRegionNode<P, N> node : nodes()) { 136 boundary = node.getCutBoundary(); 137 if (boundary != null) { 138 sum += boundary.getSize(); 139 } 140 } 141 142 boundarySize = sum; 143 } 144 145 return boundarySize; 146 } 147 148 /** Insert a hyperplane subset into the tree, using the default {@link RegionCutRule} of 149 * {@link RegionCutRule#MINUS_INSIDE MINUS_INSIDE}. 150 * @param sub the hyperplane subset to insert into the tree 151 */ 152 public void insert(final HyperplaneSubset<P> sub) { 153 insert(sub, DEFAULT_REGION_CUT_RULE); 154 } 155 156 /** Insert a hyperplane subset into the tree. 157 * @param sub the hyperplane subset to insert into the tree 158 * @param cutRule rule used to determine the region locations of new child nodes 159 */ 160 public void insert(final HyperplaneSubset<P> sub, final RegionCutRule cutRule) { 161 insert(sub.toConvex(), cutRule); 162 } 163 164 /** Insert a hyperplane convex subset into the tree, using the default {@link RegionCutRule} of 165 * {@link RegionCutRule#MINUS_INSIDE MINUS_INSIDE}. 166 * @param convexSub the hyperplane convex subset to insert into the tree 167 */ 168 public void insert(final HyperplaneConvexSubset<P> convexSub) { 169 insert(convexSub, DEFAULT_REGION_CUT_RULE); 170 } 171 172 /** Insert a hyperplane convex subset into the tree. 173 * @param convexSub the hyperplane convex subset to insert into the tree 174 * @param cutRule rule used to determine the region locations of new child nodes 175 */ 176 public void insert(final HyperplaneConvexSubset<P> convexSub, final RegionCutRule cutRule) { 177 insert(convexSub, getSubtreeInitializer(cutRule)); 178 } 179 180 /** Insert a set of hyperplane convex subsets into the tree, using the default {@link RegionCutRule} of 181 * {@link RegionCutRule#MINUS_INSIDE MINUS_INSIDE}. 182 * @param convexSubs iterable containing a collection of hyperplane convex subsets 183 * to insert into the tree 184 */ 185 public void insert(final Iterable<? extends HyperplaneConvexSubset<P>> convexSubs) { 186 insert(convexSubs, DEFAULT_REGION_CUT_RULE); 187 } 188 189 /** Insert a set of hyperplane convex subsets into the tree. 190 * @param convexSubs iterable containing a collection of hyperplane convex subsets 191 * to insert into the tree 192 * @param cutRule rule used to determine the region locations of new child nodes 193 */ 194 public void insert(final Iterable<? extends HyperplaneConvexSubset<P>> convexSubs, final RegionCutRule cutRule) { 195 for (final HyperplaneConvexSubset<P> convexSub : convexSubs) { 196 insert(convexSub, cutRule); 197 } 198 } 199 200 /** Insert all hyperplane convex subsets from the given source into the tree, using the default 201 * {@link RegionCutRule} of {@link RegionCutRule#MINUS_INSIDE MINUS_INSIDE}. 202 * @param boundarySrc source of boundary hyperplane subsets to insert 203 * into the tree 204 */ 205 public void insert(final BoundarySource<? extends HyperplaneConvexSubset<P>> boundarySrc) { 206 insert(boundarySrc, DEFAULT_REGION_CUT_RULE); 207 } 208 209 /** Insert all hyperplane convex subsets from the given source into the tree. 210 * @param boundarySrc source of boundary hyperplane subsets to insert 211 * into the tree 212 * @param cutRule rule used to determine the region locations of new child nodes 213 */ 214 public void insert(final BoundarySource<? extends HyperplaneConvexSubset<P>> boundarySrc, 215 final RegionCutRule cutRule) { 216 try (Stream<? extends HyperplaneConvexSubset<P>> stream = boundarySrc.boundaryStream()) { 217 stream.forEach(c -> insert(c, cutRule)); 218 } 219 } 220 221 /** Get the subtree initializer to use for the given region cut rule. 222 * @param cutRule the cut rule to get an initializer for 223 * @return the subtree initializer for the given region cut rule 224 */ 225 protected SubtreeInitializer<N> getSubtreeInitializer(final RegionCutRule cutRule) { 226 switch (cutRule) { 227 case INHERIT: 228 return root -> { 229 final RegionLocation rootLoc = root.getLocation(); 230 231 root.getMinus().setLocationValue(rootLoc); 232 root.getPlus().setLocationValue(rootLoc); 233 }; 234 case PLUS_INSIDE: 235 return root -> { 236 root.getMinus().setLocationValue(RegionLocation.OUTSIDE); 237 root.getPlus().setLocationValue(RegionLocation.INSIDE); 238 }; 239 default: 240 return root -> { 241 root.getMinus().setLocationValue(RegionLocation.INSIDE); 242 root.getPlus().setLocationValue(RegionLocation.OUTSIDE); 243 }; 244 } 245 } 246 247 /** Return an {@link Iterable} for iterating over the boundaries of the region. 248 * Each boundary is oriented such that its plus side points to the outside of the 249 * region. The exact ordering of the boundaries is determined by the internal structure 250 * of the tree. 251 * @return an {@link Iterable} for iterating over the boundaries of the region 252 * @see #getBoundaries() 253 */ 254 public Iterable<? extends HyperplaneConvexSubset<P>> boundaries() { 255 return createBoundaryIterable(Function.identity()); 256 } 257 258 /** Internal method for creating the iterable instances used to iterate the region boundaries. 259 * @param typeConverter function to convert the generic hyperplane subset type into 260 * the type specific for this tree 261 * @param <C> HyperplaneConvexSubset implementation type 262 * @return an iterable to iterating the region boundaries 263 */ 264 protected <C extends HyperplaneConvexSubset<P>> Iterable<C> createBoundaryIterable( 265 final Function<HyperplaneConvexSubset<P>, C> typeConverter) { 266 267 return () -> new RegionBoundaryIterator<>( 268 getRoot().nodes().iterator(), 269 typeConverter); 270 } 271 272 /** Return a list containing the boundaries of the region. Each boundary is oriented such 273 * that its plus side points to the outside of the region. The exact ordering of 274 * the boundaries is determined by the internal structure of the tree. 275 * @return a list of the boundaries of the region 276 */ 277 public List<? extends HyperplaneConvexSubset<P>> getBoundaries() { 278 return createBoundaryList(Function.identity()); 279 } 280 281 /** Internal method for creating a list of the region boundaries. 282 * @param typeConverter function to convert the generic convex subset type into 283 * the type specific for this tree 284 * @param <C> HyperplaneConvexSubset implementation type 285 * @return a list of the region boundaries 286 */ 287 protected <C extends HyperplaneConvexSubset<P>> List<C> createBoundaryList( 288 final Function<HyperplaneConvexSubset<P>, C> typeConverter) { 289 290 final List<C> result = new ArrayList<>(); 291 292 final RegionBoundaryIterator<P, C, N> it = new RegionBoundaryIterator<>(nodes().iterator(), typeConverter); 293 it.forEachRemaining(result::add); 294 295 return result; 296 } 297 298 /** {@inheritDoc} */ 299 @Override 300 public P project(final P pt) { 301 final BoundaryProjector<P, N> projector = new BoundaryProjector<>(pt); 302 accept(projector); 303 304 return projector.getProjected(); 305 } 306 307 /** {@inheritDoc} */ 308 @Override 309 public P getCentroid() { 310 return getRegionSizeProperties().getCentroid(); 311 } 312 313 /** Helper method implementing the algorithm for splitting a tree by a hyperplane. Subclasses 314 * should call this method with two instantiated trees of the correct type. 315 * @param splitter splitting hyperplane 316 * @param minus tree that will contain the minus side of the split result 317 * @param plus tree that will contain the plus side of the split result 318 * @param <T> Tree implementation type 319 * @return result of splitting this tree with the given hyperplane 320 */ 321 protected <T extends AbstractRegionBSPTree<P, N>> Split<T> split(final Hyperplane<P> splitter, 322 final T minus, final T plus) { 323 324 splitIntoTrees(splitter, minus, plus); 325 326 T splitMinus = null; 327 T splitPlus = null; 328 329 if (minus != null) { 330 minus.getRoot().getPlus().setLocationValue(RegionLocation.OUTSIDE); 331 minus.condense(); 332 333 splitMinus = minus.isEmpty() ? null : minus; 334 } 335 if (plus != null) { 336 plus.getRoot().getMinus().setLocationValue(RegionLocation.OUTSIDE); 337 plus.condense(); 338 339 splitPlus = plus.isEmpty() ? null : plus; 340 } 341 342 return new Split<>(splitMinus, splitPlus); 343 } 344 345 /** Get the size-related properties for the region. The value is computed 346 * lazily and cached. 347 * @return the size-related properties for the region 348 */ 349 protected RegionSizeProperties<P> getRegionSizeProperties() { 350 if (regionSizeProperties == null) { 351 regionSizeProperties = computeRegionSizeProperties(); 352 } 353 354 return regionSizeProperties; 355 } 356 357 /** Compute the size-related properties of the region. 358 * @return object containing size properties for the region 359 */ 360 protected abstract RegionSizeProperties<P> computeRegionSizeProperties(); 361 362 /** {@inheritDoc} 363 * 364 * <p>If the point is {@link org.apache.commons.geometry.core.Spatial#isNaN() NaN}, then 365 * {@link RegionLocation#OUTSIDE} is returned.</p> 366 */ 367 @Override 368 public RegionLocation classify(final P point) { 369 if (point.isNaN()) { 370 return RegionLocation.OUTSIDE; 371 } 372 373 return classifyRecursive(getRoot(), point); 374 } 375 376 /** Recursively classify a point with respect to the region. 377 * @param node the node to classify against 378 * @param point the point to classify 379 * @return the classification of the point with respect to the region rooted 380 * at the given node 381 */ 382 private RegionLocation classifyRecursive(final AbstractRegionNode<P, N> node, final P point) { 383 if (node.isLeaf()) { 384 // the point is in a leaf, so the classification is just the leaf location 385 return node.getLocation(); 386 } else { 387 final HyperplaneLocation cutLoc = node.getCutHyperplane().classify(point); 388 389 if (cutLoc == HyperplaneLocation.MINUS) { 390 return classifyRecursive(node.getMinus(), point); 391 } else if (cutLoc == HyperplaneLocation.PLUS) { 392 return classifyRecursive(node.getPlus(), point); 393 } else { 394 // the point is on the cut boundary; classify against both child 395 // subtrees and see if we end up with the same result or not 396 final RegionLocation minusLoc = classifyRecursive(node.getMinus(), point); 397 final RegionLocation plusLoc = classifyRecursive(node.getPlus(), point); 398 399 if (minusLoc == plusLoc) { 400 return minusLoc; 401 } 402 return RegionLocation.BOUNDARY; 403 } 404 } 405 } 406 407 /** Change this region into its complement. All inside nodes become outside 408 * nodes and vice versa. The orientations of the node cuts are not modified. 409 */ 410 public void complement() { 411 complementRecursive(getRoot()); 412 } 413 414 /** Set this instance to be the complement of the given tree. The argument 415 * is not modified. 416 * @param tree the tree to become the complement of 417 */ 418 public void complement(final AbstractRegionBSPTree<P, N> tree) { 419 copySubtree(tree.getRoot(), getRoot()); 420 complementRecursive(getRoot()); 421 } 422 423 /** Recursively switch all inside nodes to outside nodes and vice versa. 424 * @param node the node at the root of the subtree to switch 425 */ 426 private void complementRecursive(final AbstractRegionNode<P, N> node) { 427 if (node != null) { 428 final RegionLocation newLoc = (node.getLocation() == RegionLocation.INSIDE) ? 429 RegionLocation.OUTSIDE : 430 RegionLocation.INSIDE; 431 432 node.setLocationValue(newLoc); 433 434 complementRecursive(node.getMinus()); 435 complementRecursive(node.getPlus()); 436 } 437 } 438 439 /** Compute the union of this instance and the given region, storing the result back in 440 * this instance. The argument is not modified. 441 * @param other the tree to compute the union with 442 */ 443 public void union(final AbstractRegionBSPTree<P, N> other) { 444 new UnionOperator<P, N>().apply(this, other, this); 445 } 446 447 /** Compute the union of the two regions passed as arguments and store the result in 448 * this instance. Any nodes currently existing in this instance are removed. 449 * @param a first argument to the union operation 450 * @param b second argument to the union operation 451 */ 452 public void union(final AbstractRegionBSPTree<P, N> a, final AbstractRegionBSPTree<P, N> b) { 453 new UnionOperator<P, N>().apply(a, b, this); 454 } 455 456 /** Compute the intersection of this instance and the given region, storing the result back in 457 * this instance. The argument is not modified. 458 * @param other the tree to compute the intersection with 459 */ 460 public void intersection(final AbstractRegionBSPTree<P, N> other) { 461 new IntersectionOperator<P, N>().apply(this, other, this); 462 } 463 464 /** Compute the intersection of the two regions passed as arguments and store the result in 465 * this instance. Any nodes currently existing in this instance are removed. 466 * @param a first argument to the intersection operation 467 * @param b second argument to the intersection operation 468 */ 469 public void intersection(final AbstractRegionBSPTree<P, N> a, final AbstractRegionBSPTree<P, N> b) { 470 new IntersectionOperator<P, N>().apply(a, b, this); 471 } 472 473 /** Compute the difference of this instance and the given region, storing the result back in 474 * this instance. The argument is not modified. 475 * @param other the tree to compute the difference with 476 */ 477 public void difference(final AbstractRegionBSPTree<P, N> other) { 478 new DifferenceOperator<P, N>().apply(this, other, this); 479 } 480 481 /** Compute the difference of the two regions passed as arguments and store the result in 482 * this instance. Any nodes currently existing in this instance are removed. 483 * @param a first argument to the difference operation 484 * @param b second argument to the difference operation 485 */ 486 public void difference(final AbstractRegionBSPTree<P, N> a, final AbstractRegionBSPTree<P, N> b) { 487 new DifferenceOperator<P, N>().apply(a, b, this); 488 } 489 490 /** Compute the symmetric difference (xor) of this instance and the given region, storing the result back in 491 * this instance. The argument is not modified. 492 * @param other the tree to compute the symmetric difference with 493 */ 494 public void xor(final AbstractRegionBSPTree<P, N> other) { 495 new XorOperator<P, N>().apply(this, other, this); 496 } 497 498 /** Compute the symmetric difference (xor) of the two regions passed as arguments and store the result in 499 * this instance. Any nodes currently existing in this instance are removed. 500 * @param a first argument to the symmetric difference operation 501 * @param b second argument to the symmetric difference operation 502 */ 503 public void xor(final AbstractRegionBSPTree<P, N> a, final AbstractRegionBSPTree<P, N> b) { 504 new XorOperator<P, N>().apply(a, b, this); 505 } 506 507 /** Condense this tree by removing redundant subtrees, returning true if the 508 * tree structure was modified. 509 * 510 * <p>This operation can be used to reduce the total number of nodes in the 511 * tree after performing node manipulations. For example, if two sibling leaf 512 * nodes both represent the same {@link RegionLocation}, then there is no reason 513 * from the perspective of the geometric region to retain both nodes. They are 514 * therefore both merged into their parent node. This method performs this 515 * simplification process. 516 * </p> 517 * @return true if the tree structure was modified, otherwise false 518 */ 519 public boolean condense() { 520 return new Condenser<P, N>().condense(getRoot()); 521 } 522 523 /** {@inheritDoc} */ 524 @Override 525 protected void copyNodeProperties(final N src, final N dst) { 526 dst.setLocationValue(src.getLocation()); 527 } 528 529 /** {@inheritDoc} */ 530 @Override 531 protected void invalidate() { 532 super.invalidate(); 533 534 // clear cached region properties 535 boundarySize = UNKNOWN_SIZE; 536 regionSizeProperties = null; 537 } 538 539 /** {@link BSPTree.Node} implementation for use with {@link AbstractRegionBSPTree}s. 540 * @param <P> Point implementation type 541 * @param <N> BSP tree node implementation type 542 */ 543 public abstract static class AbstractRegionNode<P extends Point<P>, N extends AbstractRegionNode<P, N>> 544 extends AbstractBSPTree.AbstractNode<P, N> { 545 /** The location for the node. This will only be set on leaf nodes. */ 546 private RegionLocation location; 547 548 /** Object representing the part of the node cut hyperplane subset that lies on the 549 * region boundary. This is calculated lazily and is only present on internal nodes. 550 */ 551 private RegionCutBoundary<P> cutBoundary; 552 553 /** Simple constructor. 554 * @param tree owning tree instance 555 */ 556 protected AbstractRegionNode(final AbstractBSPTree<P, N> tree) { 557 super(tree); 558 } 559 560 /** {@inheritDoc} */ 561 @Override 562 public AbstractRegionBSPTree<P, N> getTree() { 563 // cast to our parent tree type 564 return (AbstractRegionBSPTree<P, N>) super.getTree(); 565 } 566 567 /** Get the location property of the node. Only the locations of leaf nodes are meaningful 568 * as they relate to the region represented by the BSP tree. For example, changing 569 * the location of an internal node will only affect the geometric properties 570 * of the region if the node later becomes a leaf node. 571 * @return the location of the node 572 */ 573 public RegionLocation getLocation() { 574 return location; 575 } 576 577 /** Set the location property for the node. If the location is changed, the tree is 578 * invalidated. 579 * 580 * <p>Only the locations of leaf nodes are meaningful 581 * as they relate to the region represented by the BSP tree. For example, changing 582 * the location of an internal node will only affect the geometric properties 583 * of the region if the node later becomes a leaf node.</p> 584 * @param location the location for the node 585 * @throws IllegalArgumentException if {@code location} is not one of 586 * {@link RegionLocation#INSIDE INSIDE} or {@link RegionLocation#OUTSIDE OUTSIDE} 587 */ 588 public void setLocation(final RegionLocation location) { 589 if (location != RegionLocation.INSIDE && location != RegionLocation.OUTSIDE) { 590 throw new IllegalArgumentException("Invalid node location: " + location); 591 } 592 if (this.location != location) { 593 this.location = location; 594 595 getTree().invalidate(); 596 } 597 } 598 599 /** True if the node is a leaf node and has a location of {@link RegionLocation#INSIDE}. 600 * @return true if the node is a leaf node and has a location of 601 * {@link RegionLocation#INSIDE} 602 */ 603 public boolean isInside() { 604 return isLeaf() && getLocation() == RegionLocation.INSIDE; 605 } 606 607 /** True if the node is a leaf node and has a location of {@link RegionLocation#OUTSIDE}. 608 * @return true if the node is a leaf node and has a location of 609 * {@link RegionLocation#OUTSIDE} 610 */ 611 public boolean isOutside() { 612 return isLeaf() && getLocation() == RegionLocation.OUTSIDE; 613 } 614 615 /** Insert a cut into this node, using the default region cut rule of 616 * {@link RegionCutRule#MINUS_INSIDE}. 617 * @param cutter the hyperplane to cut the node's region with 618 * @return true if the cutting hyperplane intersected the node's region, resulting 619 * in the creation of new child nodes 620 * @see #insertCut(Hyperplane, RegionCutRule) 621 */ 622 public boolean insertCut(final Hyperplane<P> cutter) { 623 return insertCut(cutter, DEFAULT_REGION_CUT_RULE); 624 } 625 626 /** Insert a cut into this node. If the given hyperplane intersects 627 * this node's region, then the node's cut is set to the {@link HyperplaneConvexSubset} 628 * representing the intersection, new plus and minus child leaf nodes 629 * are assigned, and true is returned. If the hyperplane does not intersect 630 * the node's region, then the node's cut and plus and minus child references 631 * are all set to null (ie, it becomes a leaf node) and false is returned. In 632 * either case, any existing cut and/or child nodes are removed by this method. 633 * @param cutter the hyperplane to cut the node's region with 634 * @param cutRule rule used to determine the region locations of newly created 635 * child nodes 636 * @return true if the cutting hyperplane intersected the node's region, resulting 637 * in the creation of new child nodes 638 */ 639 public boolean insertCut(final Hyperplane<P> cutter, final RegionCutRule cutRule) { 640 final AbstractRegionBSPTree<P, N> tree = getTree(); 641 return tree.cutNode(getSelf(), cutter, tree.getSubtreeInitializer(cutRule)); 642 } 643 644 /** Remove the cut from this node. Returns true if the node previously had a cut. 645 * @return true if the node had a cut before the call to this method 646 */ 647 public boolean clearCut() { 648 return getTree().removeNodeCut(getSelf()); 649 } 650 651 /** Cut this node with the given hyperplane. The same node is returned, regardless of 652 * the outcome of the cut operation. If the operation succeeded, then the node will 653 * have plus and minus child nodes. 654 * @param cutter the hyperplane to cut the node's region with 655 * @return this node 656 * @see #insertCut(Hyperplane) 657 */ 658 public N cut(final Hyperplane<P> cutter) { 659 return cut(cutter, DEFAULT_REGION_CUT_RULE); 660 } 661 662 /** Cut this node with the given hyperplane, using {@code cutRule} to determine the region 663 * locations of any new child nodes. The same node is returned, regardless of 664 * the outcome of the cut operation. If the operation succeeded, then the node will 665 * have plus and minus child nodes. 666 * @param cutter the hyperplane to cut the node's region with 667 * @param cutRule rule used to determine the region locations of newly created 668 * child nodes 669 * @return this node 670 * @see #insertCut(Hyperplane, RegionCutRule) 671 */ 672 public N cut(final Hyperplane<P> cutter, final RegionCutRule cutRule) { 673 this.insertCut(cutter, cutRule); 674 675 return getSelf(); 676 } 677 678 /** Get the portion of the node's cut that lies on the boundary of the region. 679 * @return the portion of the node's cut that lies on the boundary of 680 * the region 681 */ 682 public RegionCutBoundary<P> getCutBoundary() { 683 if (!isLeaf()) { 684 checkValid(); 685 686 if (cutBoundary == null) { 687 cutBoundary = computeBoundary(); 688 } 689 } 690 691 return cutBoundary; 692 } 693 694 /** Compute the portion of the node's cut that lies on the boundary of the region. 695 * This method must only be called on internal nodes. 696 * @return object representing the portions of the node's cut that lie on the region's boundary 697 */ 698 private RegionCutBoundary<P> computeBoundary() { 699 final HyperplaneConvexSubset<P> sub = getCut(); 700 701 // find the portions of the node cut hyperplane subset that touch inside and 702 // outside cells in the minus sub-tree 703 final List<HyperplaneConvexSubset<P>> minusIn = new ArrayList<>(); 704 final List<HyperplaneConvexSubset<P>> minusOut = new ArrayList<>(); 705 706 characterizeHyperplaneSubset(sub, getMinus(), minusIn, minusOut); 707 708 final ArrayList<HyperplaneConvexSubset<P>> insideFacing = new ArrayList<>(); 709 final ArrayList<HyperplaneConvexSubset<P>> outsideFacing = new ArrayList<>(); 710 711 if (!minusIn.isEmpty()) { 712 // Add to the boundary anything that touches an inside cell in the minus sub-tree 713 // and an outside cell in the plus sub-tree. These portions are oriented with their 714 // plus side pointing to the outside of the region. 715 for (final HyperplaneConvexSubset<P> minusInFragment : minusIn) { 716 characterizeHyperplaneSubset(minusInFragment, getPlus(), null, outsideFacing); 717 } 718 } 719 720 if (!minusOut.isEmpty()) { 721 // Add to the boundary anything that touches an outside cell in the minus sub-tree 722 // and an inside cell in the plus sub-tree. These portions are oriented with their 723 // plus side pointing to the inside of the region. 724 for (final HyperplaneConvexSubset<P> minusOutFragment : minusOut) { 725 characterizeHyperplaneSubset(minusOutFragment, getPlus(), insideFacing, null); 726 } 727 } 728 729 insideFacing.trimToSize(); 730 outsideFacing.trimToSize(); 731 732 return new RegionCutBoundary<>( 733 insideFacing.isEmpty() ? null : insideFacing, 734 outsideFacing.isEmpty() ? null : outsideFacing); 735 } 736 737 /** Recursive method to characterize a hyperplane convex subset with respect to the region's 738 * boundaries. 739 * @param sub the hyperplane convex subset to characterize 740 * @param node the node to characterize the hyperplane convex subset against 741 * @param in list that will receive the portions of the subset that lie in the inside 742 * of the region; may be null 743 * @param out list that will receive the portions of the subset that lie on the outside 744 * of the region; may be null 745 */ 746 private void characterizeHyperplaneSubset(final HyperplaneConvexSubset<P> sub, 747 final AbstractRegionNode<P, N> node, final List<? super HyperplaneConvexSubset<P>> in, 748 final List<? super HyperplaneConvexSubset<P>> out) { 749 750 if (sub != null) { 751 if (node.isLeaf()) { 752 if (node.isInside() && in != null) { 753 in.add(sub); 754 } else if (node.isOutside() && out != null) { 755 out.add(sub); 756 } 757 } else { 758 final Split<? extends HyperplaneConvexSubset<P>> split = sub.split(node.getCutHyperplane()); 759 760 // Continue further on down the subtree with the same subset if the 761 // subset lies directly on the current node's cut 762 if (split.getLocation() == SplitLocation.NEITHER) { 763 characterizeHyperplaneSubset(sub, node.getPlus(), in, out); 764 characterizeHyperplaneSubset(sub, node.getMinus(), in, out); 765 } else { 766 characterizeHyperplaneSubset(split.getPlus(), node.getPlus(), in, out); 767 characterizeHyperplaneSubset(split.getMinus(), node.getMinus(), in, out); 768 } 769 } 770 } 771 } 772 773 /** {@inheritDoc} */ 774 @Override 775 public String toString() { 776 final StringBuilder sb = new StringBuilder(); 777 sb.append(this.getClass().getSimpleName()) 778 .append("[cut= ") 779 .append(getCut()) 780 .append(", location= ") 781 .append(getLocation()) 782 .append("]"); 783 784 return sb.toString(); 785 } 786 787 /** {@inheritDoc} */ 788 @Override 789 protected void nodeInvalidated() { 790 super.nodeInvalidated(); 791 792 // null any computed boundary value since it is no longer valid 793 cutBoundary = null; 794 } 795 796 /** Directly set the value of the location property for the node. No input validation 797 * is performed and the tree is not invalidated. 798 * @param locationValue the new location value for the node 799 * @see #setLocation(RegionLocation) 800 */ 801 protected void setLocationValue(final RegionLocation locationValue) { 802 this.location = locationValue; 803 } 804 } 805 806 /** Class used to compute the point on the region's boundary that is closest to a target point. 807 * @param <P> Point implementation type 808 * @param <N> BSP tree node implementation type 809 */ 810 protected static class BoundaryProjector<P extends Point<P>, N extends AbstractRegionNode<P, N>> 811 extends ClosestFirstVisitor<P, N> { 812 /** The projected point. */ 813 private P projected; 814 815 /** The current closest distance to the boundary found. */ 816 private double minDist = -1.0; 817 818 /** Simple constructor. 819 * @param point the point to project onto the region's boundary 820 */ 821 public BoundaryProjector(final P point) { 822 super(point); 823 } 824 825 /** {@inheritDoc} */ 826 @Override 827 public Result visit(final N node) { 828 final P point = getTarget(); 829 830 if (node.isInternal() && (minDist < 0.0 || isPossibleClosestCut(node.getCut(), point, minDist))) { 831 final RegionCutBoundary<P> boundary = node.getCutBoundary(); 832 final P boundaryPt = boundary.closest(point); 833 834 final double dist = boundaryPt.distance(point); 835 final int cmp = Double.compare(dist, minDist); 836 837 if (minDist < 0.0 || cmp < 0) { 838 projected = boundaryPt; 839 minDist = dist; 840 } else if (cmp == 0) { 841 // the two points are the _exact_ same distance from the reference point, so use 842 // a separate method to disambiguate them 843 projected = disambiguateClosestPoint(point, projected, boundaryPt); 844 } 845 } 846 847 return Result.CONTINUE; 848 } 849 850 /** Return true if the given node cut is a possible candidate for containing the closest region 851 * boundary point to the target. 852 * @param cut the node cut to test 853 * @param target the target point being projected 854 * @param currentMinDist the smallest distance found so far to a region boundary; this value is guaranteed 855 * to be non-negative 856 * @return true if the cut is a possible candidate for containing the closest region 857 * boundary point to the target 858 */ 859 protected boolean isPossibleClosestCut(final HyperplaneSubset<P> cut, final P target, 860 final double currentMinDist) { 861 return Math.abs(cut.getHyperplane().offset(target)) <= currentMinDist; 862 } 863 864 /** Method used to determine which of points {@code a} and {@code b} should be considered 865 * as the "closest" point to {@code target} when the points are exactly equidistant. 866 * @param target the target point 867 * @param a first point to consider 868 * @param b second point to consider 869 * @return which of {@code a} or {@code b} should be considered as the one closest to 870 * {@code target} 871 */ 872 protected P disambiguateClosestPoint(final P target, final P a, final P b) { 873 return a; 874 } 875 876 /** Get the projected point on the region's boundary, or null if no point could be found. 877 * @return the projected point on the region's boundary 878 */ 879 public P getProjected() { 880 return projected; 881 } 882 } 883 884 /** Class containing the primary size-related properties of a region. These properties 885 * are typically computed at the same time, so this class serves to encapsulate the result 886 * of the combined computation. 887 * @param <P> Point implementation type 888 */ 889 protected static class RegionSizeProperties<P extends Point<P>> { 890 /** The size of the region. */ 891 private final double size; 892 893 /** The centroid of the region. */ 894 private final P centroid; 895 896 /** Simple constructor. 897 * @param size the region size 898 * @param centroid the region centroid 899 */ 900 public RegionSizeProperties(final double size, final P centroid) { 901 this.size = size; 902 this.centroid = centroid; 903 } 904 905 /** Get the size of the region. 906 * @return the size of the region 907 */ 908 public double getSize() { 909 return size; 910 } 911 912 /** Get the centroid of the region. 913 * @return the centroid of the region 914 */ 915 public P getCentroid() { 916 return centroid; 917 } 918 } 919 920 /** Class containing the basic algorithm for merging region BSP trees. 921 * @param <P> Point implementation type 922 * @param <N> BSP tree node implementation type 923 */ 924 private abstract static class RegionMergeOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>> 925 extends AbstractBSPTreeMergeOperator<P, N> { 926 927 /** Merge two input trees, storing the output in the third. The output tree can be one of the 928 * input trees. The output tree is condensed before the method returns. 929 * @param inputTree1 first input tree 930 * @param inputTree2 second input tree 931 * @param outputTree the tree that will contain the result of the merge; may be one 932 * of the input trees 933 */ 934 public void apply(final AbstractRegionBSPTree<P, N> inputTree1, final AbstractRegionBSPTree<P, N> inputTree2, 935 final AbstractRegionBSPTree<P, N> outputTree) { 936 937 this.performMerge(inputTree1, inputTree2, outputTree); 938 939 outputTree.condense(); 940 } 941 } 942 943 /** Class for performing boolean union operations on region trees. 944 * @param <P> Point implementation type 945 * @param <N> BSP tree node implementation type 946 */ 947 private static final class UnionOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>> 948 extends RegionMergeOperator<P, N> { 949 950 /** {@inheritDoc} */ 951 @Override 952 protected N mergeLeaf(final N node1, final N node2) { 953 if (node1.isLeaf()) { 954 return node1.isInside() ? node1 : node2; 955 } 956 957 // call again with flipped arguments 958 return mergeLeaf(node2, node1); 959 } 960 } 961 962 /** Class for performing boolean intersection operations on region trees. 963 * @param <P> Point implementation type 964 * @param <N> BSP tree node implementation type 965 */ 966 private static final class IntersectionOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>> 967 extends RegionMergeOperator<P, N> { 968 969 /** {@inheritDoc} */ 970 @Override 971 protected N mergeLeaf(final N node1, final N node2) { 972 if (node1.isLeaf()) { 973 return node1.isInside() ? node2 : node1; 974 } 975 976 // call again with flipped arguments 977 return mergeLeaf(node2, node1); 978 } 979 } 980 981 /** Class for performing boolean difference operations on region trees. 982 * @param <P> Point implementation type 983 * @param <N> BSP tree node implementation type 984 */ 985 private static final class DifferenceOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>> 986 extends RegionMergeOperator<P, N> { 987 988 /** {@inheritDoc} */ 989 @Override 990 protected N mergeLeaf(final N node1, final N node2) { 991 // a region is included if it belongs in tree1 and is not in tree2 992 993 if (node1.isInside()) { 994 // this region is inside of tree1, so only include subregions that are 995 // not in tree2, ie include everything in node2's complement 996 final N output = outputSubtree(node2); 997 output.getTree().complementRecursive(output); 998 999 return output; 1000 } else if (node2.isInside()) { 1001 // this region is inside of tree2 and so cannot be in the result region 1002 final N output = outputNode(); 1003 output.setLocationValue(RegionLocation.OUTSIDE); 1004 1005 return output; 1006 } 1007 1008 // this region is not in tree2, so we can include everything in tree1 1009 return node1; 1010 } 1011 } 1012 1013 /** Class for performing boolean symmetric difference (xor) operations on region trees. 1014 * @param <P> Point implementation type 1015 * @param <N> BSP tree node implementation type 1016 */ 1017 private static final class XorOperator<P extends Point<P>, N extends AbstractRegionNode<P, N>> 1018 extends RegionMergeOperator<P, N> { 1019 1020 /** {@inheritDoc} */ 1021 @Override 1022 protected N mergeLeaf(final N node1, final N node2) { 1023 // a region is included if it belongs in tree1 and is not in tree2 OR 1024 // it belongs in tree2 and is not in tree1 1025 1026 if (node1.isLeaf()) { 1027 if (node1.isInside()) { 1028 // this region is inside node1, so only include subregions that are 1029 // not in node2, ie include everything in node2's complement 1030 final N output = outputSubtree(node2); 1031 output.getTree().complementRecursive(output); 1032 1033 return output; 1034 } else { 1035 // this region is not in node1, so only include subregions that 1036 // in node2 1037 return node2; 1038 } 1039 } 1040 1041 // the operation is symmetric, so perform the same operation but with the 1042 // nodes flipped 1043 return mergeLeaf(node2, node1); 1044 } 1045 } 1046 1047 /** Internal class used to perform tree condense operations. 1048 * @param <P> Point implementation type 1049 * @param <N> BSP tree node implementation type 1050 */ 1051 private static final class Condenser<P extends Point<P>, N extends AbstractRegionNode<P, N>> { 1052 /** Flag set to true if the tree was modified during the operation. */ 1053 private boolean modifiedTree; 1054 1055 /** Condense the nodes in the subtree rooted at the given node. Redundant child nodes are 1056 * removed. The tree is invalidated if the tree structure was modified. 1057 * @param node the root node of the subtree to condense 1058 * @return true if the tree was modified. 1059 */ 1060 boolean condense(final N node) { 1061 modifiedTree = false; 1062 1063 condenseRecursive(node); 1064 1065 return modifiedTree; 1066 } 1067 1068 /** Recursively condense nodes that have children with homogenous location attributes 1069 * (eg, both inside, both outside) into single nodes. 1070 * @param node the root of the subtree to condense 1071 * @return the location of the successfully condensed subtree or null if no condensing was 1072 * able to be performed 1073 */ 1074 private RegionLocation condenseRecursive(final N node) { 1075 if (node.isLeaf()) { 1076 return node.getLocation(); 1077 } 1078 1079 final RegionLocation minusLocation = condenseRecursive(node.getMinus()); 1080 final RegionLocation plusLocation = condenseRecursive(node.getPlus()); 1081 1082 if (minusLocation == plusLocation && minusLocation != null) { 1083 node.setLocationValue(minusLocation); 1084 node.clearCut(); 1085 1086 modifiedTree = true; 1087 1088 return minusLocation; 1089 } 1090 1091 return null; 1092 } 1093 } 1094 1095 /** Class that iterates over the boundary hyperplane convex subsets from a set of region nodes. 1096 * @param <P> Point implementation type 1097 * @param <C> Boundary hyperplane convex subset implementation type 1098 * @param <N> BSP tree node implementation type 1099 */ 1100 private static final class RegionBoundaryIterator< 1101 P extends Point<P>, 1102 C extends HyperplaneConvexSubset<P>, 1103 N extends AbstractRegionNode<P, N>> 1104 extends IteratorTransform<N, C> { 1105 1106 /** Function that converts from the convex subset type to the output type. */ 1107 private final Function<? super HyperplaneConvexSubset<P>, C> typeConverter; 1108 1109 /** Simple constructor. 1110 * @param inputIterator iterator that will provide all nodes in the tree 1111 * @param typeConverter function that converts from the convex subset type to the output type 1112 */ 1113 RegionBoundaryIterator(final Iterator<N> inputIterator, 1114 final Function<? super HyperplaneConvexSubset<P>, C> typeConverter) { 1115 super(inputIterator); 1116 1117 this.typeConverter = typeConverter; 1118 } 1119 1120 /** {@inheritDoc} */ 1121 @Override 1122 protected void acceptInput(final N input) { 1123 if (input.isInternal()) { 1124 final RegionCutBoundary<P> cutBoundary = input.getCutBoundary(); 1125 1126 for (final HyperplaneConvexSubset<P> boundary : cutBoundary.getOutsideFacing()) { 1127 addOutput(typeConverter.apply(boundary)); 1128 } 1129 1130 for (final HyperplaneConvexSubset<P> boundary : cutBoundary.getInsideFacing()) { 1131 final HyperplaneConvexSubset<P> reversed = boundary.reverse(); 1132 1133 addOutput(typeConverter.apply(reversed)); 1134 } 1135 } 1136 } 1137 } 1138}