commons-geometry-spherical/src/main/java/org/apache/commons/geometry/spherical/oned/AngularInterval.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.geometry.spherical.oned;

import java.text.MessageFormat;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.function.BiFunction;

import org.apache.commons.geometry.core.Geometry;
import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.core.Transform;
import org.apache.commons.geometry.core.exception.GeometryException;
import org.apache.commons.geometry.core.partitioning.Hyperplane;
import org.apache.commons.geometry.core.partitioning.HyperplaneBoundedRegion;
import org.apache.commons.geometry.core.partitioning.HyperplaneLocation;
import org.apache.commons.geometry.core.partitioning.Split;
import org.apache.commons.geometry.core.precision.DoublePrecisionContext;

/** Class representing an angular interval of size greater than zero to {@code 2pi}. The interval is
 * defined by two azimuth angles: a min and a max. The interval starts at the min azimuth angle and
 * contains all points in the direction of increasing azimuth angles up to max.
 *
 * <p>Instances of this class are guaranteed to be immutable.</p>
 */
public class AngularInterval implements HyperplaneBoundedRegion<Point1S> {
    /** The minimum boundary of the interval. */
    private final CutAngle minBoundary;

    /** The maximum boundary of the interval. */
    private final CutAngle maxBoundary;

    /** Point halfway between the min and max boundaries. */
    private final Point1S midpoint;

    /** Construct a new instance representing the angular region between the given
     * min and max azimuth boundaries. The arguments must be either all finite or all
     * null (to indicate the full space). If the boundaries are finite, then the min
     * boundary azimuth value must be numerically less than the max boundary. Callers are
     * responsible for enforcing these constraints. No validation is performed.
     * @param minBoundary minimum boundary for the interval
     * @param maxBoundary maximum boundary for the interval
     */
    private AngularInterval(final CutAngle minBoundary, final CutAngle maxBoundary) {

        this.minBoundary = minBoundary;
        this.maxBoundary = maxBoundary;
        this.midpoint = (minBoundary != null && maxBoundary != null) ?
                Point1S.of(0.5 * (minBoundary.getAzimuth() + maxBoundary.getAzimuth())) :
                null;
    }

    /** Get the minimum azimuth angle for the interval, or {@code 0}
     * if the interval is full.
     * @return the minimum azimuth angle for the interval or {@code 0}
     *      if the interval represents the full space.
     */
    public double getMin() {
        return (minBoundary != null) ?
                minBoundary.getAzimuth() :
                Geometry.ZERO_PI;
    }

    /** Get the minimum boundary for the interval, or null if the
     * interval represents the full space.
     * @return the minimum point for the interval or null if
     *      the interval represents the full space
     */
    public CutAngle getMinBoundary() {
        return minBoundary;
    }

    /** Get the maximum azimuth angle for the interval, or {@code 2pi} if
     * the interval represents the full space.
     * @return the maximum azimuth angle for the interval or {@code 2pi} if
     *      the interval represents the full space.
     */
    public double getMax() {
        return (maxBoundary != null) ?
                maxBoundary.getAzimuth() :
                Geometry.TWO_PI;
    }

    /** Get the maximum point for the interval. This will be null if the
     * interval represents the full space.
     * @return the maximum point for the interval or null if
     *      the interval represents the full space
     */
    public CutAngle getMaxBoundary() {
        return maxBoundary;
    }

    /** Get the midpoint of the interval or null if the interval represents
     *  the full space.
     * @return the midpoint of the interval or null if the interval represents
     *      the full space
     * @see #getBarycenter()
     */
    public Point1S getMidPoint() {
        return midpoint;
    }

    /** {@inheritDoc} */
    @Override
    public boolean isFull() {
        // minBoundary and maxBoundary are either both null or both not null
        return minBoundary == null;
    }

    /** {@inheritDoc}
     *
     * <p>This method always returns false.</p>
     */
    @Override
    public boolean isEmpty() {
        return false;
    }

    /** {@inheritDoc} */
    @Override
    public double getSize() {
        return getMax() - getMin();
    }

    /** {@inheritDoc}
     *
     * <p>This method simply returns 0 because boundaries in one dimension do not
     *  have any size.</p>
     */
    @Override
    public double getBoundarySize() {
        return 0;
    }

    /** {@inheritDoc}
     *
     * <p>This method is an alias for {@link #getMidPoint()}.</p>
     * @see #getMidPoint()
     */
    @Override
    public Point1S getBarycenter() {
        return getMidPoint();
    }

