This is an automated email from the ASF dual-hosted git repository.
jiayu pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/sedona.git
The following commit(s) were added to refs/heads/master by this push:
new aeb8822187 [GH-2611] Merge linestring splitting results to avoid extra
segments (#2612)
aeb8822187 is described below
commit aeb88221871a1b2f5f4604bbb36a683093c38e15
Author: Kristin Cowalcijk <[email protected]>
AuthorDate: Fri Feb 6 17:12:08 2026 +0800
[GH-2611] Merge linestring splitting results to avoid extra segments (#2612)
---
.../sedona/common/utils/GeometrySplitter.java | 26 +-
.../sedona/common/utils/LineStringMerger.java | 316 +++++++++++++++++++++
.../org/apache/sedona/common/FunctionsTest.java | 30 ++
3 files changed, 367 insertions(+), 5 deletions(-)
diff --git
a/common/src/main/java/org/apache/sedona/common/utils/GeometrySplitter.java
b/common/src/main/java/org/apache/sedona/common/utils/GeometrySplitter.java
index 89473c5d3c..5f663a9fd9 100644
--- a/common/src/main/java/org/apache/sedona/common/utils/GeometrySplitter.java
+++ b/common/src/main/java/org/apache/sedona/common/utils/GeometrySplitter.java
@@ -36,12 +36,9 @@ import org.locationtech.jts.geom.Point;
import org.locationtech.jts.geom.Polygon;
import org.locationtech.jts.linearref.LinearGeometryBuilder;
import org.locationtech.jts.operation.polygonize.Polygonizer;
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
/** Class to split geometry by other geometry. */
public final class GeometrySplitter {
- static final Logger logger = LoggerFactory.getLogger(GeometrySplitter.class);
private final GeometryFactory geometryFactory;
public GeometrySplitter(GeometryFactory geometryFactory) {
@@ -149,8 +146,27 @@ public final class GeometrySplitter {
private MultiLineString splitLinesByLines(Geometry inputLines, Geometry
blade) {
Geometry diff = inputLines.difference(blade);
- if (diff instanceof MultiLineString) {
- return (MultiLineString) diff;
+ Geometry merged =
+ LineStringMerger.mergeDifferenceSplit(diff, inputLines, blade,
geometryFactory);
+ if (merged instanceof MultiLineString) {
+ return (MultiLineString) merged;
+ } else if (merged instanceof LineString) {
+ return geometryFactory.createMultiLineString(new LineString[]
{(LineString) merged});
+ } else if (merged instanceof GeometryCollection) {
+ List<LineString> lineStrings = new ArrayList<>();
+ GeometryCollection gc = (GeometryCollection) merged;
+ for (int i = 0; i < gc.getNumGeometries(); i++) {
+ Geometry g = gc.getGeometryN(i);
+ if (g instanceof LineString) {
+ lineStrings.add((LineString) g);
+ } else if (g instanceof MultiLineString) {
+ MultiLineString mls = (MultiLineString) g;
+ for (int j = 0; j < mls.getNumGeometries(); j++) {
+ lineStrings.add((LineString) mls.getGeometryN(j));
+ }
+ }
+ }
+ return geometryFactory.createMultiLineString(lineStrings.toArray(new
LineString[0]));
} else {
return geometryFactory.createMultiLineString(new LineString[]
{(LineString) inputLines});
}
diff --git
a/common/src/main/java/org/apache/sedona/common/utils/LineStringMerger.java
b/common/src/main/java/org/apache/sedona/common/utils/LineStringMerger.java
new file mode 100644
index 0000000000..c7bb9f2310
--- /dev/null
+++ b/common/src/main/java/org/apache/sedona/common/utils/LineStringMerger.java
@@ -0,0 +1,316 @@
+/*
+ * 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.sedona.common.utils;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+import java.util.Set;
+import org.locationtech.jts.geom.Coordinate;
+import org.locationtech.jts.geom.CoordinateList;
+import org.locationtech.jts.geom.Geometry;
+import org.locationtech.jts.geom.GeometryFactory;
+import org.locationtech.jts.geom.LineString;
+import org.locationtech.jts.geom.util.LineStringExtracter;
+
+/**
+ * Post-processes line split results to merge adjacent segments that were only
split by JTS overlay
+ * noding, not by a real split point. This avoids extra line segments after
{@code
+ * Geometry#difference} on linework.
+ *
+ * <p>JTS has an internal line merge capability in LineBuilder (not yet
exposed/used by the overlay
+ * API). Once JTS supports it in future releases, we should rely on that
directly. See
+ *
https://github.com/locationtech/jts/blob/1.20.0/modules/core/src/main/java/org/locationtech/jts/operation/overlayng/LineBuilder.java#L247-L261
+ */
+public final class LineStringMerger {
+ private LineStringMerger() {}
+
+ @SuppressWarnings("unchecked")
+ public static Geometry mergeDifferenceSplit(
+ Geometry linework, Geometry originalLines, Geometry blade,
GeometryFactory factory) {
+ if (linework == null || linework.isEmpty() ||
!GeomUtils.geometryIsLineal(linework)) {
+ return linework;
+ }
+
+ List<Geometry> geoms = LineStringExtracter.getLines(linework);
+ List<LineString> lines = new ArrayList<>();
+ List<Geometry> nonLines = new ArrayList<>();
+ extractLines(geoms, lines, nonLines);
+ if (lines.size() <= 1) {
+ return linework;
+ }
+
+ Set<CoordKey> stopPointIndex = buildStopPointIndex(originalLines, blade);
+ List<LineString> merged = mergeLinesAtNonStopNodes(lines, stopPointIndex,
factory);
+
+ if (nonLines.isEmpty()) {
+ return factory.buildGeometry(merged);
+ } else {
+ nonLines.addAll(merged);
+ return factory.buildGeometry(nonLines);
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ private static Set<CoordKey> buildStopPointIndex(Geometry originalLines,
Geometry blade) {
+ Set<CoordKey> index = new HashSet<>();
+ if (originalLines != null && blade != null && !originalLines.isEmpty() &&
!blade.isEmpty()) {
+ Coordinate[] coords = originalLines.intersection(blade).getCoordinates();
+ for (Coordinate coord : coords) {
+ index.add(new CoordKey(coord));
+ }
+ }
+
+ if (originalLines == null || originalLines.isEmpty()) {
+ return index;
+ }
+
+ List<Geometry> geoms = LineStringExtracter.getLines(originalLines);
+ for (Geometry geom : geoms) {
+ if (!(geom instanceof LineString)) {
+ continue;
+ }
+ LineString line = (LineString) geom;
+ if (line.isClosed() || line.getNumPoints() == 0) {
+ continue;
+ }
+ index.add(new CoordKey(line.getCoordinateN(0)));
+ index.add(new CoordKey(line.getCoordinateN(line.getNumPoints() - 1)));
+ }
+
+ return index;
+ }
+
+ private static void extractLines(
+ List<Geometry> geoms, List<LineString> lines, List<Geometry> nonLines) {
+ for (Geometry geom : geoms) {
+ if (geom instanceof LineString) {
+ lines.add((LineString) geom);
+ } else {
+ nonLines.add(geom);
+ }
+ }
+ }
+
+ private static List<LineString> mergeLinesAtNonStopNodes(
+ List<LineString> lines, Set<CoordKey> stopPointIndex, GeometryFactory
factory) {
+ if (lines.size() <= 1) {
+ return lines;
+ }
+
+ Map<CoordKey, List<EndpointRef>> endpointIndex = buildEndpointIndex(lines);
+ boolean[] visited = new boolean[lines.size()];
+ List<LineString> merged = new ArrayList<>();
+
+ for (int i = 0; i < lines.size(); i++) {
+ if (visited[i]) {
+ continue;
+ }
+
+ LineString line = lines.get(i);
+ Coordinate start = line.getCoordinateN(0);
+ Coordinate end = line.getCoordinateN(line.getNumPoints() - 1);
+
+ CoordKey startKey = new CoordKey(start);
+ CoordKey endKey = new CoordKey(end);
+
+ boolean startMergeable = isMergeableNode(startKey, endpointIndex,
stopPointIndex);
+ boolean endMergeable = isMergeableNode(endKey, endpointIndex,
stopPointIndex);
+
+ if (!startMergeable) {
+ merged.add(
+ mergeTowardsDirection(i, true, lines, endpointIndex,
stopPointIndex, visited, factory));
+ continue;
+ }
+ if (!endMergeable) {
+ merged.add(
+ mergeTowardsDirection(
+ i, false, lines, endpointIndex, stopPointIndex, visited,
factory));
+ }
+ }
+
+ for (int i = 0; i < lines.size(); i++) {
+ if (visited[i]) {
+ continue;
+ }
+ merged.add(
+ mergeTowardsDirection(i, true, lines, endpointIndex, stopPointIndex,
visited, factory));
+ }
+
+ return merged;
+ }
+
+ private static Map<CoordKey, List<EndpointRef>>
buildEndpointIndex(List<LineString> lines) {
+ Map<CoordKey, List<EndpointRef>> index = new HashMap<>();
+ for (int i = 0; i < lines.size(); i++) {
+ LineString line = lines.get(i);
+ addEndpoint(index, new CoordKey(line.getCoordinateN(0)), new
EndpointRef(i));
+ addEndpoint(
+ index, new CoordKey(line.getCoordinateN(line.getNumPoints() - 1)),
new EndpointRef(i));
+ }
+ return index;
+ }
+
+ private static void addEndpoint(
+ Map<CoordKey, List<EndpointRef>> index, CoordKey key, EndpointRef ref) {
+ List<EndpointRef> refs = index.computeIfAbsent(key, k -> new
ArrayList<>());
+ refs.add(ref);
+ }
+
+ private static boolean isMergeableNode(
+ CoordKey key, Map<CoordKey, List<EndpointRef>> endpointIndex,
Set<CoordKey> stopPointIndex) {
+ if (stopPointIndex.contains(key)) {
+ return false;
+ }
+ List<EndpointRef> refs = endpointIndex.get(key);
+ return refs != null && refs.size() == 2;
+ }
+
+ private static LineString mergeTowardsDirection(
+ int startLineIndex,
+ boolean forward,
+ List<LineString> lines,
+ Map<CoordKey, List<EndpointRef>> endpointIndex,
+ Set<CoordKey> stopPointIndex,
+ boolean[] visited,
+ GeometryFactory factory) {
+ LineString first = lines.get(startLineIndex);
+ Coordinate startNode =
+ forward ? first.getCoordinateN(0) :
first.getCoordinateN(first.getNumPoints() - 1);
+ Coordinate[] firstCoords = orientedCoordinates(first, startNode);
+ if (firstCoords == null) {
+ visited[startLineIndex] = true;
+ return first;
+ }
+
+ visited[startLineIndex] = true;
+ CoordinateList coordList = new CoordinateList();
+ coordList.add(firstCoords, false);
+ Coordinate currentEnd = coordList.getCoordinate(coordList.size() - 1);
+ int currentLineIndex = startLineIndex;
+
+ while (true) {
+ CoordKey endKey = new CoordKey(currentEnd);
+ if (!isMergeableNode(endKey, endpointIndex, stopPointIndex)) {
+ break;
+ }
+
+ EndpointRef nextRef = nextEndpointRef(endpointIndex.get(endKey),
currentLineIndex);
+ if (nextRef == null || visited[nextRef.lineIndex]) {
+ break;
+ }
+
+ LineString nextLine = lines.get(nextRef.lineIndex);
+ Coordinate[] nextCoords = orientedCoordinates(nextLine, currentEnd);
+ if (nextCoords == null) {
+ break;
+ }
+
+ for (int i = 1; i < nextCoords.length; i++) {
+ coordList.add(nextCoords[i], false);
+ }
+ visited[nextRef.lineIndex] = true;
+ currentLineIndex = nextRef.lineIndex;
+ currentEnd = coordList.getCoordinate(coordList.size() - 1);
+
+ if (currentEnd.equals2D(coordList.getCoordinate(0))) {
+ break;
+ }
+ }
+
+ return factory.createLineString(coordList.toCoordinateArray());
+ }
+
+ private static EndpointRef nextEndpointRef(List<EndpointRef> refs, int
currentLineIndex) {
+ if (refs == null) {
+ return null;
+ }
+ for (EndpointRef ref : refs) {
+ if (ref.lineIndex != currentLineIndex) {
+ return ref;
+ }
+ }
+ return null;
+ }
+
+ private static Coordinate[] orientedCoordinates(LineString line, Coordinate
shared) {
+ Coordinate[] coords = line.getCoordinates();
+ if (coords.length == 0) {
+ return null;
+ }
+ boolean start = coords[0].equals2D(shared);
+ boolean end = coords[coords.length - 1].equals2D(shared);
+ if (start && end) {
+ return null;
+ }
+ if (start) {
+ return coords;
+ }
+ if (end) {
+ return reverse(coords);
+ }
+ return null;
+ }
+
+ private static Coordinate[] reverse(Coordinate[] coords) {
+ Coordinate[] reversed = new Coordinate[coords.length];
+ for (int i = 0; i < coords.length; i++) {
+ reversed[i] = coords[coords.length - 1 - i];
+ }
+ return reversed;
+ }
+
+ private static final class EndpointRef {
+ final int lineIndex;
+
+ EndpointRef(int lineIndex) {
+ this.lineIndex = lineIndex;
+ }
+ }
+
+ private static final class CoordKey {
+ final long xBits;
+ final long yBits;
+
+ CoordKey(Coordinate c) {
+ this.xBits = Double.doubleToLongBits(c.x);
+ this.yBits = Double.doubleToLongBits(c.y);
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(xBits, yBits);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (!(obj instanceof CoordKey)) {
+ return false;
+ }
+ CoordKey other = (CoordKey) obj;
+ return xBits == other.xBits && yBits == other.yBits;
+ }
+ }
+}
diff --git a/common/src/test/java/org/apache/sedona/common/FunctionsTest.java
b/common/src/test/java/org/apache/sedona/common/FunctionsTest.java
index ec7fbe00fe..e379e67d6d 100644
--- a/common/src/test/java/org/apache/sedona/common/FunctionsTest.java
+++ b/common/src/test/java/org/apache/sedona/common/FunctionsTest.java
@@ -562,6 +562,36 @@ public class FunctionsTest extends TestBase {
}
}
+ @Test
+ public void splitCircleExteriorRingInto2LineStrings() throws ParseException {
+ String polygonWkt =
+ "POLYGON ((-117.76405581088967 34.111876749328026, -117.76407506132291
34.11170068822483, "
+ + "-117.76413523652074 34.111531133837936, -117.76423402376724
34.11137460199335, -117.76436762657538 34.11123710803779, "
+ + "-117.76453091060647 34.11112393568514, -117.76471760098879
34.11103943398174, -117.76492052345083 34.11098685019075, "
+ + "-117.76513188000408 34.1109682050154, -117.76534354858369
34.11098421495394, -117.76554739513688 34.11103426476887, "
+ + "-117.76573558617179 34.11111643112786, -117.76590088976099
34.111227556508084, -117.76603695343799 34.11136337052523, "
+ + "-117.76613854831002 34.11151865402651, -117.76620177000793
34.11168743964393, -117.76622418874936 34.111863241103265, "
+ + "-117.76620494274577 34.11203930247842, -117.76614477135817
34.11220885781403, -117.7660459867224 34.11236539113964, "
+ + "-117.76591238492807 34.11250288688306, -117.7657491001595
34.11261606105824, -117.7655624074007 34.11270056434135, "
+ + "-117.76535948128496 34.112753149228745, -117.76514812035703
34.11277179485027, -117.76493644734776 34.112755784639766, "
+ + "-117.76473259698435 34.112705733876126, -117.76454440333869
34.11262356603611, -117.76437909873567 34.11251243886801, "
+ + "-117.76424303579616 34.11237662302835, -117.76414144330062
34.112221337947354, -117.76407822525644 34.11205255123353, "
+ + "-117.76405581088967 34.111876749328026))";
+ String knifeWkt =
+ "LINESTRING (-117.7640751398563 34.111535124121441,
-117.76628486838135 34.112204866513046)";
+
+ Polygon polygon = (Polygon) Constructors.geomFromWKT(polygonWkt, 4326);
+ Geometry knife = Constructors.geomFromWKT(knifeWkt, 4326);
+ Geometry resultLineStrings = Functions.split(polygon.getExteriorRing(),
knife);
+ double perimeter = polygon.getExteriorRing().getLength();
+
+ assertEquals(2, resultLineStrings.getNumGeometries());
+ for (int i = 0; i < resultLineStrings.getNumGeometries(); i++) {
+ double length = resultLineStrings.getGeometryN(i).getLength();
+ assertEquals(2.0, perimeter / length, 0.1);
+ }
+ }
+
@Test
public void dimensionGeometry2D() {
Point point = GEOMETRY_FACTORY.createPoint(new Coordinate(1, 2));
