AbstractBounds.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;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.function.ToDoubleFunction;
import org.apache.commons.geometry.core.partitioning.HyperplaneBoundedRegion;
import org.apache.commons.numbers.core.Precision;
/** Base class representing an axis-aligned bounding box with minimum and maximum bounding points.
* @param <P> Point implementation type
* @param <B> Bounds implementation type
*/
public abstract class AbstractBounds<
P extends EuclideanVector<P>,
B extends AbstractBounds<P, B>> {
/** Minimum point. */
private final P min;
/** Maximum point. */
private final P max;
/** Simple constructor. Callers are responsible for ensuring that all coordinate values are finite and
* that all values in {@code min} are less than or equal to their corresponding values in {@code max}.
* No validation is performed.
* @param min minimum point
* @param max maximum point
*/
protected AbstractBounds(final P min, final P max) {
this.min = min;
this.max = max;
}
/** Get the minimum point.
* @return the minimum point
*/
public P getMin() {
return min;
}
/** Get the maximum point.
* @return the maximum point
*/
public P getMax() {
return max;
}
/** Get the diagonal of the bounding box. The return value is a vector pointing from
* {@code min} to {@code max} and contains the size of the box along each coordinate axis.
* @return the diagonal vector of the bounding box
*/
public P getDiagonal() {
return min.vectorTo(max);
}
/** Get the centroid, or geometric center, of the bounding box.
* @return the centroid of the bounding box
*/
public P getCentroid() {
return min.lerp(max, 0.5);
}
/** Return true if the bounding box has non-zero size along each coordinate axis, as
* evaluated by the given precision context.
* @param precision precision context used for floating point comparisons
* @return true if the bounding box has non-zero size along each coordinate axis
*/
public abstract boolean hasSize(Precision.DoubleEquivalence precision);
/** Return true if the given point is strictly within or on the boundary of the bounding box.
* In other words, true if returned if <code>p<sub>t</sub> >= min<sub>t</sub></code> and
* <code>p<sub>t</sub> <= max<sub>t</sub></code> for each coordinate value <code>t</code>.
* Floating point comparisons are strict; values are considered equal only if they match exactly.
* @param pt the point to check
* @return true if the given point is strictly within or on the boundary of the instance
* @see #contains(EuclideanVector, Precision.DoubleEquivalence)
*/
public abstract boolean contains(P pt);
/** Return true if the given point is within or on the boundary of the bounding box, using the given
* precision context for floating point comparisons. This is similar to {@link #contains(EuclideanVector)}
* but allows points that may be strictly outside of the box due to floating point errors to be considered
* inside.
* @param pt the point to check
* @param precision precision context used to compare floating point values
* @return if the given point is within or on the boundary of the bounds, as determined
* by the given precision context
* @see #contains(EuclideanVector, Precision.DoubleEquivalence)
*/
public abstract boolean contains(P pt, Precision.DoubleEquivalence precision);
/** Return true if any point on the interior or boundary of this instance is also considered to be
* on the interior or boundary of the argument. Specifically, true is returned if
* <code>aMin<sub>t</sub> <= bMax<sub>t</sub></code> and <code>aMax<sub>t</sub> >= bMin<sub>t</sub></code>
* for all coordinate values {@code t}, where {@code a} is the current instance and {@code b} is the argument.
* Floating point comparisons are strict; values are considered equal only if they match exactly.
* @param other bounding box to intersect with
* @return true if the bounds intersect
*/
public abstract boolean intersects(B other);
/** Return the intersection of this bounding box and the argument, or null if no intersection exists.
* Floating point comparisons are strict; values are considered equal only if they match exactly. Note
* this this method may return bounding boxes with zero size in one or more coordinate axes.
* @param other bounding box to intersect with
* @return the intersection of this instance and the argument, or null if no such intersection
* exists
* @see #intersects(AbstractBounds)
*/
public abstract B intersection(B other);
/** Return a hyperplane-bounded region containing the same points as this instance.
* @param precision precision context used for floating point comparisons in the returned
* region instance
* @return a hyperplane-bounded region containing the same points as this instance
*/
public abstract HyperplaneBoundedRegion<P> toRegion(Precision.DoubleEquivalence precision);
/** Return true if the current instance and argument are considered equal as evaluated by the
* given precision context. Bounds are considered equal if they contain equivalent min and max
* points.
* @param other bounds to compare with
* @param precision precision context to compare floating point numbers
* @return true if this instance is equivalent to the argument, as evaluated by the given
* precision context
* @see EuclideanVector#eq(EuclideanVector, Precision.DoubleEquivalence)
*/
public boolean eq(final B other, final Precision.DoubleEquivalence precision) {
return min.eq(other.getMin(), precision) &&
max.eq(other.getMax(), precision);
}
/** {@inheritDoc} */
@Override
public String toString() {
final StringBuilder sb = new StringBuilder();
sb.append(getClass().getSimpleName())
.append("[min= ")
.append(min)
.append(", max= ")
.append(max)
.append(']');
return sb.toString();
}
/** Abstract internal class used to perform line convex subset intersection operations using the
* <a href="https://education.siggraph.org/static/HyperGraph/raytrace/rtinter3.htm">slabs algorithm</a>.
* Subclasses are expected to reference a line convex subset in their target dimension that is being
* evaluated against the bounding box. Access to the line and subset properties is facilitated through
* abstract methods.
* @param <S> Line segment type
* @param <I> Boundary intersection type
*/
protected abstract class BoundsLinecaster<S, I> {
/** Precision used for floating point comparisons. */
private final Precision.DoubleEquivalence precision;
/** Near slab intersection abscissa value. */
private double near = Double.NEGATIVE_INFINITY;
/** Far slab intersection abscissa value. */
private double far = Double.POSITIVE_INFINITY;
/** Construct a new instance that uses the given precision instance for floating
* point comparisons.
* @param precision precision instance for floating point comparisons
*/
protected BoundsLinecaster(final Precision.DoubleEquivalence precision) {
this.precision = precision;
}
/** Return {@code true} if the line convex subset shares any points with the
* bounding box.
* @return {@code true} if the line convex subset shares any points with the
* bounding box
*/
public boolean intersectsRegion() {
return computeNearFar() &&
precision.gte(getSubspaceEnd(), near) &&
precision.lte(getSubspaceStart(), far);
}
/** Get the segment containing all points shared by the line convex
* subset and the bounding box, or {@code null} if no points are shared.
* @return segment containing all points shared by the line convex
* subset and the bounding box, or {@code null} if no points are shared.
*/
public S getRegionIntersection() {
if (intersectsRegion()) {
final double start = Math.max(near, getSubspaceStart());
final double end = Math.min(far, getSubspaceEnd());
return createSegment(start, end);
}
return null;
}
/** Get the intersections between the line convex subset and the boundaries of the
* bounding box. An empty list is returned if there are no intersections.
* @return intersections between the line convex subset and the boundaries of the
* bounding box
*/
public List<I> getBoundaryIntersections() {
if (computeNearFar()) {
final int maxSize = min.getDimension() * 2;
final List<I> results = new ArrayList<>(maxSize);
addBoundaryIntersections(near, results);
if (!precision.eq(near, far)) {
addBoundaryIntersections(far, results);
}
results.sort(getBoundaryIntersectionComparator());
return results;
}
return Collections.emptyList();
}
/** Get an object representing the <em>first</em> intersection of the line convex subset
* with the boundaries of the bounding box. Null is returned if no such intersection exists.
* @return object representing the first intersection of the line convex subset with the
* boundaries of the bounding box, or {@code null} if no such intersection exists
*/
public I getFirstBoundaryIntersection() {
final List<I> results = getBoundaryIntersections();
return results.isEmpty() ?
null :
results.get(0);
}
/** Add a boundary intersection to {@code results} if the given point lies on
* one of the bounding box boundaries orthogonal to {@code dimPlusDir}.
* @param pt potential intersection point
* @param dimMinusDir minus direction for the dimension being evaluated
* @param dimPlusDir plus direction for the dimension being evaluated
* @param coordinateFn function used to access point coordinate values for
* the dimension being evaluated
* @param results list containing intersection results
*/
protected void addBoundaryIntersectionIfPresent(
final P pt,
final P dimMinusDir,
final P dimPlusDir,
final ToDoubleFunction<P> coordinateFn,
final List<I> results) {
// only include results for dimensions that are not considered
// parallel to the line, according to the precision
if (!precision.eqZero(getLineDir().dot(dimPlusDir))) {
final double coordinate = coordinateFn.applyAsDouble(pt);
final double dimMin = coordinateFn.applyAsDouble(min);
final double dimMax = coordinateFn.applyAsDouble(max);
if (precision.eq(coordinate, dimMin)) {
results.add(createBoundaryIntersection(pt, dimMinusDir));
}
if (precision.eq(coordinate, dimMax)) {
results.add(createBoundaryIntersection(pt, dimPlusDir));
}
}
}
/** Update the {@code near} and {@code far} slab intersection points with the
* intersection values for the coordinates returned by {@code coordinateFn}, returning
* {@code false} if the line is determined to not intersect the bounding box.
* @param coordinateFn function returning the coordinate for the dimension
* being evaluated
* @return {@code false} if the line is determined to not intersect the bounding
* box
*/
protected boolean updateNearFar(final ToDoubleFunction<P> coordinateFn) {
final double dir = coordinateFn.applyAsDouble(getLineDir());
final double origin = coordinateFn.applyAsDouble(getLineOrigin());
final double minCoord = coordinateFn.applyAsDouble(min);
final double maxCoord = coordinateFn.applyAsDouble(max);
double t1 = (minCoord - origin) / dir;
double t2 = (maxCoord - origin) / dir;
if (!Double.isFinite(t1) || !Double.isFinite(t2)) {
// the line is parallel to this dimension; only continue if the
// line origin lies between the min and max for this dimension
return precision.gte(origin, minCoord) && precision.lte(origin, maxCoord);
}
if (t1 > t2) {
final double temp = t1;
t1 = t2;
t2 = temp;
}
if (t1 > near) {
near = t1;
}
if (t2 < far) {
far = t2;
}
return precision.lte(near, far);
}
/** Create a line segment with the given start and end abscissas.
* @param startAbscissa start abscissa
* @param endAbscissa end abscissa
* @return line segment with the given start and end abscissas
*/
protected abstract S createSegment(double startAbscissa, double endAbscissa);
/** Construct a new boundary intersection instance.
* @param pt boundary intersection point
* @param normal boundary normal at the intersection
* @return a new boundary intersection instance
*/
protected abstract I createBoundaryIntersection(P pt, P normal);
/** Add all boundary intersections at the given line abscissa value to {@code results}.
* Subclasses should call {@link #addBoundaryIntersectionIfPresent} for each dimension
* in the target space.
* @param abscissa intersection abscissa
* @param results boundary intersection result list
*/
protected abstract void addBoundaryIntersections(double abscissa, List<I> results);
/** Get the comparator used to produce a standardized ordering of boundary intersection
* results.
* @return comparator used to store boundary intersections
*/
protected abstract Comparator<I> getBoundaryIntersectionComparator();
/** Compute the {@code near} and {@code far} slab intersection values for the
* line under test, returning {@code true} if the line intersects the bounding
* box. This method should call {@link #updateNearFar(ToDoubleFunction)} for each
* dimension in the space.
* @return {@code true} if the line intersects the bounding box
*/
protected abstract boolean computeNearFar();
/** Get the line direction.
* @return line direction
*/
protected abstract P getLineDir();
/** Get the line origin.
* @return line origin
*/
protected abstract P getLineOrigin();
/** Get the line convex subset start abscissa.
* @return line convex subset start abscissa
*/
protected abstract double getSubspaceStart();
/** Get the line convex subset end abscissa.
* @return line convex subset end abscissa
*/
protected abstract double getSubspaceEnd();
}
}