    /** {@inheritDoc} */
    @Override
    public RegionLocation classify(final Point1S pt) {
        if (!isFull()) {
            final HyperplaneLocation minLoc = minBoundary.classify(pt);
            final HyperplaneLocation maxLoc = maxBoundary.classify(pt);

            final boolean wraps = wrapsZero();

            if ((!wraps && (minLoc == HyperplaneLocation.PLUS || maxLoc == HyperplaneLocation.PLUS)) ||
                    (wraps && minLoc == HyperplaneLocation.PLUS && maxLoc == HyperplaneLocation.PLUS)) {
                return RegionLocation.OUTSIDE;
            } else if (minLoc == HyperplaneLocation.ON || maxLoc == HyperplaneLocation.ON) {
                return RegionLocation.BOUNDARY;
            }
        }
        return RegionLocation.INSIDE;
    }

    /** {@inheritDoc} */
    @Override
    public Point1S project(final Point1S pt) {
        if (!isFull()) {
            final double minDist = minBoundary.getPoint().distance(pt);
            final double maxDist = maxBoundary.getPoint().distance(pt);

            return (minDist <= maxDist) ?
                    minBoundary.getPoint() :
                    maxBoundary.getPoint();
        }
        return null;
    }

    /** Return true if the interval wraps around the zero/{@code 2pi} point. In this
     * case, the max boundary azimuth is less than that of the min boundary when both
     * values are normalized to the range {@code [0, 2pi)}.
     * @return true if the interval wraps around the zero/{@code 2pi} point
     */
    public boolean wrapsZero() {
        if (!isFull()) {
            final double minNormAz = minBoundary.getPoint().getNormalizedAzimuth();
            final double maxNormAz = maxBoundary.getPoint().getNormalizedAzimuth();

            return maxNormAz < minNormAz;
        }
        return false;
    }

    /** Return a new instance transformed by the argument. If the transformed size
     * of the interval is greater than or equal to 2pi, then an interval representing
     * the full space is returned.
     * @param transform transform to apply
     * @return a new instance transformed by the argument
     */
    public AngularInterval transform(final Transform<Point1S> transform) {
        return AngularInterval.transform(this, transform, AngularInterval::of);
    }

    /** {@inheritDoc}
    *
    * <p>This method returns instances of {@link RegionBSPTree1S} instead of
    * {@link AngularInterval} since it is possible for a convex angular interval
    * to be split into disjoint regions by a single hyperplane. These disjoint
    * regions cannot be represented by this class and require the use of a BSP
    * tree.</p>
    *
    * @see RegionBSPTree1S#split(Hyperplane)
    */
    @Override
    public Split<RegionBSPTree1S> split(final Hyperplane<Point1S> splitter) {
        return toTree().split(splitter);
    }

    /** Return a {@link RegionBSPTree1S} instance representing the same region
     * as this instance.
     * @return a BSP tree representing the same region as this instance
     */
    public RegionBSPTree1S toTree() {
        return RegionBSPTree1S.fromInterval(this);
    }

    /** Return a list of convex intervals comprising this region.
     * @return a list of convex intervals comprising this region
     * @see Convex
     */
    public List<AngularInterval.Convex> toConvex() {
        if (isConvex(minBoundary, maxBoundary)) {
            return Collections.singletonList(new Convex(minBoundary, maxBoundary));
        }

        final CutAngle midPos = CutAngle.createPositiveFacing(midpoint, minBoundary.getPrecision());
        final CutAngle midNeg = CutAngle.createNegativeFacing(midpoint, maxBoundary.getPrecision());

        return Arrays.asList(
                    new Convex(minBoundary, midPos),
                    new Convex(midNeg, maxBoundary)
                );
    }

    /** {@inheritDoc} */
    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder();
        sb.append(this.getClass().getSimpleName())
            .append("[min= ")
            .append(getMin())
            .append(", max= ")
            .append(getMax())
            .append(']');

