Interval.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.euclidean.oned;
import java.text.MessageFormat;
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.core.Precision;
/** Class representing an interval in one dimension. The interval is defined
* by minimum and maximum values. One or both of these values may be infinite
* although not with the same sign.
*
* <p>Instances of this class are guaranteed to be immutable.</p>
*/
public final class Interval implements HyperplaneBoundedRegion<Vector1D> {
/** Interval instance representing the entire real number line. */
private static final Interval FULL = new Interval(null, null);
/** {@link OrientedPoint} instance representing the min boundary of the interval,
* or null if no min boundary exists. If present, this instance will be negative-facing.
* Infinite values are allowed but not NaN.
*/
private final OrientedPoint minBoundary;
/** {@link OrientedPoint} instance representing the max boundary of the interval,
* or null if no max boundary exists. If present, this instance will be negative-facing.
* Infinite values are allowed but not NaN.
*/
private final OrientedPoint maxBoundary;
/** Create an instance from min and max bounding hyperplanes. No validation is performed.
* Callers are responsible for ensuring that the given hyperplanes represent a valid
* interval.
* @param minBoundary the min (negative-facing) hyperplane
* @param maxBoundary the max (positive-facing) hyperplane
*/
private Interval(final OrientedPoint minBoundary, final OrientedPoint maxBoundary) {
this.minBoundary = minBoundary;
this.maxBoundary = maxBoundary;
}
/** Get the minimum value for the interval or {@link Double#NEGATIVE_INFINITY}
* if no minimum value exists.
* @return the minimum value for the interval or {@link Double#NEGATIVE_INFINITY}
* if no minimum value exists.
*/
public double getMin() {
return (minBoundary != null) ? minBoundary.getLocation() : Double.NEGATIVE_INFINITY;
}
/** Get the maximum value for the interval or {@link Double#POSITIVE_INFINITY}
* if no maximum value exists.
* @return the maximum value for the interval or {@link Double#POSITIVE_INFINITY}
* if no maximum value exists.
*/
public double getMax() {
return (maxBoundary != null) ? maxBoundary.getLocation() : Double.POSITIVE_INFINITY;
}
/**
* Get the {@link OrientedPoint} forming the minimum bounding hyperplane
* of the interval, or null if none exists. If present, This hyperplane
* is oriented to point in the negative direction.
* @return the hyperplane forming the minimum boundary of the interval or
* null if no minimum boundary exists
*/
public OrientedPoint getMinBoundary() {
return minBoundary;
}
/**
* Get the {@link OrientedPoint} forming the maximum bounding hyperplane
* of the interval, or null if none exists. If present, this hyperplane
* is oriented to point in the positive direction.
* @return the hyperplane forming the maximum boundary of the interval or
* null if no maximum boundary exists
*/
public OrientedPoint getMaxBoundary() {
return maxBoundary;
}
/** Return true if the interval has a minimum (lower) boundary.
* @return true if the interval has minimum (lower) boundary
*/
public boolean hasMinBoundary() {
return minBoundary != null;
}
/** Return true if the interval has a maximum (upper) boundary.
* @return true if the interval has maximum (upper) boundary
*/
public boolean hasMaxBoundary() {
return maxBoundary != null;
}
/** True if the region is infinite, meaning that at least one of the boundaries
* does not exist.
* @return true if the region is infinite
*/
@Override
public boolean isInfinite() {
return minBoundary == null || maxBoundary == null;
}
/** True if the region is finite, meaning that both the minimum and maximum
* boundaries exist and the region size is finite.
* @return true if the region is finite
*/
@Override
public boolean isFinite() {
return !isInfinite();
}
/** {@inheritDoc} */
@Override
public RegionLocation classify(final Vector1D pt) {
return classify(pt.getX());
}
/** Classify a point with respect to the interval.
* @param location the location to classify
* @return the classification of the point with respect to the interval
* @see #classify(Vector1D)
*/
public RegionLocation classify(final double location) {
final RegionLocation minLoc = classifyWithBoundary(location, minBoundary);
final RegionLocation maxLoc = classifyWithBoundary(location, maxBoundary);
if (minLoc == RegionLocation.BOUNDARY || maxLoc == RegionLocation.BOUNDARY) {
return RegionLocation.BOUNDARY;
} else if (minLoc == RegionLocation.INSIDE && maxLoc == RegionLocation.INSIDE) {
return RegionLocation.INSIDE;
}
return RegionLocation.OUTSIDE;
}
/** Classify the location using the given interval boundary, which may be null.
* @param location the location to classify
* @param boundary interval boundary to classify against
* @return the location of the point relative to the boundary
*/
private RegionLocation classifyWithBoundary(final double location, final OrientedPoint boundary) {
if (Double.isNaN(location)) {
return RegionLocation.OUTSIDE;
} else if (boundary == null) {
return RegionLocation.INSIDE;
} else {
final HyperplaneLocation hyperLoc = boundary.classify(location);
if (hyperLoc == HyperplaneLocation.ON) {
return RegionLocation.BOUNDARY;
} else if (hyperLoc == HyperplaneLocation.PLUS) {
return RegionLocation.OUTSIDE;
}
return RegionLocation.INSIDE;
}
}
/** Return true if the given point location is on the inside or boundary
* of the region.
* @param x the location to test
* @return true if the location is on the inside or boundary of the region
* @see #contains(org.apache.commons.geometry.core.Point)
*/
public boolean contains(final double x) {
return classify(x) != RegionLocation.OUTSIDE;
}
/** {@inheritDoc}
*
* <p>The point is projected onto the nearest interval boundary. When a point
* is on the inside of the interval and is equidistant from both boundaries,
* then the minimum boundary is selected. when a point is on the outside of the
* interval and is equidistant from both boundaries (as is the case for intervals
* representing a single point), then the boundary facing the point is returned,
* ensuring that the returned offset is positive.
* </p>
*/
@Override
public Vector1D project(final Vector1D pt) {
OrientedPoint boundary = null;
if (minBoundary != null && maxBoundary != null) {
// both boundaries are present; use the closest
final double minOffset = minBoundary.offset(pt.getX());
final double maxOffset = maxBoundary.offset(pt.getX());
final double minDist = Math.abs(minOffset);
final double maxDist = Math.abs(maxOffset);
// Project onto the max boundary if it's the closest or the point is on its plus side.
// Otherwise, project onto the min boundary.
if (maxDist < minDist || maxOffset > 0) {
boundary = maxBoundary;
} else {
boundary = minBoundary;
}
} else if (minBoundary != null) {
// only the min boundary is present
boundary = minBoundary;
} else if (maxBoundary != null) {
// only the max boundary is present
boundary = maxBoundary;
}
return (boundary != null) ? boundary.project(pt) : null;
}
/** Return a new instance transformed by the argument.
* @param transform transform to apply
* @return a new instance transformed by the argument
*/
public Interval transform(final Transform<Vector1D> transform) {
final OrientedPoint transformedMin = (minBoundary != null) ?
minBoundary.transform(transform) :
null;
final OrientedPoint transformedMax = (maxBoundary != null) ?
maxBoundary.transform(transform) :
null;
return of(transformedMin, transformedMax);
}
/** {@inheritDoc}
*
* <p>This method always returns false since there is always at least
* one point that can be classified as not being on the outside of
* the region.</p>
*/
@Override
public boolean isEmpty() {
return false;
}
/** {@inheritDoc} */
@Override
public boolean isFull() {
return minBoundary == null && maxBoundary == null;
}
/** {@inheritDoc} */
@Override
public double getSize() {
if (isInfinite()) {
return Double.POSITIVE_INFINITY;
}
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} */
@Override
public Vector1D getCentroid() {
if (isInfinite()) {
return null;
}
final double min = getMin();
final double max = getMax();
return Vector1D.of((0.5 * (max - min)) + min);
}
/** {@inheritDoc} */
@Override
public Split<Interval> split(final Hyperplane<Vector1D> splitter) {
final OrientedPoint splitOrientedPoint = (OrientedPoint) splitter;
final Vector1D splitPoint = splitOrientedPoint.getPoint();
final HyperplaneLocation splitterMinLoc = (minBoundary != null) ? minBoundary.classify(splitPoint) : null;
final HyperplaneLocation splitterMaxLoc = (maxBoundary != null) ? maxBoundary.classify(splitPoint) : null;
Interval low = null;
Interval high = null;
if (splitterMinLoc != HyperplaneLocation.ON || splitterMaxLoc != HyperplaneLocation.ON) {
if (splitterMinLoc != null && splitterMinLoc != HyperplaneLocation.MINUS) {
// splitter is on or below min boundary
high = this;
} else if (splitterMaxLoc != null && splitterMaxLoc != HyperplaneLocation.MINUS) {
// splitter is on or above max boundary
low = this;
} else {
// the interval is split in two
low = new Interval(minBoundary, OrientedPoints.createPositiveFacing(
splitPoint, splitOrientedPoint.getPrecision()));
high = new Interval(OrientedPoints.createNegativeFacing(
splitPoint, splitOrientedPoint.getPrecision()), maxBoundary);
}
}
// assign minus/plus based on the orientation of the splitter
final boolean lowIsMinus = splitOrientedPoint.isPositiveFacing();
final Interval minus = lowIsMinus ? low : high;
final Interval plus = lowIsMinus ? high : low;
return new Split<>(minus, plus);
}
/** Return a {@link RegionBSPTree1D} representing the same region as this instance.
* @return a BSP tree representing the same region
* @see RegionBSPTree1D#from(Interval, Interval...)
*/
public RegionBSPTree1D toTree() {
return RegionBSPTree1D.from(this);
}
/** {@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();
}
/** Create a new interval from the given point locations. The returned interval represents
* the region between the points, regardless of the order they are given as arguments.
* @param a first point location
* @param b second point location
* @param precision precision context used to compare floating point numbers
* @return a new interval representing the region between the given point locations
* @throws IllegalArgumentException if either number is {@link Double#NaN NaN} or the numbers
* are both infinite and have the same sign
*/
public static Interval of(final double a, final double b, final Precision.DoubleEquivalence precision) {
validateIntervalValues(a, b);
final double min = Math.min(a, b);
final double max = Math.max(a, b);
final OrientedPoint minBoundary = Double.isFinite(min) ?
OrientedPoints.fromLocationAndDirection(min, false, precision) :
null;
final OrientedPoint maxBoundary = Double.isFinite(max) ?
OrientedPoints.fromLocationAndDirection(max, true, precision) :
null;
if (minBoundary == null && maxBoundary == null) {
return FULL;
}
return new Interval(minBoundary, maxBoundary);
}
/** Create a new interval from the given points. The returned interval represents
* the region between the points, regardless of the order they are given as arguments.
* @param a first point
* @param b second point
* @param precision precision context used to compare floating point numbers
* @return a new interval representing the region between the given points
* @throws IllegalArgumentException if either point is {@link Vector1D#isNaN() NaN} or the points
* are both {@link Vector1D#isInfinite() infinite} and have the same sign
*/
public static Interval of(final Vector1D a, final Vector1D b, final Precision.DoubleEquivalence precision) {
return of(a.getX(), b.getX(), precision);
}
/** Create a new interval from the given hyperplanes. The hyperplanes may be given in
* any order but one must be positive-facing and the other negative-facing, with the positive-facing
* hyperplane located above the negative-facing hyperplane. Either or both argument may be null,
* in which case the returned interval will extend to infinity in the appropriate direction. If both
* arguments are null, an interval representing the full space is returned.
* @param a first hyperplane; may be null
* @param b second hyperplane; may be null
* @return a new interval representing the region between the given hyperplanes
* @throws IllegalArgumentException if the hyperplanes have the same orientation or
* do not form an interval (for example, if the positive-facing hyperplane is below
* the negative-facing hyperplane)
*/
public static Interval of(final OrientedPoint a, final OrientedPoint b) {
validateBoundaryRelationship(a, b);
final boolean hasA = a != null;
final boolean hasB = b != null;
if (!hasA && !hasB) {
// both boundaries null; return the full space
return FULL;
}
// determine the ordering of the hyperplanes; we know that at least one is non-null
final OrientedPoint minBoundary = ((hasA && !a.isPositiveFacing()) || (hasB && b.isPositiveFacing())) ? a : b;
final OrientedPoint maxBoundary = ((hasA && a.isPositiveFacing()) || (hasB && !b.isPositiveFacing())) ? a : b;
// validate the boundary locations; this will ensure that we don't have NaN values
final double minLoc = (minBoundary != null) ? minBoundary.getLocation() : Double.NEGATIVE_INFINITY;
final double maxLoc = (maxBoundary != null) ? maxBoundary.getLocation() : Double.POSITIVE_INFINITY;
validateIntervalValues(minLoc, maxLoc);
// create the interval, replacing infinites with nulls
return new Interval(
Double.isFinite(minLoc) ? minBoundary : null,
Double.isFinite(maxLoc) ? maxBoundary : null);
}
/** Return an interval with the given min value and no max.
* @param min min value for the interval
* @param precision precision context used to compare floating point numbers
* @return an interval with the given min value and no max.
*/
public static Interval min(final double min, final Precision.DoubleEquivalence precision) {
return of(min, Double.POSITIVE_INFINITY, precision);
}
/** Return an interval with the given max value and no min.
* @param max max value for the interval
* @param precision precision context used to compare floating point numbers
* @return an interval with the given max value and no min.
*/
public static Interval max(final double max, final Precision.DoubleEquivalence precision) {
return of(Double.NEGATIVE_INFINITY, max, precision);
}
/** Return an interval representing a single point at the given location.
* @param location the location of the interval
* @param precision precision context used to compare floating point numbers
* @return an interval representing a single point
*/
public static Interval point(final double location, final Precision.DoubleEquivalence precision) {
return of(location, location, precision);
}
/** Return an interval representing the entire real number line. The {@link #isFull()}
* method of the instance will return true.
* @return an interval representing the entire real number line
* @see #isFull()
*/
public static Interval full() {
return FULL;
}
/** Validate that the orientations and positions of the arguments may be used to create an interval.
* The arguments may be given in any order. Does nothing if one or both arguments are null.
* @param a first boundary; may be null
* @param b second boundary may be null
* @throws IllegalArgumentException is {@code a} and {@code b} have the same orientation or one does
* not lie on the plus side of the other.
*/
private static void validateBoundaryRelationship(final OrientedPoint a, final OrientedPoint b) {
if (a != null && b != null) {
if (a.isPositiveFacing() == b.isPositiveFacing()) {
throw new IllegalArgumentException(
MessageFormat.format("Invalid interval: hyperplanes have same orientation: {0}, {1}", a, b));
}
if (a.classify(b.getPoint()) == HyperplaneLocation.PLUS ||
b.classify(a.getPoint()) == HyperplaneLocation.PLUS) {
throw new IllegalArgumentException(
MessageFormat.format("Invalid interval: hyperplanes do not form interval: {0}, {1}", a, b));
}
}
}
/** Validate that the given value can be used to construct an interval. The values
* must not be NaN and if infinite, must have opposite signs.
* @param a first value
* @param b second value
* @throws IllegalArgumentException if either value is NaN or if both values are infinite
* and have the same sign
*/
private static void validateIntervalValues(final double a, final double b) {
if (Double.isNaN(a) || Double.isNaN(b) ||
(Double.isInfinite(a) && Double.compare(a, b) == 0)) {
throw new IllegalArgumentException(
MessageFormat.format("Invalid interval values: [{0}, {1}]", a, b));
}
}
}