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 c596827e598825d02b203338999b8fab0ea50ae9 Author: jsorel <[email protected]> AuthorDate: Wed Oct 14 16:27:00 2026 +0200 fix(Geometry): fix EarClipping holes not correctly handled --- .../operation/triangulate/EarClipping.java | 24 +++++-- .../test/org/apache/sis/geometries/EmptyTest.java | 6 +- .../sis/geometries/operation/ToPrimitiveTest.java | 75 ++++++++++++++++++++-- 3 files changed, 92 insertions(+), 13 deletions(-) diff --git a/incubator/src/org.apache.sis.geometry/main/org/apache/sis/geometries/operation/triangulate/EarClipping.java b/incubator/src/org.apache.sis.geometry/main/org/apache/sis/geometries/operation/triangulate/EarClipping.java index 2a73af2664..b3f4660abc 100644 --- a/incubator/src/org.apache.sis.geometry/main/org/apache/sis/geometries/operation/triangulate/EarClipping.java +++ b/incubator/src/org.apache.sis.geometry/main/org/apache/sis/geometries/operation/triangulate/EarClipping.java @@ -17,9 +17,12 @@ package org.apache.sis.geometries.operation.triangulate; import java.util.ArrayList; +import java.util.Arrays; import java.util.Collections; import java.util.Comparator; import java.util.List; +import java.util.stream.Collectors; +import org.opengis.referencing.crs.CoordinateReferenceSystem; import org.apache.sis.geometries.Geometry; import org.apache.sis.geometries.DataPointsType; import org.apache.sis.geometries.curve.LineString; @@ -130,7 +133,9 @@ public class EarClipping { public MeshPrimitive.Triangles toMesh(Polygon polygon) { final List<Vector[]> list = triangulate(polygon); - final Array positions = NDArrays.of(polygon.getCoordinateReferenceSystem(), new double[list.size()*3*2]); + final CoordinateReferenceSystem crs = polygon.getCoordinateReferenceSystem(); + final int dimension = crs.getCoordinateSystem().getDimension(); + final Array positions = NDArrays.of(crs, new double[list.size()*3*dimension]); for (int i = 0, k = 0, n = list.size(); i < n; i++, k+=3) { final Vector[] t = list.get(i); positions.set(k+0, t[0]); @@ -147,19 +152,23 @@ public class EarClipping { private void run(SimplePolygon part){ //build a single geometry linking inner holes. + //the array stream reuses a single vector for all positions, so each one is copied. final List<Vector<?>> borderCoords = new ArrayList<>(); - part.outter.getDataPoints().getAttributeArray(DataPointsType.ATT_POSITION).stream(false).forEach(borderCoords::add); + part.outter.getDataPoints().getAttributeArray(DataPointsType.ATT_POSITION).stream(false) + .map(Vector::copy).forEach(borderCoords::add); //sort inner holes by minimum x value orderHoles(part); //attach holes to the main geometry for(int i=0,n=part.inners.size();i<n;i++){ //we must find the minimum x coordinate in the inner loop - final List<Vector<?>> loop = part.inners.get(i).getDataPoints().getAttributeArray(DataPointsType.ATT_POSITION).stream(false).toList(); + //copied for the same reason as the outer loop, in a mutable list since its last point is removed below. + final List<Vector<?>> loop = part.inners.get(i).getDataPoints().getAttributeArray(DataPointsType.ATT_POSITION).stream(false) + .map(Vector::copy).collect(Collectors.toCollection(ArrayList::new)); int index = 0; Vector min = loop.get(index); for(int k=1,p=loop.size();k<p;k++){ - Vector candidate = (Vector) loop.get(1); + Vector candidate = (Vector) loop.get(k); if (candidate.get(0) < min.get(0)) { min = candidate; index = k; @@ -304,8 +313,13 @@ public class EarClipping { if (!isConvex(i)){ //check it's not one of the current segment if(i!=index && i!=indexNext && i!=indexPrevious){ + final double[] p = new double[]{coords[i].get(0),coords[i].get(1)}; + //a hole bridge duplicates its end points, a copy located on a triangle vertex does not block the ear + if (Arrays.equals(p, a) || Arrays.equals(p, b) || Arrays.equals(p, c)) { + continue; + } //check if it's in the segment triangle - if(Maths.inTriangle(a, b, c, new double[]{coords[i].get(0),coords[i].get(1)})){ + if(Maths.inTriangle(a, b, c, p)){ return false; } } diff --git a/incubator/src/org.apache.sis.geometry/test/org/apache/sis/geometries/EmptyTest.java b/incubator/src/org.apache.sis.geometry/test/org/apache/sis/geometries/EmptyTest.java index b324a85ba9..57e21329b7 100644 --- a/incubator/src/org.apache.sis.geometry/test/org/apache/sis/geometries/EmptyTest.java +++ b/incubator/src/org.apache.sis.geometry/test/org/apache/sis/geometries/EmptyTest.java @@ -163,11 +163,11 @@ public abstract class EmptyTest extends GeometryTest { final Empty empty = createEmpty(CRS_2D); assertEquals(-1, empty.getDimension(null), "Dimension of the whole geometry."); /* - * TODO: the empty set has no interior position, therefore no position where the dimension - * is unambiguous. Replace this check if a value is defined for that case. + * The empty set contains no position, so no position has a dimension in it: + * −1, as for a position outside the elements of a collection. */ final DirectPosition position = new GeneralDirectPosition(CRS_2D); - assertThrows(UnsupportedOperationException.class, () -> empty.getDimension(position)); + assertEquals(-1, empty.getDimension(position), "Dimension at a position."); } @Test diff --git a/incubator/src/org.apache.sis.geometry/test/org/apache/sis/geometries/operation/ToPrimitiveTest.java b/incubator/src/org.apache.sis.geometry/test/org/apache/sis/geometries/operation/ToPrimitiveTest.java index bed4931ace..a71bccc12c 100644 --- a/incubator/src/org.apache.sis.geometry/test/org/apache/sis/geometries/operation/ToPrimitiveTest.java +++ b/incubator/src/org.apache.sis.geometry/test/org/apache/sis/geometries/operation/ToPrimitiveTest.java @@ -67,14 +67,79 @@ public class ToPrimitiveTest { @Test public void testPolygon() { - final Array positions = NDArrays.of(CRS2D, new double[]{0,1,2,3}); - final DataPoints points = GeometryFactory.DEFAULT.createDataPoints(positions); - final LinearRing exterior = GeometryFactory.DEFAULT.createLinearRing(points); - final Polygon point = GeometryFactory.DEFAULT.createPolygon(exterior, null); - final Geometry result = new GeometryProcessor().toPrimitive(point); + final LinearRing exterior = ring(0,0, 2,0, 2,2, 0,2, 0,0); + final Polygon polygon = GeometryFactory.DEFAULT.createPolygon(exterior, null); + final Geometry result = new GeometryProcessor().toPrimitive(polygon); assertTrue(result instanceof MeshPrimitive); final MeshPrimitive primitive = (MeshPrimitive) result; assertEquals(MeshPrimitive.Type.TRIANGLES, primitive.getType()); + assertEquals(6, primitive.getPositions().getLength(), "Expected 2 triangles."); + assertEquals(4, trianglesArea(primitive), 1E-12); + } + + /** + * Tests the triangulation of a polygon with a hole, which requires to cut the exterior + * ring toward the hole. The triangles shall cover the polygon area without the hole. + */ + @Test + public void testPolygonWithHole() { + final LinearRing exterior = ring(0,0, 10,0, 10,10, 0,10, 0,0); + final LinearRing hole = ring(2,2, 2,4, 4,4, 4,2, 2,2); + final Polygon polygon = GeometryFactory.DEFAULT.createPolygon(exterior, java.util.List.of(hole)); + final MeshPrimitive primitive = (MeshPrimitive) new GeometryProcessor().toPrimitive(polygon); + assertEquals(MeshPrimitive.Type.TRIANGLES, primitive.getType()); + assertEquals(96, trianglesArea(primitive), 1E-9); + } + + /** + * Same test as {@link #testPolygonWithHole()}, with the hole ring starting at a point which is + * not its leftmost one. The cut toward the hole shall still start from the leftmost point. + */ + @Test + public void testPolygonWithHoleStartingAnywhere() { + final LinearRing exterior = ring(0,0, 10,0, 10,10, 0,10, 0,0); + final LinearRing hole = ring(4,4, 4,2, 2,2, 2,4, 4,4); + final Polygon polygon = GeometryFactory.DEFAULT.createPolygon(exterior, java.util.List.of(hole)); + final MeshPrimitive primitive = (MeshPrimitive) new GeometryProcessor().toPrimitive(polygon); + assertEquals(96, trianglesArea(primitive), 1E-9); + } + + /** + * Tests the triangulation of a three-dimensional polygon, which shall keep the z coordinates. + */ + @Test + public void testPolygon3D() { + final LinearRing exterior = GeometryFactory.DEFAULT.createLinearRing(GeometryFactory.DEFAULT.createDataPoints( + NDArrays.of(CommonCRS.WGS84.geographic3D(), 0,0,5, 2,0,5, 2,2,7, 0,2,7, 0,0,5))); + final Polygon polygon = GeometryFactory.DEFAULT.createPolygon(exterior, null); + final MeshPrimitive primitive = (MeshPrimitive) new GeometryProcessor().toPrimitive(polygon); + assertEquals(MeshPrimitive.Type.TRIANGLES, primitive.getType()); + assertEquals(3, primitive.getPositions().getDimension()); + assertEquals(6, primitive.getPositions().getLength(), "Expected 2 triangles."); + final double[] c = primitive.getPositions().toArrayDouble(); + for (int i = 0; i < c.length; i += 3) { + assertEquals(c[i+1] == 0 ? 5 : 7, c[i+2], "z shall follow the polygon plane."); + } + } + + /** + * Creates a ring in the two-dimensional test CRS. + */ + private static LinearRing ring(final double... coordinates) { + return GeometryFactory.DEFAULT.createLinearRing( + GeometryFactory.DEFAULT.createDataPoints(NDArrays.of(CRS2D, coordinates))); + } + + /** + * Returns the sum of the areas of the triangles of the given non-indexed mesh. + */ + private static double trianglesArea(final MeshPrimitive primitive) { + final double[] c = primitive.getPositions().toArrayDouble(); + double area = 0; + for (int i = 0; i + 5 < c.length; i += 6) { + area += Math.abs((c[i+2] - c[i]) * (c[i+5] - c[i+1]) - (c[i+4] - c[i]) * (c[i+3] - c[i+1])) / 2; + } + return area; } @Test
