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