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 91a1ca0ee16e605d23dc3ad877a017e3272822d8 Author: jsorel <[email protected]> AuthorDate: Wed Oct 21 13:34:08 2026 +0200 fix(Delaunay): fix incorrect point hash --- .../operation/triangulate/delaunay/Delaunay.java | 50 +++++++++++++++++----- 1 file changed, 40 insertions(+), 10 deletions(-) diff --git a/incubator/src/org.apache.sis.geometry/main/org/apache/sis/geometries/operation/triangulate/delaunay/Delaunay.java b/incubator/src/org.apache.sis.geometry/main/org/apache/sis/geometries/operation/triangulate/delaunay/Delaunay.java index eb74236c50..2b2267b0a4 100644 --- a/incubator/src/org.apache.sis.geometry/main/org/apache/sis/geometries/operation/triangulate/delaunay/Delaunay.java +++ b/incubator/src/org.apache.sis.geometry/main/org/apache/sis/geometries/operation/triangulate/delaunay/Delaunay.java @@ -24,7 +24,9 @@ import java.util.concurrent.atomic.AtomicInteger; import java.util.logging.Level; import java.util.logging.Logger; import org.opengis.geometry.Envelope; +import org.apache.sis.geometries.Geometries; import org.apache.sis.geometries.index.KdTree; +import org.apache.sis.geometries.internal.shared.Planar; import org.apache.sis.geometries.mesh.MeshPrimitive; import org.apache.sis.geometries.mesh.MeshPrimitive.Vertex; import org.apache.sis.geometries.operation.OperationException; @@ -76,16 +78,8 @@ public final class Delaunay { @Override public void addFirst(OrientedEdge e) { - //create a key not affected by edge orientation - int idx0 = (int)e.getStart().getIndex(); - int idx1 = (int)e.getEnd().getIndex(); - if (idx0 > idx1) { - int i = idx0; - idx0 = idx1; - idx1 = i; - } - final long key = idx0 + ((long) idx1) << 32l; - if (unique.add(key)) { + //key not affected by edge orientation + if (unique.add(Planar.edgeKey((int) e.getStart().getIndex(), (int) e.getEnd().getIndex()))) { super.addFirst(e); } else { crossingConstraints.incrementAndGet(); @@ -221,6 +215,42 @@ public final class Delaunay { return primitive; } + /** + * Computes a constrained Delaunay triangulation of points in the plane. + * The points must be distinct, and the constraint segments must not cross each other. + * Flat triangles are removed and the returned triangles are counterclockwise. + * + * @param xy (x,y) coordinates of the points, two values per point. + * @param constraints pairs of point indices of the segments which must be edges of the triangulation. + * @return indices of the points of the triangles, three values per triangle. + * @throws OperationException if an algorithm exception occurs + */ + public static int[] triangulate(final double[] xy, final int[] constraints) throws OperationException { + ArgumentChecks.ensureNonNull("xy", xy); + ArgumentChecks.ensureNonNull("constraints", constraints); + if (xy.length < 6) { + return new int[0]; + } + final MeshPrimitive.Points points = new MeshPrimitive.Points(); + points.setPositions(NDArrays.of(Geometries.getUndefinedCRS(2), xy.clone())); + final Delaunay delaunay = new Delaunay(); + delaunay.build(points); + if (constraints.length > 0) { + delaunay.pushConstraint(NDArrays.ofUnsigned(1, constraints), true); + } + //triangles are counterclockwise, only flat ones need to be removed + final int[] index = delaunay.getTrianglesIndex().toArrayInt(); + int n = 0; + for (int i = 0; i < index.length; i += 3) { + final int a = index[i]*2, b = index[i+1]*2, c = index[i+2]*2; + if (Maths.lineSide(xy[a], xy[a+1], xy[b], xy[b+1], xy[c], xy[c+1]) != 0) { + System.arraycopy(index, i, index, n, 3); + n += 3; + } + } + return Arrays.copyOf(index, n); + } + /** * Create the delaunay triangulation without constraints. * @throws IllegalArgumentException if an index is incorrect
