ArcsSet.java

  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.  */

  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;

  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;

  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;

  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[]> {

  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.     }

  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.     }

  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.     }

  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.     }

  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 {

  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.         }

  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();

  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.         }

  183.     }

  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 {

  191.         // start search at the tree root
  192.         BSPTree<Sphere1D, S1Point, LimitAngle, SubLimitAngle> root = getTree(false);
  193.         if (root.getCut() == null) {
  194.             return;
  195.         }

  197.         // find the inside/outside state before the smallest internal node
  198.         final Boolean stateBefore = (Boolean) getFirstLeaf(root).getAttribute();

  200.         // find the inside/outside state after the largest internal node
  201.         final Boolean stateAfter = (Boolean) getLastLeaf(root).getAttribute();

  203.         if (stateBefore ^ stateAfter) {
  204.             throw new InconsistentStateAt2PiWrapping();
  205.         }

  207.     }

  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) {

  216.         if (root.getCut() == null) {
  217.             return root;
  218.         }

  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.         }

  226.         return leafBefore(smallest);

  228.     }

  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) {

  237.         if (root.getCut() == null) {
  238.             return root;
  239.         }

  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.         }

  247.         return leafAfter(largest);

  249.     }

  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() {

  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.         }

  263.         // walk tree until we find the smallest internal node
  264.         node = getFirstLeaf(node).getParent();

  266.         // walk tree until we find an arc start
  267.         while (node != null && !isArcStart(node)) {
  268.             node = nextInternalNode(node);
  269.         }

  271.         return node;

  273.     }

  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) {

  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.         }

  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.         }

  291.         // the cell has an outside before and an inside after it
  292.         // it is the start of an arc
  293.         return true;

  295.     }

  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) {

  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.         }

  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.         }

  313.         // the cell has an inside before and an outside after it
  314.         // it is the end of an arc
  315.         return true;

  317.     }

  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) {

  327.         if (childAfter(node).getCut() != null) {
  328.             // the next node is in the sub-tree
  329.             return leafAfter(node).getParent();
  330.         }

  332.         // there is nothing left deeper in the tree, we backtrack
  333.         while (isAfterParent(node)) {
  334.             node = node.getParent();
  335.         }
  336.         return node.getParent();

  338.     }

  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) {

  348.         if (childBefore(node).getCut() != null) {
  349.             // the next node is in the sub-tree
  350.             return leafBefore(node).getParent();
  351.         }

  353.         // there is nothing left deeper in the tree, we backtrack
  354.         while (isBeforeParent(node)) {
  355.             node = node.getParent();
  356.         }
  357.         return node.getParent();

  359.     }

  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) {

  368.         node = childBefore(node);
  369.         while (node.getCut() != null) {
  370.             node = childAfter(node);
  371.         }

  373.         return node;

  375.     }

  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) {

  384.         node = childAfter(node);
  385.         while (node.getCut() != null) {
  386.             node = childBefore(node);
  387.         }

  389.         return node;

  391.     }

  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.     }

  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.     }

  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.     }

  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.     }

  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.     }

  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.     }

  465.     /** {@inheritDoc} */
  466.     @Override
  467.     public ArcsSet buildNew(final BSPTree<Sphere1D, S1Point, LimitAngle, SubLimitAngle> tree) {
  468.         return new ArcsSet(tree, getTolerance());
  469.     }

  471.     /** {@inheritDoc} */
  472.     @Override
  473.     public S1Point getInteriorPoint() {

  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.         }

  487.         return Double.isNaN(selectedPoint) ? null : new S1Point(selectedPoint);

  489.     }

  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.     }

  517.     /** {@inheritDoc}
  518.      */
  519.     @Override
  520.     public BoundaryProjection<Sphere1D, S1Point> projectToBoundary(final S1Point point) {

  522.         // get position of test point
  523.         final double alpha = point.getAlpha();

  525.         boolean wrapFirst = false;
  526.         double first      = Double.NaN;
  527.         double previous   = Double.NaN;
  528.         for (final double[] a : this) {

  530.             if (Double.isNaN(first)) {
  531.                 // remember the first angle in case we need it later
  532.                 first = a[0];
  533.             }

  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.         }

  566.         if (Double.isNaN(previous)) {

  568.             // there are no points at all in the arcs set
  569.             return new BoundaryProjection<>(point, null, MathUtils.TWO_PI);

  571.         } else {

  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.             }

  595.         }

  597.     }

  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.     }

  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.     }

  627.     /** Local iterator for sub-arcs. */
  628.     private class SubArcsIterator implements Iterator<double[]> {

  630.         /** Start of the first arc. */
  631.         private final BSPTree<Sphere1D, S1Point, LimitAngle, SubLimitAngle> firstStart;

  633.         /** Current node. */
  634.         private BSPTree<Sphere1D, S1Point, LimitAngle, SubLimitAngle> current;

  636.         /** Sub-arc no yet returned. */
  637.         private double[] pending;

  639.         /** Simple constructor.
  640.          */
  641.         SubArcsIterator() {

  643.             firstStart = getFirstArcStart();
  644.             current    = firstStart;

  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.         }

  661.         /** Walk the tree to select the pending sub-arc.
  662.          */
  663.         private void selectPending() {

  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.             }

  671.             if (start == null) {
  672.                 // we have exhausted the iterator
  673.                 current = null;
  674.                 pending = null;
  675.                 return;
  676.             }

  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.             }

  684.             if (end != null) {

  686.                 // we have identified the arc
  687.                 pending = new double[] {
  688.                     getAngle(start), getAngle(end)
  689.                 };

  691.                 // prepare search for next arc
  692.                 current = end;

  694.             } else {

  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.                 }

  706.                 // we have identified the last arc
  707.                 pending = new double[] {
  708.                     getAngle(start), getAngle(end) + MathUtils.TWO_PI
  709.                 };

  711.                 // there won't be any other arcs
  712.                 current = null;

  714.             }

  716.         }

  718.         /** {@inheritDoc} */
  719.         @Override
  720.         public boolean hasNext() {
  721.             return pending != null;
  722.         }

  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.         }

  735.         /** {@inheritDoc} */
  736.         @Override
  737.         public void remove() {
  738.             throw new UnsupportedOperationException();
  739.         }

  741.     }

  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) {

  751.         final List<Double> minus = new ArrayList<>();
  752.         final List<Double>  plus = new ArrayList<>();

  754.         final double reference = FastMath.PI + arc.getInf();
  755.         final double arcLength = arc.getSup() - arc.getInf();

  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.         }

  812.         return new Split(createSplitPart(plus), createSplitPart(minus));

  814.     }

  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) {

  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.         }

  831.         node.insertCut(limit);
  832.         node.setAttribute(null);
  833.         node.getPlus().setAttribute(Boolean.FALSE);
  834.         node.getMinus().setAttribute(Boolean.TRUE);

  836.     }

  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 {

  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.             }

  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.             }

  895.             if (tree.getCut() == null) {
  896.                 // we did not insert anything
  897.                 return null;
  898.             }

  900.             return new ArcsSet(tree, getTolerance());

  902.         }
  903.     }

  905.     /** Class holding the results of the {@link #split split} method.
  906.      */
  907.     public static class Split {

  909.         /** Part of the arcs set on the plus side of the splitting arc. */
  910.         private final ArcsSet plus;

  912.         /** Part of the arcs set on the minus side of the splitting arc. */
  913.         private final ArcsSet minus;

  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.         }

  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.         }

  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.         }

  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.         }

  961.     }

  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.     {

  973.         /** Serializable UID. */
  974.         private static final long serialVersionUID = 20140107L;

  976.         /** Simple constructor.
  977.          */
  978.         public InconsistentStateAt2PiWrapping() {
  979.             super(LocalizedGeometryFormats.INCONSISTENT_STATE_AT_2_PI_WRAPPING);
  980.         }

  982.     }

  984. }
Created with JaCoCo 0.8.12.202403310830