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.Collection; 21 import java.util.Comparator; 22 import java.util.HashMap; 23 import java.util.Iterator; 24 import java.util.Map; 25 import java.util.TreeSet; 26 27 import org.apache.commons.math3.geometry.Point; 28 import org.apache.commons.math3.geometry.Space; 29 import org.apache.commons.math3.geometry.Vector; 30 31 /** Abstract class for all regions, independently of geometry type or dimension. 32 33 * @param <S> Type of the space. 34 * @param <T> Type of the sub-space. 35 36 * @since 3.0 37 */ 38 public abstract class AbstractRegion<S extends Space, T extends Space> implements Region<S> { 39 40 /** Inside/Outside BSP tree. */ 41 private BSPTree<S> tree; 42 43 /** Tolerance below which points are considered to belong to hyperplanes. */ 44 private final double tolerance; 45 46 /** Size of the instance. */ 47 private double size; 48 49 /** Barycenter. */ 50 private Point<S> barycenter; 51 52 /** Build a region representing the whole space. 53 * @param tolerance tolerance below which points are considered identical. 54 */ AbstractRegion(final double tolerance)55 protected AbstractRegion(final double tolerance) { 56 this.tree = new BSPTree<S>(Boolean.TRUE); 57 this.tolerance = tolerance; 58 } 59 60 /** Build a region from an inside/outside BSP tree. 61 * <p>The leaf nodes of the BSP tree <em>must</em> have a 62 * {@code Boolean} attribute representing the inside status of 63 * the corresponding cell (true for inside cells, false for outside 64 * cells). In order to avoid building too many small objects, it is 65 * recommended to use the predefined constants 66 * {@code Boolean.TRUE} and {@code Boolean.FALSE}. The 67 * tree also <em>must</em> have either null internal nodes or 68 * internal nodes representing the boundary as specified in the 69 * {@link #getTree getTree} method).</p> 70 * @param tree inside/outside BSP tree representing the region 71 * @param tolerance tolerance below which points are considered identical. 72 */ AbstractRegion(final BSPTree<S> tree, final double tolerance)73 protected AbstractRegion(final BSPTree<S> tree, final double tolerance) { 74 this.tree = tree; 75 this.tolerance = tolerance; 76 } 77 78 /** Build a Region from a Boundary REPresentation (B-rep). 79 * <p>The boundary is provided as a collection of {@link 80 * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the 81 * interior part of the region on its minus side and the exterior on 82 * its plus side.</p> 83 * <p>The boundary elements can be in any order, and can form 84 * several non-connected sets (like for example polygons with holes 85 * or a set of disjoints polyhedrons considered as a whole). In 86 * fact, the elements do not even need to be connected together 87 * (their topological connections are not used here). However, if the 88 * boundary does not really separate an inside open from an outside 89 * open (open having here its topological meaning), then subsequent 90 * calls to the {@link #checkPoint(Point) checkPoint} method will not be 91 * meaningful anymore.</p> 92 * <p>If the boundary is empty, the region will represent the whole 93 * space.</p> 94 * @param boundary collection of boundary elements, as a 95 * collection of {@link SubHyperplane SubHyperplane} objects 96 * @param tolerance tolerance below which points are considered identical. 97 */ AbstractRegion(final Collection<SubHyperplane<S>> boundary, final double tolerance)98 protected AbstractRegion(final Collection<SubHyperplane<S>> boundary, final double tolerance) { 99 100 this.tolerance = tolerance; 101 102 if (boundary.size() == 0) { 103 104 // the tree represents the whole space 105 tree = new BSPTree<S>(Boolean.TRUE); 106 107 } else { 108 109 // sort the boundary elements in decreasing size order 110 // (we don't want equal size elements to be removed, so 111 // we use a trick to fool the TreeSet) 112 final TreeSet<SubHyperplane<S>> ordered = new TreeSet<SubHyperplane<S>>(new Comparator<SubHyperplane<S>>() { 113 /** {@inheritDoc} */ 114 public int compare(final SubHyperplane<S> o1, final SubHyperplane<S> o2) { 115 final double size1 = o1.getSize(); 116 final double size2 = o2.getSize(); 117 return (size2 < size1) ? -1 : ((o1 == o2) ? 0 : +1); 118 } 119 }); 120 ordered.addAll(boundary); 121 122 // build the tree top-down 123 tree = new BSPTree<S>(); 124 insertCuts(tree, ordered); 125 126 // set up the inside/outside flags 127 tree.visit(new BSPTreeVisitor<S>() { 128 129 /** {@inheritDoc} */ 130 public Order visitOrder(final BSPTree<S> node) { 131 return Order.PLUS_SUB_MINUS; 132 } 133 134 /** {@inheritDoc} */ 135 public void visitInternalNode(final BSPTree<S> node) { 136 } 137 138 /** {@inheritDoc} */ 139 public void visitLeafNode(final BSPTree<S> node) { 140 if (node.getParent() == null || node == node.getParent().getMinus()) { 141 node.setAttribute(Boolean.TRUE); 142 } else { 143 node.setAttribute(Boolean.FALSE); 144 } 145 } 146 }); 147 148 } 149 150 } 151 152 /** Build a convex region from an array of bounding hyperplanes. 153 * @param hyperplanes array of bounding hyperplanes (if null, an 154 * empty region will be built) 155 * @param tolerance tolerance below which points are considered identical. 156 */ AbstractRegion(final Hyperplane<S>[] hyperplanes, final double tolerance)157 public AbstractRegion(final Hyperplane<S>[] hyperplanes, final double tolerance) { 158 this.tolerance = tolerance; 159 if ((hyperplanes == null) || (hyperplanes.length == 0)) { 160 tree = new BSPTree<S>(Boolean.FALSE); 161 } else { 162 163 // use the first hyperplane to build the right class 164 tree = hyperplanes[0].wholeSpace().getTree(false); 165 166 // chop off parts of the space 167 BSPTree<S> node = tree; 168 node.setAttribute(Boolean.TRUE); 169 for (final Hyperplane<S> hyperplane : hyperplanes) { 170 if (node.insertCut(hyperplane)) { 171 node.setAttribute(null); 172 node.getPlus().setAttribute(Boolean.FALSE); 173 node = node.getMinus(); 174 node.setAttribute(Boolean.TRUE); 175 } 176 } 177 178 } 179 180 } 181 182 /** {@inheritDoc} */ buildNew(BSPTree<S> newTree)183 public abstract AbstractRegion<S, T> buildNew(BSPTree<S> newTree); 184 185 /** Get the tolerance below which points are considered to belong to hyperplanes. 186 * @return tolerance below which points are considered to belong to hyperplanes 187 */ getTolerance()188 public double getTolerance() { 189 return tolerance; 190 } 191 192 /** Recursively build a tree by inserting cut sub-hyperplanes. 193 * @param node current tree node (it is a leaf node at the beginning 194 * of the call) 195 * @param boundary collection of edges belonging to the cell defined 196 * by the node 197 */ insertCuts(final BSPTree<S> node, final Collection<SubHyperplane<S>> boundary)198 private void insertCuts(final BSPTree<S> node, final Collection<SubHyperplane<S>> boundary) { 199 200 final Iterator<SubHyperplane<S>> iterator = boundary.iterator(); 201 202 // build the current level 203 Hyperplane<S> inserted = null; 204 while ((inserted == null) && iterator.hasNext()) { 205 inserted = iterator.next().getHyperplane(); 206 if (!node.insertCut(inserted.copySelf())) { 207 inserted = null; 208 } 209 } 210 211 if (!iterator.hasNext()) { 212 return; 213 } 214 215 // distribute the remaining edges in the two sub-trees 216 final ArrayList<SubHyperplane<S>> plusList = new ArrayList<SubHyperplane<S>>(); 217 final ArrayList<SubHyperplane<S>> minusList = new ArrayList<SubHyperplane<S>>(); 218 while (iterator.hasNext()) { 219 final SubHyperplane<S> other = iterator.next(); 220 final SubHyperplane.SplitSubHyperplane<S> split = other.split(inserted); 221 switch (split.getSide()) { 222 case PLUS: 223 plusList.add(other); 224 break; 225 case MINUS: 226 minusList.add(other); 227 break; 228 case BOTH: 229 plusList.add(split.getPlus()); 230 minusList.add(split.getMinus()); 231 break; 232 default: 233 // ignore the sub-hyperplanes belonging to the cut hyperplane 234 } 235 } 236 237 // recurse through lower levels 238 insertCuts(node.getPlus(), plusList); 239 insertCuts(node.getMinus(), minusList); 240 241 } 242 243 /** {@inheritDoc} */ copySelf()244 public AbstractRegion<S, T> copySelf() { 245 return buildNew(tree.copySelf()); 246 } 247 248 /** {@inheritDoc} */ isEmpty()249 public boolean isEmpty() { 250 return isEmpty(tree); 251 } 252 253 /** {@inheritDoc} */ isEmpty(final BSPTree<S> node)254 public boolean isEmpty(final BSPTree<S> node) { 255 256 // we use a recursive function rather than the BSPTreeVisitor 257 // interface because we can stop visiting the tree as soon as we 258 // have found an inside cell 259 260 if (node.getCut() == null) { 261 // if we find an inside node, the region is not empty 262 return !((Boolean) node.getAttribute()); 263 } 264 265 // check both sides of the sub-tree 266 return isEmpty(node.getMinus()) && isEmpty(node.getPlus()); 267 268 } 269 270 /** {@inheritDoc} */ isFull()271 public boolean isFull() { 272 return isFull(tree); 273 } 274 275 /** {@inheritDoc} */ isFull(final BSPTree<S> node)276 public boolean isFull(final BSPTree<S> node) { 277 278 // we use a recursive function rather than the BSPTreeVisitor 279 // interface because we can stop visiting the tree as soon as we 280 // have found an outside cell 281 282 if (node.getCut() == null) { 283 // if we find an outside node, the region does not cover full space 284 return (Boolean) node.getAttribute(); 285 } 286 287 // check both sides of the sub-tree 288 return isFull(node.getMinus()) && isFull(node.getPlus()); 289 290 } 291 292 /** {@inheritDoc} */ contains(final Region<S> region)293 public boolean contains(final Region<S> region) { 294 return new RegionFactory<S>().difference(region, this).isEmpty(); 295 } 296 297 /** {@inheritDoc} 298 * @since 3.3 299 */ projectToBoundary(final Point<S> point)300 public BoundaryProjection<S> projectToBoundary(final Point<S> point) { 301 final BoundaryProjector<S, T> projector = new BoundaryProjector<S, T>(point); 302 getTree(true).visit(projector); 303 return projector.getProjection(); 304 } 305 306 /** Check a point with respect to the region. 307 * @param point point to check 308 * @return a code representing the point status: either {@link 309 * Region.Location#INSIDE}, {@link Region.Location#OUTSIDE} or 310 * {@link Region.Location#BOUNDARY} 311 */ checkPoint(final Vector<S> point)312 public Location checkPoint(final Vector<S> point) { 313 return checkPoint((Point<S>) point); 314 } 315 316 /** {@inheritDoc} */ checkPoint(final Point<S> point)317 public Location checkPoint(final Point<S> point) { 318 return checkPoint(tree, point); 319 } 320 321 /** Check a point with respect to the region starting at a given node. 322 * @param node root node of the region 323 * @param point point to check 324 * @return a code representing the point status: either {@link 325 * Region.Location#INSIDE INSIDE}, {@link Region.Location#OUTSIDE 326 * OUTSIDE} or {@link Region.Location#BOUNDARY BOUNDARY} 327 */ checkPoint(final BSPTree<S> node, final Vector<S> point)328 protected Location checkPoint(final BSPTree<S> node, final Vector<S> point) { 329 return checkPoint(node, (Point<S>) point); 330 } 331 332 /** Check a point with respect to the region starting at a given node. 333 * @param node root node of the region 334 * @param point point to check 335 * @return a code representing the point status: either {@link 336 * Region.Location#INSIDE INSIDE}, {@link Region.Location#OUTSIDE 337 * OUTSIDE} or {@link Region.Location#BOUNDARY BOUNDARY} 338 */ checkPoint(final BSPTree<S> node, final Point<S> point)339 protected Location checkPoint(final BSPTree<S> node, final Point<S> point) { 340 final BSPTree<S> cell = node.getCell(point, tolerance); 341 if (cell.getCut() == null) { 342 // the point is in the interior of a cell, just check the attribute 343 return ((Boolean) cell.getAttribute()) ? Location.INSIDE : Location.OUTSIDE; 344 } 345 346 // the point is on a cut-sub-hyperplane, is it on a boundary ? 347 final Location minusCode = checkPoint(cell.getMinus(), point); 348 final Location plusCode = checkPoint(cell.getPlus(), point); 349 return (minusCode == plusCode) ? minusCode : Location.BOUNDARY; 350 351 } 352 353 /** {@inheritDoc} */ getTree(final boolean includeBoundaryAttributes)354 public BSPTree<S> getTree(final boolean includeBoundaryAttributes) { 355 if (includeBoundaryAttributes && (tree.getCut() != null) && (tree.getAttribute() == null)) { 356 // compute the boundary attributes 357 tree.visit(new BoundaryBuilder<S>()); 358 } 359 return tree; 360 } 361 362 /** {@inheritDoc} */ getBoundarySize()363 public double getBoundarySize() { 364 final BoundarySizeVisitor<S> visitor = new BoundarySizeVisitor<S>(); 365 getTree(true).visit(visitor); 366 return visitor.getSize(); 367 } 368 369 /** {@inheritDoc} */ getSize()370 public double getSize() { 371 if (barycenter == null) { 372 computeGeometricalProperties(); 373 } 374 return size; 375 } 376 377 /** Set the size of the instance. 378 * @param size size of the instance 379 */ setSize(final double size)380 protected void setSize(final double size) { 381 this.size = size; 382 } 383 384 /** {@inheritDoc} */ getBarycenter()385 public Point<S> getBarycenter() { 386 if (barycenter == null) { 387 computeGeometricalProperties(); 388 } 389 return barycenter; 390 } 391 392 /** Set the barycenter of the instance. 393 * @param barycenter barycenter of the instance 394 */ setBarycenter(final Vector<S> barycenter)395 protected void setBarycenter(final Vector<S> barycenter) { 396 setBarycenter((Point<S>) barycenter); 397 } 398 399 /** Set the barycenter of the instance. 400 * @param barycenter barycenter of the instance 401 */ setBarycenter(final Point<S> barycenter)402 protected void setBarycenter(final Point<S> barycenter) { 403 this.barycenter = barycenter; 404 } 405 406 /** Compute some geometrical properties. 407 * <p>The properties to compute are the barycenter and the size.</p> 408 */ computeGeometricalProperties()409 protected abstract void computeGeometricalProperties(); 410 411 /** {@inheritDoc} */ 412 @Deprecated side(final Hyperplane<S> hyperplane)413 public Side side(final Hyperplane<S> hyperplane) { 414 final InsideFinder<S> finder = new InsideFinder<S>(this); 415 finder.recurseSides(tree, hyperplane.wholeHyperplane()); 416 return finder.plusFound() ? 417 (finder.minusFound() ? Side.BOTH : Side.PLUS) : 418 (finder.minusFound() ? Side.MINUS : Side.HYPER); 419 } 420 421 /** {@inheritDoc} */ intersection(final SubHyperplane<S> sub)422 public SubHyperplane<S> intersection(final SubHyperplane<S> sub) { 423 return recurseIntersection(tree, sub); 424 } 425 426 /** Recursively compute the parts of a sub-hyperplane that are 427 * contained in the region. 428 * @param node current BSP tree node 429 * @param sub sub-hyperplane traversing the region 430 * @return filtered sub-hyperplane 431 */ recurseIntersection(final BSPTree<S> node, final SubHyperplane<S> sub)432 private SubHyperplane<S> recurseIntersection(final BSPTree<S> node, final SubHyperplane<S> sub) { 433 434 if (node.getCut() == null) { 435 return (Boolean) node.getAttribute() ? sub.copySelf() : null; 436 } 437 438 final Hyperplane<S> hyperplane = node.getCut().getHyperplane(); 439 final SubHyperplane.SplitSubHyperplane<S> split = sub.split(hyperplane); 440 if (split.getPlus() != null) { 441 if (split.getMinus() != null) { 442 // both sides 443 final SubHyperplane<S> plus = recurseIntersection(node.getPlus(), split.getPlus()); 444 final SubHyperplane<S> minus = recurseIntersection(node.getMinus(), split.getMinus()); 445 if (plus == null) { 446 return minus; 447 } else if (minus == null) { 448 return plus; 449 } else { 450 return plus.reunite(minus); 451 } 452 } else { 453 // only on plus side 454 return recurseIntersection(node.getPlus(), sub); 455 } 456 } else if (split.getMinus() != null) { 457 // only on minus side 458 return recurseIntersection(node.getMinus(), sub); 459 } else { 460 // on hyperplane 461 return recurseIntersection(node.getPlus(), 462 recurseIntersection(node.getMinus(), sub)); 463 } 464 465 } 466 467 /** Transform a region. 468 * <p>Applying a transform to a region consist in applying the 469 * transform to all the hyperplanes of the underlying BSP tree and 470 * of the boundary (and also to the sub-hyperplanes embedded in 471 * these hyperplanes) and to the barycenter. The instance is not 472 * modified, a new instance is built.</p> 473 * @param transform transform to apply 474 * @return a new region, resulting from the application of the 475 * transform to the instance 476 */ applyTransform(final Transform<S, T> transform)477 public AbstractRegion<S, T> applyTransform(final Transform<S, T> transform) { 478 479 // transform the tree, except for boundary attribute splitters 480 final Map<BSPTree<S>, BSPTree<S>> map = new HashMap<BSPTree<S>, BSPTree<S>>(); 481 final BSPTree<S> transformedTree = recurseTransform(getTree(false), transform, map); 482 483 // set up the boundary attributes splitters 484 for (final Map.Entry<BSPTree<S>, BSPTree<S>> entry : map.entrySet()) { 485 if (entry.getKey().getCut() != null) { 486 @SuppressWarnings("unchecked") 487 BoundaryAttribute<S> original = (BoundaryAttribute<S>) entry.getKey().getAttribute(); 488 if (original != null) { 489 @SuppressWarnings("unchecked") 490 BoundaryAttribute<S> transformed = (BoundaryAttribute<S>) entry.getValue().getAttribute(); 491 for (final BSPTree<S> splitter : original.getSplitters()) { 492 transformed.getSplitters().add(map.get(splitter)); 493 } 494 } 495 } 496 } 497 498 return buildNew(transformedTree); 499 500 } 501 502 /** Recursively transform an inside/outside BSP-tree. 503 * @param node current BSP tree node 504 * @param transform transform to apply 505 * @param map transformed nodes map 506 * @return a new tree 507 */ 508 @SuppressWarnings("unchecked") recurseTransform(final BSPTree<S> node, final Transform<S, T> transform, final Map<BSPTree<S>, BSPTree<S>> map)509 private BSPTree<S> recurseTransform(final BSPTree<S> node, final Transform<S, T> transform, 510 final Map<BSPTree<S>, BSPTree<S>> map) { 511 512 final BSPTree<S> transformedNode; 513 if (node.getCut() == null) { 514 transformedNode = new BSPTree<S>(node.getAttribute()); 515 } else { 516 517 final SubHyperplane<S> sub = node.getCut(); 518 final SubHyperplane<S> tSub = ((AbstractSubHyperplane<S, T>) sub).applyTransform(transform); 519 BoundaryAttribute<S> attribute = (BoundaryAttribute<S>) node.getAttribute(); 520 if (attribute != null) { 521 final SubHyperplane<S> tPO = (attribute.getPlusOutside() == null) ? 522 null : ((AbstractSubHyperplane<S, T>) attribute.getPlusOutside()).applyTransform(transform); 523 final SubHyperplane<S> tPI = (attribute.getPlusInside() == null) ? 524 null : ((AbstractSubHyperplane<S, T>) attribute.getPlusInside()).applyTransform(transform); 525 // we start with an empty list of splitters, it will be filled in out of recursion 526 attribute = new BoundaryAttribute<S>(tPO, tPI, new NodesSet<S>()); 527 } 528 529 transformedNode = new BSPTree<S>(tSub, 530 recurseTransform(node.getPlus(), transform, map), 531 recurseTransform(node.getMinus(), transform, map), 532 attribute); 533 } 534 535 map.put(node, transformedNode); 536 return transformedNode; 537 538 } 539 540 } 541