You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by er...@apache.org on 2020/01/07 15:14:35 UTC
[commons-geometry] 01/08: GEOMETRY-68: adding Linecast2D/3D API
This is an automated email from the ASF dual-hosted git repository.
erans pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-geometry.git
commit 6c10297aa665ab0342ec4ffaa6f013d394c69f05
Author: Matt Juntunen <ma...@hotmail.com>
AuthorDate: Sun Dec 29 00:55:06 2019 -0500
GEOMETRY-68: adding Linecast2D/3D API
---
.../geometry/euclidean/AbstractLinecastPoint.java | 130 ++++++++++
.../threed/BoundarySourceLinecastWrapper3D.java | 85 ++++++
.../geometry/euclidean/threed/ConvexSubPlane.java | 27 ++
.../geometry/euclidean/threed/ConvexVolume.java | 14 +-
.../geometry/euclidean/threed/LinecastPoint3D.java | 50 ++++
.../geometry/euclidean/threed/Linecastable3D.java | 71 +++++
.../geometry/euclidean/threed/RegionBSPTree3D.java | 191 +++++++++++---
.../twod/BoundarySourceLinecastWrapper2D.java | 85 ++++++
.../geometry/euclidean/twod/ConvexArea.java | 14 +-
.../geometry/euclidean/twod/LinecastPoint2D.java | 50 ++++
.../geometry/euclidean/twod/Linecastable2D.java | 72 ++++++
.../commons/geometry/euclidean/twod/Polyline.java | 14 +-
.../geometry/euclidean/twod/RegionBSPTree2D.java | 192 +++++++++++++-
.../BoundarySourceLinecastWrapper3DTest.java | 213 +++++++++++++++
.../euclidean/threed/ConvexSubPlaneTest.java | 42 +++
.../euclidean/threed/ConvexVolumeTest.java | 41 +++
.../euclidean/threed/LinecastChecker3D.java | 191 ++++++++++++++
.../euclidean/threed/LinecastPoint3DTest.java | 126 +++++++++
.../euclidean/threed/RegionBSPTree3DTest.java | 286 +++++++++++++++------
.../twod/BoundarySourceLinecastWrapper2DTest.java | 204 +++++++++++++++
.../geometry/euclidean/twod/ConvexAreaTest.java | 41 +++
.../geometry/euclidean/twod/LinecastChecker2D.java | 191 ++++++++++++++
.../euclidean/twod/LinecastPoint2DTest.java | 126 +++++++++
.../geometry/euclidean/twod/PolylineTest.java | 41 +++
.../euclidean/twod/RegionBSPTree2DTest.java | 111 ++++++++
25 files changed, 2488 insertions(+), 120 deletions(-)
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/AbstractLinecastPoint.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/AbstractLinecastPoint.java
new file mode 100644
index 0000000..756df65
--- /dev/null
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/AbstractLinecastPoint.java
@@ -0,0 +1,130 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.geometry.euclidean;
+
+import java.util.Objects;
+
+import org.apache.commons.geometry.core.Embedding;
+import org.apache.commons.geometry.euclidean.oned.Vector1D;
+
+/** Base class for intersections discovered during linecast operations. This class contains
+ * the intersection point and the normal of the target boundary at the point of intersection
+ * along with the intersecting line and abscissa.
+ * @param <P> Euclidean point/vector implementation type
+ * @param <U> Unit-length Euclidean vector implementation type
+ * @param <L> Line implementation type
+ */
+public abstract class AbstractLinecastPoint<
+ P extends EuclideanVector<P>,
+ U extends P,
+ L extends Embedding<P, Vector1D>> {
+
+ /** Line intersection point. */
+ private final P point;
+
+ /** Normal of the target boundary at the intersection point. */
+ private final U normal;
+
+ /** The intersecting line. */
+ private final L line;
+
+ /** Abscissa of the intersection point along the intersecting line. */
+ private final double abscissa;
+
+ /** Construct a new instance from its components.
+ * @param point intersection point
+ * @param normal surface normal
+ * @param line line that the intersection point belongs to
+ */
+ protected AbstractLinecastPoint(final P point, final U normal, final L line) {
+ this.point = point;
+ this.normal = normal;
+ this.line = line;
+
+ this.abscissa = line.toSubspace(point).getX();
+ }
+
+ /** Get the line intersection point.
+ * @return the line intersection point
+ */
+ public P getPoint() {
+ return point;
+ }
+
+ /** Get the normal of the target boundary at the intersection point.
+ * @return the normal of the target boundary at the intersection point
+ */
+ public U getNormal() {
+ return normal;
+ }
+
+ /** Get the intersecting line.
+ * @return the intersecting line
+ */
+ public L getLine() {
+ return line;
+ }
+
+ /** Get the abscissa (1D position) of the intersection point
+ * along the linecast line.
+ * @return the abscissa of the intersection point.
+ */
+ public double getAbscissa() {
+ return abscissa;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public int hashCode() {
+ return Objects.hash(point, normal, line);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public boolean equals(final Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (obj == null || !getClass().equals(obj.getClass())) {
+ return false;
+ }
+
+ final AbstractLinecastPoint<?, ?, ?> other = (AbstractLinecastPoint<?, ?, ?>) obj;
+
+ return Objects.equals(point, other.point) &&
+ Objects.equals(normal, other.normal) &&
+ Objects.equals(line, other.line);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public String toString() {
+ final StringBuilder sb = new StringBuilder();
+ sb.append(getClass().getSimpleName())
+ .append("[point= ")
+ .append(getPoint())
+ .append(", normal= ")
+ .append(getNormal())
+ .append(", abscissa= ")
+ .append(getAbscissa())
+ .append(", line= ")
+ .append(getLine())
+ .append(']');
+
+ return sb.toString();
+ }
+}
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/BoundarySourceLinecastWrapper3D.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/BoundarySourceLinecastWrapper3D.java
new file mode 100644
index 0000000..30c33bb
--- /dev/null
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/BoundarySourceLinecastWrapper3D.java
@@ -0,0 +1,85 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.geometry.euclidean.threed;
+
+import java.util.List;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+/** Class that wraps a {@link BoundarySource3D} instance with the {@link Linecastable3D}
+ * interface. This class performs a brute-force computation of the intersections of the
+ * line or line segment against all boundaries. Some data structures may support more
+ * efficient algorithms and should therefore prefer those instead.
+ */
+final class BoundarySourceLinecastWrapper3D implements Linecastable3D {
+
+ /** The boundary source instance providing boundaries for the linecast operation. */
+ private final BoundarySource3D boundarySrc;
+
+ /** Construct a new instance for linecasting against the given boundary source.
+ * @param boundarySrc boundary source to linecast against.
+ */
+ BoundarySourceLinecastWrapper3D(final BoundarySource3D boundarySrc) {
+ this.boundarySrc = boundarySrc;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public List<LinecastPoint3D> linecast(final Segment3D segment) {
+ return getIntersectionStream(segment)
+ .sorted(LinecastPoint3D.ABSCISSA_ORDER)
+ .collect(Collectors.toList());
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public LinecastPoint3D linecastFirst(final Segment3D segment) {
+ return getIntersectionStream(segment)
+ .min(LinecastPoint3D.ABSCISSA_ORDER)
+ .orElse(null);
+ }
+
+ /** Return a stream containing intersections between the boundary source and the
+ * given line segment.
+ * @param segment segment to intersect
+ * @return a stream containing linecast intersections
+ */
+ private Stream<LinecastPoint3D> getIntersectionStream(final Segment3D segment) {
+ return boundarySrc.boundaryStream()
+ .map(boundary -> computeIntersection(boundary, segment))
+ .filter(intersection -> intersection != null);
+ }
+
+ /** Compute the intersection between a boundary subplane and linecast intersecting segment. Null is
+ * returned if no intersection is discovered.
+ * @param boundary boundary from the boundary source
+ * @param segment linecast segment to intersect with
+ * @return the linecast intersection between the two arguments or null if there is no such
+ * intersection
+ */
+ private LinecastPoint3D computeIntersection(final ConvexSubPlane boundary, final Segment3D segment) {
+ final Vector3D intersectionPt = boundary.intersection(segment);
+
+ if (intersectionPt != null) {
+ final Vector3D normal = boundary.getPlane().getNormal();
+
+ return new LinecastPoint3D(intersectionPt, normal, segment.getLine());
+ }
+
+ return null; // no intersection
+ }
+}
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/ConvexSubPlane.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/ConvexSubPlane.java
index 3d42a6d..cd0d5b4 100644
--- a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/ConvexSubPlane.java
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/ConvexSubPlane.java
@@ -90,6 +90,33 @@ public final class ConvexSubPlane extends AbstractSubPlane<ConvexArea>
return splitInternal(splitter, this, (p, r) -> new ConvexSubPlane(p, (ConvexArea) r));
}
+ /** Get the unique intersection of this subplane with the given line. Null is
+ * returned if no unique intersection point exists (ie, the line and plane are
+ * parallel or coincident) or the line does not intersect the subplane.
+ * @param line line to intersect with this subplane
+ * @return the unique intersection point between the line and this subplane
+ * or null if no such point exists.
+ * @see Plane#intersection(Line3D)
+ */
+ public Vector3D intersection(final Line3D line) {
+ final Vector3D pt = getPlane().intersection(line);
+ return (pt != null && contains(pt)) ? pt : null;
+ }
+
+ /** Get the unique intersection of this subplane with the given segment. Null
+ * is returned if the underlying line and plane do not have a unique intersection
+ * point (ie, they are parallel or coincident) or the intersection point is unique
+ * but in not contained in both the segment and subplane.
+ * @param segment segment to intersect with
+ * @return the unique intersection point between this subplane and the argument or
+ * null if no such point exists.
+ * @see Plane#intersection(Line3D)
+ */
+ public Vector3D intersection(final Segment3D segment) {
+ final Vector3D pt = intersection(segment.getLine());
+ return (pt != null && segment.contains(pt)) ? pt : null;
+ }
+
/** Get the vertices for the subplane. The vertices lie at the intersections of the
* 2D area bounding lines.
* @return the vertices for the subplane
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/ConvexVolume.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/ConvexVolume.java
index 1089027..03ba3db 100644
--- a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/ConvexVolume.java
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/ConvexVolume.java
@@ -32,7 +32,7 @@ import org.apache.commons.geometry.euclidean.twod.ConvexArea;
* The boundaries of this area, if any, are composed of convex subplanes.
*/
public final class ConvexVolume extends AbstractConvexHyperplaneBoundedRegion<Vector3D, ConvexSubPlane>
- implements BoundarySource3D {
+ implements BoundarySource3D, Linecastable3D {
/** Instance representing the full 3D volume. */
private static final ConvexVolume FULL = new ConvexVolume(Collections.emptyList());
@@ -131,6 +131,18 @@ public final class ConvexVolume extends AbstractConvexHyperplaneBoundedRegion<Ve
/** {@inheritDoc} */
@Override
+ public List<LinecastPoint3D> linecast(final Segment3D segment) {
+ return new BoundarySourceLinecastWrapper3D(this).linecast(segment);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public LinecastPoint3D linecastFirst(final Segment3D segment) {
+ return new BoundarySourceLinecastWrapper3D(this).linecastFirst(segment);
+ }
+
+ /** {@inheritDoc} */
+ @Override
public ConvexSubPlane trim(final ConvexSubHyperplane<Vector3D> convexSubHyperplane) {
return (ConvexSubPlane) super.trim(convexSubHyperplane);
}
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/LinecastPoint3D.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/LinecastPoint3D.java
new file mode 100644
index 0000000..0a2431d
--- /dev/null
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/LinecastPoint3D.java
@@ -0,0 +1,50 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.geometry.euclidean.threed;
+
+import java.util.Comparator;
+
+import org.apache.commons.geometry.euclidean.AbstractLinecastPoint;
+
+/** Class representing intersections resulting from linecast operations in Euclidean
+ * 3D space. This class contains the intersection point along with the boundary normal
+ * of the target at the point of intersection.
+ * @see Linecastable3D
+ */
+public class LinecastPoint3D extends AbstractLinecastPoint<Vector3D, Vector3D.Unit, Line3D> {
+
+ /** Comparator that sorts intersection instances by increasing abscissa order. If two abscissa
+ * values are equal, the comparison uses {@link Vector3D#COORDINATE_ASCENDING_ORDER} with the
+ * intersection normals.
+ */
+ public static final Comparator<LinecastPoint3D> ABSCISSA_ORDER = (a, b) -> {
+ int cmp = Double.compare(a.getAbscissa(), b.getAbscissa());
+ if (cmp == 0) {
+ cmp = Vector3D.COORDINATE_ASCENDING_ORDER.compare(a.getNormal(), b.getNormal());
+ }
+ return cmp;
+ };
+
+ /** Construct a new instance from its components.
+ * @param point intersection point
+ * @param normal normal of the target boundary at the intersection point
+ * @param line intersecting line
+ */
+ public LinecastPoint3D(final Vector3D point, final Vector3D normal, final Line3D line) {
+ super(point, normal.normalize(), line);
+ }
+}
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/Linecastable3D.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/Linecastable3D.java
new file mode 100644
index 0000000..43f2cbb
--- /dev/null
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/Linecastable3D.java
@@ -0,0 +1,71 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.geometry.euclidean.threed;
+
+import java.util.List;
+
+/** Interface for objects that support linecast operations in Euclidean 3D space.
+ *
+ * <p>
+ * Linecasting is a process that takes a line or line segment and intersects it with
+ * the boundaries of a region. This is similar to
+ * <a href="https://en.wikipedia.org/wiki/Ray_casting">raycasting</a> used
+ * for collision detection with the exception that the intersecting element can be a
+ * line or line segment and not just a ray.
+ * </p>
+ */
+public interface Linecastable3D {
+
+ /** Intersect the given line against the boundaries in this instance, returning a
+ * list of all intersections in order of increasing distance along the line. An empty
+ * list is returned if no intersections are discovered.
+ * @param line line the line to intersect
+ * @return a list of computed intersections in order of increasing distance
+ * along the line
+ */
+ default List<LinecastPoint3D> linecast(final Line3D line) {
+ return linecast(line.span());
+ }
+
+ /** Intersect the given line segment against the boundaries in this instance, returning
+ * a list of all intersections in order of increasing distance along the line. An empty
+ * list is returned if no intersections are discovered.
+ * @param segment segment to intersect
+ * @return a list of computed intersections in order of increasing distance
+ * along the line
+ */
+ List<LinecastPoint3D> linecast(Segment3D segment);
+
+ /** Intersect the given line against the boundaries in this instance, returning the first
+ * intersection found when traveling in the direction of the line from infinity.
+ * @param line the line to intersect
+ * @return the first intersection found or null if no intersection
+ * is found
+ */
+ default LinecastPoint3D linecastFirst(final Line3D line) {
+ return linecastFirst(line.span());
+ }
+
+ /** Intersect the given line segment against the boundaries in this instance, returning
+ * the first intersection found when traveling in the direction of the line segment
+ * from its start point.
+ * @param segment segment to intersect
+ * @return the first intersection found or null if no intersection
+ * is found
+ */
+ LinecastPoint3D linecastFirst(Segment3D segment);
+}
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/RegionBSPTree3D.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/RegionBSPTree3D.java
index db238bc..54a5b30 100644
--- a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/RegionBSPTree3D.java
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/threed/RegionBSPTree3D.java
@@ -17,6 +17,7 @@
package org.apache.commons.geometry.euclidean.threed;
import java.util.ArrayList;
+import java.util.Collections;
import java.util.List;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;
@@ -36,7 +37,7 @@ import org.apache.commons.geometry.euclidean.twod.Vector2D;
* Euclidean space.
*/
public final class RegionBSPTree3D extends AbstractRegionBSPTree<Vector3D, RegionBSPTree3D.RegionNode3D>
- implements BoundarySource3D {
+ implements BoundarySource3D, Linecastable3D {
/** Create a new, empty region. */
public RegionBSPTree3D() {
@@ -136,18 +137,22 @@ public final class RegionBSPTree3D extends AbstractRegionBSPTree<Vector3D, Regio
return projector.getProjected();
}
- /** Find the first intersection of the given ray/line segment with the boundary of
- * the region. The return value is the cut subhyperplane of the node containing the
- * intersection. Null is returned if no intersection exists.
- * @param ray ray to intersect with the region
- * @return the node cut subhyperplane containing the intersection or null if no
- * intersection exists
- */
- public ConvexSubPlane raycastFirst(final Segment3D ray) {
- final RaycastIntersectionVisitor visitor = new RaycastIntersectionVisitor(ray);
- getRoot().accept(visitor);
+ /** {@inheritDoc} */
+ @Override
+ public List<LinecastPoint3D> linecast(final Segment3D segment) {
+ final LinecastVisitor visitor = new LinecastVisitor(segment);
+ accept(visitor);
- return visitor.getIntersectionCut();
+ return visitor.getResults();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public LinecastPoint3D linecastFirst(final Segment3D segment) {
+ final LinecastFirstVisitor visitor = new LinecastFirstVisitor(segment);
+ accept(visitor);
+
+ return visitor.getResult();
}
/** {@inheritDoc} */
@@ -357,39 +362,137 @@ public final class RegionBSPTree3D extends AbstractRegionBSPTree<Vector3D, Regio
}
}
- /** BSP tree visitor that locates the node cut subhyperplane for the first intersection between a
- * given line segment and BSP tree region boundary.
+ /** Base class for BSP tree visitors that perform linecast operations.
*/
- private static final class RaycastIntersectionVisitor implements BSPTreeVisitor<Vector3D, RegionNode3D> {
+ private abstract static class AbstractLinecastVisitor implements BSPTreeVisitor<Vector3D, RegionNode3D> {
- /** The line segment to intersect with the BSP tree. */
- private final Segment3D segment;
+ /** The line segment to intersect with the boundaries of the BSP tree. */
+ private final Segment3D linecastSegment;
- /** The node cut subhyperplane containing the first boundary intersection. */
- private ConvexSubPlane intersectionCut;
+ /** Create a new instance with the given intersecting line segment.
+ * @param linecastSegment segment to intersect with the BSP tree region boundary
+ */
+ AbstractLinecastVisitor(final Segment3D linecastSegment) {
+ this.linecastSegment = linecastSegment;
+ }
- /** Create a new instance that locates the first boundary intersection between the given line segment and
- * the visited BSP tree.
- * @param segment segment to intersect with the BSP tree region boundary
+ /** Get the intersecting segment for the linecast operation.
+ * @return the intersecting segment for the linecast operation
*/
- RaycastIntersectionVisitor(final Segment3D segment) {
- this.segment = segment;
+ protected Segment3D getLinecastSegment() {
+ return linecastSegment;
}
- /** Get the node cut subhyperplane containing the first intersection between the configured line segment
- * and the BSP tree region boundary. This must be called after the tree nodes have been visited.
- * @return the node cut subhyperplane containing the first intersection between the configured line segment
- * and the BSP tree region boundary or null if no such intersection was found
+ /** Compute the linecast point for the given intersection point and tree node, returning null
+ * if the point does not actually lie on the region boundary.
+ * @param pt intersection point
+ * @param node node containing the cut subhyperplane that the linecast line
+ * intersected with
+ * @return a new linecast point instance or null if the intersection point does not lie
+ * on the region boundary
*/
- public ConvexSubPlane getIntersectionCut() {
- return intersectionCut;
+ protected LinecastPoint3D computeLinecastPoint(final Vector3D pt, final RegionNode3D node) {
+ final Plane cut = (Plane) node.getCutHyperplane();
+ final RegionCutBoundary<Vector3D> boundary = node.getCutBoundary();
+
+ boolean onBoundary = false;
+ boolean negateNormal = false;
+
+ if (boundary.getInsideFacing() != null && boundary.getInsideFacing().contains(pt)) {
+ // on inside-facing boundary
+ onBoundary = true;
+ negateNormal = true;
+ } else if (boundary.getOutsideFacing() != null && boundary.getOutsideFacing().contains(pt)) {
+ // on outside-facing boundary
+ onBoundary = true;
+ }
+
+ if (onBoundary) {
+ Vector3D normal = cut.getNormal();
+ if (negateNormal) {
+ normal = normal.negate();
+ }
+
+ return new LinecastPoint3D(pt, normal, getLinecastSegment().getLine());
+ }
+
+ return null;
+ }
+ }
+
+ /** BSP tree visitor that performs a linecast operation against the boundaries of the visited tree, returning
+ * all computed boundary intersections, in order of their abscissa position along the intersecting line.
+ */
+ private static final class LinecastVisitor extends AbstractLinecastVisitor {
+
+ /** Results of the linecast operation. */
+ private final List<LinecastPoint3D> results = new ArrayList<>();
+
+ /** Create a new instance with the given intersecting line segment.
+ * @param linecastSegment segment to intersect with the BSP tree region boundary
+ */
+ LinecastVisitor(final Segment3D linecastSegment) {
+ super(linecastSegment);
+ }
+
+ /** Get the ordered results of the linecast operation.
+ * @return the ordered results of the linecast operation
+ */
+ public List<LinecastPoint3D> getResults() {
+ // sort the results before returning
+ Collections.sort(results, LinecastPoint3D.ABSCISSA_ORDER);
+
+ return results;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public Result visit(final RegionNode3D node) {
+ if (node.isInternal()) {
+ // check if the line segment intersects the cut subhyperplane
+ final Segment3D segment = getLinecastSegment();
+ final Line3D line = segment.getLine();
+ final Vector3D pt = ((Plane) node.getCutHyperplane()).intersection(line);
+
+ if (pt != null && segment.contains(pt)) {
+ final LinecastPoint3D resultPoint = computeLinecastPoint(pt, node);
+ if (resultPoint != null) {
+ results.add(resultPoint);
+ }
+ }
+ }
+
+ return Result.CONTINUE;
+ }
+ }
+
+ /** BSP tree visitor that performs a linecast operation against the boundaries of the visited tree, returning
+ * only the intersection closest to the start of the line segment.
+ */
+ private static final class LinecastFirstVisitor extends AbstractLinecastVisitor {
+
+ /** The result of the linecast operation. */
+ private LinecastPoint3D result;
+
+ /** Create a new instance with the given intersecting line segment.
+ * @param linecastSegment segment to intersect with the BSP tree region boundary
+ */
+ LinecastFirstVisitor(final Segment3D linecastSegment) {
+ super(linecastSegment);
+ }
+
+ /** Get the {@link LinecastPoint2D} resulting from the linecast operation.
+ * @return the linecast result point
+ */
+ public LinecastPoint3D getResult() {
+ return result;
}
/** {@inheritDoc} */
@Override
public Order visitOrder(final RegionNode3D internalNode) {
final Plane cut = (Plane) internalNode.getCutHyperplane();
- final Line3D line = segment.getLine();
+ final Line3D line = getLinecastSegment().getLine();
final boolean plusIsNear = line.getDirection().dot(cut.getNormal()) < 0;
@@ -403,20 +506,24 @@ public final class RegionBSPTree3D extends AbstractRegionBSPTree<Vector3D, Regio
public Result visit(final RegionNode3D node) {
if (node.isInternal()) {
// check if the line segment intersects the cut subhyperplane
+ final Segment3D segment = getLinecastSegment();
final Line3D line = segment.getLine();
- final Vector3D intersection = ((Plane) node.getCutHyperplane()).intersection(line);
-
- if (intersection != null && segment.contains(intersection)) {
-
- final RegionCutBoundary<Vector3D> boundary = node.getCutBoundary();
-
- // check if the intersection point lies on the region boundary
- if ((boundary.getInsideFacing() != null && boundary.getInsideFacing().contains(intersection)) ||
- boundary.getOutsideFacing() != null && boundary.getOutsideFacing().contains(intersection)) {
-
- intersectionCut = (ConvexSubPlane) node.getCut();
+ final Vector3D pt = ((Plane) node.getCutHyperplane()).intersection(line);
+ if (pt != null) {
+ if (result != null && line.getPrecision()
+ .compare(result.getAbscissa(), line.abscissa(pt)) < 0) {
+ // we have a result and we are now sure that no other intersection points will be
+ // found that are closer or at the same position on the intersecting line.
return Result.TERMINATE;
+ } else if (segment.contains(pt)) {
+ // we've potentially found a new linecast point; it just needs to lie on
+ // the boundary and be closer than any current result
+ LinecastPoint3D potentialResult = computeLinecastPoint(pt, node);
+ if (potentialResult != null && (result == null ||
+ LinecastPoint3D.ABSCISSA_ORDER.compare(potentialResult, result) < 0)) {
+ result = potentialResult;
+ }
}
}
}
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/BoundarySourceLinecastWrapper2D.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/BoundarySourceLinecastWrapper2D.java
new file mode 100644
index 0000000..836aee5
--- /dev/null
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/BoundarySourceLinecastWrapper2D.java
@@ -0,0 +1,85 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.geometry.euclidean.twod;
+
+import java.util.List;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+/** Class that wraps a {@link BoundarySource2D} instance with the {@link Linecastable2D}
+ * interface. This class performs a brute-force computation of the intersections of the
+ * line or line segment against all boundaries. Some data structures may support more
+ * efficient algorithms and should therefore prefer those instead.
+ */
+final class BoundarySourceLinecastWrapper2D implements Linecastable2D {
+
+ /** The boundary source instance providing boundaries for the linecast operation. */
+ private final BoundarySource2D boundarySrc;
+
+ /** Construct a new instance for linecasting against the given boundary source.
+ * @param boundarySrc boundary source to linecast against.
+ */
+ BoundarySourceLinecastWrapper2D(final BoundarySource2D boundarySrc) {
+ this.boundarySrc = boundarySrc;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public List<LinecastPoint2D> linecast(final Segment segment) {
+ return getIntersectionStream(segment)
+ .sorted(LinecastPoint2D.ABSCISSA_ORDER)
+ .collect(Collectors.toList());
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public LinecastPoint2D linecastFirst(final Segment segment) {
+ return getIntersectionStream(segment)
+ .min(LinecastPoint2D.ABSCISSA_ORDER)
+ .orElse(null);
+ }
+
+ /** Return a stream containing intersections between the boundary source and the
+ * given line segment.
+ * @param segment segment to intersect
+ * @return a stream containing linecast intersections
+ */
+ private Stream<LinecastPoint2D> getIntersectionStream(final Segment segment) {
+ return boundarySrc.boundaryStream()
+ .map(boundary -> computeIntersection(boundary, segment))
+ .filter(intersection -> intersection != null);
+ }
+
+ /** Compute the intersection between a boundary segment and linecast intersecting segment. Null is
+ * returned if no intersection is discovered.
+ * @param boundary boundary from the boundary source
+ * @param segment linecast segment to intersect with
+ * @return the linecast intersection between the two arguments or null if there is no such
+ * intersection
+ */
+ private LinecastPoint2D computeIntersection(final Segment boundary, final Segment segment) {
+ final Vector2D intersectionPt = boundary.intersection(segment);
+
+ if (intersectionPt != null) {
+ final Vector2D normal = boundary.getLine().getOffsetDirection();
+
+ return new LinecastPoint2D(intersectionPt, normal, segment.getLine());
+ }
+
+ return null; // no intersection
+ }
+}
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/ConvexArea.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/ConvexArea.java
index 87594f9..2061053 100644
--- a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/ConvexArea.java
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/ConvexArea.java
@@ -35,7 +35,7 @@ import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
* The boundaries of this area, if any, are composed of line segments.
*/
public final class ConvexArea extends AbstractConvexHyperplaneBoundedRegion<Vector2D, Segment>
- implements BoundarySource2D {
+ implements BoundarySource2D, Linecastable2D {
/** Instance representing the full 2D plane. */
private static final ConvexArea FULL = new ConvexArea(Collections.emptyList());
@@ -165,6 +165,18 @@ public final class ConvexArea extends AbstractConvexHyperplaneBoundedRegion<Vect
return splitInternal(splitter, this, Segment.class, ConvexArea::new);
}
+ /** {@inheritDoc} */
+ @Override
+ public List<LinecastPoint2D> linecast(final Segment segment) {
+ return new BoundarySourceLinecastWrapper2D(this).linecast(segment);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public LinecastPoint2D linecastFirst(final Segment segment) {
+ return new BoundarySourceLinecastWrapper2D(this).linecastFirst(segment);
+ }
+
/** Return an instance representing the full 2D area.
* @return an instance representing the full 2D area.
*/
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/LinecastPoint2D.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/LinecastPoint2D.java
new file mode 100644
index 0000000..8bfc55a
--- /dev/null
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/LinecastPoint2D.java
@@ -0,0 +1,50 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.geometry.euclidean.twod;
+
+import java.util.Comparator;
+
+import org.apache.commons.geometry.euclidean.AbstractLinecastPoint;
+
+/** Class representing intersections resulting from linecast operations in Euclidean
+ * 2D space. This class contains the intersection point along with the boundary normal
+ * of the target at the point of intersection.
+ * @see Linecastable2D
+ */
+public class LinecastPoint2D extends AbstractLinecastPoint<Vector2D, Vector2D.Unit, Line> {
+
+ /** Comparator that sorts intersection instances by increasing abscissa order. If two abscissa
+ * values are equal, the comparison uses {@link Vector2D#COORDINATE_ASCENDING_ORDER} with the
+ * intersection normals.
+ */
+ public static final Comparator<LinecastPoint2D> ABSCISSA_ORDER = (a, b) -> {
+ int cmp = Double.compare(a.getAbscissa(), b.getAbscissa());
+ if (cmp == 0) {
+ cmp = Vector2D.COORDINATE_ASCENDING_ORDER.compare(a.getNormal(), b.getNormal());
+ }
+ return cmp;
+ };
+
+ /** Construct a new instance from its components.
+ * @param point the linecast intersection point
+ * @param normal the surface of the linecast target at the intersection point
+ * @param line intersecting line
+ */
+ public LinecastPoint2D(final Vector2D point, final Vector2D normal, final Line line) {
+ super(point, normal.normalize(), line);
+ }
+}
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Linecastable2D.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Linecastable2D.java
new file mode 100644
index 0000000..a9ee49e
--- /dev/null
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Linecastable2D.java
@@ -0,0 +1,72 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.geometry.euclidean.twod;
+
+import java.util.List;
+
+/** Interface for objects that support linecast operations in Euclidean 2D space.
+ *
+ * <p>
+ * Linecasting is a process that takes a line or line segment and intersects it with
+ * the boundaries of a region. This is similar to
+ * <a href="https://en.wikipedia.org/wiki/Ray_casting">raycasting</a> used
+ * for collision detection with the exception that the intersecting element can be a
+ * line or line segment and not just a ray.
+ * </p>
+ */
+public interface Linecastable2D {
+
+ /** Intersect the given line against the boundaries in this instance, returning a
+ * list of all intersections in order of increasing position along the line. An empty
+ * list is returned if no intersections are discovered.
+ * @param line line the line to intersect
+ * @return a list of computed intersections in order of increasing position
+ * along the line
+ */
+ default List<LinecastPoint2D> linecast(final Line line) {
+ return linecast(line.span());
+ }
+
+ /** Intersect the given line segment against the boundaries in this instance, returning
+ * a list of all intersections in order of increasing position along the line. An empty
+ * list is returned if no intersections are discovered.
+ * @param segment segment to intersect
+ * @return a list of computed intersections in order of increasing position
+ * along the line
+ */
+ List<LinecastPoint2D> linecast(Segment segment);
+
+ /** Intersect the given line against the boundaries in this instance, returning
+ * the first intersection found when traveling in the direction of the line from
+ * infinity.
+ * @param line the line to intersect
+ * @return the first intersection found or null if no intersection
+ * is found
+ */
+ default LinecastPoint2D linecastFirst(final Line line) {
+ return linecastFirst(line.span());
+ }
+
+ /** Intersect the given line segment against the boundaries in this instance, returning
+ * the first intersection found when traveling in the direction of the line segment
+ * from its start point.
+ * @param segment segment to intersect
+ * @return the first intersection found or null if no intersection
+ * is found
+ */
+ LinecastPoint2D linecastFirst(Segment segment);
+}
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Polyline.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Polyline.java
index 9ceb1b6..65948f0 100644
--- a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Polyline.java
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/Polyline.java
@@ -36,7 +36,7 @@ import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
* <p>Instances of this class are guaranteed to be immutable.</p>
* @see <a href="https://en.wikipedia.org/wiki/Polygonal_chain">Polygonal chain</a>
*/
-public class Polyline implements BoundarySource2D {
+public class Polyline implements BoundarySource2D, Linecastable2D {
/** Polyline instance containing no segments. */
private static final Polyline EMPTY = new Polyline(Collections.emptyList());
@@ -257,6 +257,18 @@ public class Polyline implements BoundarySource2D {
return new SimplifiedPolyline(simplified);
}
+ /** {@inheritDoc} */
+ @Override
+ public List<LinecastPoint2D> linecast(final Segment segment) {
+ return new BoundarySourceLinecastWrapper2D(this).linecast(segment);
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public LinecastPoint2D linecastFirst(final Segment segment) {
+ return new BoundarySourceLinecastWrapper2D(this).linecastFirst(segment);
+ }
+
/** Return a string representation of the segment polyline.
*
* <p>In order to keep the string representation short but useful, the exact format of the return
diff --git a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/RegionBSPTree2D.java b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/RegionBSPTree2D.java
index 8aa61b7..cf171a0 100644
--- a/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/RegionBSPTree2D.java
+++ b/commons-geometry-euclidean/src/main/java/org/apache/commons/geometry/euclidean/twod/RegionBSPTree2D.java
@@ -28,12 +28,14 @@ import org.apache.commons.geometry.core.partitioning.Hyperplane;
import org.apache.commons.geometry.core.partitioning.Split;
import org.apache.commons.geometry.core.partitioning.bsp.AbstractBSPTree;
import org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree;
+import org.apache.commons.geometry.core.partitioning.bsp.BSPTreeVisitor;
+import org.apache.commons.geometry.core.partitioning.bsp.RegionCutBoundary;
/** Binary space partitioning (BSP) tree representing a region in two dimensional
* Euclidean space.
*/
public final class RegionBSPTree2D extends AbstractRegionBSPTree<Vector2D, RegionBSPTree2D.RegionNode2D>
- implements BoundarySource2D {
+ implements BoundarySource2D, Linecastable2D {
/** List of line segment paths comprising the region boundary. */
private List<Polyline> boundaryPaths;
@@ -155,6 +157,24 @@ public final class RegionBSPTree2D extends AbstractRegionBSPTree<Vector2D, Regio
return projector.getProjected();
}
+ /** {@inheritDoc} */
+ @Override
+ public List<LinecastPoint2D> linecast(final Segment segment) {
+ final LinecastVisitor visitor = new LinecastVisitor(segment);
+ accept(visitor);
+
+ return visitor.getResults();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public LinecastPoint2D linecastFirst(final Segment segment) {
+ final LinecastFirstVisitor visitor = new LinecastFirstVisitor(segment);
+ accept(visitor);
+
+ return visitor.getResult();
+ }
+
/** Compute the line segment paths comprising the region boundary.
* @return the line segment paths comprising the region boundary
*/
@@ -324,4 +344,174 @@ public final class RegionBSPTree2D extends AbstractRegionBSPTree<Vector2D, Regio
return cmp < 0 ? a : b;
}
}
+
+ /** Base class for BSP tree visitors that perform linecast operations.
+ */
+ private abstract static class AbstractLinecastVisitor implements BSPTreeVisitor<Vector2D, RegionNode2D> {
+
+ /** The line segment to intersect with the boundaries of the BSP tree. */
+ private final Segment linecastSegment;
+
+ /** Create a new instance with the given intersecting line segment.
+ * @param linecastSegment segment to intersect with the BSP tree region boundary
+ */
+ AbstractLinecastVisitor(final Segment linecastSegment) {
+ this.linecastSegment = linecastSegment;
+ }
+
+ /** Get the intersecting segment for the linecast operation.
+ * @return the intersecting segment for the linecast operation
+ */
+ protected Segment getLinecastSegment() {
+ return linecastSegment;
+ }
+
+ /** Compute the linecast point for the given intersection point and tree node, returning null
+ * if the point does not actually lie on the region boundary.
+ * @param pt intersection point
+ * @param node node containing the cut subhyperplane that the linecast line
+ * intersected with
+ * @return a new linecast point instance or null if the intersection point does not lie
+ * on the region boundary
+ */
+ protected LinecastPoint2D computeLinecastPoint(final Vector2D pt, final RegionNode2D node) {
+ final Line cut = (Line) node.getCutHyperplane();
+ final RegionCutBoundary<Vector2D> boundary = node.getCutBoundary();
+
+ boolean onBoundary = false;
+ boolean negateNormal = false;
+
+ if (boundary.getInsideFacing() != null && boundary.getInsideFacing().contains(pt)) {
+ // on inside-facing boundary
+ onBoundary = true;
+ negateNormal = true;
+ } else if (boundary.getOutsideFacing() != null && boundary.getOutsideFacing().contains(pt)) {
+ // on outside-facing boundary
+ onBoundary = true;
+ }
+
+ if (onBoundary) {
+ Vector2D normal = cut.getOffsetDirection();
+ if (negateNormal) {
+ normal = normal.negate();
+ }
+
+ return new LinecastPoint2D(pt, normal, getLinecastSegment().getLine());
+ }
+
+ return null;
+ }
+ }
+
+ /** BSP tree visitor that performs a linecast operation against the boundaries of the visited tree, returning
+ * all computed boundary intersections, in order of their abscissa position along the intersecting line.
+ */
+ private static final class LinecastVisitor extends AbstractLinecastVisitor {
+
+ /** Results of the linecast operation. */
+ private final List<LinecastPoint2D> results = new ArrayList<>();
+
+ /** Create a new instance with the given intersecting line segment.
+ * @param linecastSegment segment to intersect with the BSP tree region boundary
+ */
+ LinecastVisitor(final Segment linecastSegment) {
+ super(linecastSegment);
+ }
+
+ /** Get the ordered results of the linecast operation.
+ * @return the ordered results of the linecast operation
+ */
+ public List<LinecastPoint2D> getResults() {
+ // sort the results before returning
+ Collections.sort(results, LinecastPoint2D.ABSCISSA_ORDER);
+
+ return results;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public Result visit(final RegionNode2D node) {
+ if (node.isInternal()) {
+ // check if the line segment intersects the cut subhyperplane
+ final Segment segment = getLinecastSegment();
+ final Line line = segment.getLine();
+ final Vector2D pt = ((Line) node.getCutHyperplane()).intersection(line);
+
+ if (pt != null && segment.contains(pt)) {
+ final LinecastPoint2D resultPoint = computeLinecastPoint(pt, node);
+ if (resultPoint != null) {
+ results.add(resultPoint);
+ }
+ }
+ }
+
+ return Result.CONTINUE;
+ }
+ }
+
+ /** BSP tree visitor that performs a linecast operation against the boundaries of the visited tree, returning
+ * only the intersection closest to the start of the line segment.
+ */
+ private static final class LinecastFirstVisitor extends AbstractLinecastVisitor {
+
+ /** The result of the linecast operation. */
+ private LinecastPoint2D result;
+
+ /** Create a new instance with the given intersecting line segment.
+ * @param linecastSegment segment to intersect with the BSP tree region boundary
+ */
+ LinecastFirstVisitor(final Segment linecastSegment) {
+ super(linecastSegment);
+ }
+
+ /** Get the {@link LinecastPoint2D} resulting from the linecast operation.
+ * @return the linecast result point
+ */
+ public LinecastPoint2D getResult() {
+ return result;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public Order visitOrder(final RegionNode2D internalNode) {
+ final Line cut = (Line) internalNode.getCutHyperplane();
+ final Line line = getLinecastSegment().getLine();
+
+ final boolean plusIsNear = line.getDirection().dot(cut.getOffsetDirection()) < 0;
+
+ return plusIsNear ?
+ Order.PLUS_NODE_MINUS :
+ Order.MINUS_NODE_PLUS;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public Result visit(final RegionNode2D node) {
+ if (node.isInternal()) {
+ // check if the line segment intersects the cut subhyperplane
+ final Segment segment = getLinecastSegment();
+ final Line line = segment.getLine();
+ final Vector2D pt = ((Line) node.getCutHyperplane()).intersection(line);
+
+ if (pt != null) {
+ if (result != null && line.getPrecision()
+ .compare(result.getAbscissa(), line.abscissa(pt)) < 0) {
+ // we have a result and we are now sure that no other intersection points will be
+ // found that are closer or at the same position on the intersecting line.
+ return Result.TERMINATE;
+ } else if (segment.contains(pt)) {
+ // we've potentially found a new linecast point; it just needs to lie on
+ // the boundary and be closer than any current result
+ LinecastPoint2D potentialResult = computeLinecastPoint(pt, node);
+ if (potentialResult != null && (result == null ||
+ LinecastPoint2D.ABSCISSA_ORDER.compare(potentialResult, result) < 0)) {
+ result = potentialResult;
+ }
+ }
+ }
+ }
+
+ return Result.CONTINUE;
+ }
+ }
}
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/BoundarySourceLinecastWrapper3DTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/BoundarySourceLinecastWrapper3DTest.java
new file mode 100644
index 0000000..2301645
--- /dev/null
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/BoundarySourceLinecastWrapper3DTest.java
@@ -0,0 +1,213 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.geometry.euclidean.threed;
+
+import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
+import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
+import org.junit.Test;
+
+public class BoundarySourceLinecastWrapper3DTest {
+
+ private static final double TEST_EPS = 1e-10;
+
+ private static final DoublePrecisionContext TEST_PRECISION =
+ new EpsilonDoublePrecisionContext(TEST_EPS);
+
+ private static final BoundarySource3D UNIT_CUBE =
+ Boundaries3D.rect(Vector3D.ZERO, Vector3D.of(1, 1, 1), TEST_PRECISION);
+
+ @Test
+ public void testLinecast_line_simple() {
+ // arrange
+ BoundarySourceLinecastWrapper3D wrapper = new BoundarySourceLinecastWrapper3D(UNIT_CUBE);
+
+ // act/assert
+
+ // no intersections
+ LinecastChecker3D.with(wrapper)
+ .returnsNothing()
+ .whenGiven(Line3D.fromPointAndDirection(Vector3D.of(0, 4, 4), Vector3D.Unit.MINUS_X, TEST_PRECISION));
+
+ // through center; two directions
+ LinecastChecker3D.with(wrapper)
+ .returns(Vector3D.of(0, 0.5, 0.5), Vector3D.Unit.MINUS_X)
+ .and(Vector3D.of(1, 0.5, 0.5), Vector3D.Unit.PLUS_X)
+ .whenGiven(Line3D.fromPointAndDirection(Vector3D.of(0.5, 0.5, 0.5), Vector3D.Unit.PLUS_X, TEST_PRECISION));
+
+ LinecastChecker3D.with(wrapper)
+ .returns(Vector3D.of(1, 0.5, 0.5), Vector3D.Unit.PLUS_X)
+ .and(Vector3D.of(0, 0.5, 0.5), Vector3D.Unit.MINUS_X)
+ .whenGiven(Line3D.fromPointAndDirection(Vector3D.of(0.5, 0.5, 0.5), Vector3D.Unit.MINUS_X, TEST_PRECISION));
+ }
+
+ @Test
+ public void testLinecast_line_alongFace() {
+ // arrange
+ BoundarySourceLinecastWrapper3D wrapper = new BoundarySourceLinecastWrapper3D(UNIT_CUBE);
+
+ // act/assert
+ LinecastChecker3D.with(wrapper)
+ .returns(Vector3D.ZERO, Vector3D.Unit.MINUS_Y)
+ .and(Vector3D.ZERO, Vector3D.Unit.MINUS_Z)
+ .and(Vector3D.of(0, 1, 1), Vector3D.Unit.PLUS_Z)
+ .and(Vector3D.of(0, 1, 1), Vector3D.Unit.PLUS_Y)
+ .whenGiven(Line3D.fromPointAndDirection(Vector3D.ZERO, Vector3D.of(0, 1, 1), TEST_PRECISION));
+ }
+
+ @Test
+ public void testLinecast_line_corners() {
+ // arrange
+ BoundarySourceLinecastWrapper3D wrapper = new BoundarySourceLinecastWrapper3D(UNIT_CUBE);
+
+ // act/assert
+
+ // through single corner vertex
+ LinecastChecker3D.with(wrapper)
+ .returns(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_Z)
+ .and(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_Y)
+ .and(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_X)
+ .whenGiven(Line3D.fromPointAndDirection(Vector3D.of(1, 1, 1), Vector3D.of(1, -1, -1), TEST_PRECISION));
+
+ // through two corner vertices
+ LinecastChecker3D.with(wrapper)
+ .returns(Vector3D.ZERO, Vector3D.Unit.MINUS_X)
+ .and(Vector3D.ZERO, Vector3D.Unit.MINUS_Y)
+ .and(Vector3D.ZERO, Vector3D.Unit.MINUS_Z)
+ .and(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_Z)
+ .and(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_Y)
+ .and(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_X)
+ .whenGiven(Line3D.fromPointAndDirection(Vector3D.ZERO, Vector3D.of(1, 1, 1), TEST_PRECISION));
+ }
+
+ @Test
+ public void testLinecast_segment_simple() {
+ // arrange
+ BoundarySourceLinecastWrapper3D wrapper = new BoundarySourceLinecastWrapper3D(UNIT_CUBE);
+
+ // act/assert
+
+ // no intersections; underlying line does not intersect
+ LinecastChecker3D.with(wrapper)
+ .returnsNothing()
+ .whenGiven(Line3D.fromPointAndDirection(Vector3D.of(0, 4, 4), Vector3D.Unit.MINUS_X, TEST_PRECISION)
+ .segment(-10, 10));
+
+ // no intersections; underlying line does intersect
+ LinecastChecker3D.with(wrapper)
+ .returnsNothing()
+ .whenGiven(Line3D.fromPointAndDirection(Vector3D.of(0.5, 0.5, 0.5), Vector3D.Unit.PLUS_X, TEST_PRECISION)
+ .segment(2, 10));
+
+ // no boundaries excluded; two directions
+ LinecastChecker3D.with(wrapper)
+ .returns(Vector3D.of(0, 0.5, 0.5), Vector3D.Unit.MINUS_X)
+ .and(Vector3D.of(1, 0.5, 0.5), Vector3D.Unit.PLUS_X)
+ .whenGiven(Line3D.fromPointAndDirection(Vector3D.of(0.5, 0.5, 0.5), Vector3D.Unit.PLUS_X, TEST_PRECISION)
+ .segment(-10, 10));
+
+ LinecastChecker3D.with(wrapper)
+ .returns(Vector3D.of(1, 0.5, 0.5), Vector3D.Unit.PLUS_X)
+ .and(Vector3D.of(0, 0.5, 0.5), Vector3D.Unit.MINUS_X)
+ .whenGiven(Line3D.fromPointAndDirection(Vector3D.of(0.5, 0.5, 0.5), Vector3D.Unit.MINUS_X, TEST_PRECISION)
+ .segment(-10, 10));
+ }
+
+ @Test
+ public void testLinecast_segment_boundaryExcluded() {
+ // arrange
+ BoundarySourceLinecastWrapper3D wrapper = new BoundarySourceLinecastWrapper3D(UNIT_CUBE);
+
+ // act/assert
+ Vector3D center = Vector3D.of(0.5, 0.5, 0.5);
+ LinecastChecker3D.with(wrapper)
+ .returns(Vector3D.of(1, 0.5, 0.5), Vector3D.Unit.PLUS_X)
+ .whenGiven(Line3D.fromPointAndDirection(center, Vector3D.Unit.PLUS_X, TEST_PRECISION)
+ .segmentFrom(center));
+
+ LinecastChecker3D.with(wrapper)
+ .returns(Vector3D.of(1, 0.5, 0.5), Vector3D.Unit.PLUS_X)
+ .whenGiven(Line3D.fromPointAndDirection(center, Vector3D.Unit.MINUS_X, TEST_PRECISION)
+ .segmentTo(center));
+ }
+
+ @Test
+ public void testLinecast_segment_startEndPointsOnBoundaries() {
+ // arrange
+ BoundarySourceLinecastWrapper3D wrapper = new BoundarySourceLinecastWrapper3D(UNIT_CUBE);
+
+ // act/assert
+ LinecastChecker3D.with(wrapper)
+ .returns(Vector3D.of(1, 0.5, 0.5), Vector3D.Unit.PLUS_X)
+ .and(Vector3D.of(0, 0.5, 0.5), Vector3D.Unit.MINUS_X)
+ .whenGiven(Segment3D.fromPoints(Vector3D.of(1, 0.5, 0.5), Vector3D.of(0, 0.5, 0.5), TEST_PRECISION));
+ }
+
+ @Test
+ public void testLinecast_segment_alongFace() {
+ // arrange
+ BoundarySourceLinecastWrapper3D wrapper = new BoundarySourceLinecastWrapper3D(UNIT_CUBE);
+
+ // act/assert
+
+ // includes two intersecting boundaries
+ LinecastChecker3D.with(wrapper)
+ .returns(Vector3D.of(0, 1, 0), Vector3D.Unit.MINUS_X)
+ .and(Vector3D.of(1, 1, 0), Vector3D.Unit.PLUS_X)
+ .whenGiven(Segment3D.fromPoints(Vector3D.of(-1, 1, 0), Vector3D.of(2, 1, 0), TEST_PRECISION));
+
+ // one intersecting boundary
+ LinecastChecker3D.with(wrapper)
+ .returns(Vector3D.of(1, 1, 0), Vector3D.Unit.PLUS_X)
+ .whenGiven(Segment3D.fromPoints(Vector3D.of(0.25, 1, 0), Vector3D.of(2, 1, 0), TEST_PRECISION));
+
+ // no intersecting boundary
+ LinecastChecker3D.with(wrapper)
+ .returnsNothing()
+ .whenGiven(Segment3D.fromPoints(Vector3D.of(0.25, 1, 0), Vector3D.of(0.75, 1, 0), TEST_PRECISION));
+ }
+
+ @Test
+ public void testLinecast_segment_corners() {
+ // arrange
+ BoundarySourceLinecastWrapper3D wrapper = new BoundarySourceLinecastWrapper3D(UNIT_CUBE);
+
+ Vector3D corner = Vector3D.of(1, 1, 1);
+
+ // act/assert
+
+ // through corner
+ LinecastChecker3D.with(wrapper)
+ .returns(corner, Vector3D.Unit.PLUS_Z)
+ .and(corner, Vector3D.Unit.PLUS_Y)
+ .and(corner, Vector3D.Unit.PLUS_X)
+ .whenGiven(Segment3D.fromPoints(Vector3D.of(0.5, 0.5, 0.5), Vector3D.of(2, 2, 2), TEST_PRECISION));
+
+ // starts on corner
+ LinecastChecker3D.with(wrapper)
+ .returns(corner, Vector3D.Unit.PLUS_Z)
+ .and(corner, Vector3D.Unit.PLUS_Y)
+ .and(corner, Vector3D.Unit.PLUS_X)
+ .whenGiven(Segment3D.fromPoints(corner, Vector3D.of(2, 0, 2), TEST_PRECISION));
+
+ // ends on corner
+ LinecastChecker3D.with(wrapper)
+ .returns(corner, Vector3D.Unit.PLUS_Z)
+ .and(corner, Vector3D.Unit.PLUS_Y)
+ .and(corner, Vector3D.Unit.PLUS_X)
+ .whenGiven(Segment3D.fromPoints(Vector3D.of(0, 2, 2), corner, TEST_PRECISION));
+ }
+}
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/ConvexSubPlaneTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/ConvexSubPlaneTest.java
index 1c90c3b..0f3ba79 100644
--- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/ConvexSubPlaneTest.java
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/ConvexSubPlaneTest.java
@@ -599,6 +599,48 @@ public class ConvexSubPlaneTest {
}
@Test
+ public void testIntersection_line() {
+ // arrange
+ ConvexSubPlane sp = ConvexSubPlane.fromVertexLoop(Arrays.asList(
+ Vector3D.of(0, 0, 2), Vector3D.of(1, 0, 2), Vector3D.of(1, 1, 2), Vector3D.of(0, 1, 2)),
+ TEST_PRECISION);
+
+ // act/assert
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0.5, 0.5, 2),
+ sp.intersection(Line3D.fromPoints(Vector3D.of(0.5, 0.5, 2), Vector3D.ZERO, TEST_PRECISION)), TEST_EPS);
+
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 1, 2),
+ sp.intersection(Line3D.fromPoints(Vector3D.of(1, 1, 2), Vector3D.of(1, 1, 0), TEST_PRECISION)), TEST_EPS);
+
+ Assert.assertNull(sp.intersection(Line3D.fromPoints(Vector3D.ZERO, Vector3D.Unit.PLUS_X, TEST_PRECISION)));
+ Assert.assertNull(sp.intersection(Line3D.fromPoints(Vector3D.of(0, 0, 2), Vector3D.of(1, 1, 2), TEST_PRECISION)));
+
+ Assert.assertNull(sp.intersection(Line3D.fromPoints(Vector3D.of(4, 4, 2), Vector3D.of(4, 4, 0), TEST_PRECISION)));
+ }
+
+ @Test
+ public void testIntersection_segment() {
+ // arrange
+ ConvexSubPlane sp = ConvexSubPlane.fromVertexLoop(Arrays.asList(
+ Vector3D.of(0, 0, 2), Vector3D.of(1, 0, 2), Vector3D.of(1, 1, 2), Vector3D.of(0, 1, 2)),
+ TEST_PRECISION);
+
+ // act/assert
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0.5, 0.5, 2),
+ sp.intersection(Segment3D.fromPoints(Vector3D.of(0.5, 0.5, 2), Vector3D.ZERO, TEST_PRECISION)), TEST_EPS);
+
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 1, 2),
+ sp.intersection(Segment3D.fromPoints(Vector3D.of(1, 1, 2), Vector3D.of(1, 1, 0), TEST_PRECISION)), TEST_EPS);
+
+ Assert.assertNull(sp.intersection(Segment3D.fromPoints(Vector3D.of(0.5, 0.5, 4), Vector3D.of(0.5, 0.5, 3), TEST_PRECISION)));
+
+ Assert.assertNull(sp.intersection(Segment3D.fromPoints(Vector3D.ZERO, Vector3D.Unit.PLUS_X, TEST_PRECISION)));
+ Assert.assertNull(sp.intersection(Segment3D.fromPoints(Vector3D.of(0, 0, 2), Vector3D.of(1, 1, 2), TEST_PRECISION)));
+
+ Assert.assertNull(sp.intersection(Segment3D.fromPoints(Vector3D.of(4, 4, 2), Vector3D.of(4, 4, 0), TEST_PRECISION)));
+ }
+
+ @Test
public void testToString() {
// arrange
ConvexSubPlane sp = ConvexSubPlane.fromVertexLoop(Arrays.asList(
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/ConvexVolumeTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/ConvexVolumeTest.java
index cd748e6..eff7ca0 100644
--- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/ConvexVolumeTest.java
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/ConvexVolumeTest.java
@@ -216,6 +216,47 @@ public class ConvexVolumeTest {
}
@Test
+ public void testLinecast_full() {
+ // arrange
+ ConvexVolume volume = ConvexVolume.full();
+
+ // act/assert
+ LinecastChecker3D.with(volume)
+ .returnsNothing()
+ .whenGiven(Line3D.fromPoints(Vector3D.ZERO, Vector3D.Unit.PLUS_X, TEST_PRECISION));
+
+ LinecastChecker3D.with(volume)
+ .returnsNothing()
+ .whenGiven(Segment3D.fromPoints(Vector3D.Unit.MINUS_X, Vector3D.Unit.PLUS_X, TEST_PRECISION));
+ }
+
+ @Test
+ public void testLinecast() {
+ // arrange
+ ConvexVolume volume = rect(Vector3D.of(0.5, 0.5, 0.5), 0.5, 0.5, 0.5);
+
+ // act/assert
+ LinecastChecker3D.with(volume)
+ .returnsNothing()
+ .whenGiven(Line3D.fromPoints(Vector3D.of(0, 5, 5), Vector3D.of(1, 5, 5), TEST_PRECISION));
+
+ LinecastChecker3D.with(volume)
+ .returns(Vector3D.ZERO, Vector3D.Unit.MINUS_X)
+ .and(Vector3D.ZERO, Vector3D.Unit.MINUS_Y)
+ .and(Vector3D.ZERO, Vector3D.Unit.MINUS_Z)
+ .and(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_Z)
+ .and(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_Y)
+ .and(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_X)
+ .whenGiven(Line3D.fromPoints(Vector3D.ZERO, Vector3D.of(1, 1, 1), TEST_PRECISION));
+
+ LinecastChecker3D.with(volume)
+ .returns(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_Z)
+ .and(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_Y)
+ .and(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_X)
+ .whenGiven(Segment3D.fromPoints(Vector3D.of(0.5, 0.5, 0.5), Vector3D.of(1, 1, 1), TEST_PRECISION));
+ }
+
+ @Test
public void testTransform() {
// arrange
ConvexVolume vol = rect(Vector3D.ZERO, 0.5, 0.5, 0.5);
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/LinecastChecker3D.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/LinecastChecker3D.java
new file mode 100644
index 0000000..a66ca05
--- /dev/null
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/LinecastChecker3D.java
@@ -0,0 +1,191 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.geometry.euclidean.threed;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
+import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
+import org.junit.Assert;
+
+/** Helper class designed to assist with linecast test assertions in 3D.
+ */
+class LinecastChecker3D {
+
+ private static final double TEST_EPS = 1e-10;
+
+ private static final DoublePrecisionContext TEST_PRECISION =
+ new EpsilonDoublePrecisionContext(TEST_EPS);
+
+ /** The linecastable target. */
+ private final Linecastable3D target;
+
+ /** List of expected results from the line cast operation. */
+ private final List<ExpectedResult> expectedResults = new ArrayList<>();
+
+ /** Construct a new instance that performs linecast assertions against the
+ * given target.
+ * @param target
+ */
+ LinecastChecker3D(final Linecastable3D target) {
+ this.target = target;
+ }
+
+ /** Configure the instance to expect no results (an empty list from linecast() and null from
+ * linecastFirst()) from the next linecast operation performed by {@link #whenGiven(Line)}
+ * or {@link #whenGiven(Segment)}.
+ * @return
+ */
+ public LinecastChecker3D returnsNothing() {
+ expectedResults.clear();
+
+ return this;
+ }
+
+ /** Configure the instance to expect a linecast point with the given parameters on the next
+ * linecast operation. Multiple calls to this method and/or {@link #and(Vector3D, Vector3D)}
+ * create an internal ordered list of results.
+ * @param point
+ * @param normal
+ * @return
+ */
+ public LinecastChecker3D returns(final Vector3D point, final Vector3D normal) {
+ expectedResults.add(new ExpectedResult(point, normal));
+
+ return this;
+ }
+
+ /** Fluent API alias for {@link #returns(Vector3D, Vector3D)}.
+ * @param point
+ * @param normal
+ * @return
+ */
+ public LinecastChecker3D and(final Vector3D point, final Vector3D normal) {
+ return returns(point, normal);
+ }
+
+ /** Perform {@link Linecastable2D#linecast(Line)} and {@link Linecastable2D#linecastFirst(Line)}
+ * operations using the given line and assert that the results match the configured expected
+ * values.
+ * @param line
+ */
+ public void whenGiven(final Line3D line) {
+ checkLinecastResults(target.linecast(line), line);
+ checkLinecastFirstResult(target.linecastFirst(line), line);
+ }
+
+ /** Perform {@link Linecastable2D#linecast(Segment)} and {@link Linecastable2D#linecastFirst(Segment)}
+ * operations using the given line segment and assert that the results match the configured
+ * expected results.
+ * @param segment
+ */
+ public void whenGiven(final Segment3D segment) {
+ Line3D line = segment.getLine();
+
+ checkLinecastResults(target.linecast(segment), line);
+ checkLinecastFirstResult(target.linecastFirst(segment), line);
+ }
+
+ /** Check that the given set of linecast result points matches those expected.
+ * @param results
+ * @param line
+ */
+ private void checkLinecastResults(List<LinecastPoint3D> results, Line3D line) {
+ Assert.assertNotNull("Linecast result list cannot be null", results);
+ Assert.assertEquals("Unexpected result size for linecast", expectedResults.size(), results.size());
+
+ for (int i = 0; i < expectedResults.size(); ++i) {
+ LinecastPoint3D expected = toLinecastPoint(expectedResults.get(i), line);
+ LinecastPoint3D actual = results.get(i);
+
+ if (!eq(expected, actual)) {
+ Assert.fail("Unexpected linecast point at index " + i + " expected " + expected +
+ " but was " + actual);
+ }
+ }
+ }
+
+ /** Check that the given linecastFirst result matches that expected.
+ * @param result
+ * @param line
+ */
+ private void checkLinecastFirstResult(LinecastPoint3D result, Line3D line) {
+ if (expectedResults.isEmpty()) {
+ Assert.assertNull("Expected linecastFirst result to be null", result);
+ } else {
+ LinecastPoint3D expected = toLinecastPoint(expectedResults.get(0), line);
+
+ Assert.assertNotNull("Expected linecastFirst result to not be null", result);
+
+ if (!eq(expected, result)) {
+ Assert.fail("Unexpected result from linecastFirst: expected " + expected +
+ " but was " + result);
+ }
+ }
+ }
+
+ /** Fluent API method for creating new instances.
+ * @param src
+ * @return
+ */
+ public static LinecastChecker3D with(final Linecastable3D src) {
+ return new LinecastChecker3D(src);
+ }
+
+ /** Return true if the given linecast points are equivalent according to the test precision.
+ * @param expected
+ * @param actual
+ * @return
+ */
+ private static boolean eq(LinecastPoint3D a, LinecastPoint3D b) {
+ return a.getPoint().eq(b.getPoint(), TEST_PRECISION) &&
+ a.getNormal().eq(b.getNormal(), TEST_PRECISION) &&
+ a.getLine().equals(b.getLine()) &&
+ TEST_PRECISION.eq(a.getAbscissa(), b.getAbscissa());
+ }
+
+ /** Convert an {@link ExpectedResult} struct to a {@link LinecastPoint2D} instance
+ * using the given line.
+ * @param expected
+ * @param line
+ * @return
+ */
+ private static LinecastPoint3D toLinecastPoint(ExpectedResult expected, Line3D line) {
+ return new LinecastPoint3D(expected.getPoint(), expected.getNormal(), line);
+ }
+
+ /** Class containing intermediate expected results for a linecast operation.
+ */
+ private static final class ExpectedResult {
+ private final Vector3D point;
+ private final Vector3D normal;
+
+ ExpectedResult(final Vector3D point, final Vector3D normal) {
+ this.point = point;
+ this.normal = normal;
+ }
+
+ public Vector3D getPoint() {
+ return point;
+ }
+
+ public Vector3D getNormal() {
+ return normal;
+ }
+ }
+}
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/LinecastPoint3DTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/LinecastPoint3DTest.java
new file mode 100644
index 0000000..fa4aea6
--- /dev/null
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/LinecastPoint3DTest.java
@@ -0,0 +1,126 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.geometry.euclidean.threed;
+
+import org.apache.commons.geometry.core.GeometryTestUtils;
+import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
+import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class LinecastPoint3DTest {
+
+ private static final double TEST_EPS = 1e-10;
+
+ private static final DoublePrecisionContext TEST_PRECISION =
+ new EpsilonDoublePrecisionContext(TEST_EPS);
+
+ private static final Line3D X_AXIS =
+ Line3D.fromPointAndDirection(Vector3D.ZERO, Vector3D.Unit.PLUS_X, TEST_PRECISION);
+
+ private static final Line3D Y_AXIS =
+ Line3D.fromPointAndDirection(Vector3D.ZERO, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
+
+ @Test
+ public void testProperties() {
+ // arrange
+ Vector3D pt = Vector3D.of(1, 1, 1);
+ Vector3D normal = Vector3D.Unit.MINUS_X;
+
+ LinecastPoint3D it = new LinecastPoint3D(pt, normal, X_AXIS);
+
+ // act
+ Assert.assertSame(pt, it.getPoint());
+ Assert.assertSame(normal, it.getNormal());
+ Assert.assertSame(X_AXIS, it.getLine());
+ Assert.assertEquals(1.0, it.getAbscissa(), TEST_EPS);
+ }
+
+ @Test
+ public void testCompareTo() {
+ // arrange
+ LinecastPoint3D a = new LinecastPoint3D(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_X, X_AXIS);
+
+ LinecastPoint3D b = new LinecastPoint3D(Vector3D.of(2, 2, 2), Vector3D.Unit.PLUS_X, X_AXIS);
+ LinecastPoint3D c = new LinecastPoint3D(Vector3D.of(-3, 3, 3), Vector3D.Unit.PLUS_X, X_AXIS);
+ LinecastPoint3D d = new LinecastPoint3D(Vector3D.of(1, 4, 4), Vector3D.Unit.PLUS_Y, X_AXIS);
+ LinecastPoint3D e = new LinecastPoint3D(Vector3D.of(1, 4, 4), Vector3D.Unit.PLUS_X, X_AXIS);
+
+ // act/assert
+ Assert.assertEquals(-1, LinecastPoint3D.ABSCISSA_ORDER.compare(a, b));
+ Assert.assertEquals(1, LinecastPoint3D.ABSCISSA_ORDER.compare(a, c));
+ Assert.assertEquals(1, LinecastPoint3D.ABSCISSA_ORDER.compare(a, d));
+ Assert.assertEquals(0, LinecastPoint3D.ABSCISSA_ORDER.compare(a, e));
+ }
+
+ @Test
+ public void testHashCode() {
+ // arrange
+ LinecastPoint3D a = new LinecastPoint3D(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_X, X_AXIS);
+ LinecastPoint3D b = new LinecastPoint3D(Vector3D.of(2, 2, 2), Vector3D.Unit.PLUS_X, X_AXIS);
+ LinecastPoint3D c = new LinecastPoint3D(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_Y, X_AXIS);
+ LinecastPoint3D d = new LinecastPoint3D(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_X, Y_AXIS);
+ LinecastPoint3D e = new LinecastPoint3D(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_X, X_AXIS);
+
+ // act
+ int hash = a.hashCode();
+
+ // assert
+ Assert.assertEquals(hash, a.hashCode());
+
+ Assert.assertNotEquals(hash, b.hashCode());
+ Assert.assertNotEquals(hash, c.hashCode());
+ Assert.assertNotEquals(hash, d.hashCode());
+
+ Assert.assertEquals(hash, e.hashCode());
+ }
+
+ @Test
+ public void testEquals() {
+ // arrange
+ LinecastPoint3D a = new LinecastPoint3D(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_X, X_AXIS);
+ LinecastPoint3D b = new LinecastPoint3D(Vector3D.of(2, 2, 2), Vector3D.Unit.PLUS_X, X_AXIS);
+ LinecastPoint3D c = new LinecastPoint3D(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_Y, X_AXIS);
+ LinecastPoint3D d = new LinecastPoint3D(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_X, Y_AXIS);
+ LinecastPoint3D e = new LinecastPoint3D(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_X, X_AXIS);
+
+ // act/assert
+ Assert.assertTrue(a.equals(a));
+
+ Assert.assertFalse(a.equals(null));
+ Assert.assertFalse(a.equals(new Object()));
+
+ Assert.assertFalse(a.equals(b));
+ Assert.assertFalse(a.equals(c));
+ Assert.assertFalse(a.equals(d));
+
+ Assert.assertTrue(a.equals(e));
+ Assert.assertTrue(e.equals(a));
+ }
+
+ @Test
+ public void testToString() {
+ // arrange
+ LinecastPoint3D it = new LinecastPoint3D(Vector3D.of(1, 1, 1), Vector3D.Unit.PLUS_X, X_AXIS);
+
+ // act
+ String str = it.toString();
+
+ // assert
+ GeometryTestUtils.assertContains("LinecastPoint3D[point= (1.0, 1.0, 1.0), normal= (1.0, 0.0, 0.0)", str);
+ }
+}
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/RegionBSPTree3DTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/RegionBSPTree3DTest.java
index 8dbcc6b..4baeed8 100644
--- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/RegionBSPTree3DTest.java
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/threed/RegionBSPTree3DTest.java
@@ -271,7 +271,129 @@ public class RegionBSPTree3DTest {
}
@Test
- public void testRaycastFirstFace() {
+ public void testLinecast_empty() {
+ // arrange
+ RegionBSPTree3D tree = RegionBSPTree3D.empty();
+
+ // act/assert
+ LinecastChecker3D.with(tree)
+ .returnsNothing()
+ .whenGiven(Line3D.fromPoints(Vector3D.ZERO, Vector3D.Unit.PLUS_X, TEST_PRECISION));
+
+ LinecastChecker3D.with(tree)
+ .returnsNothing()
+ .whenGiven(Segment3D.fromPoints(Vector3D.Unit.MINUS_X, Vector3D.Unit.PLUS_X, TEST_PRECISION));
+ }
+
+ @Test
+ public void testLinecast_full() {
+ // arrange
+ RegionBSPTree3D tree = RegionBSPTree3D.full();
+
+ // act/assert
+ LinecastChecker3D.with(tree)
+ .returnsNothing()
+ .whenGiven(Line3D.fromPoints(Vector3D.ZERO, Vector3D.Unit.PLUS_X, TEST_PRECISION));
+
+ LinecastChecker3D.with(tree)
+ .returnsNothing()
+ .whenGiven(Segment3D.fromPoints(Vector3D.Unit.MINUS_X, Vector3D.Unit.PLUS_X, TEST_PRECISION));
+ }
+
+ @Test
+ public void testLinecast() {
+ // arrange
+ RegionBSPTree3D tree = Boundaries3D.rect(Vector3D.ZERO, Vector3D.of(1, 1, 1), TEST_PRECISION)
+ .toTree();
+
+ // act/assert
+ LinecastChecker3D.with(tree)
+ .returnsNothing()
+ .whenGiven(Line3D.fromPoints(Vector3D.of(0, 5, 5), Vector3D.of(1, 6, 6), TEST_PRECISION));
+
+ Vector3D corner = Vector3D.of(1, 1, 1);
+
+ LinecastChecker3D.with(tree)
+ .returns(Vector3D.ZERO, Vector3D.Unit.MINUS_X)
+ .and(Vector3D.ZERO, Vector3D.Unit.MINUS_Y)
+ .and(Vector3D.ZERO, Vector3D.Unit.MINUS_Z)
+ .and(corner, Vector3D.Unit.PLUS_Z)
+ .and(corner, Vector3D.Unit.PLUS_Y)
+ .and(corner, Vector3D.Unit.PLUS_X)
+ .whenGiven(Line3D.fromPoints(Vector3D.ZERO, corner, TEST_PRECISION));
+
+ LinecastChecker3D.with(tree)
+ .returns(corner, Vector3D.Unit.PLUS_Z)
+ .and(corner, Vector3D.Unit.PLUS_Y)
+ .and(corner, Vector3D.Unit.PLUS_X)
+ .whenGiven(Segment3D.fromPoints(Vector3D.of(0.5, 0.5, 0.5), corner, TEST_PRECISION));
+ }
+
+ @Test
+ public void testLinecast_complementedTree() {
+ // arrange
+ RegionBSPTree3D tree = Boundaries3D.rect(Vector3D.ZERO, Vector3D.of(1, 1, 1), TEST_PRECISION)
+ .toTree();
+
+ tree.complement();
+
+ // act/assert
+ LinecastChecker3D.with(tree)
+ .returnsNothing()
+ .whenGiven(Line3D.fromPoints(Vector3D.of(0, 5, 5), Vector3D.of(1, 6, 6), TEST_PRECISION));
+
+ Vector3D corner = Vector3D.of(1, 1, 1);
+
+ LinecastChecker3D.with(tree)
+ .returns(Vector3D.ZERO, Vector3D.Unit.PLUS_Z)
+ .and(Vector3D.ZERO, Vector3D.Unit.PLUS_Y)
+ .and(Vector3D.ZERO, Vector3D.Unit.PLUS_X)
+ .and(corner, Vector3D.Unit.MINUS_X)
+ .and(corner, Vector3D.Unit.MINUS_Y)
+ .and(corner, Vector3D.Unit.MINUS_Z)
+ .whenGiven(Line3D.fromPoints(Vector3D.ZERO, corner, TEST_PRECISION));
+
+ LinecastChecker3D.with(tree)
+ .returns(corner, Vector3D.Unit.MINUS_X)
+ .and(corner, Vector3D.Unit.MINUS_Y)
+ .and(corner, Vector3D.Unit.MINUS_Z)
+ .whenGiven(Segment3D.fromPoints(Vector3D.of(0.5, 0.5, 0.5), corner, TEST_PRECISION));
+ }
+
+ @Test
+ public void testLinecast_complexRegion() {
+ // arrange
+ RegionBSPTree3D a = RegionBSPTree3D.empty();
+ Boundaries3D.rect(Vector3D.ZERO, Vector3D.of(0.5, 1, 1), TEST_PRECISION).boundaryStream()
+ .map(ConvexSubPlane::reverse)
+ .forEach(a::insert);
+ a.complement();
+
+ RegionBSPTree3D b = RegionBSPTree3D.empty();
+ Boundaries3D.rect(Vector3D.of(0.5, 0, 0), Vector3D.of(1, 1, 1), TEST_PRECISION).boundaryStream()
+ .map(ConvexSubPlane::reverse)
+ .forEach(b::insert);
+ b.complement();
+
+ RegionBSPTree3D c = Boundaries3D.rect(Vector3D.of(0.5, 0.5, 0.5), Vector3D.of(1.5, 1.5, 1.5), TEST_PRECISION)
+ .toTree();
+
+ RegionBSPTree3D tree = RegionBSPTree3D.empty();
+ tree.union(a, b);
+ tree.union(c);
+
+ // act/assert
+ Vector3D corner = Vector3D.of(1.5, 1.5, 1.5);
+
+ LinecastChecker3D.with(tree)
+ .returns(corner, Vector3D.Unit.PLUS_Z)
+ .and(corner, Vector3D.Unit.PLUS_Y)
+ .and(corner, Vector3D.Unit.PLUS_X)
+ .whenGiven(Segment3D.fromPoints(Vector3D.of(0.25, 0.25, 0.25), Vector3D.of(2, 2, 2), TEST_PRECISION));
+ }
+
+ @Test
+ public void testLinecastFirst_multipleDirections() {
// arrange
RegionBSPTree3D tree = Boundaries3D.rect(Vector3D.of(-1, -1, -1), Vector3D.of(1, 1, 1), TEST_PRECISION)
.toTree();
@@ -286,40 +408,58 @@ public class RegionBSPTree3DTest {
Line3D zMinus = Line3D.fromPoints(Vector3D.ZERO, Vector3D.of(0, 0, -1), TEST_PRECISION);
// act/assert
- assertSubPlaneNormal(Vector3D.of(-1, 0, 0), tree.raycastFirst(xPlus.segmentFrom(Vector3D.of(-1.1, 0, 0))));
- assertSubPlaneNormal(Vector3D.of(-1, 0, 0), tree.raycastFirst(xPlus.segmentFrom(Vector3D.of(-1, 0, 0))));
- assertSubPlaneNormal(Vector3D.of(1, 0, 0), tree.raycastFirst(xPlus.segmentFrom(Vector3D.of(-0.9, 0, 0))));
- Assert.assertEquals(null, tree.raycastFirst(xPlus.segmentFrom(Vector3D.of(1.1, 0, 0))));
-
- assertSubPlaneNormal(Vector3D.of(1, 0, 0), tree.raycastFirst(xMinus.segmentFrom(Vector3D.of(1.1, 0, 0))));
- assertSubPlaneNormal(Vector3D.of(1, 0, 0), tree.raycastFirst(xMinus.segmentFrom(Vector3D.of(1, 0, 0))));
- assertSubPlaneNormal(Vector3D.of(-1, 0, 0), tree.raycastFirst(xMinus.segmentFrom(Vector3D.of(0.9, 0, 0))));
- Assert.assertEquals(null, tree.raycastFirst(xMinus.segmentFrom(Vector3D.of(-1.1, 0, 0))));
-
- assertSubPlaneNormal(Vector3D.of(0, -1, 0), tree.raycastFirst(yPlus.segmentFrom(Vector3D.of(0, -1.1, 0))));
- assertSubPlaneNormal(Vector3D.of(0, -1, 0), tree.raycastFirst(yPlus.segmentFrom(Vector3D.of(0, -1, 0))));
- assertSubPlaneNormal(Vector3D.of(0, 1, 0), tree.raycastFirst(yPlus.segmentFrom(Vector3D.of(0, -0.9, 0))));
- Assert.assertEquals(null, tree.raycastFirst(yPlus.segmentFrom(Vector3D.of(0, 1.1, 0))));
-
- assertSubPlaneNormal(Vector3D.of(0, 1, 0), tree.raycastFirst(yMinus.segmentFrom(Vector3D.of(0, 1.1, 0))));
- assertSubPlaneNormal(Vector3D.of(0, 1, 0), tree.raycastFirst(yMinus.segmentFrom(Vector3D.of(0, 1, 0))));
- assertSubPlaneNormal(Vector3D.of(0, -1, 0), tree.raycastFirst(yMinus.segmentFrom(Vector3D.of(0, 0.9, 0))));
- Assert.assertEquals(null, tree.raycastFirst(yMinus.segmentFrom(Vector3D.of(0, -1.1, 0))));
-
- assertSubPlaneNormal(Vector3D.of(0, 0, -1), tree.raycastFirst(zPlus.segmentFrom(Vector3D.of(0, 0, -1.1))));
- assertSubPlaneNormal(Vector3D.of(0, 0, -1), tree.raycastFirst(zPlus.segmentFrom(Vector3D.of(0, 0, -1))));
- assertSubPlaneNormal(Vector3D.of(0, 0, 1), tree.raycastFirst(zPlus.segmentFrom(Vector3D.of(0, 0, -0.9))));
- Assert.assertEquals(null, tree.raycastFirst(zPlus.segmentFrom(Vector3D.of(0, 0, 1.1))));
-
- assertSubPlaneNormal(Vector3D.of(0, 0, 1), tree.raycastFirst(zMinus.segmentFrom(Vector3D.of(0, 0, 1.1))));
- assertSubPlaneNormal(Vector3D.of(0, 0, 1), tree.raycastFirst(zMinus.segmentFrom(Vector3D.of(0, 0, 1))));
- assertSubPlaneNormal(Vector3D.of(0, 0, -1), tree.raycastFirst(zMinus.segmentFrom(Vector3D.of(0, 0, 0.9))));
- Assert.assertEquals(null, tree.raycastFirst(zMinus.segmentFrom(Vector3D.of(0, 0, -1.1))));
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(-1, 0, 0),
+ tree.linecastFirst(xPlus.segmentFrom(Vector3D.of(-1.1, 0, 0))).getNormal(), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(-1, 0, 0),
+ tree.linecastFirst(xPlus.segmentFrom(Vector3D.of(-1, 0, 0))).getNormal(), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 0, 0),
+ tree.linecastFirst(xPlus.segmentFrom(Vector3D.of(-0.9, 0, 0))).getNormal(), TEST_EPS);
+ Assert.assertNull(tree.linecastFirst(xPlus.segmentFrom(Vector3D.of(1.1, 0, 0))));
+
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 0, 0),
+ tree.linecastFirst(xMinus.segmentFrom(Vector3D.of(1.1, 0, 0))).getNormal(), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(1, 0, 0),
+ tree.linecastFirst(xMinus.segmentFrom(Vector3D.of(1, 0, 0))).getNormal(), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(-1, 0, 0),
+ tree.linecastFirst(xMinus.segmentFrom(Vector3D.of(0.9, 0, 0))).getNormal(), TEST_EPS);
+ Assert.assertNull(tree.linecastFirst(xMinus.segmentFrom(Vector3D.of(-1.1, 0, 0))));
+
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, -1, 0),
+ tree.linecastFirst(yPlus.segmentFrom(Vector3D.of(0, -1.1, 0))).getNormal(), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, -1, 0),
+ tree.linecastFirst(yPlus.segmentFrom(Vector3D.of(0, -1, 0))).getNormal(), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 1, 0),
+ tree.linecastFirst(yPlus.segmentFrom(Vector3D.of(0, -0.9, 0))).getNormal(), TEST_EPS);
+ Assert.assertNull(tree.linecastFirst(yPlus.segmentFrom(Vector3D.of(0, 1.1, 0))));
+
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 1, 0),
+ tree.linecastFirst(yMinus.segmentFrom(Vector3D.of(0, 1.1, 0))).getNormal(), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 1, 0),
+ tree.linecastFirst(yMinus.segmentFrom(Vector3D.of(0, 1, 0))).getNormal(), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, -1, 0),
+ tree.linecastFirst(yMinus.segmentFrom(Vector3D.of(0, 0.9, 0))).getNormal(), TEST_EPS);
+ Assert.assertNull(tree.linecastFirst(yMinus.segmentFrom(Vector3D.of(0, -1.1, 0))));
+
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, -1),
+ tree.linecastFirst(zPlus.segmentFrom(Vector3D.of(0, 0, -1.1))).getNormal(), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, -1),
+ tree.linecastFirst(zPlus.segmentFrom(Vector3D.of(0, 0, -1))).getNormal(), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 1),
+ tree.linecastFirst(zPlus.segmentFrom(Vector3D.of(0, 0, -0.9))).getNormal(), TEST_EPS);
+ Assert.assertNull(tree.linecastFirst(zPlus.segmentFrom(Vector3D.of(0, 0, 1.1))));
+
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 1),
+ tree.linecastFirst(zMinus.segmentFrom(Vector3D.of(0, 0, 1.1))).getNormal(), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, 1),
+ tree.linecastFirst(zMinus.segmentFrom(Vector3D.of(0, 0, 1))).getNormal(), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.of(0, 0, -1),
+ tree.linecastFirst(zMinus.segmentFrom(Vector3D.of(0, 0, 0.9))).getNormal(), TEST_EPS);
+ Assert.assertNull(tree.linecastFirst(zMinus.segmentFrom(Vector3D.of(0, 0, -1.1))));
}
// issue GEOMETRY-38
@Test
- public void testRaycastFirstFace_linePassesThroughVertex() {
+ public void testLinecastFirst_linePassesThroughVertex() {
// arrange
Vector3D lowerCorner = Vector3D.ZERO;
Vector3D upperCorner = Vector3D.of(1, 1, 1);
@@ -331,21 +471,21 @@ public class RegionBSPTree3DTest {
Line3D downDiagonal = upDiagonal.reverse();
// act/assert
- ConvexSubPlane upFromOutsideResult = tree.raycastFirst(upDiagonal.segmentFrom(Vector3D.of(-1, -1, -1)));
+ LinecastPoint3D upFromOutsideResult = tree.linecastFirst(upDiagonal.segmentFrom(Vector3D.of(-1, -1, -1)));
Assert.assertNotNull(upFromOutsideResult);
- EuclideanTestUtils.assertCoordinatesEqual(lowerCorner, upFromOutsideResult.getPlane().intersection(upDiagonal), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(lowerCorner, upFromOutsideResult.getPoint(), TEST_EPS);
- ConvexSubPlane upFromCenterResult = tree.raycastFirst(upDiagonal.segmentFrom(center));
+ LinecastPoint3D upFromCenterResult = tree.linecastFirst(upDiagonal.segmentFrom(center));
Assert.assertNotNull(upFromCenterResult);
- EuclideanTestUtils.assertCoordinatesEqual(upperCorner, upFromCenterResult.getPlane().intersection(upDiagonal), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(upperCorner, upFromCenterResult.getPoint(), TEST_EPS);
- ConvexSubPlane downFromOutsideResult = tree.raycastFirst(downDiagonal.segmentFrom(Vector3D.of(2, 2, 2)));
+ LinecastPoint3D downFromOutsideResult = tree.linecastFirst(downDiagonal.segmentFrom(Vector3D.of(2, 2, 2)));
Assert.assertNotNull(downFromOutsideResult);
- EuclideanTestUtils.assertCoordinatesEqual(upperCorner, downFromOutsideResult.getPlane().intersection(downDiagonal), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(upperCorner, downFromOutsideResult.getPoint(), TEST_EPS);
- ConvexSubPlane downFromCenterResult = tree.raycastFirst(downDiagonal.segmentFrom(center));
+ LinecastPoint3D downFromCenterResult = tree.linecastFirst(downDiagonal.segmentFrom(center));
Assert.assertNotNull(downFromCenterResult);
- EuclideanTestUtils.assertCoordinatesEqual(lowerCorner, downFromCenterResult.getPlane().intersection(downDiagonal), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(lowerCorner, downFromCenterResult.getPoint(), TEST_EPS);
}
// Issue GEOMETRY-43
@@ -365,19 +505,19 @@ public class RegionBSPTree3DTest {
Vector3D expectedIntersection2 = Vector3D.of(0.5, 1.0, 0.0);
// act/assert
- ConvexSubPlane bottom = tree.raycastFirst(bottomLine.segmentFrom(firstPointOnLine));
+ LinecastPoint3D bottom = tree.linecastFirst(bottomLine.segmentFrom(firstPointOnLine));
Assert.assertNotNull(bottom);
- EuclideanTestUtils.assertCoordinatesEqual(expectedIntersection1, bottom.getHyperplane().intersection(bottomLine), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(expectedIntersection1, bottom.getPoint(), TEST_EPS);
- bottom = tree.raycastFirst(bottomLine.segmentFrom(Vector3D.of(0.5, 0.1, 0.0)));
+ bottom = tree.linecastFirst(bottomLine.segmentFrom(Vector3D.of(0.5, 0.1, 0.0)));
Assert.assertNotNull(bottom);
- Vector3D intersection = bottom.getPlane().intersection(bottomLine);
+ Vector3D intersection = bottom.getPoint();
Assert.assertNotNull(intersection);
EuclideanTestUtils.assertCoordinatesEqual(expectedIntersection2, intersection, TEST_EPS);
}
@Test
- public void testRaycastFirstFace_rayPointOnFace() {
+ public void testLinecastFirst_rayPointOnFace() {
// arrange
Vector3D lowerCorner = Vector3D.ZERO;
Vector3D upperCorner = Vector3D.of(1, 1, 1);
@@ -389,17 +529,15 @@ public class RegionBSPTree3DTest {
Line3D outOfBoxLine = Line3D.fromPoints(pt, pt.add(Vector3D.Unit.MINUS_Z), TEST_PRECISION);
// act/assert
- ConvexSubPlane intoBoxResult = tree.raycastFirst(intoBoxLine.segmentFrom(pt));
- Vector3D intoBoxPt = intoBoxResult.getPlane().intersection(intoBoxLine);
- EuclideanTestUtils.assertCoordinatesEqual(pt, intoBoxPt, TEST_EPS);
+ LinecastPoint3D intoBoxResult = tree.linecastFirst(intoBoxLine.segmentFrom(pt));
+ EuclideanTestUtils.assertCoordinatesEqual(pt, intoBoxResult.getPoint(), TEST_EPS);
- ConvexSubPlane outOfBoxResult = tree.raycastFirst(outOfBoxLine.segmentFrom(pt));
- Vector3D outOfBoxPt = outOfBoxResult.getPlane().intersection(outOfBoxLine);
- EuclideanTestUtils.assertCoordinatesEqual(pt, outOfBoxPt, TEST_EPS);
+ LinecastPoint3D outOfBoxResult = tree.linecastFirst(outOfBoxLine.segmentFrom(pt));
+ EuclideanTestUtils.assertCoordinatesEqual(pt, outOfBoxResult.getPoint(), TEST_EPS);
}
@Test
- public void testRaycastFirstFace_rayPointOnVertex() {
+ public void testLinecastFirst_rayPointOnVertex() {
// arrange
Vector3D lowerCorner = Vector3D.ZERO;
Vector3D upperCorner = Vector3D.of(1, 1, 1);
@@ -410,17 +548,15 @@ public class RegionBSPTree3DTest {
Line3D outOfBoxLine = intoBoxLine.reverse();
// act/assert
- ConvexSubPlane intoBoxResult = tree.raycastFirst(intoBoxLine.segmentFrom(lowerCorner));
- Vector3D intoBoxPt = intoBoxResult.getPlane().intersection(intoBoxLine);
- EuclideanTestUtils.assertCoordinatesEqual(lowerCorner, intoBoxPt, TEST_EPS);
+ LinecastPoint3D intoBoxResult = tree.linecastFirst(intoBoxLine.segmentFrom(lowerCorner));
+ EuclideanTestUtils.assertCoordinatesEqual(lowerCorner, intoBoxResult.getPoint(), TEST_EPS);
- ConvexSubPlane outOfBoxResult = tree.raycastFirst(outOfBoxLine.segmentFrom(lowerCorner));
- Vector3D outOfBoxPt = outOfBoxResult.getPlane().intersection(outOfBoxLine);
- EuclideanTestUtils.assertCoordinatesEqual(lowerCorner, outOfBoxPt, TEST_EPS);
+ LinecastPoint3D outOfBoxResult = tree.linecastFirst(outOfBoxLine.segmentFrom(lowerCorner));
+ EuclideanTestUtils.assertCoordinatesEqual(lowerCorner, outOfBoxResult.getPoint(), TEST_EPS);
}
@Test
- public void testRaycastFirstFace_onlyReturnsPointsWithinSegment() throws IOException, ParseException {
+ public void testLinecastFirst_onlyReturnsPointsWithinSegment() throws IOException, ParseException {
// arrange
Vector3D lowerCorner = Vector3D.ZERO;
Vector3D upperCorner = Vector3D.of(1, 1, 1);
@@ -430,18 +566,24 @@ public class RegionBSPTree3DTest {
Line3D line = Line3D.fromPointAndDirection(Vector3D.of(0.5, 0.5, 0.5), Vector3D.Unit.PLUS_X, TEST_PRECISION);
// act/assert
- assertSubPlaneNormal(Vector3D.Unit.MINUS_X, tree.raycastFirst(line.span()));
- assertSubPlaneNormal(Vector3D.Unit.PLUS_X, tree.raycastFirst(line.reverse().span()));
-
- assertSubPlaneNormal(Vector3D.Unit.MINUS_X, tree.raycastFirst(line.segment(Vector3D.of(-2, 0.5, 0.5), Vector3D.of(0.5, 0.5, 0.5))));
- assertSubPlaneNormal(Vector3D.Unit.MINUS_X, tree.raycastFirst(line.segment(Vector3D.of(-2, 0.5, 0.5), Vector3D.of(0, 0.5, 0.5))));
-
- assertSubPlaneNormal(Vector3D.Unit.PLUS_X, tree.raycastFirst(line.segment(Vector3D.of(0.5, 0.5, 0.5), Vector3D.of(2, 0.5, 0.5))));
- assertSubPlaneNormal(Vector3D.Unit.PLUS_X, tree.raycastFirst(line.segment(Vector3D.of(0.5, 0.5, 0.5), Vector3D.of(1, 0.5, 0.5))));
-
- Assert.assertNull(tree.raycastFirst(line.segment(Vector3D.of(-2, 0.5, 0.5), Vector3D.of(-1, 0.5, 0.5))));
- Assert.assertNull(tree.raycastFirst(line.segment(Vector3D.of(-2, 0.5, 0.5), Vector3D.of(-1, 0.5, 0.5))));
- Assert.assertNull(tree.raycastFirst(line.segment(Vector3D.of(0.25, 0.5, 0.5), Vector3D.of(0.75, 0.5, 0.5))));
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.MINUS_X,
+ tree.linecastFirst(line.span()).getNormal(), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.PLUS_X,
+ tree.linecastFirst(line.reverse().span()).getNormal(), TEST_EPS);
+
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.MINUS_X,
+ tree.linecastFirst(line.segment(Vector3D.of(-2, 0.5, 0.5), Vector3D.of(0.5, 0.5, 0.5))).getNormal(), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.MINUS_X,
+ tree.linecastFirst(line.segment(Vector3D.of(-2, 0.5, 0.5), Vector3D.of(0, 0.5, 0.5))).getNormal(), TEST_EPS);
+
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.PLUS_X,
+ tree.linecastFirst(line.segment(Vector3D.of(0.5, 0.5, 0.5), Vector3D.of(2, 0.5, 0.5))).getNormal(), TEST_EPS);
+ EuclideanTestUtils.assertCoordinatesEqual(Vector3D.Unit.PLUS_X,
+ tree.linecastFirst(line.segment(Vector3D.of(0.5, 0.5, 0.5), Vector3D.of(1, 0.5, 0.5))).getNormal(), TEST_EPS);
+
+ Assert.assertNull(tree.linecastFirst(line.segment(Vector3D.of(-2, 0.5, 0.5), Vector3D.of(-1, 0.5, 0.5))));
+ Assert.assertNull(tree.linecastFirst(line.segment(Vector3D.of(-2, 0.5, 0.5), Vector3D.of(-1, 0.5, 0.5))));
+ Assert.assertNull(tree.linecastFirst(line.segment(Vector3D.of(0.25, 0.5, 0.5), Vector3D.of(0.75, 0.5, 0.5))));
}
@Test
@@ -1402,10 +1544,6 @@ public class RegionBSPTree3DTest {
return tree;
}
- private static void assertSubPlaneNormal(Vector3D expectedNormal, ConvexSubPlane sub) {
- EuclideanTestUtils.assertCoordinatesEqual(expectedNormal, sub.getPlane().getNormal(), TEST_EPS);
- }
-
private static double cubeVolume(double size) {
return size * size * size;
}
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/BoundarySourceLinecastWrapper2DTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/BoundarySourceLinecastWrapper2DTest.java
new file mode 100644
index 0000000..b3d31d3
--- /dev/null
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/BoundarySourceLinecastWrapper2DTest.java
@@ -0,0 +1,204 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.geometry.euclidean.twod;
+
+import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
+import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
+import org.junit.Test;
+
+public class BoundarySourceLinecastWrapper2DTest {
+
+ private static final double TEST_EPS = 1e-10;
+
+ private static final DoublePrecisionContext TEST_PRECISION =
+ new EpsilonDoublePrecisionContext(TEST_EPS);
+
+ private static final BoundarySource2D UNIT_SQUARE =
+ Boundaries2D.rect(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION);
+
+ @Test
+ public void testLinecast_line_simple() {
+ // arrange
+ BoundarySourceLinecastWrapper2D wrapper = new BoundarySourceLinecastWrapper2D(UNIT_SQUARE);
+
+ // act/assert
+
+ // no intersections
+ LinecastChecker2D.with(wrapper)
+ .returnsNothing()
+ .whenGiven(Line.fromPointAndDirection(Vector2D.of(0, 4), Vector2D.Unit.MINUS_X, TEST_PRECISION));
+
+ // through center; two directions
+ LinecastChecker2D.with(wrapper)
+ .returns(Vector2D.of(0, 0.5), Vector2D.Unit.MINUS_X)
+ .and(Vector2D.of(1, 0.5), Vector2D.Unit.PLUS_X)
+ .whenGiven(Line.fromPointAndDirection(Vector2D.of(0.5, 0.5), Vector2D.Unit.PLUS_X, TEST_PRECISION));
+
+ LinecastChecker2D.with(wrapper)
+ .returns(Vector2D.of(1, 0.5), Vector2D.Unit.PLUS_X)
+ .and(Vector2D.of(0, 0.5), Vector2D.Unit.MINUS_X)
+ .whenGiven(Line.fromPointAndDirection(Vector2D.of(0.5, 0.5), Vector2D.Unit.MINUS_X, TEST_PRECISION));
+ }
+
+ @Test
+ public void testLinecast_line_alongFace() {
+ // arrange
+ BoundarySourceLinecastWrapper2D wrapper = new BoundarySourceLinecastWrapper2D(UNIT_SQUARE);
+
+ // act/assert
+ LinecastChecker2D.with(wrapper)
+ .returns(Vector2D.of(0, 1), Vector2D.Unit.MINUS_X)
+ .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X)
+ .whenGiven(Line.fromPointAndDirection(Vector2D.of(0, 1), Vector2D.Unit.PLUS_X, TEST_PRECISION));
+ }
+
+ @Test
+ public void testLinecast_line_corners() {
+ // arrange
+ BoundarySourceLinecastWrapper2D wrapper = new BoundarySourceLinecastWrapper2D(UNIT_SQUARE);
+
+ // act/assert
+
+ // through single corner vertex
+ LinecastChecker2D.with(wrapper)
+ .returns(Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y)
+ .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X)
+ .whenGiven(Line.fromPointAndDirection(Vector2D.of(0, 2), Vector2D.of(1, -1), TEST_PRECISION));
+
+ // through two corner vertices
+ LinecastChecker2D.with(wrapper)
+ .returns(Vector2D.ZERO, Vector2D.Unit.MINUS_X)
+ .and(Vector2D.ZERO, Vector2D.Unit.MINUS_Y)
+ .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y)
+ .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X)
+ .whenGiven(Line.fromPointAndDirection(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION));
+ }
+
+ @Test
+ public void testLinecast_segment_simple() {
+ // arrange
+ BoundarySourceLinecastWrapper2D wrapper = new BoundarySourceLinecastWrapper2D(UNIT_SQUARE);
+
+ // act/assert
+
+ // no intersections; underlying line does not intersect
+ LinecastChecker2D.with(wrapper)
+ .returnsNothing()
+ .whenGiven(Line.fromPointAndDirection(Vector2D.of(0, 4), Vector2D.Unit.MINUS_X, TEST_PRECISION)
+ .segment(-10, 10));
+
+ // no intersections; underlying line does intersect
+ LinecastChecker2D.with(wrapper)
+ .returnsNothing()
+ .whenGiven(Line.fromPointAndDirection(Vector2D.of(0.5, 0.5), Vector2D.Unit.PLUS_X, TEST_PRECISION)
+ .segment(2, 10));
+
+ // no boundaries excluded; two directions
+ LinecastChecker2D.with(wrapper)
+ .returns(Vector2D.of(0, 0.5), Vector2D.Unit.MINUS_X)
+ .and(Vector2D.of(1, 0.5), Vector2D.Unit.PLUS_X)
+ .whenGiven(Line.fromPointAndDirection(Vector2D.of(0.5, 0.5), Vector2D.Unit.PLUS_X, TEST_PRECISION)
+ .segment(-10, 10));
+
+ LinecastChecker2D.with(wrapper)
+ .returns(Vector2D.of(1, 0.5), Vector2D.Unit.PLUS_X)
+ .and(Vector2D.of(0, 0.5), Vector2D.Unit.MINUS_X)
+ .whenGiven(Line.fromPointAndDirection(Vector2D.of(0.5, 0.5), Vector2D.Unit.MINUS_X, TEST_PRECISION)
+ .segment(-10, 10));
+ }
+
+ @Test
+ public void testLinecast_segment_boundaryExcluded() {
+ // arrange
+ BoundarySourceLinecastWrapper2D wrapper = new BoundarySourceLinecastWrapper2D(UNIT_SQUARE);
+
+ // act/assert
+ Vector2D center = Vector2D.of(0.5, 0.5);
+ LinecastChecker2D.with(wrapper)
+ .returns(Vector2D.of(1, 0.5), Vector2D.Unit.PLUS_X)
+ .whenGiven(Line.fromPointAndDirection(center, Vector2D.Unit.PLUS_X, TEST_PRECISION)
+ .segmentFrom(center));
+
+ LinecastChecker2D.with(wrapper)
+ .returns(Vector2D.of(1, 0.5), Vector2D.Unit.PLUS_X)
+ .whenGiven(Line.fromPointAndDirection(center, Vector2D.Unit.MINUS_X, TEST_PRECISION)
+ .segmentTo(center));
+ }
+
+ @Test
+ public void testLinecast_segment_startEndPointsOnBoundaries() {
+ // arrange
+ BoundarySourceLinecastWrapper2D wrapper = new BoundarySourceLinecastWrapper2D(UNIT_SQUARE);
+
+ // act/assert
+ LinecastChecker2D.with(wrapper)
+ .returns(Vector2D.of(1, 0.5), Vector2D.Unit.PLUS_X)
+ .and(Vector2D.of(0, 0.5), Vector2D.Unit.MINUS_X)
+ .whenGiven(Segment.fromPoints(Vector2D.of(1, 0.5), Vector2D.of(0, 0.5), TEST_PRECISION));
+ }
+
+ @Test
+ public void testLinecast_segment_alongFace() {
+ // arrange
+ BoundarySourceLinecastWrapper2D wrapper = new BoundarySourceLinecastWrapper2D(UNIT_SQUARE);
+
+ // act/assert
+
+ // includes two intersecting boundaries
+ LinecastChecker2D.with(wrapper)
+ .returns(Vector2D.of(0, 1), Vector2D.Unit.MINUS_X)
+ .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X)
+ .whenGiven(Segment.fromPoints(Vector2D.of(-1, 1), Vector2D.of(2, 1), TEST_PRECISION));
+
+ // one intersecting boundary
+ LinecastChecker2D.with(wrapper)
+ .returns(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X)
+ .whenGiven(Segment.fromPoints(Vector2D.of(0.25, 1), Vector2D.of(2, 1), TEST_PRECISION));
+
+ // no intersecting boundary
+ LinecastChecker2D.with(wrapper)
+ .returnsNothing()
+ .whenGiven(Segment.fromPoints(Vector2D.of(0.25, 1), Vector2D.of(0.75, 1), TEST_PRECISION));
+ }
+
+ @Test
+ public void testLinecast_segment_corners() {
+ // arrange
+ BoundarySourceLinecastWrapper2D wrapper = new BoundarySourceLinecastWrapper2D(UNIT_SQUARE);
+
+ // act/assert
+
+ // through corner
+ LinecastChecker2D.with(wrapper)
+ .returns(Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y)
+ .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X)
+ .whenGiven(Segment.fromPoints(Vector2D.of(0, 2), Vector2D.of(2, 0), TEST_PRECISION));
+
+ // starts on corner
+ LinecastChecker2D.with(wrapper)
+ .returns(Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y)
+ .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X)
+ .whenGiven(Segment.fromPoints(Vector2D.of(1, 1), Vector2D.of(2, 0), TEST_PRECISION));
+
+ // ends on corner
+ LinecastChecker2D.with(wrapper)
+ .returns(Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y)
+ .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X)
+ .whenGiven(Segment.fromPoints(Vector2D.of(0, 2), Vector2D.of(1, 1), TEST_PRECISION));
+ }
+}
+
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/ConvexAreaTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/ConvexAreaTest.java
index a054329..2ed0e37 100644
--- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/ConvexAreaTest.java
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/ConvexAreaTest.java
@@ -664,6 +664,47 @@ public class ConvexAreaTest {
}
@Test
+ public void testLinecast_full() {
+ // arrange
+ ConvexArea area = ConvexArea.full();
+
+ // act/assert
+ LinecastChecker2D.with(area)
+ .returnsNothing()
+ .whenGiven(Line.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION));
+
+ LinecastChecker2D.with(area)
+ .returnsNothing()
+ .whenGiven(Segment.fromPoints(Vector2D.Unit.MINUS_X, Vector2D.Unit.PLUS_X, TEST_PRECISION));
+ }
+
+ @Test
+ public void testLinecast() {
+ // arrange
+ ConvexArea area = ConvexArea.fromVertexLoop(Arrays.asList(
+ Vector2D.ZERO, Vector2D.of(1, 0),
+ Vector2D.of(1, 1), Vector2D.of(0, 1)
+ ), TEST_PRECISION);
+
+ // act/assert
+ LinecastChecker2D.with(area)
+ .returnsNothing()
+ .whenGiven(Line.fromPoints(Vector2D.of(0, 5), Vector2D.of(1, 6), TEST_PRECISION));
+
+ LinecastChecker2D.with(area)
+ .returns(Vector2D.ZERO, Vector2D.Unit.MINUS_X)
+ .and(Vector2D.ZERO, Vector2D.Unit.MINUS_Y)
+ .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y)
+ .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X)
+ .whenGiven(Line.fromPoints(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION));
+
+ LinecastChecker2D.with(area)
+ .returns(Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y)
+ .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X)
+ .whenGiven(Segment.fromPoints(Vector2D.of(0.5, 0.5), Vector2D.of(1, 1), TEST_PRECISION));
+ }
+
+ @Test
public void testToString() {
// arrange
ConvexArea area = ConvexArea.full();
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/LinecastChecker2D.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/LinecastChecker2D.java
new file mode 100644
index 0000000..3cc22ad
--- /dev/null
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/LinecastChecker2D.java
@@ -0,0 +1,191 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.geometry.euclidean.twod;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
+import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
+import org.junit.Assert;
+
+/** Helper class designed to assist with linecast test assertions in 2D.
+ */
+class LinecastChecker2D {
+
+ private static final double TEST_EPS = 1e-10;
+
+ private static final DoublePrecisionContext TEST_PRECISION =
+ new EpsilonDoublePrecisionContext(TEST_EPS);
+
+ /** The linecastable target. */
+ private final Linecastable2D target;
+
+ /** List of expected results from the line cast operation. */
+ private final List<ExpectedResult> expectedResults = new ArrayList<>();
+
+ /** Construct a new instance that performs linecast assertions against the
+ * given target.
+ * @param target
+ */
+ LinecastChecker2D(final Linecastable2D target) {
+ this.target = target;
+ }
+
+ /** Configure the instance to expect no results (an empty list from linecast() and null from
+ * linecastFirst()) from the next linecast operation performed by {@link #whenGiven(Line)}
+ * or {@link #whenGiven(Segment)}.
+ * @return
+ */
+ public LinecastChecker2D returnsNothing() {
+ expectedResults.clear();
+
+ return this;
+ }
+
+ /** Configure the instance to expect a linecast point with the given parameters on the next
+ * linecast operation. Multiple calls to this method and/or {@link #and(Vector2D, Vector2D)}
+ * create an internal ordered list of results.
+ * @param point
+ * @param normal
+ * @return
+ */
+ public LinecastChecker2D returns(final Vector2D point, final Vector2D normal) {
+ expectedResults.add(new ExpectedResult(point, normal));
+
+ return this;
+ }
+
+ /** Fluent API alias for {@link #returns(Vector2D, Vector2D)}.
+ * @param point
+ * @param normal
+ * @return
+ */
+ public LinecastChecker2D and(final Vector2D point, final Vector2D normal) {
+ return returns(point, normal);
+ }
+
+ /** Perform {@link Linecastable2D#linecast(Line)} and {@link Linecastable2D#linecastFirst(Line)}
+ * operations using the given line and assert that the results match the configured expected
+ * values.
+ * @param line
+ */
+ public void whenGiven(final Line line) {
+ checkLinecastResults(target.linecast(line), line);
+ checkLinecastFirstResult(target.linecastFirst(line), line);
+ }
+
+ /** Perform {@link Linecastable2D#linecast(Segment)} and {@link Linecastable2D#linecastFirst(Segment)}
+ * operations using the given line segment and assert that the results match the configured
+ * expected results.
+ * @param segment
+ */
+ public void whenGiven(final Segment segment) {
+ Line line = segment.getLine();
+
+ checkLinecastResults(target.linecast(segment), line);
+ checkLinecastFirstResult(target.linecastFirst(segment), line);
+ }
+
+ /** Check that the given set of linecast result points matches those expected.
+ * @param results
+ * @param line
+ */
+ private void checkLinecastResults(List<LinecastPoint2D> results, Line line) {
+ Assert.assertNotNull("Linecast result list cannot be null", results);
+ Assert.assertEquals("Unexpected result size for linecast", expectedResults.size(), results.size());
+
+ for (int i = 0; i < expectedResults.size(); ++i) {
+ LinecastPoint2D expected = toLinecastPoint(expectedResults.get(i), line);
+ LinecastPoint2D actual = results.get(i);
+
+ if (!eq(expected, actual)) {
+ Assert.fail("Unexpected linecast point at index " + i + " expected " + expected +
+ " but was " + actual);
+ }
+ }
+ }
+
+ /** Check that the given linecastFirst result matches that expected.
+ * @param result
+ * @param line
+ */
+ private void checkLinecastFirstResult(LinecastPoint2D result, Line line) {
+ if (expectedResults.isEmpty()) {
+ Assert.assertNull("Expected linecastFirst result to be null", result);
+ } else {
+ LinecastPoint2D expected = toLinecastPoint(expectedResults.get(0), line);
+
+ Assert.assertNotNull("Expected linecastFirst result to not be null", result);
+
+ if (!eq(expected, result)) {
+ Assert.fail("Unexpected result from linecastFirst: expected " + expected +
+ " but was " + result);
+ }
+ }
+ }
+
+ /** Fluent API method for creating new instances.
+ * @param src
+ * @return
+ */
+ public static LinecastChecker2D with(final Linecastable2D src) {
+ return new LinecastChecker2D(src);
+ }
+
+ /** Return true if the given linecast points are equivalent according to the test precision.
+ * @param expected
+ * @param actual
+ * @return
+ */
+ private static boolean eq(LinecastPoint2D a, LinecastPoint2D b) {
+ return a.getPoint().eq(b.getPoint(), TEST_PRECISION) &&
+ a.getNormal().eq(b.getNormal(), TEST_PRECISION) &&
+ a.getLine().equals(b.getLine()) &&
+ TEST_PRECISION.eq(a.getAbscissa(), b.getAbscissa());
+ }
+
+ /** Convert an {@link ExpectedResult} struct to a {@link LinecastPoint2D} instance
+ * using the given line.
+ * @param expected
+ * @param line
+ * @return
+ */
+ private static LinecastPoint2D toLinecastPoint(ExpectedResult expected, Line line) {
+ return new LinecastPoint2D(expected.getPoint(), expected.getNormal(), line);
+ }
+
+ /** Class containing intermediate expected results for a linecast operation.
+ */
+ private static final class ExpectedResult {
+ private final Vector2D point;
+ private final Vector2D normal;
+
+ ExpectedResult(final Vector2D point, final Vector2D normal) {
+ this.point = point;
+ this.normal = normal;
+ }
+
+ public Vector2D getPoint() {
+ return point;
+ }
+
+ public Vector2D getNormal() {
+ return normal;
+ }
+ }
+}
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/LinecastPoint2DTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/LinecastPoint2DTest.java
new file mode 100644
index 0000000..29a0d6d
--- /dev/null
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/LinecastPoint2DTest.java
@@ -0,0 +1,126 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.geometry.euclidean.twod;
+
+import org.apache.commons.geometry.core.GeometryTestUtils;
+import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
+import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class LinecastPoint2DTest {
+
+ private static final double TEST_EPS = 1e-10;
+
+ private static final DoublePrecisionContext TEST_PRECISION =
+ new EpsilonDoublePrecisionContext(TEST_EPS);
+
+ private static final Line X_AXIS =
+ Line.fromPointAndDirection(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION);
+
+ private static final Line Y_AXIS =
+ Line.fromPointAndDirection(Vector2D.ZERO, Vector2D.Unit.PLUS_Y, TEST_PRECISION);
+
+ @Test
+ public void testProperties() {
+ // arrange
+ Vector2D pt = Vector2D.of(1, 1);
+ Vector2D normal = Vector2D.Unit.PLUS_X;
+
+ LinecastPoint2D it = new LinecastPoint2D(pt, normal, X_AXIS);
+
+ // act
+ Assert.assertSame(pt, it.getPoint());
+ Assert.assertSame(normal, it.getNormal());
+ Assert.assertSame(X_AXIS, it.getLine());
+ Assert.assertEquals(1.0, it.getAbscissa(), TEST_EPS);
+ }
+
+ @Test
+ public void testAbscissaOrder() {
+ // arrange
+ LinecastPoint2D a = new LinecastPoint2D(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X, X_AXIS);
+
+ LinecastPoint2D b = new LinecastPoint2D(Vector2D.of(2, 2), Vector2D.Unit.PLUS_X, X_AXIS);
+ LinecastPoint2D c = new LinecastPoint2D(Vector2D.of(-3, 3), Vector2D.Unit.PLUS_Y, X_AXIS);
+ LinecastPoint2D d = new LinecastPoint2D(Vector2D.of(1, 4), Vector2D.Unit.PLUS_Y, X_AXIS);
+ LinecastPoint2D e = new LinecastPoint2D(Vector2D.of(1, 4), Vector2D.Unit.PLUS_X, X_AXIS);
+
+ // act/assert
+ Assert.assertEquals(-1, LinecastPoint2D.ABSCISSA_ORDER.compare(a, b));
+ Assert.assertEquals(1, LinecastPoint2D.ABSCISSA_ORDER.compare(a, c));
+ Assert.assertEquals(1, LinecastPoint2D.ABSCISSA_ORDER.compare(a, d));
+ Assert.assertEquals(0, LinecastPoint2D.ABSCISSA_ORDER.compare(a, e));
+ }
+
+ @Test
+ public void testHashCode() {
+ // arrange
+ LinecastPoint2D a = new LinecastPoint2D(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X, X_AXIS);
+ LinecastPoint2D b = new LinecastPoint2D(Vector2D.of(2, 2), Vector2D.Unit.PLUS_X, X_AXIS);
+ LinecastPoint2D c = new LinecastPoint2D(Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y, X_AXIS);
+ LinecastPoint2D d = new LinecastPoint2D(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X, Y_AXIS);
+ LinecastPoint2D e = new LinecastPoint2D(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X, X_AXIS);
+
+ // act
+ int hash = a.hashCode();
+
+ // assert
+ Assert.assertEquals(hash, a.hashCode());
+
+ Assert.assertNotEquals(hash, b.hashCode());
+ Assert.assertNotEquals(hash, c.hashCode());
+ Assert.assertNotEquals(hash, d.hashCode());
+
+ Assert.assertEquals(hash, e.hashCode());
+ }
+
+ @Test
+ public void testEquals() {
+ // arrange
+ LinecastPoint2D a = new LinecastPoint2D(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X, X_AXIS);
+ LinecastPoint2D b = new LinecastPoint2D(Vector2D.of(2, 2), Vector2D.Unit.PLUS_X, X_AXIS);
+ LinecastPoint2D c = new LinecastPoint2D(Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y, X_AXIS);
+ LinecastPoint2D d = new LinecastPoint2D(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X, Y_AXIS);
+ LinecastPoint2D e = new LinecastPoint2D(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X, X_AXIS);
+
+ // act/assert
+ Assert.assertTrue(a.equals(a));
+
+ Assert.assertFalse(a.equals(null));
+ Assert.assertFalse(a.equals(new Object()));
+
+ Assert.assertFalse(a.equals(b));
+ Assert.assertFalse(a.equals(c));
+ Assert.assertFalse(a.equals(d));
+
+ Assert.assertTrue(a.equals(e));
+ Assert.assertTrue(e.equals(a));
+ }
+
+ @Test
+ public void testToString() {
+ // arrange
+ LinecastPoint2D it = new LinecastPoint2D(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X, X_AXIS);
+
+ // act
+ String str = it.toString();
+
+ // assert
+ GeometryTestUtils.assertContains("LinecastPoint2D[point= (1.0, 1.0), normal= (1.0, 0.0)", str);
+ }
+}
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/PolylineTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/PolylineTest.java
index e4318ec..f7af9c7 100644
--- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/PolylineTest.java
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/PolylineTest.java
@@ -922,6 +922,47 @@ public class PolylineTest {
}
@Test
+ public void testLinecast_empty() {
+ // arrange
+ Polyline polyline = Polyline.empty();
+
+ // act/assert
+ LinecastChecker2D.with(polyline)
+ .returnsNothing()
+ .whenGiven(Line.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION));
+
+ LinecastChecker2D.with(polyline)
+ .returnsNothing()
+ .whenGiven(Segment.fromPoints(Vector2D.Unit.MINUS_X, Vector2D.Unit.PLUS_X, TEST_PRECISION));
+ }
+
+ @Test
+ public void testLinecast() {
+ // arrange
+ Polyline polyline = Polyline.fromVertexLoop(Arrays.asList(
+ Vector2D.ZERO, Vector2D.of(1, 0),
+ Vector2D.of(1, 1), Vector2D.of(0, 1)
+ ), TEST_PRECISION);
+
+ // act/assert
+ LinecastChecker2D.with(polyline)
+ .returnsNothing()
+ .whenGiven(Line.fromPoints(Vector2D.of(0, 5), Vector2D.of(1, 6), TEST_PRECISION));
+
+ LinecastChecker2D.with(polyline)
+ .returns(Vector2D.ZERO, Vector2D.Unit.MINUS_X)
+ .and(Vector2D.ZERO, Vector2D.Unit.MINUS_Y)
+ .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y)
+ .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X)
+ .whenGiven(Line.fromPoints(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION));
+
+ LinecastChecker2D.with(polyline)
+ .returns(Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y)
+ .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X)
+ .whenGiven(Segment.fromPoints(Vector2D.of(0.5, 0.5), Vector2D.of(1, 1), TEST_PRECISION));
+ }
+
+ @Test
public void testToString() {
// arrange
Line yAxis = Line.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_Y, TEST_PRECISION);
diff --git a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/RegionBSPTree2DTest.java b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/RegionBSPTree2DTest.java
index 1fbb863..5d781ae 100644
--- a/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/RegionBSPTree2DTest.java
+++ b/commons-geometry-euclidean/src/test/java/org/apache/commons/geometry/euclidean/twod/RegionBSPTree2DTest.java
@@ -973,6 +973,117 @@ public class RegionBSPTree2DTest {
}
@Test
+ public void testLinecast_empty() {
+ // arrange
+ RegionBSPTree2D tree = RegionBSPTree2D.empty();
+
+ // act/assert
+ LinecastChecker2D.with(tree)
+ .returnsNothing()
+ .whenGiven(Line.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION));
+
+ LinecastChecker2D.with(tree)
+ .returnsNothing()
+ .whenGiven(Segment.fromPoints(Vector2D.Unit.MINUS_X, Vector2D.Unit.PLUS_X, TEST_PRECISION));
+ }
+
+ @Test
+ public void testLinecast_full() {
+ // arrange
+ RegionBSPTree2D tree = RegionBSPTree2D.full();
+
+ // act/assert
+ LinecastChecker2D.with(tree)
+ .returnsNothing()
+ .whenGiven(Line.fromPoints(Vector2D.ZERO, Vector2D.Unit.PLUS_X, TEST_PRECISION));
+
+ LinecastChecker2D.with(tree)
+ .returnsNothing()
+ .whenGiven(Segment.fromPoints(Vector2D.Unit.MINUS_X, Vector2D.Unit.PLUS_X, TEST_PRECISION));
+ }
+
+ @Test
+ public void testLinecast() {
+ // arrange
+ RegionBSPTree2D tree = Boundaries2D.rect(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION)
+ .toTree();
+
+ // act/assert
+ LinecastChecker2D.with(tree)
+ .returnsNothing()
+ .whenGiven(Line.fromPoints(Vector2D.of(0, 5), Vector2D.of(1, 6), TEST_PRECISION));
+
+ LinecastChecker2D.with(tree)
+ .returns(Vector2D.ZERO, Vector2D.Unit.MINUS_X)
+ .and(Vector2D.ZERO, Vector2D.Unit.MINUS_Y)
+ .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y)
+ .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X)
+ .whenGiven(Line.fromPoints(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION));
+
+ LinecastChecker2D.with(tree)
+ .returns(Vector2D.of(1, 1), Vector2D.Unit.PLUS_Y)
+ .and(Vector2D.of(1, 1), Vector2D.Unit.PLUS_X)
+ .whenGiven(Segment.fromPoints(Vector2D.of(0.5, 0.5), Vector2D.of(1, 1), TEST_PRECISION));
+ }
+
+ @Test
+ public void testLinecast_complementedTree() {
+ // arrange
+ RegionBSPTree2D tree = Boundaries2D.rect(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION)
+ .toTree();
+
+ tree.complement();
+
+ // act/assert
+ LinecastChecker2D.with(tree)
+ .returnsNothing()
+ .whenGiven(Line.fromPoints(Vector2D.of(0, 5), Vector2D.of(1, 6), TEST_PRECISION));
+
+ LinecastChecker2D.with(tree)
+ .returns(Vector2D.ZERO, Vector2D.Unit.PLUS_Y)
+ .and(Vector2D.ZERO, Vector2D.Unit.PLUS_X)
+ .and(Vector2D.of(1, 1), Vector2D.Unit.MINUS_X)
+ .and(Vector2D.of(1, 1), Vector2D.Unit.MINUS_Y)
+ .whenGiven(Line.fromPoints(Vector2D.ZERO, Vector2D.of(1, 1), TEST_PRECISION));
+
+ LinecastChecker2D.with(tree)
+ .returns(Vector2D.of(1, 1), Vector2D.Unit.MINUS_X)
+ .and(Vector2D.of(1, 1), Vector2D.Unit.MINUS_Y)
+ .whenGiven(Segment.fromPoints(Vector2D.of(0.5, 0.5), Vector2D.of(1, 1), TEST_PRECISION));
+ }
+
+ @Test
+ public void testLinecast_complexRegion() {
+ // arrange
+ RegionBSPTree2D a = Polyline.fromVertexLoop(Arrays.asList(
+ Vector2D.ZERO, Vector2D.of(0, 1),
+ Vector2D.of(0.5, 1), Vector2D.of(0.5, 0)
+ ), TEST_PRECISION).toTree();
+ a.complement();
+
+ RegionBSPTree2D b = Polyline.fromVertexLoop(Arrays.asList(
+ Vector2D.of(0.5, 0), Vector2D.of(0.5, 1),
+ Vector2D.of(1, 1), Vector2D.of(1, 0)
+ ), TEST_PRECISION).toTree();
+ b.complement();
+
+ RegionBSPTree2D c = Polyline.fromVertexLoop(Arrays.asList(
+ Vector2D.of(0.5, 0.5), Vector2D.of(1.5, 0.5),
+ Vector2D.of(1.5, 1.5), Vector2D.of(0.5, 1.5)
+ ), TEST_PRECISION).toTree();
+
+ RegionBSPTree2D tree = RegionBSPTree2D.empty();
+ tree.union(a, b);
+ tree.union(c);
+
+ // act/assert
+ LinecastChecker2D.with(tree)
+ .returns(Vector2D.of(1.5, 1.5), Vector2D.Unit.PLUS_Y)
+ .and(Vector2D.of(1.5, 1.5), Vector2D.Unit.PLUS_X)
+ .whenGiven(Segment.fromPoints(Vector2D.of(0.25, 0.25), Vector2D.of(2, 2), TEST_PRECISION));
+ }
+
+ @Test
public void testTransform() {
// arrange
RegionBSPTree2D tree = Boundaries2D.rect(Vector2D.of(1, 1), Vector2D.of(3, 2), TEST_PRECISION)