You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@sis.apache.org by js...@apache.org on 2026/10/14 15:00:17 UTC
(sis) 10/12: fix(Geometry): fix EarClipping holes not correctly handled
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 <jo...@geomatys.com>
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