        return sb.toString();
    }

    /** Return an instance representing the full space. The returned instance contains all
     * possible azimuth angles.
     * @return an interval representing the full space
     */
    public static AngularInterval.Convex full() {
        return Convex.FULL;
    }

    /** Return an instance representing the angular interval between the given min and max azimuth
     * values. The max value is adjusted to be numerically above the min value, even if the resulting
     * azimuth value is greater than or equal to {@code 2pi}. An instance representing the full space
     * is returned if either point is infinite or min and max are equivalent as evaluated by the
     * given precision context.
     * @param min min azimuth value
     * @param max max azimuth value
     * @param precision precision precision context used to compare floating point values
     * @return a new instance resulting the angular region between the given min and max azimuths
     * @throws GeometryException if either azimuth is infinite or NaN
     */
    public static AngularInterval of(final double min, final double max, final DoublePrecisionContext precision) {
        return of(Point1S.of(min), Point1S.of(max), precision);
    }

    /** Return an instance representing the angular interval between the given min and max azimuth
     * points. The max point is adjusted to be numerically above the min point, even if the resulting
     * azimuth value is greater than or equal to {@code 2pi}. An instance representing the full space
     * is returned if either point is infinite or min and max are equivalent as evaluated by the
     * given precision context.
     * @param min min azimuth value
     * @param max max azimuth value
     * @param precision precision precision context used to compare floating point values
     * @return a new instance resulting the angular region between the given min and max points
     * @throws GeometryException if either azimuth is infinite or NaN
     */
    public static AngularInterval of(final Point1S min, final Point1S max, final DoublePrecisionContext precision) {
        return createInterval(min, max, precision, AngularInterval::new, Convex.FULL);
    }

    /** Return an instance representing the angular interval between the given oriented points.
     * The negative-facing point is used as the minimum boundary and the positive-facing point is
     * adjusted to be above the minimum. The arguments can be given in any order. The full space
     * is returned if the points are equivalent or are oriented in the same direction.
     * @param a first oriented point
     * @param b second oriented point
     * @return an instance representing the angular interval between the given oriented points
     * @throws GeometryException if either argument is infinite or NaN
     */
    public static AngularInterval of(final CutAngle a, final CutAngle b) {
        return createInterval(a, b, AngularInterval::new, Convex.FULL);
    }

    /** Internal method to create an interval between the given min and max points. The max point
     * is adjusted to be numerically above the min point, even if the resulting
     * azimuth value is greater than or equal to {@code 2pi}. The full instance argument
     * is returned if either point is infinite or min and max are equivalent as evaluated by the
     * given precision context.
     * @param min min azimuth value
     * @param max max azimuth value
     * @param precision precision precision context used to compare floating point values
     * @param factory factory object used to create new instances; this object is passed the validated
     *      min (negative-facing) cut and the max (positive-facing) cut, in that order
     * @param <T> Angular interval implementation type
     * @param fullSpace instance returned if the interval should represent the full space
     * @return a new instance resulting the angular region between the given min and max points
     * @throws GeometryException if either azimuth is infinite or NaN
     */
    private static <T extends AngularInterval> T createInterval(final Point1S min, final Point1S max,
            final DoublePrecisionContext precision, final BiFunction<CutAngle, CutAngle, T> factory,
            final T fullSpace) {

        validateIntervalValues(min, max);

        // return the full space if either point is infinite or the points are equivalent
        if (min.eq(max, precision)) {
            return fullSpace;
        }

        final Point1S adjustedMax = max.above(min);

        return factory.apply(
                    CutAngle.createNegativeFacing(min, precision),
                    CutAngle.createPositiveFacing(adjustedMax, precision)
                );
    }

    /** Internal method to create a new interval instance from the given cut angles.
     * The negative-facing point is used as the minimum boundary and the positive-facing point is
     * adjusted to be above the minimum. The arguments can be given in any order. The full space
     * argument is returned if the points are equivalent or are oriented in the same direction.
     * @param a first cut point
     * @param b second cut point
     * @param factory factory object used to create new instances; this object is passed the validated
     *      min (negative-facing) cut and the max (positive-facing) cut, in that order
     * @param fullSpace instance returned if the interval should represent the full space
     * @param <T> Angular interval implementation type
     * @return a new interval instance created from the given cut angles
     * @throws GeometryException if either argument is infinite or NaN
     */
    private static <T extends AngularInterval> T createInterval(final CutAngle a, final CutAngle b,
            final BiFunction<CutAngle, CutAngle, T> factory, final T fullSpace) {

        final Point1S aPoint = a.getPoint();
        final Point1S bPoint = b.getPoint();

        validateIntervalValues(aPoint, bPoint);

        if (a.isPositiveFacing() == b.isPositiveFacing() ||
                aPoint.eq(bPoint, a.getPrecision()) ||
                bPoint.eq(aPoint, b.getPrecision())) {
            // points are equivalent or facing in the same direction
            return fullSpace;
        }

        final CutAngle min = a.isPositiveFacing() ? b : a;
        final CutAngle max = a.isPositiveFacing() ? a : b;
        final CutAngle adjustedMax = CutAngle.createPositiveFacing(
                max.getPoint().above(min.getPoint()),
                max.getPrecision());

        return factory.apply(min, adjustedMax);
    }

    /** Validate that the given points can be used to specify an angular interval.
     * @param a first point
     * @param b second point
     * @throws GeometryException if either point is infinite NaN
     */
    private static void validateIntervalValues(final Point1S a, final Point1S b) {
        if (!a.isFinite() || !b.isFinite()) {
            throw new GeometryException(MessageFormat.format("Invalid angular interval: [{0}, {1}]",
                    a.getAzimuth(), b.getAzimuth()));
        }
    }

    /** Return true if the given cut angles define a convex region. By convention, the
     * precision context from the min cut is used for the floating point comparison.
     * @param min min (negative-facing) cut angle
     * @param max max (positive-facing) cut angle
     * @return true if the given cut angles define a convex region
     */
    private static boolean isConvex(final CutAngle min, final CutAngle max) {
        if (min != null && max != null) {
            final double dist = max.getAzimuth() - min.getAzimuth();
            final DoublePrecisionContext precision = min.getPrecision();
            return precision.lte(dist, Geometry.PI);
        }

        return true;
    }

    /** Internal transform method that transforms the given instance, using the factory
     * method to create a new instance if needed.
     * @param interval interval to transform
     * @param transform transform to apply
     * @param factory object used to create new instances
     * @param <T> Angular interval implementation type
     * @return a transformed instance
     */
    private static <T extends AngularInterval> T transform(final T interval,
            final Transform<Point1S> transform,
            final BiFunction<CutAngle, CutAngle, T> factory) {

        if (!interval.isFull()) {
            final CutAngle tMin = interval.getMinBoundary().transform(transform);
            final CutAngle tMax = interval.getMaxBoundary().transform(transform);

            return factory.apply(tMin, tMax);
        }

        return interval;
    }

    /** Class representing an angular interval with the additional property that the
     * region is convex. By convex, it is meant that the shortest path between any
     * two points in the region is also contained entirely in the region. If there is
     * a tie for shortest path, then it is sufficient that at least one lie entirely
     * within the region. For spherical 1D space, this means that the angular interval
     * is either completely full or has a length less than or equal to {@code pi}.
     */
    public static final class Convex extends AngularInterval {
        /** Interval instance representing the full space. */
        private static final Convex FULL = new Convex(null, null);

        /** Construct a new convex instance from its boundaries and midpoint. No validation
         * of the argument is performed. Callers are responsible for ensuring that the size
         * of interval is less than or equal to {@code pi}.
         * @param minBoundary minimum boundary for the interval
         * @param maxBoundary maximum boundary for the interval
         * @throws GeometryException if the interval is not convex
         */
        private Convex(final CutAngle minBoundary, final CutAngle maxBoundary) {
            super(minBoundary, maxBoundary);

            if (!isConvex(minBoundary, maxBoundary)) {
                throw new GeometryException(MessageFormat.format("Interval is not convex: [{0}, {1}]",
                        minBoundary.getAzimuth(), maxBoundary.getAzimuth()));
            }
        }

        /** {@inheritDoc} */
        @Override
        public List<AngularInterval.Convex> toConvex() {
            return Collections.singletonList(this);
        }

        /** {@inheritDoc} */
        @Override
        public Convex transform(final Transform<Point1S> transform) {
            return AngularInterval.transform(this, transform, Convex::of);
        }

        /** Split the instance along a circle diameter.The diameter is defined by the given split point and
         * its reversed antipodal point.
         * @param splitter split point defining one side of the split diameter
         * @return result of the split operation
         */
        public Split<Convex> splitDiameter(final CutAngle splitter) {

            final CutAngle opposite = CutAngle.fromPointAndDirection(
                    splitter.getPoint().antipodal(),
                    !splitter.isPositiveFacing(),
                    splitter.getPrecision());

            if (isFull()) {
                final Convex minus = Convex.of(splitter, opposite);
                final Convex plus = Convex.of(splitter.reverse(), opposite.reverse());

                return new Split<>(minus, plus);
            }

            final CutAngle minBoundary = getMinBoundary();
            final CutAngle maxBoundary = getMaxBoundary();

            final Point1S posPole = Point1S.of(splitter.getPoint().getAzimuth() + Geometry.HALF_PI);

            final int minLoc = minBoundary.getPrecision().compare(Geometry.HALF_PI,
                    posPole.distance(minBoundary.getPoint()));
            final int maxLoc = maxBoundary.getPrecision().compare(Geometry.HALF_PI,
                    posPole.distance(maxBoundary.getPoint()));

            final boolean positiveFacingSplit = splitter.isPositiveFacing();

            // assume a positive orientation of the splitter for region location
            // purposes and adjust later
            Convex pos = null;
            Convex neg = null;

            if (minLoc > 0) {
                // min is on the pos side

                if (maxLoc >= 0) {
                    // max is directly on the splitter or on the pos side
                    pos = this;
                } else {
                    // min is on the pos side and max is on the neg side
                    final CutAngle posCut = positiveFacingSplit ?
                            opposite.reverse() :
                            opposite;
                    pos = Convex.of(minBoundary, posCut);

                    final CutAngle negCut = positiveFacingSplit ?
                            opposite :
                            opposite.reverse();
                    neg = Convex.of(negCut, maxBoundary);
                }
            } else if (minLoc < 0) {
                // min is on the neg side

                if (maxLoc <= 0) {
                    // max is directly on the splitter or on the neg side
                    neg = this;
                } else {
                    // min is on the neg side and max is on the pos side
                    final CutAngle posCut = positiveFacingSplit ?
                            splitter.reverse() :
                            splitter;
                    pos = Convex.of(maxBoundary, posCut);

                    final CutAngle negCut = positiveFacingSplit ?
                            splitter :
                            splitter.reverse();
                    neg = Convex.of(negCut, minBoundary);
                }
            } else {
                // min is directly on the splitter; determine whether it was on the main split
                // point or its antipodal point
                if (splitter.getPoint().distance(minBoundary.getPoint()) < Geometry.HALF_PI) {
                    // on main splitter; interval will be located on pos side of split
                    pos = this;
                } else {
                    // on antipodal point; interval will be located on neg side of split
                    neg = this;
                }
            }

            // adjust for the actual orientation of the splitter
            final Convex minus = positiveFacingSplit ? neg : pos;
            final Convex plus = positiveFacingSplit ? pos : neg;

            return new Split<>(minus, plus);
        }

        /** Return an instance representing the convex angular interval between the given min and max azimuth
         * values. The max value is adjusted to be numerically above the min value, even if the resulting
         * azimuth value is greater than or equal to {@code 2pi}. An instance representing the full space
         * is returned if either point is infinite or min and max are equivalent as evaluated by the
         * given precision context.
         * @param min min azimuth value
         * @param max max azimuth value
         * @param precision precision precision context used to compare floating point values
         * @return a new instance resulting the angular region between the given min and max azimuths
         * @throws GeometryException if either azimuth is infinite or NaN, or the given angular
         *      interval is not convex (meaning it has a size of greater than {@code pi})
         */
        public static Convex of(final double min, final double max, final DoublePrecisionContext precision) {
            return of(Point1S.of(min), Point1S.of(max), precision);
        }

        /** Return an instance representing the convex angular interval between the given min and max azimuth
         * points. The max point is adjusted to be numerically above the min point, even if the resulting
         * azimuth value is greater than or equal to {@code 2pi}. An instance representing the full space
         * is returned if either point is infinite or min and max are equivalent as evaluated by the
         * given precision context.
         * @param min min azimuth value
         * @param max max azimuth value
         * @param precision precision precision context used to compare floating point values
         * @return a new instance resulting the angular region between the given min and max points
         * @throws GeometryException if either azimuth is infinite or NaN, or the given angular
         *      interval is not convex (meaning it has a size of greater than {@code pi})
         */
        public static Convex of(final Point1S min, final Point1S max, final DoublePrecisionContext precision) {
            return createInterval(min, max, precision, Convex::new, Convex.FULL);
        }

        /** Return an instance representing the convex angular interval between the given oriented points.
         * The negative-facing point is used as the minimum boundary and the positive-facing point is
         * adjusted to be above the minimum. The arguments can be given in any order. The full space
         * is returned if the points are equivalent or are oriented in the same direction.
         * @param a first oriented point
         * @param b second oriented point
         * @return an instance representing the angular interval between the given oriented points
         * @throws GeometryException if either azimuth is infinite or NaN, or the given angular
         *      interval is not convex (meaning it has a size of greater than {@code pi})
         */
        public static Convex of(final CutAngle a, final CutAngle b) {
            return createInterval(a, b, Convex::new, Convex.FULL);
        }
    }
}