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.RegionLocation;
import org.apache.commons.geometry.core.Transform;
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.numbers.angle.Angle;
import org.apache.commons.numbers.core.Precision;
/** 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() :
0.0;
}
/** 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() :
Angle.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 #getCentroid()
*/
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 getCentroid() {
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 = CutAngles.createPositiveFacing(midpoint, minBoundary.getPrecision());
final CutAngle midNeg = CutAngles.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 IllegalArgumentException if either azimuth is infinite or NaN
*/
public static AngularInterval of(final double min, final double max,
final Precision.DoubleEquivalence 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 IllegalArgumentException if either azimuth is infinite or NaN
*/
public static AngularInterval of(final Point1S min, final Point1S max,
final Precision.DoubleEquivalence 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 IllegalArgumentException 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 IllegalArgumentException if either azimuth is infinite or NaN
*/
private static <T extends AngularInterval> T createInterval(final Point1S min, final Point1S max,
final Precision.DoubleEquivalence precision,
final BiFunction<? super CutAngle, ? super 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(
CutAngles.createNegativeFacing(min, precision),
CutAngles.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 IllegalArgumentException if either argument is infinite or NaN
*/
private static <T extends AngularInterval> T createInterval(final CutAngle a, final CutAngle b,
final BiFunction<? super CutAngle, ? super 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 = CutAngles.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 IllegalArgumentException if either point is infinite NaN
*/
private static void validateIntervalValues(final Point1S a, final Point1S b) {
if (!a.isFinite() || !b.isFinite()) {
throw new IllegalArgumentException(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 Precision.DoubleEquivalence precision = min.getPrecision();
return precision.lte(dist, Math.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<? super CutAngle, ? super 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 IllegalArgumentException if the interval is not convex
*/
private Convex(final CutAngle minBoundary, final CutAngle maxBoundary) {
super(minBoundary, maxBoundary);
if (!isConvex(minBoundary, maxBoundary)) {
throw new IllegalArgumentException(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 = CutAngles.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() + Angle.PI_OVER_TWO);
final int minLoc = minBoundary.getPrecision().compare(Angle.PI_OVER_TWO,
posPole.distance(minBoundary.getPoint()));
final int maxLoc = maxBoundary.getPrecision().compare(Angle.PI_OVER_TWO,
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()) < Angle.PI_OVER_TWO) {
// 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 IllegalArgumentException 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 Precision.DoubleEquivalence 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 IllegalArgumentException 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 Precision.DoubleEquivalence 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 IllegalArgumentException 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);
}
}
}