001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.math3.geometry.spherical.oned;
018
019import java.util.ArrayList;
020import java.util.Collection;
021import java.util.Iterator;
022import java.util.List;
023import java.util.NoSuchElementException;
024
025import org.apache.commons.math3.exception.MathIllegalArgumentException;
026import org.apache.commons.math3.exception.MathInternalError;
027import org.apache.commons.math3.exception.NumberIsTooLargeException;
028import org.apache.commons.math3.exception.util.LocalizedFormats;
029import org.apache.commons.math3.geometry.Point;
030import org.apache.commons.math3.geometry.partitioning.AbstractRegion;
031import org.apache.commons.math3.geometry.partitioning.BSPTree;
032import org.apache.commons.math3.geometry.partitioning.BoundaryProjection;
033import org.apache.commons.math3.geometry.partitioning.Side;
034import org.apache.commons.math3.geometry.partitioning.SubHyperplane;
035import org.apache.commons.math3.util.FastMath;
036import org.apache.commons.math3.util.MathUtils;
037import org.apache.commons.math3.util.Precision;
038
039/** This class represents a region of a circle: a set of arcs.
040 * <p>
041 * Note that due to the wrapping around \(2 \pi\), barycenter is
042 * ill-defined here. It was defined only in order to fulfill
043 * the requirements of the {@link
044 * org.apache.commons.math3.geometry.partitioning.Region Region}
045 * interface, but its use is discouraged.
046 * </p>
047 * @since 3.3
048 */
049public class ArcsSet extends AbstractRegion<Sphere1D, Sphere1D> implements Iterable<double[]> {
050
051    /** Build an arcs set representing the whole circle.
052     * @param tolerance tolerance below which close sub-arcs are merged together
053     */
054    public ArcsSet(final double tolerance) {
055        super(tolerance);
056    }
057
058    /** Build an arcs set corresponding to a single arc.
059     * <p>
060     * If either {@code lower} is equals to {@code upper} or
061     * the interval exceeds \( 2 \pi \), the arc is considered
062     * to be the full circle and its initial defining boundaries
063     * will be forgotten. {@code lower} is not allowed to be greater
064     * than {@code upper} (an exception is thrown in this case).
065     * </p>
066     * @param lower lower bound of the arc
067     * @param upper upper bound of the arc
068     * @param tolerance tolerance below which close sub-arcs are merged together
069     * @exception NumberIsTooLargeException if lower is greater than upper
070     */
071    public ArcsSet(final double lower, final double upper, final double tolerance)
072        throws NumberIsTooLargeException {
073        super(buildTree(lower, upper, tolerance), tolerance);
074    }
075
076    /** Build an arcs set from an inside/outside BSP tree.
077     * <p>The leaf nodes of the BSP tree <em>must</em> have a
078     * {@code Boolean} attribute representing the inside status of
079     * the corresponding cell (true for inside cells, false for outside
080     * cells). In order to avoid building too many small objects, it is
081     * recommended to use the predefined constants
082     * {@code Boolean.TRUE} and {@code Boolean.FALSE}</p>
083     * @param tree inside/outside BSP tree representing the arcs set
084     * @param tolerance tolerance below which close sub-arcs are merged together
085     * @exception InconsistentStateAt2PiWrapping if the tree leaf nodes are not
086     * consistent across the \( 0, 2 \pi \) crossing
087     */
088    public ArcsSet(final BSPTree<Sphere1D> tree, final double tolerance)
089        throws InconsistentStateAt2PiWrapping {
090        super(tree, tolerance);
091        check2PiConsistency();
092    }
093
094    /** Build an arcs set from a Boundary REPresentation (B-rep).
095     * <p>The boundary is provided as a collection of {@link
096     * SubHyperplane sub-hyperplanes}. Each sub-hyperplane has the
097     * interior part of the region on its minus side and the exterior on
098     * its plus side.</p>
099     * <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     */
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     */
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    */
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     */
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     */
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     */
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     */
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     */
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     */
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     */
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     */
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     */
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     */
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     */
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     */
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     */
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     */
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     */
441    private double getAngle(final BSPTree<Sphere1D> node) {
442        return ((LimitAngle) node.getCut().getHyperplane()).getLocation().getAlpha();
443    }
444
445    /** {@inheritDoc} */
446    @Override
447    public ArcsSet buildNew(final BSPTree<Sphere1D> tree) {
448        return new ArcsSet(tree, getTolerance());
449    }
450
451    /** {@inheritDoc} */
452    @Override
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
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     */
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     */
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         */
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         */
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} */
679        public boolean hasNext() {
680            return pending != null;
681        }
682
683        /** {@inheritDoc} */
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} */
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
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     */
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     */
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     */
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         */
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         */
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         */
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         */
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         */
949        public InconsistentStateAt2PiWrapping() {
950            super(LocalizedFormats.INCONSISTENT_STATE_AT_2_PI_WRAPPING);
951        }
952
953    }
954
955}