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.spherical.oned; 18 19 import java.util.ArrayList; 20 import java.util.Collection; 21 import java.util.Iterator; 22 import java.util.List; 23 import java.util.NoSuchElementException; 24 25 import org.apache.commons.math3.exception.MathIllegalArgumentException; 26 import org.apache.commons.math3.exception.MathInternalError; 27 import org.apache.commons.math3.exception.NumberIsTooLargeException; 28 import org.apache.commons.math3.exception.util.LocalizedFormats; 29 import org.apache.commons.math3.geometry.Point; 30 import org.apache.commons.math3.geometry.partitioning.AbstractRegion; 31 import org.apache.commons.math3.geometry.partitioning.BSPTree; 32 import org.apache.commons.math3.geometry.partitioning.BoundaryProjection; 33 import org.apache.commons.math3.geometry.partitioning.Side; 34 import org.apache.commons.math3.geometry.partitioning.SubHyperplane; 35 import org.apache.commons.math3.util.FastMath; 36 import org.apache.commons.math3.util.MathUtils; 37 import org.apache.commons.math3.util.Precision; 38 39 /** This class represents a region of a circle: a set of arcs. 40 * <p> 41 * Note that due to the wrapping around \(2 \pi\), barycenter is 42 * ill-defined here. It was defined only in order to fulfill 43 * the requirements of the {@link 44 * org.apache.commons.math3.geometry.partitioning.Region Region} 45 * interface, but its use is discouraged. 46 * </p> 47 * @since 3.3 48 */ 49 public class ArcsSet extends AbstractRegion<Sphere1D, Sphere1D> implements Iterable<double[]> { 50 51 /** Build an arcs set representing the whole circle. 52 * @param tolerance tolerance below which close sub-arcs are merged together 53 */ ArcsSet(final double tolerance)54 public ArcsSet(final double tolerance) { 55 super(tolerance); 56 } 57 58 /** Build an arcs set corresponding to a single arc. 59 * <p> 60 * If either {@code lower} is equals to {@code upper} or 61 * the interval exceeds \( 2 \pi \), the arc is considered 62 * to be the full circle and its initial defining boundaries 63 * will be forgotten. {@code lower} is not allowed to be greater 64 * than {@code upper} (an exception is thrown in this case). 65 * </p> 66 * @param lower lower bound of the arc 67 * @param upper upper bound of the arc 68 * @param tolerance tolerance below which close sub-arcs are merged together 69 * @exception NumberIsTooLargeException if lower is greater than upper 70 */ ArcsSet(final double lower, final double upper, final double tolerance)71 public ArcsSet(final double lower, final double upper, final double tolerance) 72 throws NumberIsTooLargeException { 73 super(buildTree(lower, upper, tolerance), tolerance); 74 } 75 76 /** Build an arcs set from an inside/outside BSP tree. 77 * <p>The leaf nodes of the BSP tree <em>must</em> have a 78 * {@code Boolean} attribute representing the inside status of 79 * the corresponding cell (true for inside cells, false for outside 80 * cells). In order to avoid building too many small objects, it is 81 * recommended to use the predefined constants 82 * {@code Boolean.TRUE} and {@code Boolean.FALSE}</p> 83 * @param tree inside/outside BSP tree representing the arcs set 84 * @param tolerance tolerance below which close sub-arcs are merged together 85 * @exception InconsistentStateAt2PiWrapping if the tree leaf nodes are not 86 * consistent across the \( 0, 2 \pi \) crossing 87 */ ArcsSet(final BSPTree<Sphere1D> tree, final double tolerance)88 public ArcsSet(final BSPTree<Sphere1D> tree, final double tolerance) 89 throws InconsistentStateAt2PiWrapping { 90 super(tree, tolerance); 91 check2PiConsistency(); 92 } 93 94 /** Build an arcs set from a Boundary REPresentation (B-rep). 95 * <p>The boundary is provided as a collection of {@link 96 * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the 97 * interior part of the region on its minus side and the exterior on 98 * its plus side.</p> 99 * <p>The boundary elements can be in any order, and can form 100 * several non-connected sets (like for example polygons with holes 101 * or a set of disjoints polyhedrons considered as a whole). In 102 * fact, the elements do not even need to be connected together 103 * (their topological connections are not used here). However, if the 104 * boundary does not really separate an inside open from an outside 105 * open (open having here its topological meaning), then subsequent 106 * calls to the {@link 107 * org.apache.commons.math3.geometry.partitioning.Region#checkPoint(org.apache.commons.math3.geometry.Point) 108 * checkPoint} method will not be meaningful anymore.</p> 109 * <p>If the boundary is empty, the region will represent the whole 110 * space.</p> 111 * @param boundary collection of boundary elements 112 * @param tolerance tolerance below which close sub-arcs are merged together 113 * @exception InconsistentStateAt2PiWrapping if the tree leaf nodes are not 114 * consistent across the \( 0, 2 \pi \) crossing 115 */ ArcsSet(final Collection<SubHyperplane<Sphere1D>> boundary, final double tolerance)116 public ArcsSet(final Collection<SubHyperplane<Sphere1D>> boundary, final double tolerance) 117 throws InconsistentStateAt2PiWrapping { 118 super(boundary, tolerance); 119 check2PiConsistency(); 120 } 121 122 /** Build an inside/outside tree representing a single arc. 123 * @param lower lower angular bound of the arc 124 * @param upper upper angular bound of the arc 125 * @param tolerance tolerance below which close sub-arcs are merged together 126 * @return the built tree 127 * @exception NumberIsTooLargeException if lower is greater than upper 128 */ buildTree(final double lower, final double upper, final double tolerance)129 private static BSPTree<Sphere1D> buildTree(final double lower, final double upper, 130 final double tolerance) 131 throws NumberIsTooLargeException { 132 133 if (Precision.equals(lower, upper, 0) || (upper - lower) >= MathUtils.TWO_PI) { 134 // the tree must cover the whole circle 135 return new BSPTree<Sphere1D>(Boolean.TRUE); 136 } else if (lower > upper) { 137 throw new NumberIsTooLargeException(LocalizedFormats.ENDPOINTS_NOT_AN_INTERVAL, 138 lower, upper, true); 139 } 140 141 // this is a regular arc, covering only part of the circle 142 final double normalizedLower = MathUtils.normalizeAngle(lower, FastMath.PI); 143 final double normalizedUpper = normalizedLower + (upper - lower); 144 final SubHyperplane<Sphere1D> lowerCut = 145 new LimitAngle(new S1Point(normalizedLower), false, tolerance).wholeHyperplane(); 146 147 if (normalizedUpper <= MathUtils.TWO_PI) { 148 // simple arc starting after 0 and ending before 2 \pi 149 final SubHyperplane<Sphere1D> upperCut = 150 new LimitAngle(new S1Point(normalizedUpper), true, tolerance).wholeHyperplane(); 151 return new BSPTree<Sphere1D>(lowerCut, 152 new BSPTree<Sphere1D>(Boolean.FALSE), 153 new BSPTree<Sphere1D>(upperCut, 154 new BSPTree<Sphere1D>(Boolean.FALSE), 155 new BSPTree<Sphere1D>(Boolean.TRUE), 156 null), 157 null); 158 } else { 159 // arc wrapping around 2 \pi 160 final SubHyperplane<Sphere1D> upperCut = 161 new LimitAngle(new S1Point(normalizedUpper - MathUtils.TWO_PI), true, tolerance).wholeHyperplane(); 162 return new BSPTree<Sphere1D>(lowerCut, 163 new BSPTree<Sphere1D>(upperCut, 164 new BSPTree<Sphere1D>(Boolean.FALSE), 165 new BSPTree<Sphere1D>(Boolean.TRUE), 166 null), 167 new BSPTree<Sphere1D>(Boolean.TRUE), 168 null); 169 } 170 171 } 172 173 /** Check consistency. 174 * @exception InconsistentStateAt2PiWrapping if the tree leaf nodes are not 175 * consistent across the \( 0, 2 \pi \) crossing 176 */ check2PiConsistency()177 private void check2PiConsistency() throws InconsistentStateAt2PiWrapping { 178 179 // start search at the tree root 180 BSPTree<Sphere1D> root = getTree(false); 181 if (root.getCut() == null) { 182 return; 183 } 184 185 // find the inside/outside state before the smallest internal node 186 final Boolean stateBefore = (Boolean) getFirstLeaf(root).getAttribute(); 187 188 // find the inside/outside state after the largest internal node 189 final Boolean stateAfter = (Boolean) getLastLeaf(root).getAttribute(); 190 191 if (stateBefore ^ stateAfter) { 192 throw new InconsistentStateAt2PiWrapping(); 193 } 194 195 } 196 197 /** Get the first leaf node of a tree. 198 * @param root tree root 199 * @return first leaf node (i.e. node corresponding to the region just after 0.0 radians) 200 */ getFirstLeaf(final BSPTree<Sphere1D> root)201 private BSPTree<Sphere1D> getFirstLeaf(final BSPTree<Sphere1D> root) { 202 203 if (root.getCut() == null) { 204 return root; 205 } 206 207 // find the smallest internal node 208 BSPTree<Sphere1D> smallest = null; 209 for (BSPTree<Sphere1D> n = root; n != null; n = previousInternalNode(n)) { 210 smallest = n; 211 } 212 213 return leafBefore(smallest); 214 215 } 216 217 /** Get the last leaf node of a tree. 218 * @param root tree root 219 * @return last leaf node (i.e. node corresponding to the region just before \( 2 \pi \) radians) 220 */ getLastLeaf(final BSPTree<Sphere1D> root)221 private BSPTree<Sphere1D> getLastLeaf(final BSPTree<Sphere1D> root) { 222 223 if (root.getCut() == null) { 224 return root; 225 } 226 227 // find the largest internal node 228 BSPTree<Sphere1D> largest = null; 229 for (BSPTree<Sphere1D> n = root; n != null; n = nextInternalNode(n)) { 230 largest = n; 231 } 232 233 return leafAfter(largest); 234 235 } 236 237 /** Get the node corresponding to the first arc start. 238 * @return smallest internal node (i.e. first after 0.0 radians, in trigonometric direction), 239 * or null if there are no internal nodes (i.e. the set is either empty or covers the full circle) 240 */ getFirstArcStart()241 private BSPTree<Sphere1D> getFirstArcStart() { 242 243 // start search at the tree root 244 BSPTree<Sphere1D> node = getTree(false); 245 if (node.getCut() == null) { 246 return null; 247 } 248 249 // walk tree until we find the smallest internal node 250 node = getFirstLeaf(node).getParent(); 251 252 // walk tree until we find an arc start 253 while (node != null && !isArcStart(node)) { 254 node = nextInternalNode(node); 255 } 256 257 return node; 258 259 } 260 261 /** Check if an internal node corresponds to the start angle of an arc. 262 * @param node internal node to check 263 * @return true if the node corresponds to the start angle of an arc 264 */ isArcStart(final BSPTree<Sphere1D> node)265 private boolean isArcStart(final BSPTree<Sphere1D> node) { 266 267 if ((Boolean) leafBefore(node).getAttribute()) { 268 // it has an inside cell before it, it may end an arc but not start it 269 return false; 270 } 271 272 if (!(Boolean) leafAfter(node).getAttribute()) { 273 // it has an outside cell after it, it is a dummy cut away from real arcs 274 return false; 275 } 276 277 // the cell has an outside before and an inside after it 278 // it is the start of an arc 279 return true; 280 281 } 282 283 /** Check if an internal node corresponds to the end angle of an arc. 284 * @param node internal node to check 285 * @return true if the node corresponds to the end angle of an arc 286 */ isArcEnd(final BSPTree<Sphere1D> node)287 private boolean isArcEnd(final BSPTree<Sphere1D> node) { 288 289 if (!(Boolean) leafBefore(node).getAttribute()) { 290 // it has an outside cell before it, it may start an arc but not end it 291 return false; 292 } 293 294 if ((Boolean) leafAfter(node).getAttribute()) { 295 // it has an inside cell after it, it is a dummy cut in the middle of an arc 296 return false; 297 } 298 299 // the cell has an inside before and an outside after it 300 // it is the end of an arc 301 return true; 302 303 } 304 305 /** Get the next internal node. 306 * @param node current internal node 307 * @return next internal node in trigonometric order, or null 308 * if this is the last internal node 309 */ nextInternalNode(BSPTree<Sphere1D> node)310 private BSPTree<Sphere1D> nextInternalNode(BSPTree<Sphere1D> node) { 311 312 if (childAfter(node).getCut() != null) { 313 // the next node is in the sub-tree 314 return leafAfter(node).getParent(); 315 } 316 317 // there is nothing left deeper in the tree, we backtrack 318 while (isAfterParent(node)) { 319 node = node.getParent(); 320 } 321 return node.getParent(); 322 323 } 324 325 /** Get the previous internal node. 326 * @param node current internal node 327 * @return previous internal node in trigonometric order, or null 328 * if this is the first internal node 329 */ previousInternalNode(BSPTree<Sphere1D> node)330 private BSPTree<Sphere1D> previousInternalNode(BSPTree<Sphere1D> node) { 331 332 if (childBefore(node).getCut() != null) { 333 // the next node is in the sub-tree 334 return leafBefore(node).getParent(); 335 } 336 337 // there is nothing left deeper in the tree, we backtrack 338 while (isBeforeParent(node)) { 339 node = node.getParent(); 340 } 341 return node.getParent(); 342 343 } 344 345 /** Find the leaf node just before an internal node. 346 * @param node internal node at which the sub-tree starts 347 * @return leaf node just before the internal node 348 */ leafBefore(BSPTree<Sphere1D> node)349 private BSPTree<Sphere1D> leafBefore(BSPTree<Sphere1D> node) { 350 351 node = childBefore(node); 352 while (node.getCut() != null) { 353 node = childAfter(node); 354 } 355 356 return node; 357 358 } 359 360 /** Find the leaf node just after an internal node. 361 * @param node internal node at which the sub-tree starts 362 * @return leaf node just after the internal node 363 */ leafAfter(BSPTree<Sphere1D> node)364 private BSPTree<Sphere1D> leafAfter(BSPTree<Sphere1D> node) { 365 366 node = childAfter(node); 367 while (node.getCut() != null) { 368 node = childBefore(node); 369 } 370 371 return node; 372 373 } 374 375 /** Check if a node is the child before its parent in trigonometric order. 376 * @param node child node considered 377 * @return true is the node has a parent end is before it in trigonometric order 378 */ isBeforeParent(final BSPTree<Sphere1D> node)379 private boolean isBeforeParent(final BSPTree<Sphere1D> node) { 380 final BSPTree<Sphere1D> parent = node.getParent(); 381 if (parent == null) { 382 return false; 383 } else { 384 return node == childBefore(parent); 385 } 386 } 387 388 /** Check if a node is the child after its parent in trigonometric order. 389 * @param node child node considered 390 * @return true is the node has a parent end is after it in trigonometric order 391 */ isAfterParent(final BSPTree<Sphere1D> node)392 private boolean isAfterParent(final BSPTree<Sphere1D> node) { 393 final BSPTree<Sphere1D> parent = node.getParent(); 394 if (parent == null) { 395 return false; 396 } else { 397 return node == childAfter(parent); 398 } 399 } 400 401 /** Find the child node just before an internal node. 402 * @param node internal node at which the sub-tree starts 403 * @return child node just before the internal node 404 */ childBefore(BSPTree<Sphere1D> node)405 private BSPTree<Sphere1D> childBefore(BSPTree<Sphere1D> node) { 406 if (isDirect(node)) { 407 // smaller angles are on minus side, larger angles are on plus side 408 return node.getMinus(); 409 } else { 410 // smaller angles are on plus side, larger angles are on minus side 411 return node.getPlus(); 412 } 413 } 414 415 /** Find the child node just after an internal node. 416 * @param node internal node at which the sub-tree starts 417 * @return child node just after the internal node 418 */ childAfter(BSPTree<Sphere1D> node)419 private BSPTree<Sphere1D> childAfter(BSPTree<Sphere1D> node) { 420 if (isDirect(node)) { 421 // smaller angles are on minus side, larger angles are on plus side 422 return node.getPlus(); 423 } else { 424 // smaller angles are on plus side, larger angles are on minus side 425 return node.getMinus(); 426 } 427 } 428 429 /** Check if an internal node has a direct limit angle. 430 * @param node internal node to check 431 * @return true if the limit angle is direct 432 */ isDirect(final BSPTree<Sphere1D> node)433 private boolean isDirect(final BSPTree<Sphere1D> node) { 434 return ((LimitAngle) node.getCut().getHyperplane()).isDirect(); 435 } 436 437 /** Get the limit angle of an internal node. 438 * @param node internal node to check 439 * @return limit angle 440 */ getAngle(final BSPTree<Sphere1D> node)441 private double getAngle(final BSPTree<Sphere1D> node) { 442 return ((LimitAngle) node.getCut().getHyperplane()).getLocation().getAlpha(); 443 } 444 445 /** {@inheritDoc} */ 446 @Override buildNew(final BSPTree<Sphere1D> tree)447 public ArcsSet buildNew(final BSPTree<Sphere1D> tree) { 448 return new ArcsSet(tree, getTolerance()); 449 } 450 451 /** {@inheritDoc} */ 452 @Override computeGeometricalProperties()453 protected void computeGeometricalProperties() { 454 if (getTree(false).getCut() == null) { 455 setBarycenter(S1Point.NaN); 456 setSize(((Boolean) getTree(false).getAttribute()) ? MathUtils.TWO_PI : 0); 457 } else { 458 double size = 0.0; 459 double sum = 0.0; 460 for (final double[] a : this) { 461 final double length = a[1] - a[0]; 462 size += length; 463 sum += length * (a[0] + a[1]); 464 } 465 setSize(size); 466 if (Precision.equals(size, MathUtils.TWO_PI, 0)) { 467 setBarycenter(S1Point.NaN); 468 } else if (size >= Precision.SAFE_MIN) { 469 setBarycenter(new S1Point(sum / (2 * size))); 470 } else { 471 final LimitAngle limit = (LimitAngle) getTree(false).getCut().getHyperplane(); 472 setBarycenter(limit.getLocation()); 473 } 474 } 475 } 476 477 /** {@inheritDoc} 478 * @since 3.3 479 */ 480 @Override projectToBoundary(final Point<Sphere1D> point)481 public BoundaryProjection<Sphere1D> projectToBoundary(final Point<Sphere1D> point) { 482 483 // get position of test point 484 final double alpha = ((S1Point) point).getAlpha(); 485 486 boolean wrapFirst = false; 487 double first = Double.NaN; 488 double previous = Double.NaN; 489 for (final double[] a : this) { 490 491 if (Double.isNaN(first)) { 492 // remember the first angle in case we need it later 493 first = a[0]; 494 } 495 496 if (!wrapFirst) { 497 if (alpha < a[0]) { 498 // the test point lies between the previous and the current arcs 499 // offset will be positive 500 if (Double.isNaN(previous)) { 501 // we need to wrap around the circle 502 wrapFirst = true; 503 } else { 504 final double previousOffset = alpha - previous; 505 final double currentOffset = a[0] - alpha; 506 if (previousOffset < currentOffset) { 507 return new BoundaryProjection<Sphere1D>(point, new S1Point(previous), previousOffset); 508 } else { 509 return new BoundaryProjection<Sphere1D>(point, new S1Point(a[0]), currentOffset); 510 } 511 } 512 } else if (alpha <= a[1]) { 513 // the test point lies within the current arc 514 // offset will be negative 515 final double offset0 = a[0] - alpha; 516 final double offset1 = alpha - a[1]; 517 if (offset0 < offset1) { 518 return new BoundaryProjection<Sphere1D>(point, new S1Point(a[1]), offset1); 519 } else { 520 return new BoundaryProjection<Sphere1D>(point, new S1Point(a[0]), offset0); 521 } 522 } 523 } 524 previous = a[1]; 525 } 526 527 if (Double.isNaN(previous)) { 528 529 // there are no points at all in the arcs set 530 return new BoundaryProjection<Sphere1D>(point, null, MathUtils.TWO_PI); 531 532 } else { 533 534 // the test point if before first arc and after last arc, 535 // somewhere around the 0/2 \pi crossing 536 if (wrapFirst) { 537 // the test point is between 0 and first 538 final double previousOffset = alpha - (previous - MathUtils.TWO_PI); 539 final double currentOffset = first - alpha; 540 if (previousOffset < currentOffset) { 541 return new BoundaryProjection<Sphere1D>(point, new S1Point(previous), previousOffset); 542 } else { 543 return new BoundaryProjection<Sphere1D>(point, new S1Point(first), currentOffset); 544 } 545 } else { 546 // the test point is between last and 2\pi 547 final double previousOffset = alpha - previous; 548 final double currentOffset = first + MathUtils.TWO_PI - alpha; 549 if (previousOffset < currentOffset) { 550 return new BoundaryProjection<Sphere1D>(point, new S1Point(previous), previousOffset); 551 } else { 552 return new BoundaryProjection<Sphere1D>(point, new S1Point(first), currentOffset); 553 } 554 } 555 556 } 557 558 } 559 560 /** Build an ordered list of arcs representing the instance. 561 * <p>This method builds this arcs set as an ordered list of 562 * {@link Arc Arc} elements. An empty tree will build an empty list 563 * while a tree representing the whole circle will build a one 564 * element list with bounds set to \( 0 and 2 \pi \).</p> 565 * @return a new ordered list containing {@link Arc Arc} elements 566 */ asList()567 public List<Arc> asList() { 568 final List<Arc> list = new ArrayList<Arc>(); 569 for (final double[] a : this) { 570 list.add(new Arc(a[0], a[1], getTolerance())); 571 } 572 return list; 573 } 574 575 /** {@inheritDoc} 576 * <p> 577 * The iterator returns the limit angles pairs of sub-arcs in trigonometric order. 578 * </p> 579 * <p> 580 * The iterator does <em>not</em> support the optional {@code remove} operation. 581 * </p> 582 */ iterator()583 public Iterator<double[]> iterator() { 584 return new SubArcsIterator(); 585 } 586 587 /** Local iterator for sub-arcs. */ 588 private class SubArcsIterator implements Iterator<double[]> { 589 590 /** Start of the first arc. */ 591 private final BSPTree<Sphere1D> firstStart; 592 593 /** Current node. */ 594 private BSPTree<Sphere1D> current; 595 596 /** Sub-arc no yet returned. */ 597 private double[] pending; 598 599 /** Simple constructor. 600 */ SubArcsIterator()601 SubArcsIterator() { 602 603 firstStart = getFirstArcStart(); 604 current = firstStart; 605 606 if (firstStart == null) { 607 // all the leaf tree nodes share the same inside/outside status 608 if ((Boolean) getFirstLeaf(getTree(false)).getAttribute()) { 609 // it is an inside node, it represents the full circle 610 pending = new double[] { 611 0, MathUtils.TWO_PI 612 }; 613 } else { 614 pending = null; 615 } 616 } else { 617 selectPending(); 618 } 619 } 620 621 /** Walk the tree to select the pending sub-arc. 622 */ selectPending()623 private void selectPending() { 624 625 // look for the start of the arc 626 BSPTree<Sphere1D> start = current; 627 while (start != null && !isArcStart(start)) { 628 start = nextInternalNode(start); 629 } 630 631 if (start == null) { 632 // we have exhausted the iterator 633 current = null; 634 pending = null; 635 return; 636 } 637 638 // look for the end of the arc 639 BSPTree<Sphere1D> end = start; 640 while (end != null && !isArcEnd(end)) { 641 end = nextInternalNode(end); 642 } 643 644 if (end != null) { 645 646 // we have identified the arc 647 pending = new double[] { 648 getAngle(start), getAngle(end) 649 }; 650 651 // prepare search for next arc 652 current = end; 653 654 } else { 655 656 // the final arc wraps around 2\pi, its end is before the first start 657 end = firstStart; 658 while (end != null && !isArcEnd(end)) { 659 end = previousInternalNode(end); 660 } 661 if (end == null) { 662 // this should never happen 663 throw new MathInternalError(); 664 } 665 666 // we have identified the last arc 667 pending = new double[] { 668 getAngle(start), getAngle(end) + MathUtils.TWO_PI 669 }; 670 671 // there won't be any other arcs 672 current = null; 673 674 } 675 676 } 677 678 /** {@inheritDoc} */ hasNext()679 public boolean hasNext() { 680 return pending != null; 681 } 682 683 /** {@inheritDoc} */ next()684 public double[] next() { 685 if (pending == null) { 686 throw new NoSuchElementException(); 687 } 688 final double[] next = pending; 689 selectPending(); 690 return next; 691 } 692 693 /** {@inheritDoc} */ remove()694 public void remove() { 695 throw new UnsupportedOperationException(); 696 } 697 698 } 699 700 /** Compute the relative position of the instance with respect 701 * to an arc. 702 * <p> 703 * The {@link Side#MINUS} side of the arc is the one covered by the arc. 704 * </p> 705 * @param arc arc to check instance against 706 * @return one of {@link Side#PLUS}, {@link Side#MINUS}, {@link Side#BOTH} 707 * or {@link Side#HYPER} 708 * @deprecated as of 3.6, replaced with {@link #split(Arc)}.{@link Split#getSide()} 709 */ 710 @Deprecated side(final Arc arc)711 public Side side(final Arc arc) { 712 return split(arc).getSide(); 713 } 714 715 /** Split the instance in two parts by an arc. 716 * @param arc splitting arc 717 * @return an object containing both the part of the instance 718 * on the plus side of the arc and the part of the 719 * instance on the minus side of the arc 720 */ split(final Arc arc)721 public Split split(final Arc arc) { 722 723 final List<Double> minus = new ArrayList<Double>(); 724 final List<Double> plus = new ArrayList<Double>(); 725 726 final double reference = FastMath.PI + arc.getInf(); 727 final double arcLength = arc.getSup() - arc.getInf(); 728 729 for (final double[] a : this) { 730 final double syncedStart = MathUtils.normalizeAngle(a[0], reference) - arc.getInf(); 731 final double arcOffset = a[0] - syncedStart; 732 final double syncedEnd = a[1] - arcOffset; 733 if (syncedStart < arcLength) { 734 // the start point a[0] is in the minus part of the arc 735 minus.add(a[0]); 736 if (syncedEnd > arcLength) { 737 // the end point a[1] is past the end of the arc 738 // so we leave the minus part and enter the plus part 739 final double minusToPlus = arcLength + arcOffset; 740 minus.add(minusToPlus); 741 plus.add(minusToPlus); 742 if (syncedEnd > MathUtils.TWO_PI) { 743 // in fact the end point a[1] goes far enough that we 744 // leave the plus part of the arc and enter the minus part again 745 final double plusToMinus = MathUtils.TWO_PI + arcOffset; 746 plus.add(plusToMinus); 747 minus.add(plusToMinus); 748 minus.add(a[1]); 749 } else { 750 // the end point a[1] is in the plus part of the arc 751 plus.add(a[1]); 752 } 753 } else { 754 // the end point a[1] is in the minus part of the arc 755 minus.add(a[1]); 756 } 757 } else { 758 // the start point a[0] is in the plus part of the arc 759 plus.add(a[0]); 760 if (syncedEnd > MathUtils.TWO_PI) { 761 // the end point a[1] wraps around to the start of the arc 762 // so we leave the plus part and enter the minus part 763 final double plusToMinus = MathUtils.TWO_PI + arcOffset; 764 plus.add(plusToMinus); 765 minus.add(plusToMinus); 766 if (syncedEnd > MathUtils.TWO_PI + arcLength) { 767 // in fact the end point a[1] goes far enough that we 768 // leave the minus part of the arc and enter the plus part again 769 final double minusToPlus = MathUtils.TWO_PI + arcLength + arcOffset; 770 minus.add(minusToPlus); 771 plus.add(minusToPlus); 772 plus.add(a[1]); 773 } else { 774 // the end point a[1] is in the minus part of the arc 775 minus.add(a[1]); 776 } 777 } else { 778 // the end point a[1] is in the plus part of the arc 779 plus.add(a[1]); 780 } 781 } 782 } 783 784 return new Split(createSplitPart(plus), createSplitPart(minus)); 785 786 } 787 788 /** Add an arc limit to a BSP tree under construction. 789 * @param tree BSP tree under construction 790 * @param alpha arc limit 791 * @param isStart if true, the limit is the start of an arc 792 */ addArcLimit(final BSPTree<Sphere1D> tree, final double alpha, final boolean isStart)793 private void addArcLimit(final BSPTree<Sphere1D> tree, final double alpha, final boolean isStart) { 794 795 final LimitAngle limit = new LimitAngle(new S1Point(alpha), !isStart, getTolerance()); 796 final BSPTree<Sphere1D> node = tree.getCell(limit.getLocation(), getTolerance()); 797 if (node.getCut() != null) { 798 // this should never happen 799 throw new MathInternalError(); 800 } 801 802 node.insertCut(limit); 803 node.setAttribute(null); 804 node.getPlus().setAttribute(Boolean.FALSE); 805 node.getMinus().setAttribute(Boolean.TRUE); 806 807 } 808 809 /** Create a split part. 810 * <p> 811 * As per construction, the list of limit angles is known to have 812 * an even number of entries, with start angles at even indices and 813 * end angles at odd indices. 814 * </p> 815 * @param limits limit angles of the split part 816 * @return split part (may be null) 817 */ createSplitPart(final List<Double> limits)818 private ArcsSet createSplitPart(final List<Double> limits) { 819 if (limits.isEmpty()) { 820 return null; 821 } else { 822 823 // collapse close limit angles 824 for (int i = 0; i < limits.size(); ++i) { 825 final int j = (i + 1) % limits.size(); 826 final double lA = limits.get(i); 827 final double lB = MathUtils.normalizeAngle(limits.get(j), lA); 828 if (FastMath.abs(lB - lA) <= getTolerance()) { 829 // the two limits are too close to each other, we remove both of them 830 if (j > 0) { 831 // regular case, the two entries are consecutive ones 832 limits.remove(j); 833 limits.remove(i); 834 i = i - 1; 835 } else { 836 // special case, i the the last entry and j is the first entry 837 // we have wrapped around list end 838 final double lEnd = limits.remove(limits.size() - 1); 839 final double lStart = limits.remove(0); 840 if (limits.isEmpty()) { 841 // the ends were the only limits, is it a full circle or an empty circle? 842 if (lEnd - lStart > FastMath.PI) { 843 // it was full circle 844 return new ArcsSet(new BSPTree<Sphere1D>(Boolean.TRUE), getTolerance()); 845 } else { 846 // it was an empty circle 847 return null; 848 } 849 } else { 850 // we have removed the first interval start, so our list 851 // currently starts with an interval end, which is wrong 852 // we need to move this interval end to the end of the list 853 limits.add(limits.remove(0) + MathUtils.TWO_PI); 854 } 855 } 856 } 857 } 858 859 // build the tree by adding all angular sectors 860 BSPTree<Sphere1D> tree = new BSPTree<Sphere1D>(Boolean.FALSE); 861 for (int i = 0; i < limits.size() - 1; i += 2) { 862 addArcLimit(tree, limits.get(i), true); 863 addArcLimit(tree, limits.get(i + 1), false); 864 } 865 866 if (tree.getCut() == null) { 867 // we did not insert anything 868 return null; 869 } 870 871 return new ArcsSet(tree, getTolerance()); 872 873 } 874 } 875 876 /** Class holding the results of the {@link #split split} method. 877 */ 878 public static class Split { 879 880 /** Part of the arcs set on the plus side of the splitting arc. */ 881 private final ArcsSet plus; 882 883 /** Part of the arcs set on the minus side of the splitting arc. */ 884 private final ArcsSet minus; 885 886 /** Build a Split from its parts. 887 * @param plus part of the arcs set on the plus side of the 888 * splitting arc 889 * @param minus part of the arcs set on the minus side of the 890 * splitting arc 891 */ Split(final ArcsSet plus, final ArcsSet minus)892 private Split(final ArcsSet plus, final ArcsSet minus) { 893 this.plus = plus; 894 this.minus = minus; 895 } 896 897 /** Get the part of the arcs set on the plus side of the splitting arc. 898 * @return part of the arcs set on the plus side of the splitting arc 899 */ getPlus()900 public ArcsSet getPlus() { 901 return plus; 902 } 903 904 /** Get the part of the arcs set on the minus side of the splitting arc. 905 * @return part of the arcs set on the minus side of the splitting arc 906 */ getMinus()907 public ArcsSet getMinus() { 908 return minus; 909 } 910 911 /** Get the side of the split arc with respect to its splitter. 912 * @return {@link Side#PLUS} if only {@link #getPlus()} returns non-null, 913 * {@link Side#MINUS} if only {@link #getMinus()} returns non-null, 914 * {@link Side#BOTH} if both {@link #getPlus()} and {@link #getMinus()} 915 * return non-null or {@link Side#HYPER} if both {@link #getPlus()} and 916 * {@link #getMinus()} return null 917 * @since 3.6 918 */ getSide()919 public Side getSide() { 920 if (plus != null) { 921 if (minus != null) { 922 return Side.BOTH; 923 } else { 924 return Side.PLUS; 925 } 926 } else if (minus != null) { 927 return Side.MINUS; 928 } else { 929 return Side.HYPER; 930 } 931 } 932 933 } 934 935 /** Specialized exception for inconsistent BSP tree state inconsistency. 936 * <p> 937 * This exception is thrown at {@link ArcsSet} construction time when the 938 * {@link org.apache.commons.math3.geometry.partitioning.Region.Location inside/outside} 939 * state is not consistent at the 0, \(2 \pi \) crossing. 940 * </p> 941 */ 942 public static class InconsistentStateAt2PiWrapping extends MathIllegalArgumentException { 943 944 /** Serializable UID. */ 945 private static final long serialVersionUID = 20140107L; 946 947 /** Simple constructor. 948 */ InconsistentStateAt2PiWrapping()949 public InconsistentStateAt2PiWrapping() { 950 super(LocalizedFormats.INCONSISTENT_STATE_AT_2_PI_WRAPPING); 951 } 952 953 } 954 955 } 956