This is an automated email from the ASF dual-hosted git repository. asf-gitbox-commits pushed a commit to branch geoapi-4.0 in repository https://gitbox.apache.org/repos/asf/sis.git
commit 13e5ba92f837a8151f66c19c57a2cdc9934038b9 Author: jsorel <[email protected]> AuthorDate: Fri Oct 16 15:56:14 2026 +0200 feat(Math): add Maths.isConvex/inCone, Distance.nearest(line,point) --- .../apache/sis/geometries/operation/Distance.java | 42 ++++++++++++++++++ .../main/org/apache/sis/maths/Maths.java | 51 ++++++++++++++++++++++ .../sis/geometries/operation/DistanceTest.java | 24 ++++++++++ .../test/org/apache/sis/maths/MathsTest.java | 33 ++++++++++++++ 4 files changed, 150 insertions(+) diff --git a/incubator/src/org.apache.sis.geometry/main/org/apache/sis/geometries/operation/Distance.java b/incubator/src/org.apache.sis.geometry/main/org/apache/sis/geometries/operation/Distance.java index 379ede03bc..ba896a5647 100644 --- a/incubator/src/org.apache.sis.geometry/main/org/apache/sis/geometries/operation/Distance.java +++ b/incubator/src/org.apache.sis.geometry/main/org/apache/sis/geometries/operation/Distance.java @@ -19,6 +19,7 @@ package org.apache.sis.geometries.operation; import java.util.List; import org.apache.sis.geometries.Point; import org.apache.sis.maths.Maths; +import org.apache.sis.maths.ReadOnly; import org.apache.sis.maths.Vectors; import org.apache.sis.maths.Vector; @@ -188,6 +189,47 @@ public final class Distance { } } + /** + * A point on a polyline, given by the segment where it is and its position along that segment. + * + * @param segment index of the segment, which goes from the point at that index to the next one. + * @param ratio position along the segment, from 0 at its start to 1 at its end. + */ + public record SegmentPoint(int segment, double ratio) { + } + + /** + * Finds the point of a polyline nearest to the given point. + * Only the two first coordinates of the positions are used. + * + * @param polyline positions of the polyline, at least two + * @param point the point to search the nearest point of the polyline for + * @return the nearest point of the polyline, on the first nearest segment if many are at the same distance + * @throws IllegalArgumentException if the polyline has less than two positions + */ + public static SegmentPoint nearestSegment(List<? extends ReadOnly.Vector<?>> polyline, ReadOnly.Vector<?> point) { + if (polyline.size() < 2) { + throw new IllegalArgumentException("A polyline shall have at least two positions."); + } + final double x = point.get(0), y = point.get(1); + SegmentPoint nearest = null; + double nearestDistance = Double.POSITIVE_INFINITY; + for (int i = 1; i < polyline.size(); i++) { + final ReadOnly.Vector<?> a = polyline.get(i-1), b = polyline.get(i); + final double ax = a.get(0), ay = a.get(1), bx = b.get(0), by = b.get(1); + final double projection = Maths.projectionRatio(ax, ay, bx, by, x, y); + final double ratio = Double.isNaN(projection) ? 0 : Maths.clamp(projection, 0, 1); // NaN if the segment has no length. + final double dx = ax + ratio * (bx - ax) - x; + final double dy = ay + ratio * (by - ay) - y; + final double distance = dx*dx + dy*dy; + if (distance < nearestDistance) { + nearestDistance = distance; + nearest = new SegmentPoint(i - 1, ratio); + } + } + return nearest; + } + /** * Point to point distance. */ diff --git a/incubator/src/org.apache.sis.geometry/main/org/apache/sis/maths/Maths.java b/incubator/src/org.apache.sis.geometry/main/org/apache/sis/maths/Maths.java index 41948a2609..43b573aaa4 100644 --- a/incubator/src/org.apache.sis.geometry/main/org/apache/sis/maths/Maths.java +++ b/incubator/src/org.apache.sis.geometry/main/org/apache/sis/maths/Maths.java @@ -306,6 +306,57 @@ public final class Maths { return ShewchukPredicates.orient2d(x1, y1, x2, y2, x, y); } + /** + * Test if a ring is convex at a vertex, which is whether the ring turns toward its inside at that vertex: + * to the right for a clockwise ring, to the left for a counterclockwise ring. Only X,Y ordinates are used. + * A vertex aligned with its two neighbors is not convex. A vertex where the ring turns toward its outside, + * called reflex, is convex for the ring traversed in the opposite direction. + * + * @param previous vertex before the tested vertex in the ring + * @param vertex tested vertex + * @param next vertex after the tested vertex in the ring + * @param clockwise whether the ring is clockwise + * @return true if the ring is convex at the vertex + */ + public static boolean isConvex(ReadOnly.Vector<?> previous, + ReadOnly.Vector<?> vertex, + ReadOnly.Vector<?> next, + boolean clockwise) { + final double side = lineSide(previous, vertex, next); + return clockwise ? side < 0 : side > 0; + } + + /** + * Test if the segment from a vertex of a ring toward a point starts inside the ring, which is between + * the two edges of the ring at that vertex. A segment along one of the edges is not inside. + * Only X,Y ordinates are used. This is the {@code InCone} test of Joseph O'Rourke in + * <cite>Computational Geometry in C</cite>, which tells whether a segment between two vertices + * of a polygon is a diagonal near its ends. + * + * @param previous vertex before the tested vertex in the ring + * @param vertex start of the segment, a vertex of the ring + * @param next vertex after the tested vertex in the ring + * @param point end of the segment + * @param clockwise whether the ring is clockwise + * @return true if the segment starts inside the ring + */ + public static boolean inCone(ReadOnly.Vector<?> previous, + ReadOnly.Vector<?> vertex, + ReadOnly.Vector<?> next, + ReadOnly.Vector<?> point, + boolean clockwise) + { + final double sign = clockwise ? -1 : 1; + if (sign * lineSide(vertex, next, previous) >= 0) { + //convex vertex: the segment shall be strictly between the two edges. + return sign * lineSide(vertex, point, previous) > 0 + && sign * lineSide(point, vertex, next) > 0; + } + //reflex vertex: the segment shall not be in the outside wedge, its edges included. + return !(sign * lineSide(vertex, point, next) >= 0 + && sign * lineSide(point, vertex, previous) >= 0); + } + /** * Test if point is inside triangle using barycentric weights. * Only X,Y ordinates are used. diff --git a/incubator/src/org.apache.sis.geometry/test/org/apache/sis/geometries/operation/DistanceTest.java b/incubator/src/org.apache.sis.geometry/test/org/apache/sis/geometries/operation/DistanceTest.java index c21f4b1b7b..95e26a0690 100644 --- a/incubator/src/org.apache.sis.geometry/test/org/apache/sis/geometries/operation/DistanceTest.java +++ b/incubator/src/org.apache.sis.geometry/test/org/apache/sis/geometries/operation/DistanceTest.java @@ -16,11 +16,14 @@ */ package org.apache.sis.geometries.operation; +import java.util.List; import javax.measure.Quantity; import org.apache.sis.geometries.Geometry; import org.apache.sis.geometries.GeometryFactory; import org.apache.sis.geometries.Point; import org.apache.sis.maths.SampleSystem; +import org.apache.sis.maths.Vector; +import org.apache.sis.maths.Vectors; import org.apache.sis.measure.Quantities; import org.apache.sis.measure.Units; import org.apache.sis.referencing.CommonCRS; @@ -28,6 +31,7 @@ import org.apache.sis.referencing.CommonCRS; // Test dependencies import static org.junit.jupiter.api.Assertions.assertEquals; import static org.junit.jupiter.api.Assertions.assertNull; +import static org.junit.jupiter.api.Assertions.assertThrows; import org.junit.jupiter.api.Test; @@ -168,4 +172,24 @@ public class DistanceTest extends AbstractD9IMTest { return result.getValue().doubleValue(); } + /** + * Returns a vector of the given values. + */ + private static Vector<?> vector(final double... values) { + return Vectors.createDouble(values.length).set(values); + } + + /** + * Tests {@code Distance.nearestSegment(…)}, which clamps the nearest point inside the segments. + */ + @Test + public void testNearestSegment() { + final List<Vector<?>> polyline = List.of(vector(0,0), vector(4,0), vector(4,4)); + assertEquals(new Distance.SegmentPoint(0, 0.25), Distance.nearestSegment(polyline, vector( 1, 2))); + assertEquals(new Distance.SegmentPoint(1, 0.75), Distance.nearestSegment(polyline, vector( 5, 3))); + assertEquals(new Distance.SegmentPoint(0, 0), Distance.nearestSegment(polyline, vector(-2, -1)), "Before the start"); + //a segment without length is a point. + assertEquals(new Distance.SegmentPoint(1, 0.5), Distance.nearestSegment(List.of(vector(0,0), vector(0,0), vector(2,0)), vector(1, 1))); + assertThrows(IllegalArgumentException.class, () -> Distance.nearestSegment(List.of(vector(0,0)), vector(1, 1))); + } } diff --git a/incubator/src/org.apache.sis.geometry/test/org/apache/sis/maths/MathsTest.java b/incubator/src/org.apache.sis.geometry/test/org/apache/sis/maths/MathsTest.java index 2d52192a4b..ab7d3e59eb 100644 --- a/incubator/src/org.apache.sis.geometry/test/org/apache/sis/maths/MathsTest.java +++ b/incubator/src/org.apache.sis.geometry/test/org/apache/sis/maths/MathsTest.java @@ -149,6 +149,39 @@ public class MathsTest { assertFalse(Maths.inTriangle(a, d, e, vector(1, 0))); } + /** + * Tests {@link Maths#isConvex(ReadOnly.Vector, ReadOnly.Vector, ReadOnly.Vector, boolean)}. + */ + @Test + public void testIsConvex() { + //the counterclockwise ring (0,0), (4,0), (4,4) turns left at (4,0). + assertTrue (Maths.isConvex(vector(0,0), vector(4,0), vector(4,4), false)); + assertFalse(Maths.isConvex(vector(0,0), vector(4,0), vector(4,4), true)); + assertTrue (Maths.isConvex(vector(4,4), vector(4,0), vector(0,0), true), "Same ring traversed clockwise"); + //aligned vertices are not convex. + assertFalse(Maths.isConvex(vector(0,0), vector(2,0), vector(4,0), false)); + assertFalse(Maths.isConvex(vector(0,0), vector(2,0), vector(4,0), true)); + } + + /** + * Tests {@link Maths#inCone(ReadOnly.Vector, ReadOnly.Vector, ReadOnly.Vector, ReadOnly.Vector, boolean)} + * at a convex vertex and at a reflex vertex, in counterclockwise and clockwise rings. + */ + @Test + public void testInCone() { + //convex vertex (0,0) of the counterclockwise square (0,0), (4,0), (4,4), (0,4). + final Vector<?> vertex = vector(0,0), previous = vector(0,4), next = vector(4,0); + assertTrue (Maths.inCone(previous, vertex, next, vector( 2, 2), false)); + assertFalse(Maths.inCone(previous, vertex, next, vector(-1, -1), false)); + assertFalse(Maths.inCone(previous, vertex, next, vector( 2, 0), false), "Along an edge"); + assertTrue (Maths.inCone(next, vertex, previous, vector( 2, 2), true), "Same ring traversed clockwise"); + //reflex vertex (2,1) of the counterclockwise ring (0,0), (4,0), (4,4), (2,1), (0,4), with a notch above it. + final Vector<?> reflex = vector(2,1), before = vector(4,4), after = vector(0,4); + assertTrue (Maths.inCone(before, reflex, after, vector(2, 0), false)); + assertFalse(Maths.inCone(before, reflex, after, vector(2, 3), false), "In the notch"); + assertTrue (Maths.inCone(after, reflex, before, vector(2, 0), true), "Same ring traversed clockwise"); + } + /** * Tests {@link Maths#calculatePolygonNormal(Array)}, whose length is twice the area of the polygon. */
