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