This is an automated email from the ASF dual-hosted git repository.
mattjuntunen pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-geometry.git
The following commit(s) were added to refs/heads/master by this push:
new 27b8d65a GEOMETRY-147: adding linecast and line intersection methods
to Bounds2D and Bounds3D
27b8d65a is described below
commit 27b8d65ad6900af39b6036d8a00dcd8d448c99ee
Author: Matt <[email protected]>
AuthorDate: Fri Apr 29 23:39:40 2022 -0400
GEOMETRY-147: adding linecast and line intersection methods to Bounds2D and
Bounds3D
---
.../commons/geometry/euclidean/AbstractBounds.java | 225 +++++++
.../geometry/euclidean/threed/Bounds3D.java | 172 ++++-
.../threed/line/EmbeddedTreeLineSubset3D.java | 7 +
.../euclidean/threed/line/LineConvexSubset3D.java | 10 +-
.../threed/line/LineSpanningSubset3D.java | 13 +-
.../euclidean/threed/line/LineSubset3D.java | 7 +
.../euclidean/threed/line/LinecastPoint3D.java | 3 +-
.../geometry/euclidean/threed/line/Ray3D.java | 19 +-
.../euclidean/threed/line/ReverseRay3D.java | 19 +-
.../geometry/euclidean/threed/line/Segment3D.java | 29 +-
.../commons/geometry/euclidean/twod/Bounds2D.java | 159 ++++-
.../euclidean/twod/EmbeddedTreeLineSubset.java | 12 +-
.../geometry/euclidean/twod/LineConvexSubset.java | 7 +
.../euclidean/twod/LineSpanningSubset.java | 7 -
.../geometry/euclidean/twod/LineSubset.java | 2 +-
.../commons/geometry/euclidean/twod/Ray.java | 26 +-
.../geometry/euclidean/twod/ReverseRay.java | 26 +-
.../commons/geometry/euclidean/twod/Segment.java | 30 +-
.../geometry/euclidean/threed/Bounds3DTest.java | 696 ++++++++++++++++++++-
.../threed/line/EmbeddedTreeLineSubset3DTest.java | 19 +
.../geometry/euclidean/twod/Bounds2DTest.java | 611 ++++++++++++++++++
.../jmh/euclidean/Bounds3DPerformance.java | 208 ++++++
22 files changed, 2213 insertions(+), 94 deletions(-)
diff --git
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/AbstractBounds.java
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/AbstractBounds.java
index 168fdd8e..6f1fbb8f 100644
---
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/AbstractBounds.java
+++
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/AbstractBounds.java
@@ -16,6 +16,12 @@
*/
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;
@@ -156,4 +162,223 @@ public abstract class AbstractBounds<
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();
+ }
}
diff --git
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/Bounds3D.java
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/Bounds3D.java
index 69be9f5a..9dcc3e42 100644
---
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/Bounds3D.java
+++
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/Bounds3D.java
@@ -17,9 +17,17 @@
package org.apache.commons.geometry.euclidean.threed;
import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
import java.util.Objects;
+import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.euclidean.AbstractBounds;
+import org.apache.commons.geometry.euclidean.threed.line.Line3D;
+import org.apache.commons.geometry.euclidean.threed.line.LineConvexSubset3D;
+import org.apache.commons.geometry.euclidean.threed.line.LinecastPoint3D;
+import org.apache.commons.geometry.euclidean.threed.line.Linecastable3D;
+import org.apache.commons.geometry.euclidean.threed.line.Segment3D;
import org.apache.commons.geometry.euclidean.threed.shape.Parallelepiped;
import org.apache.commons.numbers.core.Precision;
@@ -29,7 +37,8 @@ import org.apache.commons.numbers.core.Precision;
*
* <p>Instances of this class are guaranteed to be immutable.</p>
*/
-public final class Bounds3D extends AbstractBounds<Vector3D, Bounds3D> {
+public final class Bounds3D extends AbstractBounds<Vector3D, Bounds3D>
+ implements Linecastable3D {
/** Simple constructor. Callers are responsible for ensuring the min is
not greater than max.
* @param min minimum point
@@ -120,6 +129,66 @@ public final class Bounds3D extends
AbstractBounds<Vector3D, Bounds3D> {
return null; // no intersection
}
+ /** Return {@code true} if the region represented by this instance shares
any points with
+ * the given line. Floating point comparisons are made using the
+ * {@link Line3D#getPrecision() precision} of the line.
+ * @param line line to determine intersection with
+ * @return {@code true} if the region represented by this instance
intersects
+ * the given line
+ */
+ public boolean intersects(final Line3D line) {
+ return intersects(line.span());
+ }
+
+ /** Return {@code true} if the region represented by this instance shares
any points with
+ * the given line convex subset. Floating point comparisons are made using
the
+ * {@link Line3D#getPrecision() precision} of the subset's line.
+ * @param subset line convex subset to determine intersection with
+ * @return {@code true} if the region represented by this instance
intersects
+ * the given line convex subset
+ */
+ public boolean intersects(final LineConvexSubset3D subset) {
+ return new BoundsLinecaster3D(subset).intersectsRegion();
+ }
+
+ /** Return a {@link Segment3D} representing the intersection of the region
+ * represented by this instance with the given line or {@code null} if no
such
+ * intersection exists. Floating point comparisons are made using the
+ * {@link Line3D#getPrecision() precision} of the line.
+ * @param line line to intersect with
+ * @return {@link Segment3D} representing the intersection of the region
+ * represented by this instance with the given line or {@code null}
+ * if no such intersection exists
+ */
+ public Segment3D intersection(final Line3D line) {
+ return intersection(line.span());
+ }
+
+ /** Return a {@link Segment3D} representing the intersection of the region
+ * represented by this instance with the given line convex subset or
{@code null}
+ * if no such intersection exists. Floating point comparisons are made
using the
+ * {@link Line3D#getPrecision() precision} of the subset's line.
+ * @param subset line convex subset to intersect with
+ * @return {@link Segment3D} representing the intersection of the region
+ * represented by this instance with the given line convex subset or
{@code null}
+ * if no such intersection exists
+ */
+ public Segment3D intersection(final LineConvexSubset3D subset) {
+ return new BoundsLinecaster3D(subset).getRegionIntersection();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public List<LinecastPoint3D> linecast(final LineConvexSubset3D subset) {
+ return new BoundsLinecaster3D(subset).getBoundaryIntersections();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public LinecastPoint3D linecastFirst(final LineConvexSubset3D subset) {
+ return new BoundsLinecaster3D(subset).getFirstBoundaryIntersection();
+ }
+
/** {@inheritDoc}
*
* @throws IllegalArgumentException if any dimension of the bounding box
is zero
@@ -287,4 +356,105 @@ public final class Bounds3D extends
AbstractBounds<Vector3D, Bounds3D> {
return new Bounds3D(min, max);
}
}
+
+ /** Subclass of {@link BoundsLinecaster} for 3D space.
+ */
+ private final class BoundsLinecaster3D extends BoundsLinecaster<Segment3D,
LinecastPoint3D> {
+
+ /** Line convex subset to be tested against the bounds. */
+ private final LineConvexSubset3D subset;
+
+ /** Line instance for the subset being tested. */
+ private final Line3D line;
+
+ /** Construct a new instance for computing bounds intersection
information with
+ * the given line convex subset.
+ * @param subset line convex subset to compute intersection
information for
+ */
+ BoundsLinecaster3D(final LineConvexSubset3D subset) {
+ super(subset.getLine().getPrecision());
+
+ this.subset = subset;
+ this.line = subset.getLine();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected Segment3D createSegment(final double startAbscissa, final
double endAbscissa) {
+ return line.segment(startAbscissa, endAbscissa);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected LinecastPoint3D createBoundaryIntersection(final Vector3D
pt, final Vector3D normal) {
+ return new LinecastPoint3D(pt, normal, line);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected void addBoundaryIntersections(final double abscissa, final
List<LinecastPoint3D> results) {
+ if (subset.classifyAbscissa(abscissa) != RegionLocation.OUTSIDE) {
+ final Vector3D pt = line.toSpace(abscissa);
+
+ addBoundaryIntersectionIfPresent(
+ pt,
+ Vector3D.Unit.MINUS_X,
+ Vector3D.Unit.PLUS_X,
+ Vector3D::getX,
+ results);
+
+ addBoundaryIntersectionIfPresent(
+ pt,
+ Vector3D.Unit.MINUS_Y,
+ Vector3D.Unit.PLUS_Y,
+ Vector3D::getY,
+ results);
+
+ addBoundaryIntersectionIfPresent(
+ pt,
+ Vector3D.Unit.MINUS_Z,
+ Vector3D.Unit.PLUS_Z,
+ Vector3D::getZ,
+ results);
+ }
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected boolean computeNearFar() {
+ return updateNearFar(Vector3D::getX) &&
+ updateNearFar(Vector3D::getY) &&
+ updateNearFar(Vector3D::getZ);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected Comparator<LinecastPoint3D>
getBoundaryIntersectionComparator() {
+ return LinecastPoint3D.ABSCISSA_ORDER;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected Vector3D getLineDir() {
+ return line.getDirection();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected Vector3D getLineOrigin() {
+ return line.getOrigin();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected double getSubspaceStart() {
+ return subset.getSubspaceStart();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected double getSubspaceEnd() {
+ return subset.getSubspaceEnd();
+ }
+ }
}
diff --git
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/EmbeddedTreeLineSubset3D.java
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/EmbeddedTreeLineSubset3D.java
index 72466d90..18e78af4 100644
---
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/EmbeddedTreeLineSubset3D.java
+++
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/EmbeddedTreeLineSubset3D.java
@@ -19,6 +19,7 @@ package org.apache.commons.geometry.euclidean.threed.line;
import java.util.ArrayList;
import java.util.List;
+import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.core.Transform;
import org.apache.commons.geometry.euclidean.oned.Interval;
import org.apache.commons.geometry.euclidean.oned.RegionBSPTree1D;
@@ -104,6 +105,12 @@ public final class EmbeddedTreeLineSubset3D extends
LineSubset3D {
return null;
}
+ /** {@inheritDoc} */
+ @Override
+ public RegionLocation classifyAbscissa(final double abscissa) {
+ return region.classify(abscissa);
+ }
+
/** Transform this instance.
* @param transform the transform to apply
* @return a new, transformed instance
diff --git
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/LineConvexSubset3D.java
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/LineConvexSubset3D.java
index d3d9d4bc..dee15b40 100644
---
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/LineConvexSubset3D.java
+++
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/LineConvexSubset3D.java
@@ -16,6 +16,7 @@
*/
package org.apache.commons.geometry.euclidean.threed.line;
+import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.core.Transform;
import org.apache.commons.geometry.euclidean.oned.Interval;
import org.apache.commons.geometry.euclidean.threed.Vector3D;
@@ -79,7 +80,7 @@ public abstract class LineConvexSubset3D extends LineSubset3D
{
*/
public boolean contains(final Vector3D pt) {
final Line3D line = getLine();
- return line.contains(pt) && containsAbscissa(line.abscissa(pt));
+ return line.contains(pt) && classifyAbscissa(line.abscissa(pt)) !=
RegionLocation.OUTSIDE;
}
/** Transform this instance.
@@ -87,11 +88,4 @@ public abstract class LineConvexSubset3D extends
LineSubset3D {
* @return a new, transformed instance
*/
public abstract LineConvexSubset3D transform(Transform<Vector3D>
transform);
-
- /** Return true if the given abscissa value is contained in the line
subset (ie, in the subspace region
- * or one of its 1D boundaries).
- * @param abscissa abscissa to check
- * @return true if {@code abscissa} lies on the inside or boundary of the
subspace region
- */
- abstract boolean containsAbscissa(double abscissa);
}
diff --git
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/LineSpanningSubset3D.java
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/LineSpanningSubset3D.java
index 48ddfeca..9b3404b9 100644
---
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/LineSpanningSubset3D.java
+++
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/LineSpanningSubset3D.java
@@ -18,6 +18,7 @@ package org.apache.commons.geometry.euclidean.threed.line;
import java.text.MessageFormat;
+import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.core.Transform;
import org.apache.commons.geometry.euclidean.threed.Bounds3D;
import org.apache.commons.geometry.euclidean.threed.Vector3D;
@@ -117,6 +118,12 @@ final class LineSpanningSubset3D extends
LineConvexSubset3D {
return null; // infinite; no bounds
}
+ /** {@inheritDoc} */
+ @Override
+ public RegionLocation classifyAbscissa(final double abscissa) {
+ return RegionLocation.INSIDE;
+ }
+
/** {@inheritDoc} */
@Override
public LineSpanningSubset3D transform(final Transform<Vector3D> transform)
{
@@ -133,10 +140,4 @@ final class LineSpanningSubset3D extends
LineConvexSubset3D {
line.getOrigin(),
line.getDirection());
}
-
- /** {@inheritDoc} */
- @Override
- boolean containsAbscissa(final double abscissa) {
- return true;
- }
}
diff --git
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/LineSubset3D.java
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/LineSubset3D.java
index 2bea44e4..77da45e9 100644
---
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/LineSubset3D.java
+++
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/LineSubset3D.java
@@ -17,6 +17,7 @@
package org.apache.commons.geometry.euclidean.threed.line;
import org.apache.commons.geometry.core.RegionEmbedding;
+import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.core.Sized;
import org.apache.commons.geometry.core.partitioning.HyperplaneBoundedRegion;
import org.apache.commons.geometry.euclidean.oned.Vector1D;
@@ -75,4 +76,10 @@ public abstract class LineSubset3D implements
RegionEmbedding<Vector3D, Vector1D
*/
@Override
public abstract HyperplaneBoundedRegion<Vector1D> getSubspaceRegion();
+
+ /** Classify the given line abscissa value with respect to the subspace
region.
+ * @param abscissa the abscissa value to classify
+ * @return the region location of the line abscissa value
+ */
+ public abstract RegionLocation classifyAbscissa(double abscissa);
}
diff --git
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/LinecastPoint3D.java
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/LinecastPoint3D.java
index 33ddac76..cc519531 100644
---
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/LinecastPoint3D.java
+++
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/LinecastPoint3D.java
@@ -44,7 +44,8 @@ public class LinecastPoint3D extends
AbstractLinecastPoint<Vector3D, Vector3D.Un
return cmp;
};
- /** Construct a new instance from its components.
+ /** Construct a new instance from its components. Callers are responsible
for ensuring that
+ * {@code point} lies on the given line.
* @param point intersection point
* @param normal normal of the target boundary at the intersection point
* @param line intersecting line
diff --git
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/Ray3D.java
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/Ray3D.java
index 42df5849..469b8f19 100644
---
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/Ray3D.java
+++
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/Ray3D.java
@@ -16,6 +16,7 @@
*/
package org.apache.commons.geometry.euclidean.threed.line;
+import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.core.Transform;
import org.apache.commons.geometry.euclidean.threed.Bounds3D;
import org.apache.commons.geometry.euclidean.threed.Vector3D;
@@ -133,6 +134,18 @@ public final class Ray3D extends LineConvexSubset3D {
return getLine().getDirection();
}
+ /** {@inheritDoc} */
+ @Override
+ public RegionLocation classifyAbscissa(final double abscissa) {
+ final int cmp = getLine().getPrecision().compare(abscissa, start);
+ if (cmp < 0) {
+ return RegionLocation.OUTSIDE;
+ } else if (cmp == 0) {
+ return RegionLocation.BOUNDARY;
+ }
+ return RegionLocation.INSIDE;
+ }
+
/** {@inheritDoc} */
@Override
public Ray3D transform(final Transform<Vector3D> transform) {
@@ -155,10 +168,4 @@ public final class Ray3D extends LineConvexSubset3D {
return sb.toString();
}
-
- /** {@inheritDoc} */
- @Override
- boolean containsAbscissa(final double abscissa) {
- return getLine().getPrecision().gte(abscissa, start);
- }
}
diff --git
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/ReverseRay3D.java
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/ReverseRay3D.java
index 6e1e0ef0..3257b863 100644
---
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/ReverseRay3D.java
+++
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/ReverseRay3D.java
@@ -16,6 +16,7 @@
*/
package org.apache.commons.geometry.euclidean.threed.line;
+import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.core.Transform;
import org.apache.commons.geometry.euclidean.threed.Bounds3D;
import org.apache.commons.geometry.euclidean.threed.Vector3D;
@@ -127,6 +128,18 @@ public final class ReverseRay3D extends LineConvexSubset3D
{
return null; // infinite; no bounds
}
+ /** {@inheritDoc} */
+ @Override
+ public RegionLocation classifyAbscissa(final double abscissa) {
+ final int cmp = getLine().getPrecision().compare(abscissa, end);
+ if (cmp > 0) {
+ return RegionLocation.OUTSIDE;
+ } else if (cmp == 0) {
+ return RegionLocation.BOUNDARY;
+ }
+ return RegionLocation.INSIDE;
+ }
+
/** {@inheritDoc} */
@Override
public ReverseRay3D transform(final Transform<Vector3D> transform) {
@@ -149,10 +162,4 @@ public final class ReverseRay3D extends LineConvexSubset3D
{
return sb.toString();
}
-
- /** {@inheritDoc} */
- @Override
- boolean containsAbscissa(final double abscissa) {
- return getLine().getPrecision().lte(abscissa, end);
- }
}
diff --git
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/Segment3D.java
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/Segment3D.java
index e4695cfe..0cda311a 100644
---
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/Segment3D.java
+++
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/line/Segment3D.java
@@ -16,6 +16,7 @@
*/
package org.apache.commons.geometry.euclidean.threed.line;
+import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.core.Transform;
import org.apache.commons.geometry.euclidean.threed.Bounds3D;
import org.apache.commons.geometry.euclidean.threed.Vector3D;
@@ -122,6 +123,26 @@ public final class Segment3D extends LineConvexSubset3D {
.build();
}
+ /** {@inheritDoc} */
+ @Override
+ public RegionLocation classifyAbscissa(final double abscissa) {
+ final Precision.DoubleEquivalence precision = getLine().getPrecision();
+ final int startCmp = precision.compare(abscissa, start);
+ if (startCmp < 0) {
+ return RegionLocation.OUTSIDE;
+ } else if (startCmp == 0) {
+ return RegionLocation.BOUNDARY;
+ } else {
+ final int endCmp = precision.compare(abscissa, end);
+ if (endCmp > 0) {
+ return RegionLocation.OUTSIDE;
+ } else if (endCmp == 0) {
+ return RegionLocation.BOUNDARY;
+ }
+ return RegionLocation.INSIDE;
+ }
+ }
+
/** {@inheritDoc} */
@Override
public Segment3D transform(final Transform<Vector3D> transform) {
@@ -146,12 +167,4 @@ public final class Segment3D extends LineConvexSubset3D {
return sb.toString();
}
-
- /** {@inheritDoc} */
- @Override
- boolean containsAbscissa(final double abscissa) {
- final Precision.DoubleEquivalence precision = getLine().getPrecision();
- return precision.gte(abscissa, start) &&
- precision.lte(abscissa, end);
- }
}
diff --git
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Bounds2D.java
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Bounds2D.java
index 3f30ab13..4b6cec5f 100644
---
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Bounds2D.java
+++
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Bounds2D.java
@@ -17,8 +17,11 @@
package org.apache.commons.geometry.euclidean.twod;
import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
import java.util.Objects;
+import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.euclidean.AbstractBounds;
import org.apache.commons.geometry.euclidean.twod.shape.Parallelogram;
import org.apache.commons.numbers.core.Precision;
@@ -29,7 +32,8 @@ import org.apache.commons.numbers.core.Precision;
*
* <p>Instances of this class are guaranteed to be immutable.</p>
*/
-public final class Bounds2D extends AbstractBounds<Vector2D, Bounds2D> {
+public final class Bounds2D extends AbstractBounds<Vector2D, Bounds2D>
+ implements Linecastable2D {
/** Simple constructor. Callers are responsible for ensuring the min is
not greater than max.
* @param min minimum point
@@ -112,6 +116,66 @@ public final class Bounds2D extends
AbstractBounds<Vector2D, Bounds2D> {
return null; // no intersection
}
+ /** Return {@code true} if the region represented by this instance shares
any points with
+ * the given line. Floating point comparisons are made using the
+ * {@link Line#getPrecision() precision} of the line.
+ * @param line line to determine intersection with
+ * @return {@code true} if the region represented by this instance
intersects
+ * the given line
+ */
+ public boolean intersects(final Line line) {
+ return intersects(line.span());
+ }
+
+ /** Return {@code true} if the region represented by this instance shares
any points with
+ * the given line convex subset. Floating point comparisons are made using
the
+ * {@link Line#getPrecision() precision} of the subset's line.
+ * @param subset line convex subset to determine intersection with
+ * @return {@code true} if the region represented by this instance
intersects
+ * the given line convex subset
+ */
+ public boolean intersects(final LineConvexSubset subset) {
+ return new BoundsLinecaster2D(subset).intersectsRegion();
+ }
+
+ /** Return a {@link Segment} representing the intersection of the region
+ * represented by this instance with the given line or {@code null} if no
such
+ * intersection exists. Floating point comparisons are made using the
+ * {@link Line#getPrecision() precision} of the line.
+ * @param line line to intersect with
+ * @return {@link Segment} representing the intersection of the region
+ * represented by this instance with the given line or {@code null}
+ * if no such intersection exists
+ */
+ public Segment intersection(final Line line) {
+ return intersection(line.span());
+ }
+
+ /** Return a {@link Segment} representing the intersection of the region
+ * represented by this instance with the given line convex subset or
{@code null}
+ * if no such intersection exists. Floating point comparisons are made
using the
+ * {@link Line#getPrecision() precision} of the subset's line.
+ * @param subset line convex subset to intersect with
+ * @return {@link Segment} representing the intersection of the region
+ * represented by this instance with the given line convex subset or
{@code null}
+ * if no such intersection exists
+ */
+ public Segment intersection(final LineConvexSubset subset) {
+ return new BoundsLinecaster2D(subset).getRegionIntersection();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public List<LinecastPoint2D> linecast(final LineConvexSubset subset) {
+ return new BoundsLinecaster2D(subset).getBoundaryIntersections();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public LinecastPoint2D linecastFirst(final LineConvexSubset subset) {
+ return new BoundsLinecaster2D(subset).getFirstBoundaryIntersection();
+ }
+
/** {@inheritDoc}
*
* @throws IllegalArgumentException if any dimension of the bounding box
is zero
@@ -268,4 +332,97 @@ public final class Bounds2D extends
AbstractBounds<Vector2D, Bounds2D> {
return new Bounds2D(min, max);
}
}
+
+ /** Subclass of {@link BoundsLinecaster} for 2D space.
+ */
+ private final class BoundsLinecaster2D extends BoundsLinecaster<Segment,
LinecastPoint2D> {
+
+ /** Line convex subset to be tested against the bounds. */
+ private final LineConvexSubset subset;
+
+ /** Line instance for the subset being tested. */
+ private final Line line;
+
+ /** Construct a new instance for computing bounds intersection
information with
+ * the given line convex subset.
+ * @param subset line convex subset to compute intersection
information for
+ */
+ BoundsLinecaster2D(final LineConvexSubset subset) {
+ super(subset.getLine().getPrecision());
+
+ this.subset = subset;
+ this.line = subset.getLine();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected Segment createSegment(final double startAbscissa, final
double endAbscissa) {
+ return line.segment(startAbscissa, endAbscissa);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected LinecastPoint2D createBoundaryIntersection(final Vector2D
pt, final Vector2D normal) {
+ return new LinecastPoint2D(pt, normal, line);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected void addBoundaryIntersections(final double abscissa, final
List<LinecastPoint2D> results) {
+ if (subset.classifyAbscissa(abscissa) != RegionLocation.OUTSIDE) {
+ final Vector2D pt = line.toSpace(abscissa);
+
+ addBoundaryIntersectionIfPresent(
+ pt,
+ Vector2D.Unit.MINUS_X,
+ Vector2D.Unit.PLUS_X,
+ Vector2D::getX,
+ results);
+
+ addBoundaryIntersectionIfPresent(
+ pt,
+ Vector2D.Unit.MINUS_Y,
+ Vector2D.Unit.PLUS_Y,
+ Vector2D::getY,
+ results);
+ }
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected boolean computeNearFar() {
+ return updateNearFar(Vector2D::getX) &&
+ updateNearFar(Vector2D::getY);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected Comparator<LinecastPoint2D>
getBoundaryIntersectionComparator() {
+ return LinecastPoint2D.ABSCISSA_ORDER;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected Vector2D getLineDir() {
+ return line.getDirection();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected Vector2D getLineOrigin() {
+ return line.getOrigin();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected double getSubspaceStart() {
+ return subset.getSubspaceStart();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ protected double getSubspaceEnd() {
+ return subset.getSubspaceEnd();
+ }
+ }
}
diff --git
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/EmbeddedTreeLineSubset.java
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/EmbeddedTreeLineSubset.java
index 8e94faf5..2539f174 100644
---
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/EmbeddedTreeLineSubset.java
+++
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/EmbeddedTreeLineSubset.java
@@ -156,6 +156,12 @@ public final class EmbeddedTreeLineSubset extends
LineSubset {
return region;
}
+ /** {@inheritDoc} */
+ @Override
+ public RegionLocation classifyAbscissa(final double abscissa) {
+ return region.classify(abscissa);
+ }
+
/** {@inheritDoc}
*
* <p>In all cases, the current instance is not modified. However, In
order to avoid
@@ -243,10 +249,4 @@ public final class EmbeddedTreeLineSubset extends
LineSubset {
return sb.toString();
}
-
- /** {@inheritDoc} */
- @Override
- RegionLocation classifyAbscissa(final double abscissa) {
- return region.classify(abscissa);
- }
}
diff --git
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/LineConvexSubset.java
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/LineConvexSubset.java
index 11a8db16..408fd8ef 100644
---
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/LineConvexSubset.java
+++
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/LineConvexSubset.java
@@ -19,6 +19,7 @@ package org.apache.commons.geometry.euclidean.twod;
import java.util.Collections;
import java.util.List;
+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.HyperplaneConvexSubset;
@@ -116,6 +117,12 @@ public abstract class LineConvexSubset extends LineSubset
implements HyperplaneC
return line.toSpace(closestAbscissa(abscissa));
}
+ /** {@inheritDoc} */
+ @Override
+ public RegionLocation classifyAbscissa(final double abscissa) {
+ return RegionLocation.INSIDE;
+ }
+
/** {@inheritDoc} */
@Override
public abstract LineConvexSubset transform(Transform<Vector2D> transform);
diff --git
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/LineSpanningSubset.java
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/LineSpanningSubset.java
index c99ed3cb..c0251fd6 100644
---
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/LineSpanningSubset.java
+++
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/LineSpanningSubset.java
@@ -18,7 +18,6 @@ package org.apache.commons.geometry.euclidean.twod;
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.Split;
@@ -149,12 +148,6 @@ final class LineSpanningSubset extends LineConvexSubset {
line.getDirection());
}
- /** {@inheritDoc} */
- @Override
- RegionLocation classifyAbscissa(final double abscissa) {
- return RegionLocation.INSIDE;
- }
-
/** {@inheritDoc} */
@Override
double closestAbscissa(final double abscissa) {
diff --git
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/LineSubset.java
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/LineSubset.java
index ef1e60fd..a56a4c0f 100644
---
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/LineSubset.java
+++
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/LineSubset.java
@@ -131,7 +131,7 @@ public abstract class LineSubset implements
HyperplaneSubset<Vector2D>, RegionEm
* @param abscissa the abscissa value to classify
* @return the region location of the line abscissa value
*/
- abstract RegionLocation classifyAbscissa(double abscissa);
+ public abstract RegionLocation classifyAbscissa(double abscissa);
/** Get a split result for cases where no intersection exists between the
splitting line and the
* line underlying the given line subset. This occurs when the two lines
are parallel or coincident.
diff --git
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Ray.java
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Ray.java
index 3c97e44c..5a58cf56 100644
---
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Ray.java
+++
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Ray.java
@@ -149,6 +149,19 @@ public final class Ray extends LineConvexSubset {
return new ReverseRay(getLine().reverse(), startPoint);
}
+ /** {@inheritDoc} */
+ @Override
+ public RegionLocation classifyAbscissa(final double abscissa) {
+ final int cmp = getPrecision().compare(abscissa, getSubspaceStart());
+ if (cmp > 0) {
+ return RegionLocation.INSIDE;
+ } else if (cmp == 0) {
+ return RegionLocation.BOUNDARY;
+ }
+
+ return RegionLocation.OUTSIDE;
+ }
+
/** {@inheritDoc} */
@Override
public String toString() {
@@ -163,19 +176,6 @@ public final class Ray extends LineConvexSubset {
return sb.toString();
}
- /** {@inheritDoc} */
- @Override
- RegionLocation classifyAbscissa(final double abscissa) {
- final int cmp = getPrecision().compare(abscissa, getSubspaceStart());
- if (cmp > 0) {
- return RegionLocation.INSIDE;
- } else if (cmp == 0) {
- return RegionLocation.BOUNDARY;
- }
-
- return RegionLocation.OUTSIDE;
- }
-
/** {@inheritDoc} */
@Override
double closestAbscissa(final double abscissa) {
diff --git
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/ReverseRay.java
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/ReverseRay.java
index d36756fc..86080124 100644
---
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/ReverseRay.java
+++
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/ReverseRay.java
@@ -144,6 +144,19 @@ public final class ReverseRay extends LineConvexSubset {
return new Ray(getLine().reverse(), endPoint);
}
+ /** {@inheritDoc} */
+ @Override
+ public RegionLocation classifyAbscissa(final double abscissa) {
+ final int cmp = getPrecision().compare(abscissa, getSubspaceEnd());
+ if (cmp < 0) {
+ return RegionLocation.INSIDE;
+ } else if (cmp == 0) {
+ return RegionLocation.BOUNDARY;
+ }
+
+ return RegionLocation.OUTSIDE;
+ }
+
/** {@inheritDoc} */
@Override
public String toString() {
@@ -158,19 +171,6 @@ public final class ReverseRay extends LineConvexSubset {
return sb.toString();
}
- /** {@inheritDoc} */
- @Override
- RegionLocation classifyAbscissa(final double abscissa) {
- final int cmp = getPrecision().compare(abscissa, getSubspaceEnd());
- if (cmp < 0) {
- return RegionLocation.INSIDE;
- } else if (cmp == 0) {
- return RegionLocation.BOUNDARY;
- }
-
- return RegionLocation.OUTSIDE;
- }
-
/** {@inheritDoc} */
@Override
double closestAbscissa(final double abscissa) {
diff --git
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Segment.java
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Segment.java
index 0be6054a..a93ea809 100644
---
a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Segment.java
+++
b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Segment.java
@@ -141,21 +141,7 @@ public final class Segment extends LineConvexSubset {
/** {@inheritDoc} */
@Override
- public String toString() {
- final StringBuilder sb = new StringBuilder();
- sb.append(getClass().getSimpleName())
- .append("[startPoint= ")
- .append(getStartPoint())
- .append(", endPoint= ")
- .append(getEndPoint())
- .append(']');
-
- return sb.toString();
- }
-
- /** {@inheritDoc} */
- @Override
- RegionLocation classifyAbscissa(final double abscissa) {
+ public RegionLocation classifyAbscissa(final double abscissa) {
final Precision.DoubleEquivalence precision = getPrecision();
final int startCmp = precision.compare(abscissa, getSubspaceStart());
if (startCmp > 0) {
@@ -172,6 +158,20 @@ public final class Segment extends LineConvexSubset {
return RegionLocation.OUTSIDE;
}
+ /** {@inheritDoc} */
+ @Override
+ public String toString() {
+ final StringBuilder sb = new StringBuilder();
+ sb.append(getClass().getSimpleName())
+ .append("[startPoint= ")
+ .append(getStartPoint())
+ .append(", endPoint= ")
+ .append(getEndPoint())
+ .append(']');
+
+ return sb.toString();
+ }
+
/** {@inheritDoc} */
@Override
double closestAbscissa(final double abscissa) {
diff --git
a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/Bounds3DTest.java
b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/Bounds3DTest.java
index aada5a4e..d753dcec 100644
---
a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/Bounds3DTest.java
+++
b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/Bounds3DTest.java
@@ -18,14 +18,25 @@ package org.apache.commons.geometry.euclidean.threed;
import java.util.ArrayList;
import java.util.Arrays;
+import java.util.Collection;
import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
import java.util.function.BiFunction;
import java.util.function.ToDoubleFunction;
import java.util.regex.Pattern;
import org.apache.commons.geometry.core.GeometryTestUtils;
+import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
+import org.apache.commons.geometry.euclidean.threed.line.Line3D;
+import org.apache.commons.geometry.euclidean.threed.line.LineConvexSubset3D;
+import org.apache.commons.geometry.euclidean.threed.line.LinecastPoint3D;
+import org.apache.commons.geometry.euclidean.threed.line.Lines3D;
+import org.apache.commons.geometry.euclidean.threed.line.Segment3D;
+import
org.apache.commons.geometry.euclidean.threed.rotation.QuaternionRotation;
import org.apache.commons.geometry.euclidean.threed.shape.Parallelepiped;
+import org.apache.commons.numbers.angle.Angle;
import org.apache.commons.numbers.core.Precision;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
@@ -410,6 +421,498 @@ class Bounds3DTest {
Assertions.assertFalse(b4.eq(b1, high));
}
+ @Test
+ void testLinecast_intersectsFace() {
+ // -- arrange
+ // use unequal face sizes so that our test lines do not end up passing
through
+ // a vertex on the opposite side
+ final Bounds3D bounds = Bounds3D.from(Vector3D.of(-0.9, -2, -3),
Vector3D.of(0.9, 2, 3));
+
+ // -- act/assert
+ checkLinecastIntersectingFace(bounds, Vector3D.of(0.9, 0, 0),
Vector3D.Unit.PLUS_X);
+ checkLinecastIntersectingFace(bounds, Vector3D.of(-0.9, 0, 0),
Vector3D.Unit.MINUS_X);
+
+ checkLinecastIntersectingFace(bounds, Vector3D.of(0, 2, 0),
Vector3D.Unit.PLUS_Y);
+ checkLinecastIntersectingFace(bounds, Vector3D.of(0, -2, 0),
Vector3D.Unit.MINUS_Y);
+
+ checkLinecastIntersectingFace(bounds, Vector3D.of(0, 0, 3),
Vector3D.Unit.PLUS_Z);
+ checkLinecastIntersectingFace(bounds, Vector3D.of(0, 0, -3),
Vector3D.Unit.MINUS_Z);
+ }
+
+ private void checkLinecastIntersectingFace(
+ final Bounds3D bounds,
+ final Vector3D facePt,
+ final Vector3D normal) {
+
+ // -- arrange
+ final Vector3D offset = normal.multiply(1.2);
+ final Parallelepiped region = bounds.toRegion(TEST_PRECISION);
+
+ EuclideanTestUtils.permute(-1, 1, 0.5, (x, y, z) -> {
+ final Vector3D otherPt = facePt
+ .add(Vector3D.of(x, y, z))
+ .add(offset);
+ final Line3D line = Lines3D.fromPoints(otherPt, facePt,
TEST_PRECISION);
+
+ final LinecastPoint3D reversePt =
region.linecastFirst(line.reverse());
+
+ // -- act/assert
+ linecastChecker(bounds)
+ .expect(facePt, normal)
+ .and(reversePt.getPoint(), reversePt.getNormal())
+ .whenGiven(line);
+
+ linecastChecker(bounds)
+ .and(reversePt.getPoint(), reversePt.getNormal())
+ .expect(facePt, normal)
+ .whenGiven(line.reverse());
+ });
+ }
+
+ @Test
+ void testLinecast_intersectsSingleVertex() {
+ // -- arrange
+ final Bounds3D bounds = Bounds3D.from(Vector3D.ZERO, Vector3D.of(1, 1,
1));
+
+ // -- act/assert
+ checkLinecastIntersectingSingleVertex(bounds, Vector3D.ZERO);
+ checkLinecastIntersectingSingleVertex(bounds, Vector3D.of(0, 0, 1));
+ checkLinecastIntersectingSingleVertex(bounds, Vector3D.of(0, 1, 0));
+ checkLinecastIntersectingSingleVertex(bounds, Vector3D.of(0, 1, 1));
+ checkLinecastIntersectingSingleVertex(bounds, Vector3D.of(1, 0, 0));
+ checkLinecastIntersectingSingleVertex(bounds, Vector3D.of(1, 0, 1));
+ checkLinecastIntersectingSingleVertex(bounds, Vector3D.of(1, 1, 0));
+ checkLinecastIntersectingSingleVertex(bounds, Vector3D.of(1, 1, 1));
+ }
+
+ private void checkLinecastIntersectingSingleVertex(
+ final Bounds3D bounds,
+ final Vector3D vertex) {
+
+ // -- arrange
+ final Vector3D centerToVertex =
vertex.subtract(bounds.getCentroid()).normalize();
+ final Vector3D baseLineDir = centerToVertex.orthogonal();
+
+ final int runCnt = 10;
+ for (double a = 0; a < Angle.TWO_PI; a += Angle.TWO_PI / runCnt) {
+
+ // construct a line orthogonal to the vector from the bounds
center to the vertex and passing
+ // through the vertex
+ final Vector3D lineDir =
QuaternionRotation.fromAxisAngle(centerToVertex, a).apply(baseLineDir);
+ final Line3D line = Lines3D.fromPointAndDirection(vertex, lineDir,
TEST_PRECISION);
+
+ // construct possible normals for this vertex
+ final List<Vector3D> normals = new ArrayList<>();
+
normals.add(centerToVertex.project(Vector3D.Unit.PLUS_X).normalize());
+
normals.add(centerToVertex.project(Vector3D.Unit.PLUS_Y).normalize());
+
normals.add(centerToVertex.project(Vector3D.Unit.PLUS_Z).normalize());
+
+ normals.sort(Vector3D.COORDINATE_ASCENDING_ORDER);
+
+ // create the checker and populate it with the normals of faces
that are not parallel to
+ // the line
+ final BoundsLinecastChecker3D checker = linecastChecker(bounds);
+ for (final Vector3D normal : normals) {
+ if (!TEST_PRECISION.eqZero(normal.dot(lineDir))) {
+ checker.expect(vertex, normal);
+ }
+ }
+
+ // -- act/assert
+ checker.whenGiven(line)
+ .whenGiven(line.reverse());
+ }
+ }
+
+ @Test
+ void testLinecast_vertexToVertex() {
+ // -- arrange
+ final Vector3D min = Vector3D.ZERO;
+ final Vector3D max = Vector3D.of(1, 1, 1);
+
+ final Bounds3D bounds = Bounds3D.from(min, max);
+ final Line3D line = Lines3D.fromPoints(min, max, TEST_PRECISION);
+
+ // -- act/assert
+ linecastChecker(bounds)
+ .expect(min, Vector3D.Unit.MINUS_X)
+ .and(min, Vector3D.Unit.MINUS_Y)
+ .and(min, Vector3D.Unit.MINUS_Z)
+ .and(max, Vector3D.Unit.PLUS_Z)
+ .and(max, Vector3D.Unit.PLUS_Y)
+ .and(max, Vector3D.Unit.PLUS_X)
+ .whenGiven(line);
+ }
+
+ @Test
+ void testLinecast_edgeToEdge() {
+ // -- arrange
+ final Vector3D min = Vector3D.of(0, 0, 0);
+ final Vector3D max = Vector3D.of(1, 1, 1);
+
+ final Bounds3D bounds = Bounds3D.from(min, max);
+
+ final Vector3D start = Vector3D.of(0, 0, 0.5);
+ final Vector3D end = Vector3D.of(1, 1, 0.5);
+
+ final Line3D line = Lines3D.fromPoints(start, end, TEST_PRECISION);
+
+ // -- act/assert
+ linecastChecker(bounds)
+ .expect(start, Vector3D.Unit.MINUS_X)
+ .and(start, Vector3D.Unit.MINUS_Y)
+ .and(end, Vector3D.Unit.PLUS_Y)
+ .and(end, Vector3D.Unit.PLUS_X)
+ .whenGiven(line);
+ }
+
+ @Test
+ void testLinecast_alongFace() {
+ // -- arrange
+ final Vector3D min = Vector3D.ZERO;
+ final Vector3D max = Vector3D.of(1, 1, 1);
+
+ final Bounds3D bounds = Bounds3D.from(min, max);
+
+ final int cnt = 10;
+ for (double x = min.getX();
+ x <= max.getX();
+ x += bounds.getDiagonal().getX() / cnt) {
+
+ final Vector3D start = Vector3D.of(x, min.getY(), max.getZ());
+ final Vector3D end = Vector3D.of(x, max.getY(), max.getZ());
+
+ final Line3D line = Lines3D.fromPoints(start, end, TEST_PRECISION);
+
+ // -- act/assert
+ linecastChecker(bounds)
+ .expect(start, Vector3D.Unit.MINUS_Y)
+ .and(end, Vector3D.Unit.PLUS_Y)
+ .whenGiven(line);
+ }
+ }
+
+ @Test
+ void testLinecast_noIntersection() {
+ // -- arrange
+ final Bounds3D bounds = Bounds3D.from(Vector3D.ZERO, Vector3D.of(1, 1,
1));
+
+ // -- act/assert
+ checkLinecastNoIntersection(bounds, Vector3D.ZERO);
+ checkLinecastNoIntersection(bounds, Vector3D.of(0, 0, 1));
+ checkLinecastNoIntersection(bounds, Vector3D.of(0, 1, 0));
+ checkLinecastNoIntersection(bounds, Vector3D.of(0, 1, 1));
+ checkLinecastNoIntersection(bounds, Vector3D.of(1, 0, 0));
+ checkLinecastNoIntersection(bounds, Vector3D.of(1, 0, 1));
+ checkLinecastNoIntersection(bounds, Vector3D.of(1, 1, 0));
+ checkLinecastNoIntersection(bounds, Vector3D.of(1, 1, 1));
+ }
+
+ private void checkLinecastNoIntersection(
+ final Bounds3D bounds,
+ final Vector3D vertex) {
+
+ // -- arrange
+ final Vector3D toVertex = bounds.getCentroid().directionTo(vertex);
+ final Vector3D baseLineDir = toVertex.orthogonal();
+
+ final Vector3D offsetVertex = vertex.add(toVertex);
+
+ final Line3D plusXLine = Lines3D.fromPointAndDirection(offsetVertex,
Vector3D.Unit.PLUS_X, TEST_PRECISION);
+ final Line3D plusYLine = Lines3D.fromPointAndDirection(offsetVertex,
Vector3D.Unit.PLUS_Y, TEST_PRECISION);
+ final Line3D plusZLine = Lines3D.fromPointAndDirection(offsetVertex,
Vector3D.Unit.PLUS_Z, TEST_PRECISION);
+
+ final BoundsLinecastChecker3D emptyChecker = linecastChecker(bounds)
+ .expectNothing();
+
+ // -- act/assert
+ // check axis-aligned lines
+ emptyChecker
+ .whenGiven(plusXLine)
+ .whenGiven(plusYLine)
+ .whenGiven(plusZLine);
+
+ // check lines orthogonal to the axis
+ final int runCnt = 10;
+ for (double a = 0; a < Angle.TWO_PI; a += Angle.TWO_PI / runCnt) {
+ final Vector3D lineDir =
QuaternionRotation.fromAxisAngle(toVertex, a).apply(baseLineDir);
+ final Line3D line = Lines3D.fromPointAndDirection(offsetVertex,
lineDir, TEST_PRECISION);
+
+ emptyChecker.whenGiven(line);
+ }
+ }
+
+ @Test
+ void testLinecast_nonSpan() {
+ // -- arrange
+ final Vector3D min = Vector3D.ZERO;
+ final Vector3D max = Vector3D.of(1, 1, 1);
+
+ final Bounds3D bounds = Bounds3D.from(min, max);
+
+ final Vector3D centroid = bounds.getCentroid();
+
+ final Vector3D start = Vector3D.of(max.getX(), centroid.getY(),
centroid.getZ());
+ final Vector3D end = Vector3D.of(min.getX(), centroid.getY(),
centroid.getZ());
+
+ final Line3D line = Lines3D.fromPoints(start, end, TEST_PRECISION);
+
+ // -- act/assert
+ linecastChecker(bounds)
+ .expect(end, Vector3D.Unit.MINUS_X)
+ .whenGiven(line.rayFrom(-0.5));
+
+ linecastChecker(bounds)
+ .expect(start, Vector3D.Unit.PLUS_X)
+ .whenGiven(line.reverseRayTo(-0.5));
+
+ linecastChecker(bounds)
+ .expectNothing()
+ .whenGiven(line.segment(-0.9, -0.1));
+
+ linecastChecker(bounds)
+ .expect(end, Vector3D.Unit.MINUS_X)
+ .whenGiven(line.segment(-0.9, 0.1));
+
+ linecastChecker(bounds)
+ .expect(start, Vector3D.Unit.PLUS_X)
+ .whenGiven(line.segment(-1.1, -0.1));
+
+ linecastChecker(bounds)
+ .expect(start, Vector3D.Unit.PLUS_X)
+ .expect(end, Vector3D.Unit.MINUS_X)
+ .whenGiven(line.segment(-1.1, 0.1));
+ }
+
+ @Test
+ void testLinecast_subsetEndpointOnBounds() {
+ // -- arrange
+ final Vector3D min = Vector3D.ZERO;
+ final Vector3D max = Vector3D.of(1, 1, 1);
+
+ final Bounds3D bounds = Bounds3D.from(min, max);
+
+ final Vector3D centroid = bounds.getCentroid();
+
+ final Vector3D start = Vector3D.of(max.getX(), centroid.getY(),
centroid.getZ());
+ final Vector3D end = Vector3D.of(min.getX(), centroid.getY(),
centroid.getZ());
+
+ final Line3D line = Lines3D.fromPoints(start, end, TEST_PRECISION);
+
+ // -- act/assert
+ linecastChecker(bounds)
+ .expect(end, Vector3D.Unit.MINUS_X)
+ .whenGiven(line.rayFrom(0));
+
+ linecastChecker(bounds)
+ .expect(end, Vector3D.Unit.MINUS_X)
+ .whenGiven(line.segment(0, 1));
+
+ linecastChecker(bounds)
+ .expect(start, Vector3D.Unit.PLUS_X)
+ .whenGiven(line.reverseRayTo(-1));
+
+ linecastChecker(bounds)
+ .expect(start, Vector3D.Unit.PLUS_X)
+ .whenGiven(line.segment(-2, -1));
+ }
+
+ @Test
+ void testLinecast_usesLinePrecision() {
+ // -- arrange
+ final double withinEps = 0.9 * TEST_EPS;
+ final double outsideEps = 1.1 * TEST_EPS;
+
+ final Vector3D min = Vector3D.ZERO;
+ final Vector3D max = Vector3D.of(1, 1, 1);
+
+ final Bounds3D bounds = Bounds3D.from(min, max);
+
+ final Vector3D centroid = bounds.getCentroid();
+
+ final Vector3D centerStart = Vector3D.of(max.getX(), centroid.getY(),
centroid.getZ());
+ final Vector3D centerEnd = Vector3D.of(min.getX(), centroid.getY(),
centroid.getZ());
+
+ final Line3D centerLine = Lines3D.fromPoints(centerStart, centerEnd,
TEST_PRECISION);
+
+ final Vector3D faceStart = Vector3D.of(max.getX() + withinEps,
max.getY() + withinEps, min.getZ());
+ final Vector3D faceEnd = Vector3D.of(max.getX() + withinEps,
max.getY() + withinEps, max.getZ());
+
+ final Line3D faceLine = Lines3D.fromPoints(faceStart, faceEnd,
TEST_PRECISION);
+
+ // -- act/assert
+ linecastChecker(bounds)
+ .expect(centerEnd, Vector3D.Unit.MINUS_X)
+ .whenGiven(centerLine.rayFrom(withinEps));
+
+ linecastChecker(bounds)
+ .expectNothing()
+ .whenGiven(centerLine.rayFrom(outsideEps));
+
+ linecastChecker(bounds)
+ .expect(centerStart, Vector3D.Unit.PLUS_X)
+ .expect(centerEnd, Vector3D.Unit.MINUS_X)
+ .whenGiven(centerLine.segment(-1 + withinEps, -withinEps));
+
+ linecastChecker(bounds)
+ .expectNothing()
+ .whenGiven(centerLine.segment(-1 + outsideEps, -outsideEps));
+
+ linecastChecker(bounds)
+ .expect(faceStart, Vector3D.Unit.MINUS_Z)
+ .expect(faceEnd, Vector3D.Unit.PLUS_Z)
+ .whenGiven(faceLine.segment(withinEps, 1 - withinEps));
+
+ linecastChecker(bounds)
+ .expectNothing()
+ .whenGiven(faceLine.segment(outsideEps, 1 - outsideEps));
+ }
+
+ @Test
+ void testLinecast_boundsHasNoSize() {
+ // -- arrange
+ final Vector3D pt = Vector3D.of(1, 2, 3);
+
+ final Bounds3D bounds = Bounds3D.from(pt, pt);
+
+ final Line3D diagonalLine = Lines3D.fromPointAndDirection(pt,
Vector3D.of(1, 1, 1), TEST_PRECISION);
+
+ final Line3D plusXLine = Lines3D.fromPointAndDirection(pt,
Vector3D.Unit.PLUS_X, TEST_PRECISION);
+
+ // -- act/assert
+ linecastChecker(bounds)
+ .expect(pt, Vector3D.Unit.MINUS_X)
+ .expect(pt, Vector3D.Unit.MINUS_Y)
+ .expect(pt, Vector3D.Unit.MINUS_Z)
+ .expect(pt, Vector3D.Unit.PLUS_Z)
+ .expect(pt, Vector3D.Unit.PLUS_Y)
+ .expect(pt, Vector3D.Unit.PLUS_X)
+ .whenGiven(diagonalLine);
+
+ linecastChecker(bounds)
+ .expect(pt, Vector3D.Unit.MINUS_X)
+ .expect(pt, Vector3D.Unit.PLUS_X)
+ .whenGiven(plusXLine);
+ }
+
+ @Test
+ void testLineIntersection() {
+ // -- arrange
+ final Vector3D min = Vector3D.ZERO;
+ final Vector3D max = Vector3D.of(1, 1, 1);
+
+ final Vector3D insideMin = Vector3D.of(0.1, 0.1, 0.1);
+ final Vector3D insideMax = Vector3D.of(0.9, 0.9, 0.9);
+
+ final Vector3D outsideMin = Vector3D.of(-0.1, -0.1, -0.1);
+ final Vector3D outsideMax = Vector3D.of(1.1, 1.1, 1.1);
+
+ final Bounds3D bounds = Bounds3D.from(min, max);
+
+ final Line3D diagonal = Lines3D.fromPoints(min, max, TEST_PRECISION);
+
+ // -- act/assert
+ assertLineIntersection(bounds, diagonal, min, max);
+
+ assertLineIntersection(bounds, diagonal.segment(outsideMin,
outsideMax), min, max);
+ assertLineIntersection(bounds, diagonal.segment(outsideMin,
insideMax), min, insideMax);
+ assertLineIntersection(bounds, diagonal.segment(insideMin,
outsideMax), insideMin, max);
+ assertLineIntersection(bounds, diagonal.segment(insideMin, insideMax),
insideMin, insideMax);
+
+ assertLineIntersection(bounds, diagonal.rayFrom(min), min, max);
+ assertLineIntersection(bounds, diagonal.reverseRayTo(min), min, min);
+
+ assertLineIntersection(bounds, diagonal.rayFrom(max), max, max);
+ assertLineIntersection(bounds, diagonal.reverseRayTo(max), min, max);
+
+ assertLineIntersection(bounds, diagonal.rayFrom(insideMax), insideMax,
max);
+ assertLineIntersection(bounds, diagonal.reverseRayTo(insideMax), min,
insideMax);
+ }
+
+ @Test
+ void testLineIntersection_noIntersection() {
+ // -- arrange
+ final Bounds3D bounds = Bounds3D.from(Vector3D.ZERO, Vector3D.of(1, 1,
1));
+
+ final Line3D plusXLine =
+ Lines3D.fromPointAndDirection(bounds.getCentroid(),
Vector3D.Unit.PLUS_X, TEST_PRECISION);
+
+ // -- act/assert
+ checkLineNoIntersection(bounds, Vector3D.ZERO);
+ checkLineNoIntersection(bounds, Vector3D.of(0, 0, 1));
+ checkLineNoIntersection(bounds, Vector3D.of(0, 1, 0));
+ checkLineNoIntersection(bounds, Vector3D.of(0, 1, 1));
+ checkLineNoIntersection(bounds, Vector3D.of(1, 0, 0));
+ checkLineNoIntersection(bounds, Vector3D.of(1, 0, 1));
+ checkLineNoIntersection(bounds, Vector3D.of(1, 1, 0));
+ checkLineNoIntersection(bounds, Vector3D.of(1, 1, 1));
+
+ assertNoLineIntersection(bounds, plusXLine.segment(-0.2, -0.1));
+ assertNoLineIntersection(bounds, plusXLine.reverseRayTo(-0.1));
+
+ assertNoLineIntersection(bounds, plusXLine.segment(1.1, 1.2));
+ assertNoLineIntersection(bounds, plusXLine.rayFrom(1.1));
+ }
+
+ private void checkLineNoIntersection(
+ final Bounds3D bounds,
+ final Vector3D vertex) {
+
+ // -- arrange
+ final Vector3D toVertex = bounds.getCentroid().directionTo(vertex);
+ final Vector3D baseLineDir = toVertex.orthogonal();
+
+ final Vector3D offsetVertex = vertex.add(toVertex);
+
+ final Line3D plusXLine = Lines3D.fromPointAndDirection(offsetVertex,
Vector3D.Unit.PLUS_X, TEST_PRECISION);
+ final Line3D plusYLine = Lines3D.fromPointAndDirection(offsetVertex,
Vector3D.Unit.PLUS_Y, TEST_PRECISION);
+ final Line3D plusZLine = Lines3D.fromPointAndDirection(offsetVertex,
Vector3D.Unit.PLUS_Z, TEST_PRECISION);
+
+ // -- act/assert
+ // check axis-aligned lines
+ assertNoLineIntersection(bounds, plusXLine);
+ assertNoLineIntersection(bounds, plusYLine);
+ assertNoLineIntersection(bounds, plusZLine);
+
+ // check lines orthogonal to the axis
+ final int runCnt = 10;
+ for (double a = 0; a < Angle.TWO_PI; a += Angle.TWO_PI / runCnt) {
+ final Vector3D lineDir =
QuaternionRotation.fromAxisAngle(toVertex, a).apply(baseLineDir);
+ final Line3D line = Lines3D.fromPointAndDirection(offsetVertex,
lineDir, TEST_PRECISION);
+
+ assertNoLineIntersection(bounds, line);
+ }
+ }
+
+ @Test
+ void testLineIntersection_boundsHasNoSize() {
+ // -- arrange
+ final Vector3D pt = Vector3D.of(1, 2, 3);
+
+ final Bounds3D bounds = Bounds3D.from(pt, pt);
+
+ final Line3D plusXLine = Lines3D.fromPointAndDirection(pt,
Vector3D.Unit.PLUS_X, TEST_PRECISION);
+
+ // -- act/assert
+ assertLineIntersection(bounds, plusXLine, pt, pt);
+ assertLineIntersection(bounds, plusXLine.rayFrom(pt), pt, pt);
+ }
+
+ @Test
+ void testLineIntersection_lineAlmostParallel() {
+ // -- arrange
+ final Vector3D min = Vector3D.of(1e150, -1, -1);
+ final Vector3D max = Vector3D.of(1.1e150, 1, 1);
+
+ final Bounds3D bounds = Bounds3D.from(min, max);
+
+ final Vector3D lineDir = Vector3D.of(1, -5e-11, 0);
+ final Line3D line = Lines3D.fromPointAndDirection(Vector3D.ZERO,
lineDir, TEST_PRECISION);
+
+ // -- act
+ assertNoLineIntersection(bounds, line);
+ }
+
@Test
void testHashCode() {
// arrange
@@ -519,15 +1022,204 @@ class Bounds3DTest {
EuclideanTestUtils.assertCoordinatesEqual(max, b.getMax(), TEST_EPS);
}
- private static void assertContainsStrict(final Bounds3D bounds, final
boolean contains, final Vector3D... pts) {
+ private static void assertContainsStrict(
+ final Bounds3D bounds,
+ final boolean contains,
+ final Vector3D... pts) {
for (final Vector3D pt : pts) {
Assertions.assertEquals(contains, bounds.contains(pt), "Unexpected
location for point " + pt);
}
}
- private static void assertContainsWithPrecision(final Bounds3D bounds,
final boolean contains, final Vector3D... pts) {
+ private static void assertContainsWithPrecision(
+ final Bounds3D bounds,
+ final boolean contains,
+ final Vector3D... pts) {
for (final Vector3D pt : pts) {
Assertions.assertEquals(contains, bounds.contains(pt,
TEST_PRECISION), "Unexpected location for point " + pt);
}
}
+
+ private static void assertLineIntersection(
+ final Bounds3D bounds,
+ final Line3D line,
+ final Vector3D start,
+ final Vector3D end) {
+ final Segment3D segment = bounds.intersection(line);
+
+ Assertions.assertSame(line, segment.getLine());
+ assertSegment(segment, start, end);
+
+ Assertions.assertTrue(bounds.intersects(line));
+ }
+
+ private static void assertLineIntersection(
+ final Bounds3D bounds,
+ final LineConvexSubset3D subset,
+ final Vector3D start,
+ final Vector3D end) {
+ final Segment3D segment = bounds.intersection(subset);
+
+ Assertions.assertSame(subset.getLine(), segment.getLine());
+ assertSegment(segment, start, end);
+
+ Assertions.assertTrue(bounds.intersects(subset));
+ }
+
+ private static void assertNoLineIntersection(
+ final Bounds3D bounds,
+ final Line3D line) {
+ Assertions.assertNull(bounds.intersection(line));
+ Assertions.assertFalse(bounds.intersects(line));
+ }
+
+ private static void assertNoLineIntersection(
+ final Bounds3D bounds,
+ final LineConvexSubset3D subset) {
+ Assertions.assertNull(bounds.intersection(subset));
+ Assertions.assertFalse(bounds.intersects(subset));
+ }
+
+ private static void assertSegment(final Segment3D segment, final Vector3D
start, final Vector3D end) {
+ EuclideanTestUtils.assertCoordinatesEqual(start,
segment.getStartPoint(), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(end, segment.getEndPoint(),
TEST_EPS);
+ }
+
+ private static BoundsLinecastChecker3D linecastChecker(final Bounds3D
bounds) {
+ return new BoundsLinecastChecker3D(bounds);
+ }
+
+ /**
+ * Internal test class used to perform and verify linecast operations.
+ */
+ private static final class BoundsLinecastChecker3D {
+
+ private final Bounds3D bounds;
+
+ private final Parallelepiped region;
+
+ private final LinecastChecker3D checker;
+
+ BoundsLinecastChecker3D(final Bounds3D bounds) {
+ this.bounds = bounds;
+ this.region = bounds.hasSize(TEST_PRECISION) ?
+ bounds.toRegion(TEST_PRECISION) :
+ null;
+ this.checker = LinecastChecker3D.with(bounds);
+ }
+
+ public BoundsLinecastChecker3D expectNothing() {
+ checker.expectNothing();
+ return this;
+ }
+
+ public BoundsLinecastChecker3D expect(final Vector3D pt, final
Vector3D normal) {
+ checker.expect(pt, normal);
+ return this;
+ }
+
+ public BoundsLinecastChecker3D and(final Vector3D pt, final Vector3D
normal) {
+ return expect(pt, normal);
+ }
+
+ public BoundsLinecastChecker3D whenGiven(final Line3D line) {
+ // perform the standard checks
+ checker.whenGiven(line);
+
+ // check that the returned points are equivalent to those returned
by linecasting against
+ // the region
+ final List<LinecastPoint3D> boundsResults = bounds.linecast(line);
+
+ if (region != null) {
+ assertLinecastElements(region.linecast(line),
bounds.linecast(line));
+ }
+
+ // check consistency with the intersects method; having linecast
results guarantees
+ // that we intersect the bounds but not vice versa
+ if (!boundsResults.isEmpty()) {
+ Assertions.assertTrue(bounds.intersects(line),
+ () -> "Linecast result is inconsistent with intersects
method: line= " + line);
+
+ assertLinecastResultsConsistentWithSegment(boundsResults,
bounds.intersection(line));
+ }
+
+ return this;
+ }
+
+ public BoundsLinecastChecker3D whenGiven(final LineConvexSubset3D
subset) {
+ // perform the standard checks
+ checker.whenGiven(subset);
+
+ // check that the returned points are equivalent to those returned
by linecasting against
+ // the region
+ final List<LinecastPoint3D> boundsResults =
bounds.linecast(subset);
+
+ if (region != null) {
+ assertLinecastElements(region.linecast(subset), boundsResults);
+ }
+
+ // check consistency with the intersects methods; having linecast
results guarantees
+ // that we intersect the bounds but not vice versa
+ if (!boundsResults.isEmpty()) {
+ Assertions.assertTrue(bounds.intersects(subset),
+ () -> "Linecast result is inconsistent with intersects
method: line subset= " + subset);
+
+ assertLinecastResultsConsistentWithSegment(boundsResults,
bounds.intersection(subset));
+ }
+
+ return this;
+ }
+
+ /** Assert that the two collections contain the same linecast points
and that the elements
+ * of {@code actual} are arranged in ascending abscissa order. Note
that this does <em>not</em>
+ * assert that {@code expected} and {@code actual} have the same exact
ordering, since the
+ * specific ordering if sensitive to floating point errors.
+ * @param expected expected collection
+ * @param actual actual collection
+ */
+ private void assertLinecastElements(
+ final Collection<LinecastPoint3D> expected,
+ final Collection<LinecastPoint3D> actual) {
+ Assertions.assertEquals(expected.size(), actual.size(),
"Unexpected list size");
+
+ // create a sorted copy
+ final List<LinecastPoint3D> sortedList = new ArrayList<>(actual);
+ sortedList.sort(LinecastPoint3D.ABSCISSA_ORDER);
+
+ // check element membership
+ for (final LinecastPoint3D expectedPt : expected) {
+ final Iterator<LinecastPoint3D> sortedIt =
sortedList.iterator();
+
+ boolean found = false;
+ while (sortedIt.hasNext()) {
+ if (expectedPt.eq(sortedIt.next(), TEST_PRECISION)) {
+ found = true;
+ break;
+ }
+ }
+
+ if (!found) {
+ Assertions.fail("Missing expected linecast point " +
expectedPt);
+ }
+ }
+
+ // check the order
+ Assertions.assertEquals(sortedList, actual);
+ }
+
+ /** Assert that the linecast results are consistent with the given
segment, which is taken
+ * to be the intersection of a line or line convex subset with the
bounding box.
+ * @param linecastResults
+ * @param segment
+ */
+ private void assertLinecastResultsConsistentWithSegment(
+ final List<LinecastPoint3D> linecastResults,
+ final Segment3D segment) {
+
+ for (final LinecastPoint3D pt : linecastResults) {
+ Assertions.assertEquals(RegionLocation.BOUNDARY,
segment.classifyAbscissa(pt.getAbscissa()),
+ () -> "Expected linecast point to lie on segment
boundary");
+ }
+ }
+ }
}
diff --git
a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/line/EmbeddedTreeLineSubset3DTest.java
b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/line/EmbeddedTreeLineSubset3DTest.java
index 4e99598b..d0ef401a 100644
---
a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/line/EmbeddedTreeLineSubset3DTest.java
+++
b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/line/EmbeddedTreeLineSubset3DTest.java
@@ -19,6 +19,7 @@ package org.apache.commons.geometry.euclidean.threed.line;
import java.util.List;
import org.apache.commons.geometry.core.GeometryTestUtils;
+import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.core.Transform;
import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
import org.apache.commons.geometry.euclidean.oned.Interval;
@@ -114,6 +115,8 @@ class EmbeddedTreeLineSubset3DTest {
Assertions.assertEquals(0, empty.getSize(), TEST_EPS);
Assertions.assertNull(empty.getCentroid());
Assertions.assertNull(empty.getBounds());
+
+ Assertions.assertEquals(RegionLocation.OUTSIDE,
empty.classifyAbscissa(0));
}
@Test
@@ -129,6 +132,10 @@ class EmbeddedTreeLineSubset3DTest {
GeometryTestUtils.assertPositiveInfinity(half.getSize());
Assertions.assertNull(half.getCentroid());
Assertions.assertNull(half.getBounds());
+
+ Assertions.assertEquals(RegionLocation.OUTSIDE,
half.classifyAbscissa(0));
+ Assertions.assertEquals(RegionLocation.BOUNDARY,
half.classifyAbscissa(1));
+ Assertions.assertEquals(RegionLocation.INSIDE,
half.classifyAbscissa(2));
}
@Test
@@ -151,6 +158,18 @@ class EmbeddedTreeLineSubset3DTest {
final Bounds3D bounds = sub.getBounds();
EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(-2, -2, 1),
bounds.getMin(), TEST_EPS);
EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 1, 1),
bounds.getMax(), TEST_EPS);
+
+ Assertions.assertEquals(RegionLocation.OUTSIDE,
sub.classifyAbscissa(-10));
+ Assertions.assertEquals(RegionLocation.BOUNDARY,
sub.classifyAbscissa(-2 * sqrt2));
+ Assertions.assertEquals(RegionLocation.INSIDE,
sub.classifyAbscissa(-1.5 * sqrt2));
+ Assertions.assertEquals(RegionLocation.BOUNDARY,
sub.classifyAbscissa(-sqrt2));
+ Assertions.assertEquals(RegionLocation.OUTSIDE,
sub.classifyAbscissa(-1.1));
+
+ Assertions.assertEquals(RegionLocation.OUTSIDE,
sub.classifyAbscissa(-0.1));
+ Assertions.assertEquals(RegionLocation.BOUNDARY,
sub.classifyAbscissa(0));
+ Assertions.assertEquals(RegionLocation.INSIDE,
sub.classifyAbscissa(0.1));
+ Assertions.assertEquals(RegionLocation.BOUNDARY,
sub.classifyAbscissa(sqrt2));
+ Assertions.assertEquals(RegionLocation.OUTSIDE,
sub.classifyAbscissa(2));
}
@Test
diff --git
a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/Bounds2DTest.java
b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/Bounds2DTest.java
index 17cf4979..7cac2b3d 100644
---
a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/Bounds2DTest.java
+++
b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/Bounds2DTest.java
@@ -18,13 +18,18 @@ package org.apache.commons.geometry.euclidean.twod;
import java.util.ArrayList;
import java.util.Arrays;
+import java.util.Collection;
import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
import java.util.function.BiFunction;
import java.util.function.ToDoubleFunction;
import java.util.regex.Pattern;
import org.apache.commons.geometry.core.GeometryTestUtils;
+import org.apache.commons.geometry.core.RegionLocation;
import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
+import org.apache.commons.geometry.euclidean.twod.rotation.Rotation2D;
import org.apache.commons.geometry.euclidean.twod.shape.Parallelogram;
import org.apache.commons.numbers.core.Precision;
import org.junit.jupiter.api.Assertions;
@@ -381,6 +386,429 @@ class Bounds2DTest {
Assertions.assertFalse(b4.eq(b1, high));
}
+ @Test
+ void testLinecast_intersectsSide() {
+ // -- arrange
+ // use unequal side sizes so that our test lines do not end up passing
through
+ // a vertex on the opposite side
+ final Bounds2D bounds = Bounds2D.from(Vector2D.of(-0.9, -2),
Vector2D.of(0.9, 2));
+
+ // -- act/assert
+ checkLinecastIntersectingSide(bounds, Vector2D.of(0.9, 0),
Vector2D.Unit.PLUS_X);
+ checkLinecastIntersectingSide(bounds, Vector2D.of(-0.9, 0),
Vector2D.Unit.MINUS_X);
+
+ checkLinecastIntersectingSide(bounds, Vector2D.of(0, 2),
Vector2D.Unit.PLUS_Y);
+ checkLinecastIntersectingSide(bounds, Vector2D.of(0, -2),
Vector2D.Unit.MINUS_Y);
+ }
+
+ private void checkLinecastIntersectingSide(
+ final Bounds2D bounds,
+ final Vector2D sidePt,
+ final Vector2D normal) {
+
+ // -- arrange
+ final Vector2D offset = normal.multiply(1.2);
+ final Parallelogram region = bounds.toRegion(TEST_PRECISION);
+
+ EuclideanTestUtils.permute(-1, 1, 0.5, (x, y) -> {
+ final Vector2D otherPt = sidePt
+ .add(Vector2D.of(x, y))
+ .add(offset);
+ final Line line = Lines.fromPoints(otherPt, sidePt,
TEST_PRECISION);
+
+ final LinecastPoint2D reversePt =
region.linecastFirst(line.reverse());
+
+ // -- act/assert
+ linecastChecker(bounds)
+ .expect(sidePt, normal)
+ .and(reversePt.getPoint(), reversePt.getNormal())
+ .whenGiven(line);
+
+ linecastChecker(bounds)
+ .and(reversePt.getPoint(), reversePt.getNormal())
+ .expect(sidePt, normal)
+ .whenGiven(line.reverse());
+ });
+ }
+
+ @Test
+ void testLinecast_intersectsSingleVertex() {
+ // -- arrange
+ final Bounds2D bounds = Bounds2D.from(Vector2D.ZERO, Vector2D.of(1,
1));
+
+ // -- act/assert
+ checkLinecastIntersectingSingleVertex(bounds, Vector2D.ZERO);
+ checkLinecastIntersectingSingleVertex(bounds, Vector2D.of(0, 1));
+ checkLinecastIntersectingSingleVertex(bounds, Vector2D.of(1, 0));
+ checkLinecastIntersectingSingleVertex(bounds, Vector2D.of(1, 1));
+ }
+
+ private void checkLinecastIntersectingSingleVertex(
+ final Bounds2D bounds,
+ final Vector2D vertex) {
+
+ // -- arrange
+ final Vector2D centerToVertex =
vertex.subtract(bounds.getCentroid()).normalize();
+
+ final Vector2D lineDir = centerToVertex.orthogonal();
+ final Line line = Lines.fromPointAndDirection(vertex, lineDir,
TEST_PRECISION);
+
+ // construct possible normals for this vertex
+ final List<Vector2D> normals = new ArrayList<>();
+ normals.add(centerToVertex.project(Vector2D.Unit.PLUS_X).normalize());
+ normals.add(centerToVertex.project(Vector2D.Unit.PLUS_Y).normalize());
+
+ normals.sort(Vector2D.COORDINATE_ASCENDING_ORDER);
+
+ final BoundsLinecastChecker2D checker = linecastChecker(bounds);
+ for (final Vector2D normal : normals) {
+ checker.expect(vertex, normal);
+ }
+
+ // -- act/assert
+ checker
+ .whenGiven(line)
+ .whenGiven(line.reverse());
+ }
+
+ @Test
+ void testLinecast_vertexToVertex() {
+ // -- arrange
+ final Vector2D min = Vector2D.ZERO;
+ final Vector2D max = Vector2D.of(1, 1);
+
+ final Bounds2D bounds = Bounds2D.from(min, max);
+ final Line line = Lines.fromPoints(min, max, TEST_PRECISION);
+
+ // -- act/assert
+ linecastChecker(bounds)
+ .expect(min, Vector2D.Unit.MINUS_X)
+ .and(min, Vector2D.Unit.MINUS_Y)
+ .and(max, Vector2D.Unit.PLUS_Y)
+ .and(max, Vector2D.Unit.PLUS_X)
+ .whenGiven(line);
+ }
+
+ @Test
+ void testLinecast_alongSide() {
+ // -- arrange
+ final Vector2D min = Vector2D.ZERO;
+ final Vector2D max = Vector2D.of(1, 1);
+
+ final Bounds2D bounds = Bounds2D.from(min, max);
+
+ final int cnt = 10;
+ for (double x = min.getX();
+ x <= max.getX();
+ x += bounds.getDiagonal().getX() / cnt) {
+
+ final Vector2D start = Vector2D.of(x, min.getY());
+ final Vector2D end = Vector2D.of(x, max.getY());
+
+ final Line line = Lines.fromPoints(start, end, TEST_PRECISION);
+
+ // -- act/assert
+ linecastChecker(bounds)
+ .expect(start, Vector2D.Unit.MINUS_Y)
+ .and(end, Vector2D.Unit.PLUS_Y)
+ .whenGiven(line);
+ }
+ }
+
+ @Test
+ void testLinecast_noIntersection() {
+ // -- arrange
+ final Bounds2D bounds = Bounds2D.from(Vector2D.ZERO, Vector2D.of(1,
1));
+
+ // -- act/assert
+ checkLinecastNoIntersection(bounds, Vector2D.ZERO);
+ checkLinecastNoIntersection(bounds, Vector2D.of(0, 1));
+ checkLinecastNoIntersection(bounds, Vector2D.of(1, 0));
+ checkLinecastNoIntersection(bounds, Vector2D.of(1, 1));
+ }
+
+ private void checkLinecastNoIntersection(
+ final Bounds2D bounds,
+ final Vector2D vertex) {
+
+ // -- arrange
+ final Vector2D toVertex = bounds.getCentroid().directionTo(vertex);
+
+ final Vector2D offsetVertex = vertex.add(toVertex);
+
+ final Line plusXLine = Lines.fromPointAndDirection(offsetVertex,
Vector2D.Unit.PLUS_X, TEST_PRECISION);
+ final Line plusYLine = Lines.fromPointAndDirection(offsetVertex,
Vector2D.Unit.PLUS_Y, TEST_PRECISION);
+
+ final BoundsLinecastChecker2D emptyChecker = linecastChecker(bounds)
+ .expectNothing();
+
+ // -- act/assert
+ // check axis-aligned lines
+ emptyChecker
+ .whenGiven(plusXLine)
+ .whenGiven(plusYLine);
+
+ // check slightly rotated lines
+ final Rotation2D rot = Rotation2D.of(0.1 * Math.PI);
+ emptyChecker
+ .whenGiven(plusXLine.transform(rot))
+ .whenGiven(plusYLine.transform(rot));
+ }
+
+ @Test
+ void testLinecast_nonSpan() {
+ // -- arrange
+ final Vector2D min = Vector2D.ZERO;
+ final Vector2D max = Vector2D.of(1, 1);
+
+ final Bounds2D bounds = Bounds2D.from(min, max);
+
+ final Vector2D centroid = bounds.getCentroid();
+
+ final Vector2D start = Vector2D.of(max.getX(), centroid.getY());
+ final Vector2D end = Vector2D.of(min.getX(), centroid.getY());
+
+ final Line line = Lines.fromPoints(start, end, TEST_PRECISION);
+
+ // -- act/assert
+ linecastChecker(bounds)
+ .expect(end, Vector2D.Unit.MINUS_X)
+ .whenGiven(line.rayFrom(-0.5));
+
+ linecastChecker(bounds)
+ .expect(start, Vector2D.Unit.PLUS_X)
+ .whenGiven(line.reverseRayTo(-0.5));
+
+ linecastChecker(bounds)
+ .expectNothing()
+ .whenGiven(line.segment(-0.9, -0.1));
+
+ linecastChecker(bounds)
+ .expect(end, Vector2D.Unit.MINUS_X)
+ .whenGiven(line.segment(-0.9, 0.1));
+
+ linecastChecker(bounds)
+ .expect(start, Vector2D.Unit.PLUS_X)
+ .whenGiven(line.segment(-1.1, -0.1));
+
+ linecastChecker(bounds)
+ .expect(start, Vector2D.Unit.PLUS_X)
+ .expect(end, Vector2D.Unit.MINUS_X)
+ .whenGiven(line.segment(-1.1, 0.1));
+ }
+
+ @Test
+ void testLinecast_subsetEndpointOnBounds() {
+ // -- arrange
+ final Vector2D min = Vector2D.ZERO;
+ final Vector2D max = Vector2D.of(1, 1);
+
+ final Bounds2D bounds = Bounds2D.from(min, max);
+
+ final Vector2D centroid = bounds.getCentroid();
+
+ final Vector2D start = Vector2D.of(max.getX(), centroid.getY());
+ final Vector2D end = Vector2D.of(min.getX(), centroid.getY());
+
+ final Line line = Lines.fromPoints(start, end, TEST_PRECISION);
+
+ // -- act/assert
+ linecastChecker(bounds)
+ .expect(end, Vector2D.Unit.MINUS_X)
+ .whenGiven(line.rayFrom(0));
+
+ linecastChecker(bounds)
+ .expect(end, Vector2D.Unit.MINUS_X)
+ .whenGiven(line.segment(0, 1));
+
+ linecastChecker(bounds)
+ .expect(start, Vector2D.Unit.PLUS_X)
+ .whenGiven(line.reverseRayTo(-1));
+
+ linecastChecker(bounds)
+ .expect(start, Vector2D.Unit.PLUS_X)
+ .whenGiven(line.segment(-2, -1));
+ }
+
+ @Test
+ void testLinecast_usesLinePrecision() {
+ // -- arrange
+ final double withinEps = 0.9 * TEST_EPS;
+ final double outsideEps = 1.1 * TEST_EPS;
+
+ final Vector2D min = Vector2D.ZERO;
+ final Vector2D max = Vector2D.of(1, 1);
+
+ final Bounds2D bounds = Bounds2D.from(min, max);
+
+ final Vector2D centroid = bounds.getCentroid();
+
+ final Vector2D centerStart = Vector2D.of(max.getX(), centroid.getY());
+ final Vector2D centerEnd = Vector2D.of(min.getX(), centroid.getY());
+
+ final Line centerLine = Lines.fromPoints(centerStart, centerEnd,
TEST_PRECISION);
+
+ final Vector2D sideStart = Vector2D.of(max.getX() + withinEps,
min.getY() + withinEps);
+ final Vector2D sideEnd = Vector2D.of(max.getX() + withinEps,
max.getY() + withinEps);
+
+ final Line sideLine = Lines.fromPoints(sideStart, sideEnd,
TEST_PRECISION);
+
+ // -- act/assert
+ linecastChecker(bounds)
+ .expect(centerEnd, Vector2D.Unit.MINUS_X)
+ .whenGiven(centerLine.rayFrom(withinEps));
+
+ linecastChecker(bounds)
+ .expectNothing()
+ .whenGiven(centerLine.rayFrom(outsideEps));
+
+ linecastChecker(bounds)
+ .expect(centerStart, Vector2D.Unit.PLUS_X)
+ .expect(centerEnd, Vector2D.Unit.MINUS_X)
+ .whenGiven(centerLine.segment(-1 + withinEps, -withinEps));
+
+ linecastChecker(bounds)
+ .expectNothing()
+ .whenGiven(centerLine.segment(-1 + outsideEps, -outsideEps));
+
+ linecastChecker(bounds)
+ .expectNothing()
+ .whenGiven(sideLine.segment(outsideEps, 1 - outsideEps));
+ }
+
+ @Test
+ void testLinecast_boundsHasNoSize() {
+ // -- arrange
+ final Vector2D pt = Vector2D.of(1, 2);
+
+ final Bounds2D bounds = Bounds2D.from(pt, pt);
+
+ final Line diagonalLine = Lines.fromPointAndDirection(pt,
Vector2D.of(1, 1), TEST_PRECISION);
+
+ final Line plusXLine = Lines.fromPointAndDirection(pt,
Vector2D.Unit.PLUS_X, TEST_PRECISION);
+
+ // -- act/assert
+ linecastChecker(bounds)
+ .expect(pt, Vector2D.Unit.MINUS_X)
+ .expect(pt, Vector2D.Unit.MINUS_Y)
+ .expect(pt, Vector2D.Unit.PLUS_Y)
+ .expect(pt, Vector2D.Unit.PLUS_X)
+ .whenGiven(diagonalLine);
+
+ linecastChecker(bounds)
+ .expect(pt, Vector2D.Unit.MINUS_X)
+ .expect(pt, Vector2D.Unit.PLUS_X)
+ .whenGiven(plusXLine);
+ }
+
+ @Test
+ void testLineIntersection() {
+ // -- arrange
+ final Vector2D min = Vector2D.ZERO;
+ final Vector2D max = Vector2D.of(1, 1);
+
+ final Vector2D insideMin = Vector2D.of(0.1, 0.1);
+ final Vector2D insideMax = Vector2D.of(0.9, 0.9);
+
+ final Vector2D outsideMin = Vector2D.of(-0.1, -0.1);
+ final Vector2D outsideMax = Vector2D.of(1.1, 1.1);
+
+ final Bounds2D bounds = Bounds2D.from(min, max);
+
+ final Line diagonal = Lines.fromPoints(min, max, TEST_PRECISION);
+
+ // -- act/assert
+ assertLineIntersection(bounds, diagonal, min, max);
+
+ assertLineIntersection(bounds, diagonal.segment(outsideMin,
outsideMax), min, max);
+ assertLineIntersection(bounds, diagonal.segment(outsideMin,
insideMax), min, insideMax);
+ assertLineIntersection(bounds, diagonal.segment(insideMin,
outsideMax), insideMin, max);
+ assertLineIntersection(bounds, diagonal.segment(insideMin, insideMax),
insideMin, insideMax);
+
+ assertLineIntersection(bounds, diagonal.rayFrom(min), min, max);
+ assertLineIntersection(bounds, diagonal.reverseRayTo(min), min, min);
+
+ assertLineIntersection(bounds, diagonal.rayFrom(max), max, max);
+ assertLineIntersection(bounds, diagonal.reverseRayTo(max), min, max);
+
+ assertLineIntersection(bounds, diagonal.rayFrom(insideMax), insideMax,
max);
+ assertLineIntersection(bounds, diagonal.reverseRayTo(insideMax), min,
insideMax);
+ }
+
+ @Test
+ void testLineIntersection_noIntersection() {
+ // -- arrange
+ final Bounds2D bounds = Bounds2D.from(Vector2D.ZERO, Vector2D.of(1,
1));
+
+ final Line plusXLine =
+ Lines.fromPointAndDirection(bounds.getCentroid(),
Vector2D.Unit.PLUS_X, TEST_PRECISION);
+
+ // -- act/assert
+ checkLineNoIntersection(bounds, Vector2D.ZERO);
+ checkLineNoIntersection(bounds, Vector2D.of(0, 0));
+ checkLineNoIntersection(bounds, Vector2D.of(0, 1));
+ checkLineNoIntersection(bounds, Vector2D.of(1, 0));
+ checkLineNoIntersection(bounds, Vector2D.of(1, 1));
+
+ assertNoLineIntersection(bounds, plusXLine.segment(-0.2, -0.1));
+ assertNoLineIntersection(bounds, plusXLine.reverseRayTo(-0.1));
+
+ assertNoLineIntersection(bounds, plusXLine.segment(1.1, 1.2));
+ assertNoLineIntersection(bounds, plusXLine.rayFrom(1.1));
+ }
+
+ private void checkLineNoIntersection(
+ final Bounds2D bounds,
+ final Vector2D vertex) {
+
+ // -- arrange
+ final Vector2D toVertex = bounds.getCentroid().directionTo(vertex);
+
+ final Vector2D offsetVertex = vertex.add(toVertex);
+
+ final Line plusXLine = Lines.fromPointAndDirection(offsetVertex,
Vector2D.Unit.PLUS_X, TEST_PRECISION);
+ final Line plusYLine = Lines.fromPointAndDirection(offsetVertex,
Vector2D.Unit.PLUS_Y, TEST_PRECISION);
+
+ // -- act/assert
+ // check axis-aligned lines
+ assertNoLineIntersection(bounds, plusXLine);
+ assertNoLineIntersection(bounds, plusYLine);
+
+ // check slightly rotated lines
+ final Rotation2D rot = Rotation2D.of(0.1 * Math.PI);
+ assertNoLineIntersection(bounds, plusXLine.transform(rot));
+ assertNoLineIntersection(bounds, plusYLine.transform(rot));
+ }
+
+ @Test
+ void testLineIntersection_boundsHasNoSize() {
+ // -- arrange
+ final Vector2D pt = Vector2D.of(1, 2);
+
+ final Bounds2D bounds = Bounds2D.from(pt, pt);
+
+ final Line plusXLine = Lines.fromPointAndDirection(pt,
Vector2D.Unit.PLUS_X, TEST_PRECISION);
+
+ // -- act/assert
+ assertLineIntersection(bounds, plusXLine, pt, pt);
+ assertLineIntersection(bounds, plusXLine.rayFrom(pt), pt, pt);
+ }
+
+ @Test
+ void testLineIntersection_lineAlmostParallel() {
+ // -- arrange
+ final Vector2D min = Vector2D.of(1e150, -1);
+ final Vector2D max = Vector2D.of(1.1e150, 1);
+
+ final Bounds2D bounds = Bounds2D.from(min, max);
+
+ final Vector2D lineDir = Vector2D.of(1, -5e-11);
+ final Line line = Lines.fromPointAndDirection(Vector2D.ZERO, lineDir,
TEST_PRECISION);
+
+ // -- act
+ assertNoLineIntersection(bounds, line);
+ }
+
@Test
void testHashCode() {
// arrange
@@ -498,4 +926,187 @@ class Bounds2DTest {
Assertions.assertEquals(contains, bounds.contains(pt,
TEST_PRECISION), "Unexpected location for point " + pt);
}
}
+
+ private static void assertLineIntersection(
+ final Bounds2D bounds,
+ final Line line,
+ final Vector2D start,
+ final Vector2D end) {
+ final Segment segment = bounds.intersection(line);
+
+ Assertions.assertSame(line, segment.getLine());
+ assertSegment(segment, start, end);
+
+ Assertions.assertTrue(bounds.intersects(line));
+ }
+
+ private static void assertLineIntersection(
+ final Bounds2D bounds,
+ final LineConvexSubset subset,
+ final Vector2D start,
+ final Vector2D end) {
+ final Segment segment = bounds.intersection(subset);
+
+ Assertions.assertSame(subset.getLine(), segment.getLine());
+ assertSegment(segment, start, end);
+
+ Assertions.assertTrue(bounds.intersects(subset));
+ }
+
+ private static void assertNoLineIntersection(
+ final Bounds2D bounds,
+ final Line line) {
+ Assertions.assertNull(bounds.intersection(line));
+ Assertions.assertFalse(bounds.intersects(line));
+ }
+
+ private static void assertNoLineIntersection(
+ final Bounds2D bounds,
+ final LineConvexSubset subset) {
+ Assertions.assertNull(bounds.intersection(subset));
+ Assertions.assertFalse(bounds.intersects(subset));
+ }
+
+ private static void assertSegment(final Segment segment, final Vector2D
start, final Vector2D end) {
+ EuclideanTestUtils.assertCoordinatesEqual(start,
segment.getStartPoint(), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(end, segment.getEndPoint(),
TEST_EPS);
+ }
+
+ private static BoundsLinecastChecker2D linecastChecker(final Bounds2D
bounds) {
+ return new BoundsLinecastChecker2D(bounds);
+ }
+
+ /**
+ * Internal test class used to perform and verify linecast operations.
+ */
+ private static final class BoundsLinecastChecker2D {
+
+ private final Bounds2D bounds;
+
+ private final Parallelogram region;
+
+ private final LinecastChecker2D checker;
+
+ BoundsLinecastChecker2D(final Bounds2D bounds) {
+ this.bounds = bounds;
+ this.region = bounds.hasSize(TEST_PRECISION) ?
+ bounds.toRegion(TEST_PRECISION) :
+ null;
+ this.checker = LinecastChecker2D.with(bounds);
+ }
+
+ public BoundsLinecastChecker2D expectNothing() {
+ checker.expectNothing();
+ return this;
+ }
+
+ public BoundsLinecastChecker2D expect(final Vector2D pt, final
Vector2D normal) {
+ checker.expect(pt, normal);
+ return this;
+ }
+
+ public BoundsLinecastChecker2D and(final Vector2D pt, final Vector2D
normal) {
+ return expect(pt, normal);
+ }
+
+ public BoundsLinecastChecker2D whenGiven(final Line line) {
+ // perform the standard checks
+ checker.whenGiven(line);
+
+ // check that the returned points are equivalent to those returned
by linecasting against
+ // the region
+ final List<LinecastPoint2D> boundsResults = bounds.linecast(line);
+
+ if (region != null) {
+ assertLinecastElements(region.linecast(line),
bounds.linecast(line));
+ }
+
+ // check consistency with the intersects method; having linecast
results guarantees
+ // that we intersect the bounds but not vice versa
+ if (!boundsResults.isEmpty()) {
+ Assertions.assertTrue(bounds.intersects(line),
+ () -> "Linecast result is inconsistent with intersects
method: line= " + line);
+
+ assertLinecastResultsConsistentWithSegment(boundsResults,
bounds.intersection(line));
+ }
+
+ return this;
+ }
+
+ public BoundsLinecastChecker2D whenGiven(final LineConvexSubset
subset) {
+ // perform the standard checks
+ checker.whenGiven(subset);
+
+ // check that the returned points are equivalent to those returned
by linecasting against
+ // the region
+ final List<LinecastPoint2D> boundsResults =
bounds.linecast(subset);
+
+ if (region != null) {
+ assertLinecastElements(region.linecast(subset), boundsResults);
+ }
+
+ // check consistency with the intersects methods; having linecast
results guarantees
+ // that we intersect the bounds but not vice versa
+ if (!boundsResults.isEmpty()) {
+ Assertions.assertTrue(bounds.intersects(subset),
+ () -> "Linecast result is inconsistent with intersects
method: line subset= " + subset);
+
+ assertLinecastResultsConsistentWithSegment(boundsResults,
bounds.intersection(subset));
+ }
+
+ return this;
+ }
+
+ /** Assert that the two collections contain the same linecast points
and that the elements
+ * of {@code actual} are arranged in ascending abscissa order. Note
that this does <em>not</em>
+ * assert that {@code expected} and {@code actual} have the same exact
ordering, since the
+ * specific ordering if sensitive to floating point errors.
+ * @param expected expected collection
+ * @param actual actual collection
+ */
+ private void assertLinecastElements(
+ final Collection<LinecastPoint2D> expected,
+ final Collection<LinecastPoint2D> actual) {
+ Assertions.assertEquals(expected.size(), actual.size(),
"Unexpected list size");
+
+ // create a sorted copy
+ final List<LinecastPoint2D> sortedList = new ArrayList<>(actual);
+ sortedList.sort(LinecastPoint2D.ABSCISSA_ORDER);
+
+ // check element membership
+ for (final LinecastPoint2D expectedPt : expected) {
+ final Iterator<LinecastPoint2D> sortedIt =
sortedList.iterator();
+
+ boolean found = false;
+ while (sortedIt.hasNext()) {
+ if (expectedPt.eq(sortedIt.next(), TEST_PRECISION)) {
+ found = true;
+ break;
+ }
+ }
+
+ if (!found) {
+ Assertions.fail("Missing expected linecast point " +
expectedPt);
+ }
+ }
+
+ // check the order
+ Assertions.assertEquals(sortedList, actual);
+ }
+
+ /** Assert that the linecast results are consistent with the given
segment, which is taken
+ * to be the intersection of a line or line convex subset with the
bounding box.
+ * @param linecastResults
+ * @param segment
+ */
+ private void assertLinecastResultsConsistentWithSegment(
+ final List<LinecastPoint2D> linecastResults,
+ final Segment segment) {
+
+ for (final LinecastPoint2D pt : linecastResults) {
+ Assertions.assertEquals(RegionLocation.BOUNDARY,
segment.classifyAbscissa(pt.getAbscissa()),
+ () -> "Expected linecast point to lie on segment
boundary");
+ }
+ }
+ }
}
diff --git
a/commons-geometry-examples/examples-jmh/src/main/java/org/apache/commons/geometry/examples/jmh/euclidean/Bounds3DPerformance.java
b/commons-geometry-examples/examples-jmh/src/main/java/org/apache/commons/geometry/examples/jmh/euclidean/Bounds3DPerformance.java
new file mode 100644
index 00000000..1db0e8ec
--- /dev/null
+++
b/commons-geometry-examples/examples-jmh/src/main/java/org/apache/commons/geometry/examples/jmh/euclidean/Bounds3DPerformance.java
@@ -0,0 +1,208 @@
+/*
+ * 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.examples.jmh.euclidean;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.concurrent.TimeUnit;
+
+import org.apache.commons.geometry.euclidean.threed.Bounds3D;
+import org.apache.commons.geometry.euclidean.threed.Vector3D;
+import org.apache.commons.geometry.euclidean.threed.line.Line3D;
+import org.apache.commons.geometry.euclidean.threed.line.Lines3D;
+import org.apache.commons.geometry.euclidean.threed.line.Segment3D;
+import org.apache.commons.numbers.core.Precision;
+import org.apache.commons.rng.UniformRandomProvider;
+import org.apache.commons.rng.sampling.shape.UnitBallSampler;
+import org.apache.commons.rng.simple.RandomSource;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Param;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.Warmup;
+import org.openjdk.jmh.infra.Blackhole;
+
+/** Benchmarks for the {@link Bounds3D} class.
+ */
+@BenchmarkMode(Mode.AverageTime)
+@OutputTimeUnit(TimeUnit.NANOSECONDS)
+@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
+@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
+@Fork(value = 1, jvmArgs = {"-server", "-Xms512M", "-Xmx512M"})
+public class Bounds3DPerformance {
+
+ /** Precision context. */
+ private static final Precision.DoubleEquivalence PRECISION =
+ Precision.doubleEquivalenceOfEpsilon(1e-6);
+
+ /** Benchmark input class providing random line segments. */
+ @State(Scope.Thread)
+ public static class SegmentInput {
+
+ /** Minimum value used to construct random point coordinates. */
+ private static final double COORDINATE_MIN = -10;
+
+ /** Maximum value used to construct random point coordinates. */
+ private static final double COORDINATE_MAX = +10;
+
+ /** Number of line segments to generate. */
+ @Param({"1000"})
+ private int count;
+
+ /** Seed value for randomization. */
+ @Param({"1"})
+ private int randomSeed;
+
+ /** List of segments for the run. */
+ private List<Segment3D> segments;
+
+ /** Random instance. */
+ private UniformRandomProvider random;
+
+ /** Get the segments for the run.
+ * @return segments for the run
+ */
+ public List<Segment3D> getSegments() {
+ return segments;
+ }
+
+ /** Set up the instance for the benchmark. */
+ @Setup(Level.Iteration)
+ public void setup() {
+ random = RandomSource.MT.create(randomSeed);
+
+ final UnitBallSampler ballSampler = UnitBallSampler.of(random, 3);
+
+ segments = new ArrayList<>(count);
+ for (int i = 0; i < count; ++i) {
+ final Vector3D pt = randomPoint();
+ final Vector3D dir = Vector3D.of(ballSampler.sample());
+
+ final Line3D line = Lines3D.fromPointAndDirection(pt, dir,
PRECISION);
+
+ segments.add(line.segment(randomCoordinate(),
randomCoordinate()));
+ }
+ }
+
+ /** Return a random point with coordinates within the configured min
and max range.
+ * @return a random point with coordinates within the configured min
and max range
+ */
+ private Vector3D randomPoint() {
+ return Vector3D.of(
+ randomCoordinate(),
+ randomCoordinate(),
+ randomCoordinate());
+ }
+
+ /** Return a random double coordinate value within the configured min
and max range.
+ * @return a random double coordinate value within the configured min
and max range
+ */
+ private double randomCoordinate() {
+ return ((COORDINATE_MAX - COORDINATE_MIN) * random.nextDouble()) +
COORDINATE_MIN;
+
+ }
+ }
+
+ /** Construct a default {@link Bounds3D} instance for performance testing.
+ * @return a default {@link Bounds3D} instance
+ */
+ private static Bounds3D createDefaultTestBounds() {
+ return Bounds3D.from(Vector3D.of(-1, -1, -1), Vector3D.of(1, 1, 1));
+ }
+
+ /** Baseline benchmark that construct a bounds instance and iterates
through all
+ * input values.
+ * @param input input for the run
+ * @param bh blackhole instance
+ * @return bounds instance
+ */
+ @Benchmark
+ public Bounds3D segmentBaseline(final SegmentInput input, final Blackhole
bh) {
+ final Bounds3D bounds = createDefaultTestBounds();
+ for (final Segment3D segment : input.getSegments()) {
+ bh.consume(segment);
+ }
+ return bounds;
+ }
+
+ /** Benchmark that tests the performance of the
+ * {@link
Bounds3D#intersects(org.apache.commons.geometry.euclidean.threed.line.LineConvexSubset3D)}
method.
+ * @param input input for the run
+ * @param bh blackhole instance
+ * @return bounds instance
+ */
+ @Benchmark
+ public Bounds3D segmentIntersects(final SegmentInput input, final
Blackhole bh) {
+ final Bounds3D bounds = createDefaultTestBounds();
+ for (final Segment3D segment : input.getSegments()) {
+ bh.consume(bounds.intersects(segment));
+ }
+ return bounds;
+ }
+
+ /** Benchmark that tests the performance of the
+ * {@link
Bounds3D#intersection(org.apache.commons.geometry.euclidean.threed.line.LineConvexSubset3D)}
method.
+ * @param input input for the run
+ * @param bh blackhole instance
+ * @return bounds instance
+ */
+ @Benchmark
+ public Bounds3D segmentIntersection(final SegmentInput input, final
Blackhole bh) {
+ final Bounds3D bounds = createDefaultTestBounds();
+ for (final Segment3D segment : input.getSegments()) {
+ bh.consume(bounds.intersection(segment));
+ }
+ return bounds;
+ }
+
+ /** Benchmark that tests the performance of the
+ * {@link
Bounds3D#linecast(org.apache.commons.geometry.euclidean.threed.line.LineConvexSubset3D)}
method.
+ * @param input input for the run
+ * @param bh blackhole instance
+ * @return bounds instance
+ */
+ @Benchmark
+ public Bounds3D segmentLinecast(final SegmentInput input, final Blackhole
bh) {
+ final Bounds3D bounds = createDefaultTestBounds();
+ for (final Segment3D segment : input.getSegments()) {
+ bh.consume(bounds.linecast(segment));
+ }
+ return bounds;
+ }
+
+ /** Benchmark that tests the performance of the
+ * {@link
Bounds3D#linecastFirst(org.apache.commons.geometry.euclidean.threed.line.LineConvexSubset3D)}
method.
+ * @param input input for the run
+ * @param bh blackhole instance
+ * @return bounds instance
+ */
+ @Benchmark
+ public Bounds3D segmentLinecastFirst(final SegmentInput input, final
Blackhole bh) {
+ final Bounds3D bounds = createDefaultTestBounds();
+ for (final Segment3D segment : input.getSegments()) {
+ bh.consume(bounds.linecastFirst(segment));
+ }
+ return bounds;
+ }
+}
