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 a6979909a0 [GH-2367] Add ST_ApproximateMedialAxis and
ST_StraightSkeleton UDFs (#2380)
a6979909a0 is described below
commit a6979909a0f54406afe2b59293efab61f484f5bc
Author: Feng Zhang <[email protected]>
AuthorDate: Wed Oct 15 16:28:41 2025 -0700
[GH-2367] Add ST_ApproximateMedialAxis and ST_StraightSkeleton UDFs (#2380)
---
.github/linters/codespell.txt | 1 +
common/pom.xml | 4 +
.../java/org/apache/sedona/common/Functions.java | 213 ++++++++++
.../common/approximate/StraightSkeleton.java | 400 ++++++++++++++++++
.../org/apache/sedona/common/utils/GeomUtils.java | 3 +
.../org/apache/sedona/common/FunctionsTest.java | 457 +++++++++++++++++++++
.../apache/sedona/common/StraightSkeletonTest.java | 441 ++++++++++++++++++++
docs/api/flink/Function.md | 52 +++
docs/api/snowflake/vector-data/Function.md | 40 ++
docs/api/sql/Function.md | 84 ++++
.../ST_ApproximateMedialAxis_illustration.png | Bin 0 -> 26593 bytes
.../skeleton/ST_StraightSkeleton_illustration.png | Bin 0 -> 23616 bytes
.../main/java/org/apache/sedona/flink/Catalog.java | 4 +-
.../apache/sedona/flink/expressions/Functions.java | 36 ++
.../java/org/apache/sedona/flink/FunctionTest.java | 52 +++
pom.xml | 5 +
python/sedona/spark/sql/st_functions.py | 42 ++
python/tests/sql/test_function.py | 36 ++
.../sedona/snowflake/snowsql/TestFunctions.java | 28 ++
.../sedona/snowflake/snowsql/TestFunctionsV2.java | 28 ++
.../org/apache/sedona/snowflake/snowsql/UDFs.java | 23 ++
.../apache/sedona/snowflake/snowsql/UDFsV2.java | 36 ++
.../scala/org/apache/sedona/sql/UDF/Catalog.scala | 2 +
.../sql/sedona_sql/expressions/Functions.scala | 32 ++
.../sql/sedona_sql/expressions/st_functions.scala | 18 +
.../org/apache/sedona/sql/PreserveSRIDSuite.scala | 4 +-
.../apache/sedona/sql/dataFrameAPITestScala.scala | 41 ++
.../org/apache/sedona/sql/functionTestScala.scala | 379 ++++++++++++++++-
28 files changed, 2439 insertions(+), 22 deletions(-)
diff --git a/.github/linters/codespell.txt b/.github/linters/codespell.txt
index d209260c9c..a4a089cc95 100644
--- a/.github/linters/codespell.txt
+++ b/.github/linters/codespell.txt
@@ -1,5 +1,6 @@
actualy
afterall
+allEdges
atmost
celle
checkin
diff --git a/common/pom.xml b/common/pom.xml
index b074b45fde..4291a96ae7 100644
--- a/common/pom.xml
+++ b/common/pom.xml
@@ -120,6 +120,10 @@
<artifactId>janino</artifactId>
<version>${janino-version}</version>
</dependency>
+ <dependency>
+ <groupId>org.datasyslab</groupId>
+ <artifactId>campskeleton</artifactId>
+ </dependency>
</dependencies>
<build>
<sourceDirectory>src/main/java</sourceDirectory>
diff --git a/common/src/main/java/org/apache/sedona/common/Functions.java
b/common/src/main/java/org/apache/sedona/common/Functions.java
index 0469683fb2..eb67674510 100644
--- a/common/src/main/java/org/apache/sedona/common/Functions.java
+++ b/common/src/main/java/org/apache/sedona/common/Functions.java
@@ -29,6 +29,7 @@ import java.util.List;
import java.util.stream.Collectors;
import org.apache.commons.lang3.tuple.Pair;
import org.apache.sedona.common.S2Geography.Geography;
+import org.apache.sedona.common.approximate.StraightSkeleton;
import org.apache.sedona.common.geometryObjects.Circle;
import org.apache.sedona.common.jts2geojson.GeoJSONWriter;
import org.apache.sedona.common.sphere.Spheroid;
@@ -2661,4 +2662,216 @@ public class Functions {
return fractionAlongLine * (end.getCoordinate().getM() -
start.getCoordinate().getM())
+ start.getCoordinate().getM();
}
+
+ /**
+ * Computes the straight skeleton of an areal geometry. The straight
skeleton is a method of
+ * representing a polygon by a topological skeleton, formed by a continuous
shrinking process
+ * where each edge moves inward in parallel at a uniform speed.
+ *
+ * <p>This implementation uses the campskeleton library which implements the
weighted straight
+ * skeleton algorithm based on Felkel's approach. The result represents the
"skeleton" or
+ * centerline of the polygon.
+ *
+ * @param geometry The areal geometry (Polygon or MultiPolygon)
+ * @return A MultiLineString representing the straight skeleton, or null if
input is null/empty
+ */
+ public static Geometry straightSkeleton(Geometry geometry) {
+ return straightSkeleton(geometry, 0);
+ }
+
+ /**
+ * Computes the straight skeleton of an areal geometry with optional vertex
simplification.
+ *
+ * <p>The straight skeleton is a method of representing a polygon by a
topological skeleton,
+ * formed by a continuous shrinking process where each edge moves inward in
parallel at a uniform
+ * speed.
+ *
+ * <p>For polygons with many vertices, performance can be improved by
limiting the vertex count.
+ * The algorithm will merge the shortest edges until the vertex count is
reduced to the specified
+ * limit.
+ *
+ * @param geometry The areal geometry (Polygon or MultiPolygon)
+ * @param maxVertices Maximum number of vertices per polygon (0 to disable
simplification).
+ * Recommended: 100-500 for performance
+ * @return A MultiLineString representing the straight skeleton, or null if
input is null/empty
+ */
+ public static Geometry straightSkeleton(Geometry geometry, Integer
maxVertices) {
+ if (geometry == null || geometry.isEmpty()) {
+ return null;
+ }
+
+ // Check if the geometry is areal (Polygon or MultiPolygon)
+ if (!(geometry instanceof Polygon || geometry instanceof MultiPolygon)) {
+ throw new IllegalArgumentException(
+ "ST_StraightSkeleton only supports Polygon and MultiPolygon
geometries");
+ }
+
+ GeometryFactory factory = geometry.getFactory();
+
+ // Use straight skeleton algorithm with optional simplification
+ int maxVerts = (maxVertices != null) ? maxVertices : 0;
+ return computeStraightSkeleton(geometry, factory, maxVerts);
+ }
+
+ /**
+ * Computes an approximate medial axis of an areal geometry by computing the
straight skeleton and
+ * filtering to keep only interior edges.
+ *
+ * <p>The medial axis is approximated by first computing the straight
skeleton, then filtering to
+ * keep only edges where both endpoints are interior to the polygon (not on
the boundary). This
+ * produces a cleaner skeleton by removing branches that extend to the
boundary.
+ *
+ * @param geometry The areal geometry (Polygon or MultiPolygon)
+ * @return A MultiLineString representing the approximate medial axis, or
null if input is
+ * null/empty
+ */
+ public static Geometry approximateMedialAxis(Geometry geometry) {
+ return approximateMedialAxis(geometry, 0);
+ }
+
+ /**
+ * Computes an approximate medial axis of an areal geometry by computing the
straight skeleton and
+ * filtering to keep only interior edges, with optional vertex
simplification.
+ *
+ * <p>The medial axis is approximated by first computing the straight
skeleton, then filtering to
+ * keep only edges where both endpoints are interior to the polygon (not on
the boundary). This
+ * produces a cleaner skeleton by removing branches that extend to the
boundary.
+ *
+ * <p>For polygons with many vertices, performance can be improved by
limiting the vertex count
+ * before computing the skeleton. The algorithm will merge the shortest
edges until the vertex
+ * count is reduced to the specified limit.
+ *
+ * @param geometry The areal geometry (Polygon or MultiPolygon)
+ * @param maxVertices Maximum number of vertices per polygon (0 to disable
simplification).
+ * Recommended: 100-500 for performance
+ * @return A MultiLineString representing the approximate medial axis, or
null if input is
+ * null/empty
+ */
+ public static Geometry approximateMedialAxis(Geometry geometry, Integer
maxVertices) {
+ if (geometry == null || geometry.isEmpty()) {
+ return null;
+ }
+
+ // Check if the geometry is areal (Polygon or MultiPolygon)
+ if (!(geometry instanceof Polygon || geometry instanceof MultiPolygon)) {
+ throw new IllegalArgumentException(
+ "ST_ApproximateMedialAxis only supports Polygon and MultiPolygon
geometries");
+ }
+
+ GeometryFactory factory = geometry.getFactory();
+
+ // Compute the straight skeleton with optional vertex simplification
+ Geometry skeleton = straightSkeleton(geometry, maxVertices);
+
+ if (skeleton == null || skeleton.isEmpty()) {
+ return skeleton;
+ }
+
+ // Filter to keep only interior edges (not touching boundary)
+ return filterInteriorEdges(skeleton, geometry, factory);
+ }
+
+ /**
+ * Compute the straight skeleton of a geometry.
+ *
+ * <p>This method implements the straight skeleton algorithm, which
simulates continuous inward
+ * movement of polygon edges to construct the skeleton. The algorithm
processes edge and split
+ * events in temporal order.
+ *
+ * @param geometry The input geometry (Polygon or MultiPolygon)
+ * @param factory GeometryFactory for creating result geometries
+ * @return MultiLineString representing the straight skeleton
+ */
+ private static Geometry computeStraightSkeleton(
+ Geometry geometry, GeometryFactory factory, int maxVertices) {
+ try {
+ // Handle MultiPolygon by processing each polygon separately
+ if (geometry instanceof MultiPolygon) {
+ MultiPolygon multiPoly = (MultiPolygon) geometry;
+ java.util.List<LineString> allEdges = new java.util.ArrayList<>();
+
+ for (int i = 0; i < multiPoly.getNumGeometries(); i++) {
+ Polygon poly = (Polygon) multiPoly.getGeometryN(i);
+ StraightSkeleton skeleton = new StraightSkeleton();
+ Geometry skeletonGeom = skeleton.computeSkeleton(poly, maxVertices);
+
+ if (skeletonGeom != null && !skeletonGeom.isEmpty()) {
+ // Extract LineStrings from the skeleton geometry
+ for (int j = 0; j < skeletonGeom.getNumGeometries(); j++) {
+ allEdges.add((LineString) skeletonGeom.getGeometryN(j));
+ }
+ }
+ }
+
+ if (allEdges.isEmpty()) {
+ return factory.createMultiLineString(new LineString[0]);
+ }
+
+ Geometry result = factory.createMultiLineString(allEdges.toArray(new
LineString[0]));
+ result.setSRID(geometry.getSRID());
+ return result;
+ } else {
+ // Single polygon
+ Polygon poly = (Polygon) geometry;
+ StraightSkeleton skeleton = new StraightSkeleton();
+ Geometry result = skeleton.computeSkeleton(poly, maxVertices);
+
+ if (result != null) {
+ result.setSRID(geometry.getSRID());
+ }
+
+ return result;
+ }
+ } catch (Exception e) {
+ return factory.createMultiLineString(new LineString[0]);
+ }
+ }
+
+ /**
+ * Filters skeleton edges to keep only interior edges (those that don't
touch the polygon
+ * boundary).
+ *
+ * <p>An edge is considered interior if both of its endpoints are NOT on the
polygon boundary.
+ * This produces a cleaner medial axis by removing all branches that extend
to corners and edges.
+ *
+ * @param skeleton The straight skeleton as a MultiLineString
+ * @param polygon The original polygon geometry
+ * @param factory GeometryFactory for creating result geometries
+ * @return MultiLineString containing only interior skeleton edges
+ */
+ private static Geometry filterInteriorEdges(
+ Geometry skeleton, Geometry polygon, GeometryFactory factory) {
+ java.util.List<LineString> interiorEdges = new java.util.ArrayList<>();
+
+ // Get the polygon boundary for distance checking
+ Geometry boundary = polygon.getBoundary();
+
+ // Distance threshold for considering a point "on" the boundary
+ final double BOUNDARY_TOLERANCE = 1e-6;
+
+ // Check each skeleton edge
+ for (int i = 0; i < skeleton.getNumGeometries(); i++) {
+ LineString edge = (LineString) skeleton.getGeometryN(i);
+
+ Coordinate start = edge.getCoordinateN(0);
+ Coordinate end = edge.getCoordinateN(edge.getNumPoints() - 1);
+
+ // Check if both endpoints are interior (not on boundary)
+ Point startPoint = factory.createPoint(start);
+ Point endPoint = factory.createPoint(end);
+
+ double startDist = boundary.distance(startPoint);
+ double endDist = boundary.distance(endPoint);
+
+ // Keep edge only if BOTH endpoints are interior (away from boundary)
+ if (startDist > BOUNDARY_TOLERANCE && endDist > BOUNDARY_TOLERANCE) {
+ interiorEdges.add(edge);
+ }
+ }
+
+ // Return the filtered edges, preserving SRID from input polygon
+ Geometry result = factory.createMultiLineString(interiorEdges.toArray(new
LineString[0]));
+ result.setSRID(polygon.getSRID());
+ return result;
+ }
}
diff --git
a/common/src/main/java/org/apache/sedona/common/approximate/StraightSkeleton.java
b/common/src/main/java/org/apache/sedona/common/approximate/StraightSkeleton.java
new file mode 100644
index 0000000000..0cfaa19c6c
--- /dev/null
+++
b/common/src/main/java/org/apache/sedona/common/approximate/StraightSkeleton.java
@@ -0,0 +1,400 @@
+/*
+ * 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.approximate;
+
+import java.util.*;
+import javax.vecmath.Point3d;
+import org.locationtech.jts.algorithm.Orientation;
+import org.locationtech.jts.geom.*;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+import org.twak.camp.Corner;
+import org.twak.camp.Edge;
+import org.twak.camp.Machine;
+import org.twak.camp.Output;
+import org.twak.camp.Skeleton;
+import org.twak.utils.collections.Loop;
+import org.twak.utils.collections.LoopL;
+
+/**
+ * Straight skeleton computation for polygons using the campskeleton library.
+ *
+ * <p>The straight skeleton is a method of representing a polygon by a
topological skeleton. It is
+ * defined by a continuous shrinking process in which each edge of the polygon
is moved inward in a
+ * parallel manner. This implementation uses the campskeleton library which
implements the weighted
+ * straight skeleton algorithm based on Felkel's approach.
+ *
+ * <p>References: - Tom Kelly and Peter Wonka (2011). Interactive
Architectural Modeling with
+ * Procedural Extrusions - Felkel, P., & Obdržálek, Š. (1998). Straight
skeleton implementation
+ */
+public class StraightSkeleton {
+ private static final Logger log =
LoggerFactory.getLogger(StraightSkeleton.class);
+
+ /**
+ * Target size for normalized geometry. The campskeleton library works best
with geometries of a
+ * reasonable size (around 100 units). Geometries are scaled to have their
maximum dimension equal
+ * to this value.
+ */
+ private static final double NORMALIZED_SIZE = 1000.0;
+
+ /**
+ * Default roof slope angle (in radians) for the skeleton machine. This
represents the angle at
+ * which edges shrink. For a pure straight skeleton (not weighted), this
value doesn't
+ * significantly affect the output.
+ */
+ private static final double DEFAULT_MACHINE_ANGLE = Math.PI / 4; // 45
degrees
+
+ /**
+ * Epsilon value for detecting boundary edges. Edges with z-coordinates
below this threshold on
+ * both endpoints are considered boundary edges and filtered out from the
skeleton output.
+ */
+ private static final double BOUNDARY_EDGE_EPSILON = 1e-10;
+
+ public StraightSkeleton() {}
+
+ /**
+ * Compute the straight skeleton for a polygon.
+ *
+ * <p>The campskeleton library has numerical stability issues with certain
geometries. To improve
+ * robustness, we preprocess the polygon by: 1. Centering it at the origin
(0,0) 2. Scaling it to
+ * a reasonable size 3. Ensuring counter-clockwise orientation 4. Optionally
reducing vertex count
+ * by merging shortest edges
+ *
+ * <p>After computing the skeleton, we transform it back to the original
coordinate system.
+ *
+ * @param polygon Input polygon (must be simple, non-self-intersecting)
+ * @param maxVertices Maximum number of vertices to keep (0 to disable
simplification). If the
+ * polygon has more vertices than this limit, the shortest edges will be
merged until the
+ * vertex count is reduced. Recommended: 100-500 for performance
+ * @return MultiLineString representing the straight skeleton edges
+ */
+ public Geometry computeSkeleton(Polygon polygon, int maxVertices) {
+ if (polygon == null || polygon.isEmpty()) {
+ return null;
+ }
+
+ GeometryFactory factory = polygon.getFactory();
+
+ try {
+ // Step 1: Calculate centroid and envelope for normalization
+ Point centroid = polygon.getCentroid();
+ double offsetX = centroid.getX();
+ double offsetY = centroid.getY();
+
+ Envelope envelope = polygon.getEnvelopeInternal();
+ double maxDim = Math.max(envelope.getWidth(), envelope.getHeight());
+
+ // Use a scale factor to normalize the geometry to a reasonable size
+ // This improves numerical stability in campskeleton
+ double scaleFactor = (maxDim > 0) ? (NORMALIZED_SIZE / maxDim) : 1.0;
+
+ // Step 2: Normalize the polygon (center, scale, and optionally simplify
by merging short
+ // edges)
+ Polygon normalizedPolygon =
+ normalizePolygon(polygon, offsetX, offsetY, scaleFactor,
maxVertices);
+
+ // Step 3: Convert JTS polygon to campskeleton format
+ LoopL<Edge> input = convertPolygonToEdges(normalizedPolygon);
+
+ // Step 4: Compute straight skeleton
+ Skeleton skeleton = new Skeleton(input, true);
+ skeleton.skeleton();
+
+ // Check if skeleton computation succeeded
+ if (skeleton.output == null || skeleton.output.edges == null) {
+ log.warn("Campskeleton failed to produce output for polygon: {}",
polygon.toText());
+ return factory.createMultiLineString(new LineString[0]);
+ }
+
+ // Step 5: Extract skeleton edges from normalized coordinate system
+ List<LineString> normalizedEdges = extractSkeletonEdges(skeleton,
factory);
+
+ if (normalizedEdges.isEmpty()) {
+ log.warn("No skeleton edges extracted for polygon: {}",
polygon.toText());
+ return factory.createMultiLineString(new LineString[0]);
+ }
+
+ // Step 6: Transform skeleton edges back to original coordinate system
+ List<LineString> transformedEdges = new ArrayList<>();
+ for (LineString edge : normalizedEdges) {
+ LineString transformed = transformLineStringBack(edge, offsetX,
offsetY, scaleFactor);
+ transformedEdges.add(transformed);
+ }
+
+ return factory.createMultiLineString(transformedEdges.toArray(new
LineString[0]));
+
+ } catch (Exception e) {
+ log.error("Failed to compute straight skeleton for polygon: {}",
polygon.toText(), e);
+ throw new RuntimeException("Failed to compute straight skeleton: " +
e.getMessage(), e);
+ }
+ }
+
+ /**
+ * Normalize polygon by centering at origin and scaling. If the polygon has
too many vertices, it
+ * will merge the shortest edges to reduce vertex count. Handles both
exterior ring and interior
+ * rings (holes).
+ *
+ * @param polygon Original polygon
+ * @param offsetX X offset to subtract (centroid x)
+ * @param offsetY Y offset to subtract (centroid y)
+ * @param scaleFactor Scale factor to apply
+ * @param maxVertices Maximum number of vertices to keep (0 to disable
simplification)
+ * @return Normalized polygon
+ */
+ private Polygon normalizePolygon(
+ Polygon polygon, double offsetX, double offsetY, double scaleFactor, int
maxVertices) {
+ GeometryFactory factory = polygon.getFactory();
+
+ // Normalize exterior ring
+ LinearRing normalizedShell =
+ normalizeRing(
+ polygon.getExteriorRing(), offsetX, offsetY, scaleFactor,
maxVertices, factory);
+
+ // Normalize interior rings (holes)
+ LinearRing[] normalizedHoles = new
LinearRing[polygon.getNumInteriorRing()];
+ for (int i = 0; i < polygon.getNumInteriorRing(); i++) {
+ normalizedHoles[i] =
+ normalizeRing(
+ polygon.getInteriorRingN(i), offsetX, offsetY, scaleFactor,
maxVertices, factory);
+ }
+
+ return factory.createPolygon(normalizedShell, normalizedHoles);
+ }
+
+ /**
+ * Normalize a single ring by centering at origin and scaling.
+ *
+ * @param ring Original ring
+ * @param offsetX X offset to subtract
+ * @param offsetY Y offset to subtract
+ * @param scaleFactor Scale factor to apply
+ * @param maxVertices Maximum number of vertices to keep (0 to disable
simplification)
+ * @param factory GeometryFactory for creating the result
+ * @return Normalized ring
+ */
+ private LinearRing normalizeRing(
+ LineString ring,
+ double offsetX,
+ double offsetY,
+ double scaleFactor,
+ int maxVertices,
+ GeometryFactory factory) {
+ Coordinate[] coords = ring.getCoordinates();
+
+ // First pass: normalize all coordinates
+ List<Coordinate> normalizedCoords = new ArrayList<>();
+ for (int i = 0; i < coords.length - 1; i++) { // Skip last coordinate
(duplicate of first)
+ double x = (coords[i].x - offsetX) * scaleFactor;
+ double y = (coords[i].y - offsetY) * scaleFactor;
+ normalizedCoords.add(new Coordinate(x, y));
+ }
+
+ // Second pass: merge shortest edges if we exceed maxVertices
+ if (maxVertices > 0 && normalizedCoords.size() > maxVertices) {
+ normalizedCoords = simplifyByMergingShortestEdges(normalizedCoords,
maxVertices);
+ }
+
+ // Close the ring
+ normalizedCoords.add(new Coordinate(normalizedCoords.get(0)));
+
+ Coordinate[] coordArray = normalizedCoords.toArray(new Coordinate[0]);
+ return factory.createLinearRing(coordArray);
+ }
+
+ /**
+ * Simplify a polygon by repeatedly removing the vertex that creates the
shortest edge.
+ *
+ * @param coords List of coordinates (without closing coordinate)
+ * @param targetVertexCount Target number of vertices
+ * @return Simplified list of coordinates
+ */
+ private List<Coordinate> simplifyByMergingShortestEdges(
+ List<Coordinate> coords, int targetVertexCount) {
+ // Ensure we keep at least 3 vertices for a valid polygon
+ targetVertexCount = Math.max(3, targetVertexCount);
+
+ // Create a working copy
+ List<Coordinate> result = new ArrayList<>(coords);
+
+ // Keep removing the shortest edge until we reach target
+ while (result.size() > targetVertexCount) {
+ double minLength = Double.MAX_VALUE;
+ int shortestEdgeIdx = -1;
+
+ // Find the shortest edge
+ for (int i = 0; i < result.size(); i++) {
+ Coordinate curr = result.get(i);
+ Coordinate next = result.get((i + 1) % result.size());
+ double length = curr.distance(next);
+
+ if (length < minLength) {
+ minLength = length;
+ shortestEdgeIdx = i;
+ }
+ }
+
+ // Remove the vertex at the end of the shortest edge
+ // This effectively merges the two edges adjacent to this vertex
+ int vertexToRemove = (shortestEdgeIdx + 1) % result.size();
+ result.remove(vertexToRemove);
+ }
+
+ return result;
+ }
+
+ /**
+ * Transform a LineString back from normalized coordinates to original
coordinate system.
+ *
+ * @param lineString LineString in normalized coordinates
+ * @param offsetX Original X offset to add back
+ * @param offsetY Original Y offset to add back
+ * @param scaleFactor Scale factor to reverse
+ * @return LineString in original coordinate system
+ */
+ private LineString transformLineStringBack(
+ LineString lineString, double offsetX, double offsetY, double
scaleFactor) {
+ Coordinate[] coords = lineString.getCoordinates();
+ Coordinate[] transformedCoords = new Coordinate[coords.length];
+
+ for (int i = 0; i < coords.length; i++) {
+ double x = (coords[i].x / scaleFactor) + offsetX;
+ double y = (coords[i].y / scaleFactor) + offsetY;
+ transformedCoords[i] = new Coordinate(x, y);
+ }
+
+ return lineString.getFactory().createLineString(transformedCoords);
+ }
+
+ /**
+ * Convert JTS Polygon to campskeleton LoopL<Edge> format.
+ *
+ * <p>Creates Corner objects for each vertex and connects them with Edge
objects. Each edge is
+ * assigned a default Machine (speed) for uniform shrinking.
+ *
+ * <p>The campskeleton library requires the exterior ring to be in
counter-clockwise (CCW)
+ * orientation and interior rings (holes) to be in clockwise (CW)
orientation. This method ensures
+ * proper orientation before conversion.
+ *
+ * @param polygon Input polygon with potential holes
+ * @return LoopL containing the exterior ring and all interior rings as
separate loops
+ */
+ private LoopL<Edge> convertPolygonToEdges(Polygon polygon) {
+ LoopL<Edge> input = new LoopL<>();
+ Machine defaultMachine = new Machine(DEFAULT_MACHINE_ANGLE);
+
+ // Add exterior ring (must be CCW)
+ Loop<Edge> exteriorLoop = convertRingToLoop(polygon.getExteriorRing(),
true, defaultMachine);
+ input.add(exteriorLoop);
+
+ // Add interior rings / holes (must be CW)
+ for (int i = 0; i < polygon.getNumInteriorRing(); i++) {
+ Loop<Edge> holeLoop = convertRingToLoop(polygon.getInteriorRingN(i),
false, defaultMachine);
+ input.add(holeLoop);
+ }
+
+ return input;
+ }
+
+ /**
+ * Convert a single ring (exterior or interior) to a campskeleton Loop.
+ *
+ * @param ring The linear ring to convert
+ * @param isExterior true if this is the exterior ring (CCW), false for
holes (CW)
+ * @param machine The Machine to assign to all edges
+ * @return Loop of edges representing the ring
+ */
+ private Loop<Edge> convertRingToLoop(LineString ring, boolean isExterior,
Machine machine) {
+ Loop<Edge> loop = new Loop<>();
+ Coordinate[] coords = ring.getCoordinates();
+
+ // Check orientation and reverse if needed
+ boolean isCCW = Orientation.isCCW(coords);
+
+ // Exterior rings should be CCW, holes should be CW
+ boolean needsReverse = (isExterior && !isCCW) || (!isExterior && isCCW);
+
+ if (needsReverse) {
+ // Reverse the coordinates (excluding the closing point)
+ Coordinate[] reversed = new Coordinate[coords.length];
+ for (int i = 0; i < coords.length - 1; i++) {
+ reversed[i] = coords[coords.length - 2 - i];
+ }
+ // Add the closing point
+ reversed[coords.length - 1] = reversed[0];
+ coords = reversed;
+ }
+
+ // Create corners for each vertex
+ List<Corner> corners = new ArrayList<>();
+ for (int i = 0; i < coords.length - 1; i++) { // -1 because last coord =
first coord
+ Coordinate c = coords[i];
+ corners.add(new Corner(c.x, c.y));
+ }
+
+ // Create edges connecting consecutive corners
+ for (int i = 0; i < corners.size(); i++) {
+ Corner c1 = corners.get(i);
+ Corner c2 = corners.get((i + 1) % corners.size());
+
+ Edge edge = new Edge(c1, c2);
+ edge.machine = machine; // Set machine for the edge
+ loop.append(edge);
+ }
+
+ return loop;
+ }
+
+ /**
+ * Extract skeleton edges from campskeleton output.
+ *
+ * <p>The campskeleton output contains SharedEdge objects representing the
skeleton edges. We
+ * project these from 3D to 2D by discarding the z coordinate.
+ */
+ private List<LineString> extractSkeletonEdges(Skeleton skeleton,
GeometryFactory factory) {
+ List<LineString> edges = new ArrayList<>();
+
+ // Use the edges from the skeleton output
+ // skeleton.output.edges is an IdentityLookup with a map field
+ for (Output.SharedEdge edge : skeleton.output.edges.map.values()) {
+ Point3d start = edge.start;
+ Point3d end = edge.end;
+
+ // Filter out boundary edges (those with z=0 on both endpoints)
+ // The straight skeleton edges are "raised" above the polygon plane
+ boolean isBoundaryEdge =
+ (Math.abs(start.z) < BOUNDARY_EDGE_EPSILON && Math.abs(end.z) <
BOUNDARY_EDGE_EPSILON);
+
+ if (isBoundaryEdge) {
+ continue; // Skip boundary edges
+ }
+
+ // Project from 3D to 2D (discard z coordinate)
+ Coordinate c1 = new Coordinate(start.x, start.y);
+ Coordinate c2 = new Coordinate(end.x, end.y);
+
+ // Only create edge if points are different in 2D
+ if (!c1.equals2D(c2)) {
+ LineString lineString = factory.createLineString(new Coordinate[] {c1,
c2});
+ edges.add(lineString);
+ }
+ }
+
+ return edges;
+ }
+}
diff --git a/common/src/main/java/org/apache/sedona/common/utils/GeomUtils.java
b/common/src/main/java/org/apache/sedona/common/utils/GeomUtils.java
index 98623c7a88..e5611682cd 100644
--- a/common/src/main/java/org/apache/sedona/common/utils/GeomUtils.java
+++ b/common/src/main/java/org/apache/sedona/common/utils/GeomUtils.java
@@ -622,6 +622,9 @@ public class GeomUtils {
public static Boolean isMeasuredGeometry(Geometry geom) {
Coordinate coordinate = geom.getCoordinate();
+ if (coordinate == null) {
+ return false; // Empty geometries are not measured
+ }
return !Double.isNaN(coordinate.getM());
}
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 6de3d30669..cdf1e5d97b 100644
--- a/common/src/test/java/org/apache/sedona/common/FunctionsTest.java
+++ b/common/src/test/java/org/apache/sedona/common/FunctionsTest.java
@@ -4473,4 +4473,461 @@ public class FunctionsTest extends TestBase {
double actualArea = actual.getArea();
return intersectionArea / actualArea;
}
+
+ @Test
+ public void straightSkeleton() throws ParseException {
+ // Test with a simple square polygon
+ // A square's straight skeleton has 4 edges from corners to center
+ Polygon square = GEOMETRY_FACTORY.createPolygon(coordArray(0, 0, 10, 0,
10, 10, 0, 10, 0, 0));
+ Geometry result = Functions.straightSkeleton(square);
+
+ // Result should be a MultiLineString
+ assertTrue(result instanceof MultiLineString);
+ assertFalse(result.isEmpty());
+ assertEquals(4, result.getNumGeometries()); // Square has 4 skeleton edges
+
+ // For a square, all skeleton edges should converge at the center point
+ Point expectedCenter = GEOMETRY_FACTORY.createPoint(new Coordinate(5, 5));
+ int edgesAtCenter = 0;
+ for (int i = 0; i < result.getNumGeometries(); i++) {
+ LineString edge = (LineString) result.getGeometryN(i);
+ Coordinate[] coords = edge.getCoordinates();
+ // Check if either endpoint is at the center
+ if (coords[0].distance(expectedCenter.getCoordinate()) < 0.01
+ || coords[1].distance(expectedCenter.getCoordinate()) < 0.01) {
+ edgesAtCenter++;
+ }
+ }
+ assertEquals("All 4 edges should meet at center", 4, edgesAtCenter);
+
+ // Test with an L-shaped polygon
+ Polygon lShape =
+ GEOMETRY_FACTORY.createPolygon(coordArray(0, 0, 10, 0, 10, 5, 5, 5, 5,
10, 0, 10, 0, 0));
+ result = Functions.straightSkeleton(lShape);
+
+ assertTrue(result instanceof MultiLineString);
+ assertFalse(result.isEmpty());
+ assertTrue("L-shape should have multiple skeleton edges",
result.getNumGeometries() >= 4);
+
+ // Test with a rectangular polygon
+ Polygon rectangle = GEOMETRY_FACTORY.createPolygon(coordArray(0, 0, 20, 0,
20, 5, 0, 5, 0, 0));
+ result = Functions.straightSkeleton(rectangle);
+
+ assertTrue(result instanceof MultiLineString);
+ assertFalse(result.isEmpty());
+ assertTrue("Rectangle should have at least 4 skeleton edges",
result.getNumGeometries() >= 4);
+ }
+
+ @Test
+ public void straightSkeletonSRID() throws ParseException {
+ // Test SRID preservation
+ Geometry geom = Constructors.geomFromWKT("POLYGON ((0 0, 10 0, 10 10, 0
10, 0 0))", 4326);
+ Geometry result = Functions.straightSkeleton(geom);
+
+ assertEquals(4326, result.getSRID());
+ assertTrue(result instanceof MultiLineString);
+ }
+
+ @Test
+ public void straightSkeletonNullAndEmpty() {
+ // Test null geometry
+ Geometry result = Functions.straightSkeleton(null);
+ assertNull(result);
+
+ // Test empty geometry
+ Polygon emptyPolygon = GEOMETRY_FACTORY.createPolygon();
+ result = Functions.straightSkeleton(emptyPolygon);
+ assertNull(result);
+ }
+
+ @Test
+ public void straightSkeletonInvalidGeometry() {
+ // Test with non-areal geometry (LineString)
+ LineString lineString = GEOMETRY_FACTORY.createLineString(coordArray(0, 0,
10, 10));
+ IllegalArgumentException e =
+ assertThrows(IllegalArgumentException.class, () ->
Functions.straightSkeleton(lineString));
+ assertEquals(
+ "ST_StraightSkeleton only supports Polygon and MultiPolygon
geometries", e.getMessage());
+
+ // Test with Point
+ Point point = GEOMETRY_FACTORY.createPoint(new Coordinate(5, 5));
+ e = assertThrows(IllegalArgumentException.class, () ->
Functions.straightSkeleton(point));
+ assertEquals(
+ "ST_StraightSkeleton only supports Polygon and MultiPolygon
geometries", e.getMessage());
+ }
+
+ @Test
+ public void straightSkeletonMultiPolygon() throws ParseException {
+ // Test with MultiPolygon
+ Polygon poly1 = GEOMETRY_FACTORY.createPolygon(coordArray(0, 0, 5, 0, 5,
5, 0, 5, 0, 0));
+ Polygon poly2 =
+ GEOMETRY_FACTORY.createPolygon(coordArray(10, 10, 15, 10, 15, 15, 10,
15, 10, 10));
+ MultiPolygon multiPolygon = GEOMETRY_FACTORY.createMultiPolygon(new
Polygon[] {poly1, poly2});
+
+ Geometry result = Functions.straightSkeleton(multiPolygon);
+
+ assertTrue(result instanceof MultiLineString);
+ assertFalse(result.isEmpty());
+ assertEquals(multiPolygon.getSRID(), result.getSRID());
+ }
+
+ /*
+ * Geometric Verification Tests for ST_StraightSkeleton
+ *
+ * Verification Strategy:
+ *
+ * These tests use geometrically predictable shapes where we can
mathematically reason about the
+ * expected medial axis:
+ *
+ * | Shape | Mathematical Property | Verification Method
|
+ *
|------------------|--------------------------|-------------------------------|
+ * | Narrow Rectangle | Medial axis ≈ centerline | Distance to center line
|
+ * | Square | Symmetry around center | Distance to centroid
|
+ * | Circle | Collapses to center | Centroid proximity
|
+ * | T-Shape | Follows topology | Checks both stem and top
bar |
+ * | Any Polygon | Deterministic | Consistency across runs
|
+ * | Any Polygon | Geometric validity | All points inside/on
boundary |
+ */
+
+ @Test
+ public void straightSkeletonRectangleVerification() throws ParseException {
+ // Test with a narrow rectangle where straight skeleton should have
centerline structure
+ // Rectangle from (0,0) to (100,10) - very elongated
+ Polygon rectangle =
+ GEOMETRY_FACTORY.createPolygon(coordArray(0, 0, 100, 0, 100, 10, 0,
10, 0, 0));
+ Geometry result = Functions.straightSkeleton(rectangle);
+
+ assertTrue(result instanceof MultiLineString);
+ assertFalse(result.isEmpty());
+
+ // Straight skeleton of a rectangle should have edges connecting corners
to interior
+ // All skeleton edges should be contained within or touch the polygon
+ for (int i = 0; i < result.getNumGeometries(); i++) {
+ Geometry part = result.getGeometryN(i);
+ assertTrue(
+ "Skeleton edges must be inside or intersect the polygon",
+ rectangle.contains(part) || rectangle.intersects(part));
+ }
+
+ // Check that skeleton has reasonable length (should be less than
perimeter)
+ double skeletonLength = result.getLength();
+ double perimeter = rectangle.getLength();
+ assertTrue("Skeleton length should be less than polygon perimeter",
skeletonLength < perimeter);
+ }
+
+ @Test
+ public void straightSkeletonSquareSymmetry() throws ParseException {
+ // Test with a square - straight skeleton should converge to center
+ // Square centered at origin for easier verification
+ Polygon square =
+ GEOMETRY_FACTORY.createPolygon(coordArray(-10, -10, 10, -10, 10, 10,
-10, 10, -10, -10));
+ Geometry result = Functions.straightSkeleton(square);
+
+ assertTrue(result instanceof MultiLineString);
+ assertFalse(result.isEmpty());
+ assertEquals(4, result.getNumGeometries()); // Square always has 4
skeleton edges
+
+ // For a square, all 4 skeleton edges should meet at the center (0, 0)
+ Point expectedCenter = GEOMETRY_FACTORY.createPoint(new Coordinate(0, 0));
+ int edgesAtCenter = 0;
+ for (int i = 0; i < result.getNumGeometries(); i++) {
+ LineString edge = (LineString) result.getGeometryN(i);
+ Coordinate[] coords = edge.getCoordinates();
+ // Check if either endpoint is at the center
+ if (coords[0].distance(expectedCenter.getCoordinate()) < 0.01
+ || coords[1].distance(expectedCenter.getCoordinate()) < 0.01) {
+ edgesAtCenter++;
+ }
+ }
+ assertEquals("All 4 skeleton edges should converge at the center", 4,
edgesAtCenter);
+ }
+
+ @Test
+ public void straightSkeletonCircleApproximation() throws ParseException {
+ // Test with a circular polygon (approximated by many vertices)
+ // For a circle, the straight skeleton edges radiate from center to
boundary
+ double radius = 10.0;
+ int numPoints = 16; // Reasonable approximation (16-gon)
+ Coordinate[] coords = new Coordinate[numPoints + 1];
+
+ for (int i = 0; i < numPoints; i++) {
+ double angle = 2 * Math.PI * i / numPoints;
+ coords[i] = new Coordinate(radius * Math.cos(angle), radius *
Math.sin(angle));
+ }
+ coords[numPoints] = coords[0]; // Close the ring
+
+ Polygon circle = GEOMETRY_FACTORY.createPolygon(coords);
+ Geometry result = Functions.straightSkeleton(circle);
+
+ assertTrue(result instanceof MultiLineString);
+ assertFalse(result.isEmpty());
+
+ // For a regular polygon, straight skeleton has at least N edges
+ // (can have more due to intermediate junction points)
+ assertTrue(
+ "Circle approximation should have at least one edge per vertex",
+ result.getNumGeometries() >= numPoints);
+
+ // All skeleton edges should converge at or near the center
+ Point center = GEOMETRY_FACTORY.createPoint(new Coordinate(0, 0));
+ int edgesNearCenter = 0;
+ for (int i = 0; i < result.getNumGeometries(); i++) {
+ LineString edge = (LineString) result.getGeometryN(i);
+ Coordinate[] edgeCoords = edge.getCoordinates();
+ // Check if either endpoint is near the center
+ if (edgeCoords[0].distance(center.getCoordinate()) < 0.5
+ || edgeCoords[1].distance(center.getCoordinate()) < 0.5) {
+ edgesNearCenter++;
+ }
+ }
+ assertTrue(
+ "Most skeleton edges should converge near center",
+ edgesNearCenter >= numPoints * 0.5); // At least half should be near
center
+ }
+
+ @Test
+ public void straightSkeletonTShapeTopology() throws ParseException {
+ // Test with a T-shaped polygon - straight skeleton should reflect T
topology
+ // Vertical bar: x from 4-6, y from 0-10
+ // Horizontal bar: x from 0-10, y from 8-10
+ Coordinate[] coords =
+ new Coordinate[] {
+ new Coordinate(4, 0),
+ new Coordinate(6, 0),
+ new Coordinate(6, 8),
+ new Coordinate(10, 8),
+ new Coordinate(10, 10),
+ new Coordinate(0, 10),
+ new Coordinate(0, 8),
+ new Coordinate(4, 8),
+ new Coordinate(4, 0)
+ };
+
+ Polygon tShape = GEOMETRY_FACTORY.createPolygon(coords);
+ Geometry result = Functions.straightSkeleton(tShape);
+
+ assertTrue(result instanceof MultiLineString);
+ assertFalse(result.isEmpty());
+
+ // T-shape has 8 vertices, so straight skeleton should have edges
+ assertTrue("T-shape should have multiple skeleton edges",
result.getNumGeometries() >= 6);
+
+ // All skeleton edges should be inside or touching the T-shape
+ for (int i = 0; i < result.getNumGeometries(); i++) {
+ Geometry part = result.getGeometryN(i);
+ assertTrue(
+ "All skeleton edges should be inside or intersect T-shape",
+ tShape.contains(part) || tShape.intersects(part));
+ }
+
+ // Verify skeleton has reasonable total length
+ double skeletonLength = result.getLength();
+ assertTrue("Skeleton should have positive length", skeletonLength > 0);
+ assertTrue(
+ "Skeleton length should be less than perimeter", skeletonLength <
tShape.getLength());
+ }
+
+ @Test
+ public void straightSkeletonConsistency() throws ParseException {
+ // Test that running the function twice on the same geometry gives
consistent results
+ Polygon polygon =
+ GEOMETRY_FACTORY.createPolygon(coordArray(0, 0, 10, 0, 10, 5, 5, 5, 5,
10, 0, 10, 0, 0));
+
+ Geometry result1 = Functions.straightSkeleton(polygon);
+ Geometry result2 = Functions.straightSkeleton(polygon);
+
+ // Results should be equal (same geometry)
+ assertTrue("Multiple runs should produce consistent results",
result1.equals(result2));
+ }
+
+ @Test
+ public void straightSkeletonAllPointsInsidePolygon() throws ParseException {
+ // Verify that all coordinate points in the medial axis are inside or on
the boundary
+ Polygon polygon = GEOMETRY_FACTORY.createPolygon(coordArray(0, 0, 20, 0,
20, 10, 0, 10, 0, 0));
+ Geometry result = Functions.straightSkeleton(polygon);
+
+ assertTrue(result instanceof MultiLineString);
+
+ // Extract all coordinates from the medial axis
+ Coordinate[] allCoords = result.getCoordinates();
+
+ // Every coordinate should be inside or on the polygon boundary
+ for (Coordinate coord : allCoords) {
+ Point point = GEOMETRY_FACTORY.createPoint(coord);
+ assertTrue(
+ "All medial axis points should be inside or on polygon boundary",
+ polygon.contains(point) || polygon.touches(point) ||
polygon.distance(point) < 0.01);
+ }
+ }
+
+ @Test
+ public void approximateMedialAxis() throws ParseException {
+ // Test basic functionality with an L-shaped polygon
+ // L-shapes have interior edges, unlike simple squares/rectangles
+ Polygon lShape =
+ GEOMETRY_FACTORY.createPolygon(
+ coordArray(0, 0, 100, 0, 100, 40, 40, 40, 40, 100, 0, 100, 0, 0));
+ Geometry result = Functions.approximateMedialAxis(lShape);
+
+ assertNotNull(result);
+ assertTrue(result instanceof MultiLineString);
+ assertTrue(result.getNumGeometries() > 0);
+
+ // Approximate medial axis should have fewer or equal segments than raw
skeleton due to
+ // filtering
+ Geometry straightSkel = Functions.straightSkeleton(lShape);
+ assertTrue(
+ "Filtered skeleton should have <= segments than raw skeleton",
+ result.getNumGeometries() <= straightSkel.getNumGeometries());
+
+ // Test T-shaped polygon - another shape with interior edges
+ Polygon tShape =
+ GEOMETRY_FACTORY.createPolygon(
+ coordArray(45, 0, 55, 0, 55, 40, 70, 40, 70, 50, 30, 50, 30, 40,
45, 40, 45, 0));
+ result = Functions.approximateMedialAxis(tShape);
+ assertNotNull(result);
+ assertTrue(result.getNumGeometries() > 0);
+ }
+
+ @Test
+ public void approximateMedialAxisSRID() throws ParseException {
+ // Use L-shaped polygon to ensure interior edges exist
+ Polygon geom =
+ GEOMETRY_FACTORY.createPolygon(coordArray(0, 0, 10, 0, 10, 4, 4, 4, 4,
10, 0, 10, 0, 0));
+ geom.setSRID(4326);
+ Geometry result = Functions.approximateMedialAxis(geom);
+ assertEquals(4326, result.getSRID());
+ }
+
+ @Test
+ public void approximateMedialAxisNullAndEmpty() {
+ // Test null input
+ Geometry result = Functions.approximateMedialAxis(null);
+ assertNull(result);
+
+ // Test empty polygon
+ Polygon emptyPolygon = GEOMETRY_FACTORY.createPolygon();
+ result = Functions.approximateMedialAxis(emptyPolygon);
+ assertNull(result);
+ }
+
+ @Test
+ public void approximateMedialAxisInvalidGeometry() {
+ // Test with LineString (should throw exception)
+ LineString lineString = GEOMETRY_FACTORY.createLineString(coordArray(0, 0,
10, 0, 10, 10));
+ IllegalArgumentException e =
+ assertThrows(
+ IllegalArgumentException.class, () ->
Functions.approximateMedialAxis(lineString));
+ assertTrue(
+ e.getMessage().contains("ST_ApproximateMedialAxis only supports
Polygon and MultiPolygon"));
+
+ // Test with Point (should throw exception)
+ Point point = GEOMETRY_FACTORY.createPoint(new Coordinate(5, 5));
+ e = assertThrows(IllegalArgumentException.class, () ->
Functions.approximateMedialAxis(point));
+ assertTrue(
+ e.getMessage().contains("ST_ApproximateMedialAxis only supports
Polygon and MultiPolygon"));
+ }
+
+ @Test
+ public void approximateMedialAxisMultiPolygon() throws ParseException {
+ // Create a MultiPolygon with two L-shaped polygons (which have interior
edges)
+ Polygon poly1 =
+ GEOMETRY_FACTORY.createPolygon(coordArray(0, 0, 10, 0, 10, 4, 4, 4, 4,
10, 0, 10, 0, 0));
+ Polygon poly2 =
+ GEOMETRY_FACTORY.createPolygon(
+ coordArray(20, 20, 30, 20, 30, 24, 24, 24, 24, 30, 20, 30, 20,
20));
+ MultiPolygon multiPolygon = GEOMETRY_FACTORY.createMultiPolygon(new
Polygon[] {poly1, poly2});
+
+ Geometry result = Functions.approximateMedialAxis(multiPolygon);
+
+ assertNotNull(result);
+ assertTrue(result instanceof MultiLineString);
+ // Should have segments from both polygons
+ assertTrue(result.getNumGeometries() > 0);
+ }
+
+ @Test
+ public void approximateMedialAxisPruningEffectiveness() throws
ParseException {
+ // Test T-shaped polygon - should demonstrate effective pruning
+ // T-shape has many small corner branches that should be pruned
+ Polygon tShape =
+ GEOMETRY_FACTORY.createPolygon(
+ coordArray(45, 0, 55, 0, 55, 40, 70, 40, 70, 50, 30, 50, 30, 40,
45, 40, 45, 0));
+
+ Geometry straightSkel = Functions.straightSkeleton(tShape);
+ Geometry prunedSkel = Functions.approximateMedialAxis(tShape);
+
+ // The pruned skeleton should have significantly fewer segments
+ assertTrue(
+ "Pruned skeleton should have fewer segments for T-shape",
+ prunedSkel.getNumGeometries() < straightSkel.getNumGeometries());
+
+ // All points should still be inside or on the polygon
+ Coordinate[] allCoords = prunedSkel.getCoordinates();
+ for (Coordinate coord : allCoords) {
+ Point point = GEOMETRY_FACTORY.createPoint(coord);
+ assertTrue(
+ "All pruned medial axis points should be inside or on polygon
boundary",
+ tShape.contains(point) || tShape.touches(point) ||
tShape.distance(point) < 0.01);
+ }
+ }
+
+ @Test
+ public void approximateMedialAxisConsistency() throws ParseException {
+ // Verify that the function produces consistent results for the same input
+ Polygon polygon =
+ GEOMETRY_FACTORY.createPolygon(coordArray(0, 0, 100, 0, 100, 50, 0,
50, 0, 0));
+ Geometry result1 = Functions.approximateMedialAxis(polygon);
+ Geometry result2 = Functions.approximateMedialAxis(polygon);
+
+ assertTrue("Results should be equal", result1.equalsExact(result2, 1e-6));
+ }
+
+ @Test
+ public void approximateMedialAxisAllPointsInsidePolygon() throws
ParseException {
+ // Verify that all coordinate points in the pruned medial axis are inside
or on the boundary
+ Polygon polygon = GEOMETRY_FACTORY.createPolygon(coordArray(0, 0, 20, 0,
20, 10, 0, 10, 0, 0));
+ Geometry result = Functions.approximateMedialAxis(polygon);
+
+ assertTrue(result instanceof MultiLineString);
+
+ // Extract all coordinates from the medial axis
+ Coordinate[] allCoords = result.getCoordinates();
+
+ // Every coordinate should be inside or on the polygon boundary
+ for (Coordinate coord : allCoords) {
+ Point point = GEOMETRY_FACTORY.createPoint(coord);
+ assertTrue(
+ "All pruned medial axis points should be inside or on polygon
boundary",
+ polygon.contains(point) || polygon.touches(point) ||
polygon.distance(point) < 0.01);
+ }
+ }
+
+ @Test
+ public void approximateMedialAxisPolygonWithHole() throws ParseException {
+ // Test polygon with a rectangular hole (donut shape)
+ LinearRing shell =
+ GEOMETRY_FACTORY.createLinearRing(coordArray(0, 0, 100, 0, 100, 60, 0,
60, 0, 0));
+ LinearRing hole =
+ GEOMETRY_FACTORY.createLinearRing(coordArray(20, 20, 80, 20, 80, 40,
20, 40, 20, 20));
+ Polygon polygonWithHole = GEOMETRY_FACTORY.createPolygon(shell, new
LinearRing[] {hole});
+
+ Geometry result = Functions.approximateMedialAxis(polygonWithHole);
+
+ assertNotNull("Result should not be null for polygon with hole", result);
+ assertTrue("Result should be MultiLineString", result instanceof
MultiLineString);
+ assertTrue(
+ "Result should have segments, got: " + result.getNumGeometries(),
+ result.getNumGeometries() > 0);
+
+ // Verify the result has fewer or equal segments compared to straight
skeleton
+ Geometry straightSkel = Functions.straightSkeleton(polygonWithHole);
+ assertNotNull("Straight skeleton should not be null", straightSkel);
+ assertTrue(
+ "Pruned skeleton should have <= segments than raw skeleton. Pruned: "
+ + result.getNumGeometries()
+ + ", Raw: "
+ + straightSkel.getNumGeometries(),
+ result.getNumGeometries() <= straightSkel.getNumGeometries());
+ }
}
diff --git
a/common/src/test/java/org/apache/sedona/common/StraightSkeletonTest.java
b/common/src/test/java/org/apache/sedona/common/StraightSkeletonTest.java
new file mode 100644
index 0000000000..fdf6e9a6e5
--- /dev/null
+++ b/common/src/test/java/org/apache/sedona/common/StraightSkeletonTest.java
@@ -0,0 +1,441 @@
+/*
+ * 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;
+
+import static org.junit.Assert.*;
+
+import org.junit.Test;
+import org.locationtech.jts.geom.Geometry;
+import org.locationtech.jts.geom.LineString;
+import org.locationtech.jts.geom.MultiLineString;
+
+/**
+ * Comprehensive tests for Straight Skeleton implementation.
+ *
+ * <p>Tests cover: - Simple polygons (square, rectangle, triangle) - Complex
polygons (L-shape,
+ * U-shape, T-shape, star) - Polygons with reflex angles - MultiPolygon
geometries - Edge cases
+ * (very narrow, concave shapes)
+ */
+public class StraightSkeletonTest {
+
+ /**
+ * Helper method to test a polygon and verify basic properties of its medial
axis.
+ *
+ * @param testName Name of the test for reporting
+ * @param wkt WKT representation of the polygon
+ * @param expectedSegments Expected number of skeleton segments
+ */
+ private void testPolygon(String testName, String wkt, int expectedSegments)
throws Exception {
+ testPolygon(testName, wkt, expectedSegments, true);
+ }
+
+ /**
+ * Helper method to test a polygon and verify basic properties of its medial
axis.
+ *
+ * @param testName Name of the test for reporting
+ * @param wkt WKT representation of the polygon
+ * @param expectedSegments Expected number of skeleton segments
+ * @param strictLengthCheck If false, skip perimeter comparison (for complex
road networks)
+ */
+ private void testPolygon(
+ String testName, String wkt, int expectedSegments, boolean
strictLengthCheck)
+ throws Exception {
+ Geometry polygon = Constructors.geomFromWKT(wkt, 0);
+ Geometry medialAxis = Functions.straightSkeleton(polygon);
+
+ // Basic assertions
+ assertNotNull(testName + ": Medial axis should not be null", medialAxis);
+ assertTrue(
+ testName + ": Result should be MultiLineString", medialAxis instanceof
MultiLineString);
+
+ int numSegments = medialAxis.getNumGeometries();
+
+ // If expectedSegments is -1, skip exact count assertion (just verify it
works)
+ if (expectedSegments >= 0) {
+ assertEquals(
+ testName + ": Should have exactly " + expectedSegments + " segments",
+ expectedSegments,
+ numSegments);
+ } else {
+ // Just verify we got some segments
+ assertTrue(testName + ": Should produce at least one segment",
numSegments > 0);
+ }
+
+ // Verify all skeleton edges are inside or touch the polygon
+ for (int i = 0; i < numSegments; i++) {
+ LineString edge = (LineString) medialAxis.getGeometryN(i);
+ assertTrue(
+ testName + ": All skeleton edges should be inside or intersect the
polygon",
+ polygon.contains(edge) || polygon.intersects(edge));
+ }
+
+ // Verify skeleton has reasonable length (skip for degenerate cases with 0
segments)
+ double skeletonLength = medialAxis.getLength();
+ if (expectedSegments > 0) {
+ assertTrue(testName + ": Skeleton length should be positive",
skeletonLength > 0);
+ }
+
+ // For simple polygons, skeleton should be shorter than perimeter
+ // For complex road networks, this may not hold due to branching structure
+ if (strictLengthCheck) {
+ double perimeter = polygon.getLength();
+ assertTrue(
+ testName + ": Skeleton length should be less than perimeter",
skeletonLength < perimeter);
+ }
+
+ // Note: For complex concave polygons, skeleton points may be slightly
outside due to
+ // precision issues in the straight skeleton algorithm. We skip strict
containment validation
+ // for now and rely on the other checks (edge containment, reasonable
length, etc.)
+ }
+
+ // ==================== Simple Polygon Tests ====================
+
+ @Test
+ public void testSimpleSquare() throws Exception {
+ testPolygon("Simple Square", "POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))", 4);
+ }
+
+ @Test
+ public void testSimpleRectangle() throws Exception {
+ testPolygon("Simple Rectangle", "POLYGON ((0 0, 20 0, 20 10, 0 10, 0 0))",
5);
+ }
+
+ @Test
+ public void testEquilateralTriangle() throws Exception {
+ // Equilateral triangle centered at origin
+ double height = Math.sqrt(3) / 2 * 10;
+ String wkt =
+ String.format(
+ "POLYGON ((0 %.2f, -5 -%.2f, 5 -%.2f, 0 %.2f))", height, height,
height, height);
+ testPolygon("Equilateral Triangle", wkt, 3);
+ }
+
+ @Test
+ public void testRightTriangle() throws Exception {
+ testPolygon("Right Triangle", "POLYGON ((0 0, 10 0, 0 10, 0 0))", 3);
+ }
+
+ // ==================== Complex Polygon Tests ====================
+
+ @Test
+ public void testLShapedPolygon() throws Exception {
+ testPolygon(
+ "L-Shaped Polygon",
+ "POLYGON ((190 190, 10 190, 10 10, 190 10, 190 20, 160 30, 60 30, 60
130, 190 140, 190 190))",
+ 15);
+ }
+
+ @Test
+ public void testUShapedPolygon() throws Exception {
+ // U-shape: outer rectangle with inner rectangle cut out from top
+ testPolygon(
+ "U-Shaped Polygon", "POLYGON ((0 0, 20 0, 20 20, 15 20, 15 5, 5 5, 5
20, 0 20, 0 0))", 11);
+ }
+
+ @Test
+ public void testTShapedPolygon() throws Exception {
+ // T-shape: vertical stem with horizontal top bar
+ testPolygon(
+ "T-Shaped Polygon", "POLYGON ((4 0, 6 0, 6 8, 10 8, 10 10, 0 10, 0 8,
4 8, 4 0))", 12);
+ }
+
+ @Test
+ public void testCShapedPolygon() throws Exception {
+ // C-shape: rectangle with rectangular notch on right side
+ testPolygon(
+ "C-Shaped Polygon", "POLYGON ((0 0, 10 0, 10 5, 5 5, 5 10, 10 10, 10
15, 0 15, 0 0))", 11);
+ }
+
+ @Test
+ public void testStarPolygon() throws Exception {
+ // Simple 4-pointed star
+ testPolygon("Star Polygon", "POLYGON ((5 0, 6 4, 10 5, 6 6, 5 10, 4 6, 0
5, 4 4, 5 0))", 8);
+ }
+
+ @Test
+ public void testComplexConcavePolygon() throws Exception {
+ // Irregular concave polygon with multiple reflex angles
+ testPolygon(
+ "Complex Concave Polygon",
+ "POLYGON ((0 0, 20 0, 20 5, 15 5, 15 10, 10 10, 10 5, 5 5, 5 15, 0 15,
0 0))",
+ 15,
+ false);
+ }
+
+ // ==================== Edge Case Tests ====================
+
+ @Test
+ public void testVeryNarrowRectangle() throws Exception {
+ // Very elongated rectangle (100:1 aspect ratio)
+ testPolygon("Very Narrow Rectangle", "POLYGON ((0 0, 100 0, 100 1, 0 1, 0
0))", 5);
+ }
+
+ @Test
+ public void testAlmostRegularHexagon() throws Exception {
+ // Regular hexagon (6 sides)
+ double r = 10.0;
+ StringBuilder hexWkt = new StringBuilder("POLYGON ((");
+ for (int i = 0; i < 6; i++) {
+ double angle = Math.PI / 3 * i;
+ double x = r * Math.cos(angle);
+ double y = r * Math.sin(angle);
+ if (i > 0) hexWkt.append(", ");
+ hexWkt.append(String.format("%.2f %.2f", x, y));
+ }
+ hexWkt.append(", ");
+ hexWkt.append(String.format("%.2f %.2f", r, 0.0)); // Close the ring
+ hexWkt.append("))");
+
+ testPolygon(
+ "Regular Hexagon", hexWkt.toString(), 7, false); // Allow skeleton
length > perimeter
+ }
+
+ @Test
+ public void testPentagon() throws Exception {
+ // Regular pentagon
+ double r = 10.0;
+ StringBuilder pentWkt = new StringBuilder("POLYGON ((");
+ for (int i = 0; i < 5; i++) {
+ double angle = 2 * Math.PI / 5 * i - Math.PI / 2; // Start from top
+ double x = r * Math.cos(angle);
+ double y = r * Math.sin(angle);
+ if (i > 0) pentWkt.append(", ");
+ pentWkt.append(String.format("%.2f %.2f", x, y));
+ }
+ pentWkt.append(", ");
+ pentWkt.append(
+ String.format("%.2f %.2f", r * Math.cos(-Math.PI / 2), r *
Math.sin(-Math.PI / 2)));
+ pentWkt.append("))");
+
+ testPolygon("Regular Pentagon", pentWkt.toString(), 7, false);
+ }
+
+ @Test
+ public void testCrossPolygon() throws Exception {
+ // Plus/cross shape (like + sign)
+ testPolygon(
+ "Cross Polygon",
+ "POLYGON ((4 0, 6 0, 6 4, 10 4, 10 6, 6 6, 6 10, 4 10, 4 6, 0 6, 0 4,
4 4, 4 0))",
+ 16);
+ }
+
+ // ==================== MultiPolygon Tests ====================
+
+ @Test
+ public void testSimpleMultiPolygon() throws Exception {
+ // Two separate squares
+ String wkt =
+ "MULTIPOLYGON (((0 0, 10 0, 10 10, 0 10, 0 0)), ((20 20, 30 20, 30 30,
20 30, 20 20)))";
+
+ Geometry multiPolygon = Constructors.geomFromWKT(wkt, 0);
+ Geometry medialAxis = Functions.straightSkeleton(multiPolygon);
+
+ assertNotNull("MultiPolygon: Medial axis should not be null", medialAxis);
+ assertTrue(
+ "MultiPolygon: Result should be MultiLineString", medialAxis
instanceof MultiLineString);
+
+ int numSegments = medialAxis.getNumGeometries();
+ assertEquals(
+ "MultiPolygon: Two squares should produce 8 total segments (4 each)",
8, numSegments);
+
+ // Verify skeleton is valid
+ assertTrue("MultiPolygon: Skeleton should have positive length",
medialAxis.getLength() > 0);
+ }
+
+ @Test
+ public void testComplexMultiPolygon() throws Exception {
+ // Multiple different shapes
+ String wkt =
+ "MULTIPOLYGON ("
+ + "((0 0, 10 0, 10 10, 0 10, 0 0)), "
+ + // Square
+ "((20 0, 40 0, 40 5, 20 5, 20 0)), "
+ + // Rectangle
+ "((50 0, 55 0, 52.5 5, 50 0))"
+ + // Triangle
+ ")";
+
+ Geometry multiPolygon = Constructors.geomFromWKT(wkt, 0);
+ Geometry medialAxis = Functions.straightSkeleton(multiPolygon);
+
+ assertNotNull("Complex MultiPolygon: Medial axis should not be null",
medialAxis);
+ assertTrue(
+ "Complex MultiPolygon: Result should be MultiLineString",
+ medialAxis instanceof MultiLineString);
+
+ int numSegments = medialAxis.getNumGeometries();
+ assertTrue(
+ "Complex MultiPolygon: Should have multiple segments", numSegments >=
8); // More lenient
+
+ // Verify all edges are inside or intersect the multipolygon
+ for (int i = 0; i < numSegments; i++) {
+ LineString edge = (LineString) medialAxis.getGeometryN(i);
+ assertTrue(
+ "Complex MultiPolygon: All skeleton edges should be inside or
intersect input",
+ multiPolygon.contains(edge) || multiPolygon.intersects(edge));
+ }
+ }
+
+ @Test
+ public void testMultiPolygonWithComplexShapes() throws Exception {
+ // MultiPolygon with L-shape and U-shape
+ String wkt =
+ "MULTIPOLYGON ("
+ + "((0 0, 10 0, 10 5, 5 5, 5 10, 0 10, 0 0)), "
+ + // L-shape
+ "((20 0, 30 0, 30 10, 27 10, 27 3, 23 3, 23 10, 20 10, 20 0))"
+ + // U-shape
+ ")";
+
+ Geometry multiPolygon = Constructors.geomFromWKT(wkt, 0);
+ Geometry medialAxis = Functions.straightSkeleton(multiPolygon);
+
+ assertNotNull("Complex shapes MultiPolygon: Medial axis should not be
null", medialAxis);
+ int numSegments = medialAxis.getNumGeometries();
+ assertTrue("Complex shapes MultiPolygon: Should have multiple segments",
numSegments >= 12);
+
+ // Verify SRID preservation
+ multiPolygon = Constructors.geomFromWKT(wkt, 4326);
+ medialAxis = Functions.straightSkeleton(multiPolygon);
+ assertEquals(
+ "Complex shapes MultiPolygon: SRID should be preserved", 4326,
medialAxis.getSRID());
+ }
+
+ // ==================== Special Cases ====================
+
+ @Test
+ public void testPolygonWithReflexAngles() throws Exception {
+ // Polygon with multiple reflex (concave) angles
+ testPolygon(
+ "Polygon with Reflex Angles",
+ "POLYGON ((0 0, 15 0, 15 5, 10 5, 10 10, 5 10, 5 5, 0 5, 0 0))",
+ 12,
+ false);
+ }
+
+ @Test
+ public void testArrowPolygon() throws Exception {
+ // Arrow-shaped polygon pointing right
+ testPolygon("Arrow Polygon", "POLYGON ((0 5, 8 5, 8 2, 12 6, 8 10, 8 7, 0
7, 0 5))", 8);
+ }
+
+ @Test
+ public void testDiamondPolygon() throws Exception {
+ // Diamond shape (rotated square)
+ testPolygon("Diamond Polygon", "POLYGON ((5 0, 10 5, 5 10, 0 5, 5 0))", 4);
+ }
+
+ @Test
+ public void testComplexRoadNetwork() throws Exception {
+ // Simple T-shaped road junction (vertical stem with horizontal branch at
top)
+ // This represents a realistic road junction similar to a T-intersection
+ String roadNetwork =
+ "POLYGON (("
+ // Bottom of vertical stem
+ + "45 0, 55 0, "
+ // Right side up to junction
+ + "55 40, "
+ // Right branch of horizontal road
+ + "70 40, 70 50, "
+ // Left branch of horizontal road
+ + "30 50, 30 40, "
+ // Left side down
+ + "45 40, "
+ // Close polygon
+ + "45 0))";
+
+ // T-junction produces 12 skeleton segments
+ // Use relaxed validation since road networks can have skeleton length >
perimeter
+ testPolygon("Complex Road Network (T-Junction)", roadNetwork, 12, false);
+ }
+
+ @Test
+ public void testRoadIntersectionComplex() throws Exception {
+ // Simplified but realistic road intersection test
+ // 4-way intersection with road widths
+ String intersection =
+ "POLYGON (("
+ // North road (top)
+ + "45 100, 55 100, 55 70, "
+ // Northeast corner
+ + "70 70, 70 55, "
+ // East road (right)
+ + "100 55, 100 45, 70 45, "
+ // Southeast corner
+ + "70 30, 55 30, "
+ // South road (bottom)
+ + "55 0, 45 0, 45 30, "
+ // Southwest corner
+ + "30 30, 30 45, "
+ // West road (left)
+ + "0 45, 0 55, 30 55, "
+ // Northwest corner
+ + "30 70, 45 70, "
+ // Close back to north
+ + "45 100))";
+
+ // 4-way intersection produces 24 segments with straight skeleton algorithm
+ // Use relaxed validation since road networks can have skeleton length >
perimeter
+ testPolygon("Road Intersection 4-Way", intersection, 24, false);
+ }
+
+ @Test
+ public void testComplexBranchingRoadNetwork() throws Exception {
+ // Complex branching road network with 6 branches extending from main trunk
+ // Simulates a dendritic road structure similar to the image
+ // Main trunk runs vertically with 3 branches on each side
+ String complexRoad =
+ "POLYGON (("
+ // Bottom of main trunk
+ + "47 0, 53 0, "
+ // Right side going up - start
+ + "53 15, "
+ // Branch 1 right (bottom-right)
+ + "55 16, 65 14, 66 17, 56 19, 54 18, "
+ // Continue trunk right
+ + "54 30, "
+ // Branch 2 right (middle-right)
+ + "56 31, 70 33, 71 36, 57 34, 55 33, "
+ // Continue trunk right
+ + "55 45, "
+ // Branch 3 right (top-right)
+ + "57 46, 72 50, 73 53, 58 49, 56 48, "
+ // Top of trunk
+ + "56 60, 44 60, "
+ // Left side going down - start
+ + "44 48, "
+ // Branch 3 left (top-left)
+ + "42 49, 27 53, 28 50, 43 46, "
+ // Continue trunk left
+ + "45 45, 45 33, "
+ // Branch 2 left (middle-left)
+ + "43 34, 29 36, 30 33, 44 31, "
+ // Continue trunk left
+ + "46 30, 46 18, "
+ // Branch 1 left (bottom-left)
+ + "44 19, 34 17, 35 14, 45 16, "
+ // Close to bottom
+ + "47 15, 47 0))";
+
+ // Complex branching network produces 71 skeleton segments
+ // Represents main trunk centerline plus 6 branch centerlines
+ // Use relaxed validation since complex road networks may have precision
issues
+ testPolygon("Complex Branching Road Network", complexRoad, 71, false);
+ }
+}
diff --git a/docs/api/flink/Function.md b/docs/api/flink/Function.md
index 8c63885f94..c0563b3cd2 100644
--- a/docs/api/flink/Function.md
+++ b/docs/api/flink/Function.md
@@ -251,6 +251,32 @@ Output:
0.19739555984988044
```
+## ST_ApproximateMedialAxis
+
+Introduction: Computes an approximate medial axis of a polygonal geometry. The
medial axis is a representation of the "centerline" or "skeleton" of the
polygon. This function first computes the straight skeleton and then prunes
insignificant branches to produce a cleaner result.
+
+The pruning removes small branches that represent minor penetrations into
corners. A branch is pruned if its penetration depth is less than 20% of the
width of the corner it bisects.
+
+This function may have significant performance limitations when processing
polygons with a very large number of vertices. For very large polygons (e.g.,
10,000+ vertices), applying vertex reduction or simplification is essential to
achieve practical computation times.
+
+Format: `ST_ApproximateMedialAxis(geom: Geometry)`
+
+Since: `v1.8.0`
+
+Example:
+
+```sql
+SELECT ST_ApproximateMedialAxis(
+ ST_GeomFromWKT('POLYGON ((45 0, 55 0, 55 40, 70 40, 70 50, 30 50, 30 40, 45
40, 45 0))')
+)
+```
+
+Output:
+
+```
+MULTILINESTRING ((50 45, 50 5), (50 45, 35 45), (65 45, 50 45), (35 45, 65 45))
+```
+
## ST_Area
Introduction: Return the area of A
@@ -4072,6 +4098,32 @@ Output:
POINT(100 150)
```
+## ST_StraightSkeleton
+
+Introduction: Computes the straight skeleton of a polygonal geometry. The
straight skeleton is a method of representing a polygon by a topological
skeleton, formed by a continuous shrinking process where each edge moves inward
in parallel at a uniform speed.
+
+This function uses the weighted straight skeleton algorithm based on Felkel's
approach.
+
+This function may have significant performance limitations when processing
polygons with a very large number of vertices. For very large polygons (e.g.,
10,000+ vertices), applying vertex reduction or simplification is essential to
achieve practical computation times.
+
+Format: `ST_StraightSkeleton(geom: Geometry)`
+
+Since: `v1.8.0`
+
+Example:
+
+```sql
+SELECT ST_StraightSkeleton(
+ ST_GeomFromWKT('POLYGON ((45 0, 55 0, 55 40, 70 40, 70 50, 30 50, 30 40, 45
40, 45 0))')
+)
+```
+
+Output:
+
+```
+MULTILINESTRING ((50 5, 50 45), (50 45, 35 45), (50 45, 65 45), (35 45, 30
45), (35 45, 40 40), (65 45, 70 45), (65 45, 60 40), (50 5, 45 5), (50 5, 55 5))
+```
+
## ST_SubDivide
Introduction: Returns list of geometries divided based of given maximum number
of vertices.
diff --git a/docs/api/snowflake/vector-data/Function.md
b/docs/api/snowflake/vector-data/Function.md
index 34b06a9e96..c9ed83021d 100644
--- a/docs/api/snowflake/vector-data/Function.md
+++ b/docs/api/snowflake/vector-data/Function.md
@@ -209,6 +209,26 @@ Output:
0.19739555984988044
```
+## ST_ApproximateMedialAxis
+
+Introduction: Computes an approximate medial axis of a polygonal geometry. The
medial axis is a representation of the "centerline" or "skeleton" of the
polygon. This function first computes the straight skeleton and then prunes
insignificant branches to produce a cleaner result.
+
+The pruning removes small branches that represent minor penetrations into
corners. A branch is pruned if its penetration depth is less than 20% of the
width of the corner it bisects.
+
+This function may have significant performance limitations when processing
polygons with a very large number of vertices. For very large polygons (e.g.,
10,000+ vertices), applying vertex reduction or simplification is essential to
achieve practical computation times.
+
+Format: `ST_ApproximateMedialAxis(geom: geometry)`
+
+SQL example:
+
+```sql
+SELECT Sedona.ST_ApproximateMedialAxis(
+ ST_GeometryFromWKT('POLYGON ((45 0, 55 0, 55 40, 70 40, 70 50, 30 50, 30 40,
45 40, 45 0))')
+)
+```
+
+Output: `MULTILINESTRING ((50 45, 50 5), (50 45, 35 45), (65 45, 50 45), (35
45, 65 45))`
+
## ST_Area
Introduction: Return the area of A
@@ -3200,6 +3220,26 @@ SELECT ST_StartPoint(ST_GeomFromText('LINESTRING(100
150,50 60, 70 80, 160 170)'
Output: `POINT(100 150)`
+## ST_StraightSkeleton
+
+Introduction: Computes the straight skeleton of a polygonal geometry. The
straight skeleton is a method of representing a polygon by a topological
skeleton, formed by a continuous shrinking process where each edge moves inward
in parallel at a uniform speed.
+
+This function uses the weighted straight skeleton algorithm based on Felkel's
approach.
+
+This function may have significant performance limitations when processing
polygons with a very large number of vertices. For very large polygons (e.g.,
10,000+ vertices), applying vertex reduction or simplification is essential to
achieve practical computation times.
+
+Format: `ST_StraightSkeleton(geom: geometry)`
+
+SQL example:
+
+```sql
+SELECT Sedona.ST_StraightSkeleton(
+ ST_GeometryFromWKT('POLYGON ((45 0, 55 0, 55 40, 70 40, 70 50, 30 50, 30 40,
45 40, 45 0))')
+)
+```
+
+Output: `MULTILINESTRING ((50 5, 50 45), (50 45, 35 45), (50 45, 65 45), (35
45, 30 45), (35 45, 40 40), (65 45, 70 45), (65 45, 60 40), (50 5, 45 5), (50
5, 55 5))`
+
## ST_SubDivide
Introduction: Returns a multi-geometry divided based of given maximum number
of vertices.
diff --git a/docs/api/sql/Function.md b/docs/api/sql/Function.md
index 6a893cec16..eb524512cf 100644
--- a/docs/api/sql/Function.md
+++ b/docs/api/sql/Function.md
@@ -296,6 +296,48 @@ Output:
0.19739555984988044
```
+## ST_ApproximateMedialAxis
+
+Introduction: Computes an approximate medial axis of a polygonal geometry. The
medial axis is a representation of the "centerline" or "skeleton" of the
polygon. This function first computes the straight skeleton and then prunes
insignificant branches to produce a cleaner result.
+
+The pruning removes small branches that represent minor penetrations into
corners. A branch is pruned if its penetration depth is less than 20% of the
width of the corner it bisects.
+
+This function may have significant performance limitations when processing
polygons with a very large number of vertices. For very large polygons (e.g.,
10,000+ vertices), applying vertex reduction or simplification is essential to
achieve practical computation times.
+
+Format: `ST_ApproximateMedialAxis(geom: Geometry)`
+
+Since: `v1.8.0`
+
+SQL Example:
+
+```sql
+SELECT ST_ApproximateMedialAxis(
+ ST_GeomFromWKT('POLYGON ((45 0, 55 0, 55 40, 70 40, 70 50, 30 50, 30 40, 45
40, 45 0))')
+)
+```
+
+Output:
+
+```
+MULTILINESTRING ((50 45, 50 5), (50 45, 35 45), (65 45, 50 45), (35 45, 65 45))
+```
+
+
+
+SQL Example (L-shape):
+
+```sql
+SELECT ST_ApproximateMedialAxis(
+ ST_GeomFromWKT('POLYGON ((0 0, 10 0, 10 5, 5 5, 5 10, 0 10, 0 0))')
+)
+```
+
+Output:
+
+```
+MULTILINESTRING ((2.5 2.5, 2.5 7.5), (7.5 2.5, 2.5 2.5), (2.5 7.5, 2.5 7.5))
+```
+
## ST_Area
Introduction: Return the area of A
@@ -4336,6 +4378,48 @@ Output:
POINT(100 150)
```
+## ST_StraightSkeleton
+
+Introduction: Computes the straight skeleton of a polygonal geometry. The
straight skeleton is a method of representing a polygon by a topological
skeleton, formed by a continuous shrinking process where each edge moves inward
in parallel at a uniform speed.
+
+This function uses the weighted straight skeleton algorithm based on Felkel's
approach.
+
+This function may have significant performance limitations when processing
polygons with a very large number of vertices. For very large polygons (e.g.,
10,000+ vertices), applying vertex reduction or simplification is essential to
achieve practical computation times.
+
+Format: `ST_StraightSkeleton(geom: Geometry)`
+
+Since: `v1.8.0`
+
+SQL Example:
+
+```sql
+SELECT ST_StraightSkeleton(
+ ST_GeomFromWKT('POLYGON ((45 0, 55 0, 55 40, 70 40, 70 50, 30 50, 30 40, 45
40, 45 0))')
+)
+```
+
+Output:
+
+```
+MULTILINESTRING ((50 5, 50 45), (50 45, 35 45), (50 45, 65 45), (35 45, 30
45), (35 45, 40 40), (65 45, 70 45), (65 45, 60 40), (50 5, 45 5), (50 5, 55 5))
+```
+
+
+
+SQL Example (Simple Square):
+
+```sql
+SELECT ST_StraightSkeleton(
+ ST_GeomFromWKT('POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))')
+)
+```
+
+Output:
+
+```
+MULTILINESTRING ((5 5, 0 5), (5 5, 5 0), (5 5, 10 5), (5 5, 5 10))
+```
+
## ST_SubDivide
Introduction: Returns list of geometries divided based of given maximum number
of vertices.
diff --git a/docs/image/skeleton/ST_ApproximateMedialAxis_illustration.png
b/docs/image/skeleton/ST_ApproximateMedialAxis_illustration.png
new file mode 100644
index 0000000000..b27c24b108
Binary files /dev/null and
b/docs/image/skeleton/ST_ApproximateMedialAxis_illustration.png differ
diff --git a/docs/image/skeleton/ST_StraightSkeleton_illustration.png
b/docs/image/skeleton/ST_StraightSkeleton_illustration.png
new file mode 100644
index 0000000000..7dd6592bd1
Binary files /dev/null and
b/docs/image/skeleton/ST_StraightSkeleton_illustration.png differ
diff --git a/flink/src/main/java/org/apache/sedona/flink/Catalog.java
b/flink/src/main/java/org/apache/sedona/flink/Catalog.java
index a4530c69d2..af62005483 100644
--- a/flink/src/main/java/org/apache/sedona/flink/Catalog.java
+++ b/flink/src/main/java/org/apache/sedona/flink/Catalog.java
@@ -213,11 +213,13 @@ public class Catalog {
new Functions.ST_Affine(),
new Functions.ST_BoundingDiagonal(),
new Functions.ST_Angle(),
+ new Functions.ST_ApproximateMedialAxis(),
new Functions.ST_Degrees(),
new Functions.ST_HausdorffDistance(),
new Functions.ST_IsCollection(),
new Functions.ST_CoordDim(),
- new Functions.ST_IsValidReason()
+ new Functions.ST_IsValidReason(),
+ new Functions.ST_StraightSkeleton()
};
}
diff --git
a/flink/src/main/java/org/apache/sedona/flink/expressions/Functions.java
b/flink/src/main/java/org/apache/sedona/flink/expressions/Functions.java
index b742884b93..211d7db796 100644
--- a/flink/src/main/java/org/apache/sedona/flink/expressions/Functions.java
+++ b/flink/src/main/java/org/apache/sedona/flink/expressions/Functions.java
@@ -100,6 +100,24 @@ public class Functions {
}
}
+ public static class ST_ApproximateMedialAxis extends ScalarFunction {
+ @DataTypeHint(value = "RAW", bridgedTo =
org.locationtech.jts.geom.Geometry.class)
+ public Geometry eval(
+ @DataTypeHint(value = "RAW", bridgedTo =
org.locationtech.jts.geom.Geometry.class)
+ Object o) {
+ Geometry geom = (Geometry) o;
+ return org.apache.sedona.common.Functions.approximateMedialAxis(geom);
+ }
+
+ @DataTypeHint(value = "RAW", bridgedTo =
org.locationtech.jts.geom.Geometry.class)
+ public Geometry eval(
+ @DataTypeHint(value = "RAW", bridgedTo =
org.locationtech.jts.geom.Geometry.class) Object o,
+ @DataTypeHint("Integer") Integer maxVertices) {
+ Geometry geom = (Geometry) o;
+ return org.apache.sedona.common.Functions.approximateMedialAxis(geom,
maxVertices);
+ }
+ }
+
public static class ST_Boundary extends ScalarFunction {
@DataTypeHint(value = "RAW", bridgedTo =
org.locationtech.jts.geom.Geometry.class)
public Geometry eval(
@@ -1422,6 +1440,24 @@ public class Functions {
}
}
+ public static class ST_StraightSkeleton extends ScalarFunction {
+ @DataTypeHint(value = "RAW", bridgedTo =
org.locationtech.jts.geom.Geometry.class)
+ public Geometry eval(
+ @DataTypeHint(value = "RAW", bridgedTo =
org.locationtech.jts.geom.Geometry.class)
+ Object o) {
+ Geometry geom = (Geometry) o;
+ return org.apache.sedona.common.Functions.straightSkeleton(geom);
+ }
+
+ @DataTypeHint(value = "RAW", bridgedTo =
org.locationtech.jts.geom.Geometry.class)
+ public Geometry eval(
+ @DataTypeHint(value = "RAW", bridgedTo =
org.locationtech.jts.geom.Geometry.class) Object o,
+ @DataTypeHint("Integer") Integer maxVertices) {
+ Geometry geom = (Geometry) o;
+ return org.apache.sedona.common.Functions.straightSkeleton(geom,
maxVertices);
+ }
+ }
+
public static class ST_Split extends ScalarFunction {
@DataTypeHint(value = "RAW", bridgedTo =
org.locationtech.jts.geom.Geometry.class)
public Geometry eval(
diff --git a/flink/src/test/java/org/apache/sedona/flink/FunctionTest.java
b/flink/src/test/java/org/apache/sedona/flink/FunctionTest.java
index 497ea53374..afa520af14 100644
--- a/flink/src/test/java/org/apache/sedona/flink/FunctionTest.java
+++ b/flink/src/test/java/org/apache/sedona/flink/FunctionTest.java
@@ -2971,4 +2971,56 @@ public class FunctionTest extends TestBase {
expected = 2.75;
assertEquals(expected, actual, 1e-6);
}
+
+ @Test
+ public void testST_StraightSkeleton() {
+ String polygonWkt = "POLYGON ((1 1, 1 3, 4 3, 4 1, 1 1))";
+ String actual =
+ (String)
+ first(
+ tableEnv.sqlQuery(
+ "SELECT
ST_GeometryType(ST_StraightSkeleton(ST_GeomFromWKT('"
+ + polygonWkt
+ + "')))"))
+ .getField(0);
+ assertEquals("ST_MultiLineString", actual);
+
+ // Test with maxVertices parameter
+ String complexPolygonWkt = "POLYGON ((0 0, 4 0, 4 4, 0 4, 0 0))";
+ actual =
+ (String)
+ first(
+ tableEnv.sqlQuery(
+ "SELECT
ST_GeometryType(ST_StraightSkeleton(ST_GeomFromWKT('"
+ + complexPolygonWkt
+ + "'), 10))"))
+ .getField(0);
+ assertEquals("ST_MultiLineString", actual);
+ }
+
+ @Test
+ public void testST_ApproximateMedialAxis() {
+ String polygonWkt = "POLYGON ((1 1, 1 3, 4 3, 4 1, 1 1))";
+ String actual =
+ (String)
+ first(
+ tableEnv.sqlQuery(
+ "SELECT
ST_GeometryType(ST_ApproximateMedialAxis(ST_GeomFromWKT('"
+ + polygonWkt
+ + "')))"))
+ .getField(0);
+ assertEquals("ST_MultiLineString", actual);
+
+ // Test with maxVertices parameter
+ String complexPolygonWkt = "POLYGON ((0 0, 4 0, 4 4, 0 4, 0 0))";
+ actual =
+ (String)
+ first(
+ tableEnv.sqlQuery(
+ "SELECT
ST_GeometryType(ST_ApproximateMedialAxis(ST_GeomFromWKT('"
+ + complexPolygonWkt
+ + "'), 10))"))
+ .getField(0);
+ assertEquals("ST_MultiLineString", actual);
+ }
}
diff --git a/pom.xml b/pom.xml
index 740dd951ff..5da7374507 100644
--- a/pom.xml
+++ b/pom.xml
@@ -376,6 +376,11 @@
<version>4.11.0</version>
<scope>test</scope>
</dependency>
+ <dependency>
+ <groupId>org.datasyslab</groupId>
+ <artifactId>campskeleton</artifactId>
+ <version>0.0.2-20251014</version>
+ </dependency>
</dependencies>
</dependencyManagement>
<repositories>
diff --git a/python/sedona/spark/sql/st_functions.py
b/python/sedona/spark/sql/st_functions.py
index fc10f4b9da..69a8c5ffef 100644
--- a/python/sedona/spark/sql/st_functions.py
+++ b/python/sedona/spark/sql/st_functions.py
@@ -295,6 +295,27 @@ def ST_Azimuth(point_a: ColumnOrName, point_b:
ColumnOrName) -> Column:
return _call_st_function("ST_Azimuth", (point_a, point_b))
+@validate_argument_types
+def ST_ApproximateMedialAxis(
+ geometry: ColumnOrName, max_vertices: Optional[Union[ColumnOrName, int]] =
None
+) -> Column:
+ """Compute an approximate medial axis of an areal geometry by computing
the straight skeleton
+ and filtering to keep only interior edges. The medial axis provides a
centerline representation
+ of polygons that is useful for various spatial analysis tasks.
+
+ :param geometry: Polygon or MultiPolygon geometry column to compute the
medial axis for.
+ :type geometry: ColumnOrName
+ :param max_vertices: Optional maximum number of vertices to keep in the
input geometry before computing.
+ If the geometry has more vertices, it will be simplified. This
improves performance for complex geometries.
+ :type max_vertices: Optional[Union[ColumnOrName, int]]
+ :return: MultiLineString representing the approximate medial axis as a
geometry column.
+ :rtype: Column
+ """
+ if max_vertices is not None:
+ return _call_st_function("ST_ApproximateMedialAxis", (geometry,
max_vertices))
+ return _call_st_function("ST_ApproximateMedialAxis", geometry)
+
+
@validate_argument_types
def barrier(expression: ColumnOrName, *args) -> Column:
"""Prevent filter pushdown and control predicate evaluation order in
complex spatial joins.
@@ -1782,6 +1803,27 @@ def ST_StartPoint(line_string: ColumnOrName) -> Column:
return _call_st_function("ST_StartPoint", line_string)
+@validate_argument_types
+def ST_StraightSkeleton(
+ geometry: ColumnOrName, max_vertices: Optional[Union[ColumnOrName, int]] =
None
+) -> Column:
+ """Compute the straight skeleton of an areal geometry. The straight
skeleton is a method
+ of representing a polygon by a topological skeleton formed by a continuous
shrinking process
+ where each edge moves inward in parallel at a uniform speed.
+
+ :param geometry: Polygon or MultiPolygon geometry column to compute the
straight skeleton for.
+ :type geometry: ColumnOrName
+ :param max_vertices: Optional maximum number of vertices to keep in the
input geometry before computing.
+ If the geometry has more vertices, it will be simplified. This
improves performance for complex geometries.
+ :type max_vertices: Optional[Union[ColumnOrName, int]]
+ :return: MultiLineString representing the straight skeleton as a geometry
column.
+ :rtype: Column
+ """
+ if max_vertices is not None:
+ return _call_st_function("ST_StraightSkeleton", (geometry,
max_vertices))
+ return _call_st_function("ST_StraightSkeleton", geometry)
+
+
@validate_argument_types
def ST_SubDivide(
geometry: ColumnOrName, max_vertices: Union[ColumnOrName, int]
diff --git a/python/tests/sql/test_function.py
b/python/tests/sql/test_function.py
index 3565a9abbc..b7a2f88172 100644
--- a/python/tests/sql/test_function.py
+++ b/python/tests/sql/test_function.py
@@ -2493,3 +2493,39 @@ class TestPredicateJoin(TestBase):
pt_row[0] for pt_row in
point_df.selectExpr("ST_CoordDim(geom)").collect()
]
assert point_row == [3]
+
+ def test_st_straight_skeleton(self):
+ polygon_wkt = "POLYGON ((1 1, 1 3, 4 3, 4 1, 1 1))"
+ actual_df = self.spark.sql(
+ f"SELECT ST_StraightSkeleton(ST_GeomFromText('{polygon_wkt}')) AS
geom"
+ )
+ actual = actual_df.take(1)[0][0]
+ assert actual is not None
+ assert actual.geom_type == "MultiLineString"
+
+ # Test with maxVertices parameter
+ complex_polygon_wkt = "POLYGON ((0 0, 4 0, 4 4, 0 4, 0 0))"
+ actual_df_with_max = self.spark.sql(
+ f"SELECT
ST_StraightSkeleton(ST_GeomFromText('{complex_polygon_wkt}'), 10) AS geom"
+ )
+ actual_with_max = actual_df_with_max.take(1)[0][0]
+ assert actual_with_max is not None
+ assert actual_with_max.geom_type == "MultiLineString"
+
+ def test_st_approximate_medial_axis(self):
+ polygon_wkt = "POLYGON ((1 1, 1 3, 4 3, 4 1, 1 1))"
+ actual_df = self.spark.sql(
+ f"SELECT
ST_ApproximateMedialAxis(ST_GeomFromText('{polygon_wkt}')) AS geom"
+ )
+ actual = actual_df.take(1)[0][0]
+ assert actual is not None
+ assert actual.geom_type == "MultiLineString"
+
+ # Test with maxVertices parameter
+ complex_polygon_wkt = "POLYGON ((0 0, 4 0, 4 4, 0 4, 0 0))"
+ actual_df_with_max = self.spark.sql(
+ f"SELECT
ST_ApproximateMedialAxis(ST_GeomFromText('{complex_polygon_wkt}'), 10) AS geom"
+ )
+ actual_with_max = actual_df_with_max.take(1)[0][0]
+ assert actual_with_max is not None
+ assert actual_with_max.geom_type == "MultiLineString"
diff --git
a/snowflake-tester/src/test/java/org/apache/sedona/snowflake/snowsql/TestFunctions.java
b/snowflake-tester/src/test/java/org/apache/sedona/snowflake/snowsql/TestFunctions.java
index 6e79197f0d..af36809f0b 100644
---
a/snowflake-tester/src/test/java/org/apache/sedona/snowflake/snowsql/TestFunctions.java
+++
b/snowflake-tester/src/test/java/org/apache/sedona/snowflake/snowsql/TestFunctions.java
@@ -1354,4 +1354,32 @@ public class TestFunctions extends TestBase {
"SELECT
sedona.ST_AsText(sedona.ST_Rotate(sedona.ST_GeomFromWKT('LINESTRING (0 0, 1 0,
1 1, 0 0)'), 10, 0, 0))",
"LINESTRING (0 0, -0.8390715290764524 -0.5440211108893698,
-0.2950504181870827 -1.383092639965822, 0 0)");
}
+
+ @Test
+ public void test_ST_StraightSkeleton() {
+ registerUDF("ST_StraightSkeleton", byte[].class);
+ registerUDF("GeometryType", byte[].class);
+ verifySqlSingleRes(
+ "SELECT
sedona.GeometryType(sedona.ST_StraightSkeleton(sedona.ST_GeomFromWKT('POLYGON
((1 1, 1 3, 4 3, 4 1, 1 1))')))",
+ "MULTILINESTRING");
+
+ registerUDF("ST_StraightSkeleton", byte[].class, int.class);
+ verifySqlSingleRes(
+ "SELECT
sedona.GeometryType(sedona.ST_StraightSkeleton(sedona.ST_GeomFromWKT('POLYGON
((0 0, 4 0, 4 4, 0 4, 0 0))'), 10))",
+ "MULTILINESTRING");
+ }
+
+ @Test
+ public void test_ST_ApproximateMedialAxis() {
+ registerUDF("ST_ApproximateMedialAxis", byte[].class);
+ registerUDF("GeometryType", byte[].class);
+ verifySqlSingleRes(
+ "SELECT
sedona.GeometryType(sedona.ST_ApproximateMedialAxis(sedona.ST_GeomFromWKT('POLYGON
((45 0, 55 0, 55 40, 70 40, 70 50, 30 50, 30 40, 45 40, 45 0))')))",
+ "MULTILINESTRING");
+
+ registerUDF("ST_ApproximateMedialAxis", byte[].class, int.class);
+ verifySqlSingleRes(
+ "SELECT
sedona.GeometryType(sedona.ST_ApproximateMedialAxis(sedona.ST_GeomFromWKT('POLYGON
((0 0, 10 0, 10 5, 5 5, 5 10, 0 10, 0 0))'), 100))",
+ "MULTILINESTRING");
+ }
}
diff --git
a/snowflake-tester/src/test/java/org/apache/sedona/snowflake/snowsql/TestFunctionsV2.java
b/snowflake-tester/src/test/java/org/apache/sedona/snowflake/snowsql/TestFunctionsV2.java
index a32149f560..e2efb34843 100644
---
a/snowflake-tester/src/test/java/org/apache/sedona/snowflake/snowsql/TestFunctionsV2.java
+++
b/snowflake-tester/src/test/java/org/apache/sedona/snowflake/snowsql/TestFunctionsV2.java
@@ -1295,4 +1295,32 @@ public class TestFunctionsV2 extends TestBase {
"select
ST_AsText(ST_ReducePrecision(sedona.ST_Rotate(ST_GeometryFromWKT('LINESTRING (0
0, 1 0, 1 1, 0 0)'), 10, 0, 0),2))",
"LINESTRING(0 0,-0.84 -0.54,-0.3 -1.38,0 0)");
}
+
+ @Test
+ public void test_ST_StraightSkeleton() {
+ registerUDFV2("ST_StraightSkeleton", String.class);
+ registerUDFV2("GeometryType", String.class);
+ verifySqlSingleRes(
+ "select
sedona.GeometryType(sedona.ST_StraightSkeleton(ST_GeometryFromWKT('POLYGON ((1
1, 1 3, 4 3, 4 1, 1 1))')))",
+ "MULTILINESTRING");
+
+ registerUDFV2("ST_StraightSkeleton", String.class, int.class);
+ verifySqlSingleRes(
+ "select
sedona.GeometryType(sedona.ST_StraightSkeleton(ST_GeometryFromWKT('POLYGON ((0
0, 4 0, 4 4, 0 4, 0 0))'), 10))",
+ "MULTILINESTRING");
+ }
+
+ @Test
+ public void test_ST_ApproximateMedialAxis() {
+ registerUDFV2("ST_ApproximateMedialAxis", String.class);
+ registerUDFV2("GeometryType", String.class);
+ verifySqlSingleRes(
+ "select
sedona.GeometryType(sedona.ST_ApproximateMedialAxis(ST_GeometryFromWKT('POLYGON
((45 0, 55 0, 55 40, 70 40, 70 50, 30 50, 30 40, 45 40, 45 0))')))",
+ "MULTILINESTRING");
+
+ registerUDFV2("ST_ApproximateMedialAxis", String.class, int.class);
+ verifySqlSingleRes(
+ "select
sedona.GeometryType(sedona.ST_ApproximateMedialAxis(ST_GeometryFromWKT('POLYGON
((0 0, 10 0, 10 5, 5 5, 5 10, 0 10, 0 0))'), 100))",
+ "MULTILINESTRING");
+ }
}
diff --git
a/snowflake/src/main/java/org/apache/sedona/snowflake/snowsql/UDFs.java
b/snowflake/src/main/java/org/apache/sedona/snowflake/snowsql/UDFs.java
index 40e7d9a936..2832c6accd 100644
--- a/snowflake/src/main/java/org/apache/sedona/snowflake/snowsql/UDFs.java
+++ b/snowflake/src/main/java/org/apache/sedona/snowflake/snowsql/UDFs.java
@@ -175,6 +175,18 @@ public class UDFs {
return Functions.azimuth(GeometrySerde.deserialize(left),
GeometrySerde.deserialize(right));
}
+ @UDFAnnotations.ParamMeta(argNames = {"geometry"})
+ public static byte[] ST_ApproximateMedialAxis(byte[] geometry) {
+ return GeometrySerde.serialize(
+ Functions.approximateMedialAxis(GeometrySerde.deserialize(geometry)));
+ }
+
+ @UDFAnnotations.ParamMeta(argNames = {"geometry", "maxVertices"})
+ public static byte[] ST_ApproximateMedialAxis(byte[] geometry, int
maxVertices) {
+ return GeometrySerde.serialize(
+ Functions.approximateMedialAxis(GeometrySerde.deserialize(geometry),
maxVertices));
+ }
+
@UDFAnnotations.ParamMeta(argNames = {"geometry"})
public static byte[] ST_Boundary(byte[] geometry) {
return
GeometrySerde.serialize(Functions.boundary(GeometrySerde.deserialize(geometry)));
@@ -1055,6 +1067,17 @@ public class UDFs {
return
GeometrySerde.serialize(Functions.startPoint(GeometrySerde.deserialize(geometry)));
}
+ @UDFAnnotations.ParamMeta(argNames = {"geometry"})
+ public static byte[] ST_StraightSkeleton(byte[] geometry) {
+ return
GeometrySerde.serialize(Functions.straightSkeleton(GeometrySerde.deserialize(geometry)));
+ }
+
+ @UDFAnnotations.ParamMeta(argNames = {"geometry", "maxVertices"})
+ public static byte[] ST_StraightSkeleton(byte[] geometry, int maxVertices) {
+ return GeometrySerde.serialize(
+ Functions.straightSkeleton(GeometrySerde.deserialize(geometry),
maxVertices));
+ }
+
@UDFAnnotations.ParamMeta(argNames = {"input", "reference", "tolerance"})
public static byte[] ST_Snap(byte[] input, byte[] reference, double
tolerance) {
return GeometrySerde.serialize(
diff --git
a/snowflake/src/main/java/org/apache/sedona/snowflake/snowsql/UDFsV2.java
b/snowflake/src/main/java/org/apache/sedona/snowflake/snowsql/UDFsV2.java
index a56623e3e1..0f636f1f92 100644
--- a/snowflake/src/main/java/org/apache/sedona/snowflake/snowsql/UDFsV2.java
+++ b/snowflake/src/main/java/org/apache/sedona/snowflake/snowsql/UDFsV2.java
@@ -232,6 +232,24 @@ public class UDFsV2 {
return Functions.azimuth(GeometrySerde.deserGeoJson(left),
GeometrySerde.deserGeoJson(right));
}
+ @UDFAnnotations.ParamMeta(
+ argNames = {"geometry"},
+ argTypes = {"Geometry"},
+ returnTypes = "Geometry")
+ public static String ST_ApproximateMedialAxis(String geometry) {
+ return GeometrySerde.serGeoJson(
+ Functions.approximateMedialAxis(GeometrySerde.deserGeoJson(geometry)));
+ }
+
+ @UDFAnnotations.ParamMeta(
+ argNames = {"geometry", "maxVertices"},
+ argTypes = {"Geometry", "int"},
+ returnTypes = "Geometry")
+ public static String ST_ApproximateMedialAxis(String geometry, int
maxVertices) {
+ return GeometrySerde.serGeoJson(
+ Functions.approximateMedialAxis(GeometrySerde.deserGeoJson(geometry),
maxVertices));
+ }
+
@UDFAnnotations.ParamMeta(
argNames = {"geometry"},
argTypes = {"Geometry"},
@@ -1228,6 +1246,24 @@ public class UDFsV2 {
return
GeometrySerde.serGeoJson(Functions.startPoint(GeometrySerde.deserGeoJson(geometry)));
}
+ @UDFAnnotations.ParamMeta(
+ argNames = {"geometry"},
+ argTypes = {"Geometry"},
+ returnTypes = "Geometry")
+ public static String ST_StraightSkeleton(String geometry) {
+ return GeometrySerde.serGeoJson(
+ Functions.straightSkeleton(GeometrySerde.deserGeoJson(geometry)));
+ }
+
+ @UDFAnnotations.ParamMeta(
+ argNames = {"geometry", "maxVertices"},
+ argTypes = {"Geometry", "int"},
+ returnTypes = "Geometry")
+ public static String ST_StraightSkeleton(String geometry, int maxVertices) {
+ return GeometrySerde.serGeoJson(
+ Functions.straightSkeleton(GeometrySerde.deserGeoJson(geometry),
maxVertices));
+ }
+
@UDFAnnotations.ParamMeta(
argNames = {"input", "reference", "tolerance"},
argTypes = {"Geometry", "Geometry", "double"},
diff --git
a/spark/common/src/main/scala/org/apache/sedona/sql/UDF/Catalog.scala
b/spark/common/src/main/scala/org/apache/sedona/sql/UDF/Catalog.scala
index 41b9a2233c..1063bf63e2 100644
--- a/spark/common/src/main/scala/org/apache/sedona/sql/UDF/Catalog.scala
+++ b/spark/common/src/main/scala/org/apache/sedona/sql/UDF/Catalog.scala
@@ -249,6 +249,8 @@ object Catalog extends AbstractCatalog {
function[ST_Rotate](),
function[ST_RotateX](),
function[ST_RotateY](),
+ function[ST_StraightSkeleton](),
+ function[ST_ApproximateMedialAxis](),
function[Barrier](),
// Expression for rasters
function[RS_NormalizedDifference](),
diff --git
a/spark/common/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/Functions.scala
b/spark/common/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/Functions.scala
index 001ac1a787..954fb350ad 100644
---
a/spark/common/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/Functions.scala
+++
b/spark/common/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/Functions.scala
@@ -1849,6 +1849,38 @@ private[apache] case class
ST_InterpolatePoint(inputExpressions: Seq[Expression]
copy(inputExpressions = newChildren)
}
+/**
+ * Computes the straight skeleton of an areal geometry. The straight skeleton
is a method of
+ * representing a polygon by a topological skeleton, formed by a continuous
shrinking process
+ * where each edge moves inward in parallel at a uniform speed.
+ *
+ * @param inputExpressions
+ * Geometry (Polygon or MultiPolygon), optional: maxVertices (Integer) for
vertex limit
+ */
+private[apache] case class ST_StraightSkeleton(inputExpressions:
Seq[Expression])
+ extends InferredExpression(
+ inferrableFunction2(Functions.straightSkeleton),
+ inferrableFunction1(Functions.straightSkeleton)) {
+ protected def withNewChildrenInternal(newChildren: IndexedSeq[Expression]) =
+ copy(inputExpressions = newChildren)
+}
+
+/**
+ * Computes an approximate medial axis of an areal geometry by computing the
straight skeleton and
+ * filtering to keep only interior edges. Edges where both endpoints are
interior to the polygon
+ * (not on the boundary) are kept, producing a cleaner skeleton.
+ *
+ * @param inputExpressions
+ * Geometry (Polygon or MultiPolygon), optional: maxVertices (Integer) for
vertex limit
+ */
+private[apache] case class ST_ApproximateMedialAxis(inputExpressions:
Seq[Expression])
+ extends InferredExpression(
+ inferrableFunction2(Functions.approximateMedialAxis),
+ inferrableFunction1(Functions.approximateMedialAxis)) {
+ protected def withNewChildrenInternal(newChildren: IndexedSeq[Expression]) =
+ copy(inputExpressions = newChildren)
+}
+
private[apache] case class ExpandAddress(address: Expression)
extends UnaryExpression
with ImplicitCastInputTypes
diff --git
a/spark/common/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/st_functions.scala
b/spark/common/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/st_functions.scala
index ccfc6f83b4..6fd00a6b63 100644
---
a/spark/common/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/st_functions.scala
+++
b/spark/common/src/main/scala/org/apache/spark/sql/sedona_sql/expressions/st_functions.scala
@@ -108,6 +108,15 @@ object st_functions {
def ST_Azimuth(pointA: String, pointB: String): Column =
wrapExpression[ST_Azimuth](pointA, pointB)
+ def ST_ApproximateMedialAxis(geometry: Column): Column =
+ wrapExpression[ST_ApproximateMedialAxis](geometry)
+ def ST_ApproximateMedialAxis(geometry: String): Column =
+ wrapExpression[ST_ApproximateMedialAxis](geometry)
+ def ST_ApproximateMedialAxis(geometry: Column, maxVertices: Column): Column =
+ wrapExpression[ST_ApproximateMedialAxis](geometry, maxVertices)
+ def ST_ApproximateMedialAxis(geometry: String, maxVertices: Int): Column =
+ wrapExpression[ST_ApproximateMedialAxis](geometry, maxVertices)
+
def ST_Boundary(geometry: Column): Column =
wrapExpression[ST_Boundary](geometry)
def ST_Boundary(geometry: String): Column =
wrapExpression[ST_Boundary](geometry)
@@ -625,6 +634,15 @@ object st_functions {
def ST_StartPoint(lineString: Column): Column =
wrapExpression[ST_StartPoint](lineString)
def ST_StartPoint(lineString: String): Column =
wrapExpression[ST_StartPoint](lineString)
+ def ST_StraightSkeleton(geometry: Column): Column =
+ wrapExpression[ST_StraightSkeleton](geometry)
+ def ST_StraightSkeleton(geometry: String): Column =
+ wrapExpression[ST_StraightSkeleton](geometry)
+ def ST_StraightSkeleton(geometry: Column, maxVertices: Column): Column =
+ wrapExpression[ST_StraightSkeleton](geometry, maxVertices)
+ def ST_StraightSkeleton(geometry: String, maxVertices: Int): Column =
+ wrapExpression[ST_StraightSkeleton](geometry, maxVertices)
+
def ST_Snap(input: Column, reference: Column, tolerance: Column): Column =
wrapExpression[ST_Snap](input, reference, tolerance)
def ST_Snap(input: String, reference: String, tolerance: Double): Column =
diff --git
a/spark/common/src/test/scala/org/apache/sedona/sql/PreserveSRIDSuite.scala
b/spark/common/src/test/scala/org/apache/sedona/sql/PreserveSRIDSuite.scala
index 5d8c36a342..69b1641cc4 100644
--- a/spark/common/src/test/scala/org/apache/sedona/sql/PreserveSRIDSuite.scala
+++ b/spark/common/src/test/scala/org/apache/sedona/sql/PreserveSRIDSuite.scala
@@ -120,7 +120,9 @@ class PreserveSRIDSuite extends TestBaseScala with
TableDrivenPropertyChecks {
("ST_Rotate(geom1, 10)", 1000),
("ST_RotateX(geom1, 10)", 1000),
("ST_Collect(geom1, geom2, geom3)", 1000),
- ("ST_GeneratePoints(geom1, 3)", 1000))
+ ("ST_GeneratePoints(geom1, 3)", 1000),
+ ("ST_StraightSkeleton(geom1)", 1000),
+ ("ST_ApproximateMedialAxis(geom1)", 1000))
forAll(testCases) { case (expression: String, srid: Int) =>
it(s"$expression") {
diff --git
a/spark/common/src/test/scala/org/apache/sedona/sql/dataFrameAPITestScala.scala
b/spark/common/src/test/scala/org/apache/sedona/sql/dataFrameAPITestScala.scala
index ea4cd18c13..15901c67a1 100644
---
a/spark/common/src/test/scala/org/apache/sedona/sql/dataFrameAPITestScala.scala
+++
b/spark/common/src/test/scala/org/apache/sedona/sql/dataFrameAPITestScala.scala
@@ -2535,5 +2535,46 @@ class dataFrameAPITestScala extends TestBaseScala {
assert(actual == expected, s"Expected $expected but got $actual")
}
}
+
+ it("Passed ST_StraightSkeleton") {
+ val baseDf = sparkSession.sql(
+ "SELECT ST_GeomFromWKT('POLYGON ((0 0, 1 0, 0.5 0.5, 1 1, 0 1, 0 0))')
as poly")
+ val result =
baseDf.select(ST_StraightSkeleton(col("poly"))).first().get(0)
+ assert(result != null)
+ val skeleton = result.asInstanceOf[Geometry]
+ assert(skeleton.getGeometryType == "MultiLineString")
+ assert(skeleton.getNumGeometries > 0)
+ }
+
+ it("Passed ST_StraightSkeleton with maxVertices") {
+ val baseDf = sparkSession.sql(
+ "SELECT ST_GeomFromWKT('POLYGON ((0 0, 1 0, 0.5 0.5, 1 1, 0 1, 0 0))')
as poly")
+ val result = baseDf.select(ST_StraightSkeleton(col("poly"),
lit(100))).first().get(0)
+ assert(result != null)
+ val skeleton = result.asInstanceOf[Geometry]
+ assert(skeleton.getGeometryType == "MultiLineString")
+ }
+
+ it("Passed ST_ApproximateMedialAxis") {
+ val baseDf =
+ sparkSession.sql(
+ "SELECT ST_GeomFromWKT('POLYGON ((0 0, 100 0, 100 40, 40 40, 40 100,
0 100, 0 0))') as poly")
+ val result =
baseDf.select(ST_ApproximateMedialAxis(col("poly"))).first().get(0)
+ assert(result != null)
+ val medialAxis = result.asInstanceOf[Geometry]
+ assert(medialAxis.getGeometryType == "MultiLineString")
+ // L-shaped polygon should have interior edges
+ assert(medialAxis.getNumGeometries > 0)
+ }
+
+ it("Passed ST_ApproximateMedialAxis with maxVertices") {
+ val baseDf =
+ sparkSession.sql(
+ "SELECT ST_GeomFromWKT('POLYGON ((0 0, 100 0, 100 40, 40 40, 40 100,
0 100, 0 0))') as poly")
+ val result = baseDf.select(ST_ApproximateMedialAxis(col("poly"),
lit(100))).first().get(0)
+ assert(result != null)
+ val medialAxis = result.asInstanceOf[Geometry]
+ assert(medialAxis.getGeometryType == "MultiLineString")
+ }
}
}
diff --git
a/spark/common/src/test/scala/org/apache/sedona/sql/functionTestScala.scala
b/spark/common/src/test/scala/org/apache/sedona/sql/functionTestScala.scala
index 75a6911dee..706612304c 100644
--- a/spark/common/src/test/scala/org/apache/sedona/sql/functionTestScala.scala
+++ b/spark/common/src/test/scala/org/apache/sedona/sql/functionTestScala.scala
@@ -924,17 +924,6 @@ class functionTestScala
assert(df.first().get(0).asInstanceOf[Polygon].getSRID == 3021)
}
-// it("Passed ST_AsEWKB") {
-// var df = sparkSession.sql("SELECT ST_SetSrid(ST_GeomFromWKT('POINT (1
1)'), 3021) as point")
-// df.createOrReplaceTempView("table")
-// df = sparkSession.sql("SELECT ST_AsEWKB(point) from table")
-// val s = "0101000020cd0b0000000000000000f03f000000000000f03f"
-//
assert(Hex.encodeHexString(df.first().get(0).asInstanceOf[Array[Byte]]) == s)
-// df = sparkSession.sql("SELECT ST_AsEWKB(ST_GeogFromWKT('POINT (1
1)'))")
-// val wkb = df.first().get(0).asInstanceOf[Array[Byte]]
-// assert(Hex.encodeHexString(wkb) ==
"0101000000000000000000f03f000000000000f03f")
-// }
-
it("Passed ST_AsHEXEWKB") {
val baseDf = sparkSession.sql("SELECT ST_GeomFromWKT('POINT(1 2)') as
point")
var actual = baseDf.selectExpr("ST_AsHEXEWKB(point)").first().get(0)
@@ -953,13 +942,6 @@ class functionTestScala
assert(Hex.encodeHexString(df.first().get(0).asInstanceOf[Array[Byte]])
== s)
}
-// it("Passed ST_AsEWKT") {
-// val wkt = "POLYGON ((30 10, 40 40, 20 40, 10 20, 30 10))"
-// val df = sparkSession.sql(s"SELECT ST_AsEWKT(ST_GeogFromWKT('$wkt'))")
-// val row = df.first()
-// assert(row.getString(0) == wkt)
-// }
-
it("Passed ST_Simplify") {
val baseDf = sparkSession.sql("SELECT ST_Buffer(ST_GeomFromWKT('POINT (0
2)'), 10) AS geom")
val actualPoints = baseDf.selectExpr("ST_NPoints(ST_Simplify(geom,
1))").first().get(0)
@@ -2779,8 +2761,6 @@ class functionTestScala
assert(functionDf.first().get(0) == null)
functionDf = sparkSession.sql("select ST_AsEWKT(ST_GeomFromWKT(null))")
assert(functionDf.first().get(0) == null)
-// functionDf = sparkSession.sql("select ST_AsEWKT(ST_GeogFromWKT(null))")
-// assert(functionDf.first().get(0) == null)
functionDf = sparkSession.sql("select ST_Force_2D(null)")
assert(functionDf.first().get(0) == null)
functionDf = sparkSession.sql("select ST_BuildArea(null)")
@@ -3791,4 +3771,363 @@ class functionTestScala
}
exception.getMessage should include("ST_Subdivide needs 5 or more max
vertices")
}
+
+ it("Passed ST_StraightSkeleton") {
+ val polygonWktDf = sparkSession.read
+ .format("csv")
+ .option("delimiter", "\t")
+ .option("header", "false")
+ .load(mixedWktGeometryInputLocation)
+ polygonWktDf.createOrReplaceTempView("polygontable")
+ val polygonDf =
+ sparkSession.sql("select ST_GeomFromWKT(polygontable._c0) as countyshape
from polygontable")
+ polygonDf.createOrReplaceTempView("polygondf")
+ val functionDf =
+ sparkSession.sql("select ST_StraightSkeleton(polygondf.countyshape) from
polygondf")
+ assert(functionDf.count() > 0)
+ }
+
+ it("Passed ST_StraightSkeleton with simple polygon") {
+ val squareDf = sparkSession.sql("""
+ |SELECT ST_StraightSkeleton(ST_GeomFromWKT('POLYGON ((0 0, 10 0, 10
10, 0 10, 0 0))')) as result
+ """.stripMargin)
+ val result = squareDf.collect()
+ assert(result.length == 1)
+ val medialAxis = result(0).get(0)
+ assert(medialAxis != null)
+ }
+
+ it("Passed ST_StraightSkeleton returns MultiLineString") {
+ val rectangleDf = sparkSession.sql("""
+ |SELECT ST_GeometryType(ST_StraightSkeleton(ST_GeomFromWKT('POLYGON
((0 0, 20 0, 20 5, 0 5, 0 0))'))) as geomType
+ """.stripMargin)
+ val result = rectangleDf.collect()
+ assert(result.length == 1)
+ assert(result(0).getString(0) == "ST_MultiLineString")
+ }
+
+ it("Passed ST_StraightSkeleton with SRID preservation") {
+ val geomWithSridDf = sparkSession.sql("""
+ |SELECT ST_SRID(ST_StraightSkeleton(ST_SetSRID(ST_GeomFromWKT('POLYGON
((0 0, 10 0, 10 10, 0 10, 0 0))'), 4326))) as srid
+ """.stripMargin)
+ val result = geomWithSridDf.collect()
+ assert(result.length == 1)
+ assert(result(0).getInt(0) == 4326)
+ }
+
+ it("Passed ST_StraightSkeleton with L-shaped polygon") {
+ val lShapeDf = sparkSession.sql("""
+ |SELECT ST_StraightSkeleton(ST_GeomFromWKT('POLYGON ((0 0, 10 0, 10 5,
5 5, 5 10, 0 10, 0 0))')) as result
+ """.stripMargin)
+ val result = lShapeDf.collect()
+ assert(result.length == 1)
+ val medialAxis = result(0).get(0)
+ assert(medialAxis != null)
+ }
+
+ it("Passed ST_StraightSkeleton with MultiPolygon") {
+ val multiPolygonDf = sparkSession.sql("""
+ |SELECT ST_StraightSkeleton(
+ | ST_GeomFromWKT('MULTIPOLYGON (((0 0, 5 0, 5 5, 0 5, 0 0)), ((10 10,
15 10, 15 15, 10 15, 10 10)))')
+ |) as result
+ """.stripMargin)
+ val result = multiPolygonDf.collect()
+ assert(result.length == 1)
+ val medialAxis = result(0).get(0)
+ assert(medialAxis != null)
+ }
+
+ it("should handle ST_StraightSkeleton with null geometry") {
+ val nullGeomDf = sparkSession.sql("""
+ |SELECT ST_StraightSkeleton(null) as result
+ """.stripMargin)
+ val result = nullGeomDf.collect()
+ assert(result.length == 1)
+ assert(result(0).get(0) == null)
+ }
+
+ it("should raise an error when using ST_StraightSkeleton with non-areal
geometry") {
+ val invalidDf = sparkSession.sql("""
+ |SELECT ST_StraightSkeleton(ST_GeomFromWKT('LINESTRING (0 0, 10 10)'))
as result
+ """.stripMargin)
+
+ val exception = intercept[Exception] {
+ invalidDf.collect()
+ }
+ exception.getMessage should include(
+ "ST_StraightSkeleton only supports Polygon and MultiPolygon geometries")
+ }
+
+ it("Manual test: ST_StraightSkeleton with L-shaped polygon for PostGIS
comparison") {
+ val testDf = sparkSession.sql("""
+ |SELECT
+ | ST_AsText(ST_StraightSkeleton(
+ | ST_GeomFromWKT('POLYGON ((190 190, 10 190, 10 10, 190 10, 190 20,
160 30, 60 30, 60 130, 190 140, 190 190))')
+ | )) as medial_axis_wkt,
+ | ST_NumGeometries(ST_StraightSkeleton(
+ | ST_GeomFromWKT('POLYGON ((190 190, 10 190, 10 10, 190 10, 190 20,
160 30, 60 30, 60 130, 190 140, 190 190))')
+ | )) as num_segments,
+ | ST_Length(ST_StraightSkeleton(
+ | ST_GeomFromWKT('POLYGON ((190 190, 10 190, 10 10, 190 10, 190 20,
160 30, 60 30, 60 130, 190 140, 190 190))')
+ | )) as total_length,
+ | ST_GeometryType(ST_StraightSkeleton(
+ | ST_GeomFromWKT('POLYGON ((190 190, 10 190, 10 10, 190 10, 190 20,
160 30, 60 30, 60 130, 190 140, 190 190))')
+ | )) as geometry_type
+ """.stripMargin)
+
+ val result = testDf.collect()
+ assert(result.length == 1)
+
+ // Basic assertions
+ assert(result(0).getInt(1) > 0, "Should have at least one segment")
+ assert(result(0).getDouble(2) > 0, "Should have positive length")
+ assert(result(0).getString(3) == "ST_MultiLineString")
+ }
+
+ it("Passed ST_ApproximateMedialAxis") {
+ val testDf = sparkSession.sql(
+ "SELECT ST_ApproximateMedialAxis(ST_GeomFromWKT('POLYGON ((0 0, 10 0, 10
10, 0 10, 0 0))')) as result")
+ val result = testDf.collect()
+ assert(result.length == 1)
+ assert(!result(0).isNullAt(0))
+ }
+
+ it("Passed ST_ApproximateMedialAxis with simple polygon") {
+ val testDf = sparkSession.sql("""
+ |SELECT ST_ApproximateMedialAxis(ST_GeomFromWKT('POLYGON ((0 0, 10 0,
10 10, 0 10, 0 0))')) as result
+ """.stripMargin)
+ val result = testDf.collect()
+ assert(result.length == 1)
+ assert(!result(0).isNullAt(0))
+ }
+
+ it("Passed ST_ApproximateMedialAxis returns MultiLineString") {
+ val testDf = sparkSession.sql("""
+ |SELECT
ST_GeometryType(ST_ApproximateMedialAxis(ST_GeomFromWKT('POLYGON ((0 0, 20 0,
20 5, 0 5, 0 0))'))) as geomType
+ """.stripMargin)
+ val result = testDf.collect()
+ assert(result.length == 1)
+ assert(result(0).getString(0) == "ST_MultiLineString")
+ }
+
+ it("Passed ST_ApproximateMedialAxis with SRID preservation") {
+ val testDf = sparkSession.sql("""
+ |SELECT
ST_SRID(ST_ApproximateMedialAxis(ST_SetSRID(ST_GeomFromWKT('POLYGON ((0 0, 10
0, 10 10, 0 10, 0 0))'), 4326))) as srid
+ """.stripMargin)
+ val result = testDf.collect()
+ assert(result.length == 1)
+ assert(result(0).getInt(0) == 4326)
+ }
+
+ it(
+ "Passed ST_ApproximateMedialAxis produces fewer segments than
ST_StraightSkeleton for T-shape") {
+ val testDf = sparkSession.sql("""
+ |SELECT
+ | ST_NumGeometries(ST_StraightSkeleton(
+ | ST_GeomFromWKT('POLYGON ((45 0, 55 0, 55 40, 70 40, 70 50, 30 50,
30 40, 45 40, 45 0))')
+ | )) as skeleton_segments,
+ | ST_NumGeometries(ST_ApproximateMedialAxis(
+ | ST_GeomFromWKT('POLYGON ((45 0, 55 0, 55 40, 70 40, 70 50, 30 50,
30 40, 45 40, 45 0))')
+ | )) as pruned_segments
+ """.stripMargin)
+ val result = testDf.collect()
+ assert(result.length == 1)
+ val skeletonSegments = result(0).getInt(0)
+ val prunedSegments = result(0).getInt(1)
+ assert(
+ prunedSegments <= skeletonSegments,
+ s"Pruned skeleton ($prunedSegments) should have <= segments than raw
skeleton ($skeletonSegments)")
+ }
+
+ it("Passed ST_ApproximateMedialAxis with MultiPolygon") {
+ val testDf = sparkSession.sql("""
+ |SELECT ST_ApproximateMedialAxis(
+ | ST_GeomFromWKT('MULTIPOLYGON (((0 0, 10 0, 10 10, 0 10, 0 0)), ((20
20, 30 20, 30 30, 20 30, 20 20)))')
+ |) as result
+ """.stripMargin)
+ val result = testDf.collect()
+ assert(result.length == 1)
+ assert(!result(0).isNullAt(0))
+ }
+
+ it("should handle ST_ApproximateMedialAxis with null geometry") {
+ val testDf = sparkSession.sql("""
+ |SELECT ST_ApproximateMedialAxis(null) as result
+ """.stripMargin)
+ val result = testDf.collect()
+ assert(result.length == 1)
+ assert(result(0).isNullAt(0))
+ }
+
+ it("should raise an error when using ST_ApproximateMedialAxis with non-areal
geometry") {
+ val exception = intercept[Exception] {
+ sparkSession
+ .sql("""
+ |SELECT ST_ApproximateMedialAxis(ST_GeomFromWKT('LINESTRING (0 0, 10
10)')) as result
+ """.stripMargin)
+ .collect()
+ }
+ assert(
+ exception.getMessage.contains(
+ "ST_ApproximateMedialAxis only supports Polygon and MultiPolygon
geometries"))
+ }
+
+ it("Passed ST_ApproximateMedialAxis with T-Junction polygon") {
+ val testDf = sparkSession.sql("""
+ |SELECT
+ | ST_AsText(ST_ApproximateMedialAxis(
+ | ST_GeomFromWKT('POLYGON ((45 0, 55 0,
55 40, 70 40, 70 50, 30 50, 30 40, 45 40, 45 0))')
+ | )) as result,
+ |
ST_NumGeometries(ST_ApproximateMedialAxis(
+ | ST_GeomFromWKT('POLYGON ((45 0, 55 0,
55 40, 70 40, 70 50, 30 50, 30 40, 45 40, 45 0))')
+ | )) as num_segments,
+ |
ST_GeometryType(ST_ApproximateMedialAxis(
+ | ST_GeomFromWKT('POLYGON ((45 0, 55 0,
55 40, 70 40, 70 50, 30 50, 30 40, 45 40, 45 0))')
+ | )) as geom_type
+ """.stripMargin)
+ val result = testDf.collect()
+ assert(result.length == 1)
+ assert(!result(0).isNullAt(0), "Result should not be null")
+ assert(result(0).getString(2) == "ST_MultiLineString", "Result should be
MultiLineString")
+ val numSegments = result(0).getInt(1)
+ assert(numSegments > 0, "Should have at least one segment")
+ val wkt = result(0).getString(0)
+ assert(wkt.startsWith("MULTILINESTRING"), "WKT should start with
MULTILINESTRING")
+ }
+
+ it("Test elongated rectangle at normal scale") {
+ // Test hypothesis: is the issue the tiny size or the aspect ratio?
+ // Testing various aspect ratios at normal scale
+ val elongated17Wkt = "POLYGON ((0 0, 10 0, 10 170, 0 170, 0 0))" // 17:1
like Maryland
+ val elongated1000Wkt = "POLYGON ((0 0, 10 0, 10 10000, 0 10000, 0 0))" //
1000:1 extreme
+ val squareWkt = "POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))" // 1:1
+
+ val testDf = sparkSession.sql(s"""
+ |SELECT
+ | 'Elongated 17:1' as name,
+ |
ST_NumGeometries(ST_StraightSkeleton(ST_GeomFromWKT('$elongated17Wkt'))) as
skeleton_segments
+ |UNION ALL
+ |SELECT
+ | 'Elongated 1000:1' as name,
+ |
ST_NumGeometries(ST_StraightSkeleton(ST_GeomFromWKT('$elongated1000Wkt'))) as
skeleton_segments
+ |UNION ALL
+ |SELECT
+ | 'Square 1:1' as name,
+ | ST_NumGeometries(ST_StraightSkeleton(ST_GeomFromWKT('$squareWkt')))
as skeleton_segments
+ """.stripMargin)
+
+ val results = testDf.collect()
+ val elongated17Segs = results(0).getInt(1)
+ val elongated1000Segs = results(1).getInt(1)
+ val squareSegs = results(2).getInt(1)
+
+ assert(squareSegs > 0, s"Square should work, got $squareSegs segments")
+ assert(elongated17Segs > 0, s"Elongated 17:1 should work, got
$elongated17Segs segments")
+ }
+
+ it("Test ST_ApproximateMedialAxis with simple and holey rectangles") {
+ // Test with a simple rectangle
+ val simpleRect = sparkSession.sql("""
+ SELECT ST_ApproximateMedialAxis(
+ ST_GeomFromText('POLYGON((0 0, 10 0, 10 10, 0 10, 0 0))')
+ ) as medial_axis
+ """)
+
+ simpleRect.selectExpr("ST_AsText(medial_axis)").show(false)
+
+ // Test with a rectangle with hole
+ val rectWithHole = sparkSession.sql("""
+ SELECT ST_ApproximateMedialAxis(
+ ST_GeomFromText('POLYGON((0 0, 100 0, 100 100, 0 100, 0 0), (20 20, 80
20, 80 80, 20 80, 20 20))')
+ ) as medial_axis
+ """)
+
+ rectWithHole
+ .selectExpr("ST_AsText(medial_axis)", "ST_NumGeometries(medial_axis) as
num_edges")
+ .show(false)
+
+ // Verify the function returns a geometry
+ val result =
simpleRect.first().getAs[org.locationtech.jts.geom.Geometry](0)
+ assert(result != null, "ST_ApproximateMedialAxis should return a non-null
geometry")
+ }
+
+ it("Test ST_StraightSkeleton with polygons with multiple holes") {
+ // Test with a square containing two rectangular holes
+ val squareWithTwoHoles = sparkSession.sql("""
+ SELECT ST_StraightSkeleton(
+ ST_GeomFromText('POLYGON((0 0, 100 0, 100 100, 0 100, 0 0), (20 20, 40
20, 40 40, 20 40, 20 20), (60 60, 80 60, 80 80, 60 80, 60 60))')
+ ) as skeleton
+ """)
+
+ squareWithTwoHoles.selectExpr("ST_AsText(skeleton)").show(false)
+
+ // Verify the skeleton is generated
+ val skeleton =
squareWithTwoHoles.first().getAs[org.locationtech.jts.geom.Geometry](0)
+ assert(
+ skeleton != null,
+ "ST_StraightSkeleton should return a non-null geometry for polygon with
holes")
+ assert(
+ !skeleton.isEmpty,
+ "ST_StraightSkeleton should not return empty geometry for polygon with
holes")
+ assert(
+ skeleton.getGeometryType == "MultiLineString",
+ "ST_StraightSkeleton should return MultiLineString")
+
+ val numEdges = skeleton.getNumGeometries
+ assert(numEdges > 0, "Skeleton should contain at least one edge")
+
+ // Test with vertex simplification
+ val squareWithTwoHolesSimplified = sparkSession.sql("""
+ SELECT ST_StraightSkeleton(
+ ST_GeomFromText('POLYGON((0 0, 100 0, 100 100, 0 100, 0 0), (20 20, 40
20, 40 40, 20 40, 20 20), (60 60, 80 60, 80 80, 60 80, 60 60))'),
+ 10
+ ) as skeleton
+ """)
+
+ squareWithTwoHolesSimplified.selectExpr("ST_AsText(skeleton)").show(false)
+
+ val simplifiedSkeleton =
+
squareWithTwoHolesSimplified.first().getAs[org.locationtech.jts.geom.Geometry](0)
+ assert(simplifiedSkeleton != null, "Simplified skeleton should not be
null")
+ assert(!simplifiedSkeleton.isEmpty, "Simplified skeleton should not be
empty")
+ }
+
+ it("Test ST_ApproximateMedialAxis with polygons with multiple holes") {
+ // Test with a square containing two rectangular holes
+ val squareWithTwoHoles = sparkSession.sql("""
+ SELECT ST_ApproximateMedialAxis(
+ ST_GeomFromText('POLYGON((0 0, 100 0, 100 100, 0 100, 0 0), (20 20, 40
20, 40 40, 20 40, 20 20), (60 60, 80 60, 80 80, 60 80, 60 60))')
+ ) as medial_axis
+ """)
+
+ squareWithTwoHoles
+ .selectExpr("ST_AsText(medial_axis)", "ST_NumGeometries(medial_axis) as
num_edges")
+ .show(false)
+
+ // Verify the medial axis is generated
+ val medialAxis =
squareWithTwoHoles.first().getAs[org.locationtech.jts.geom.Geometry](0)
+ assert(
+ medialAxis != null,
+ "ST_ApproximateMedialAxis should return a non-null geometry for polygon
with holes")
+ assert(
+ medialAxis.getGeometryType == "MultiLineString",
+ "ST_ApproximateMedialAxis should return MultiLineString")
+
+ // The medial axis should have fewer edges than the full skeleton since it
filters out boundary edges
+ val numEdges = medialAxis.getNumGeometries
+
+ // Test with vertex simplification
+ val squareWithTwoHolesSimplified = sparkSession.sql("""
+ SELECT ST_ApproximateMedialAxis(
+ ST_GeomFromText('POLYGON((0 0, 100 0, 100 100, 0 100, 0 0), (20 20, 40
20, 40 40, 20 40, 20 20), (60 60, 80 60, 80 80, 60 80, 60 60))'),
+ 10
+ ) as medial_axis
+ """)
+
+
squareWithTwoHolesSimplified.selectExpr("ST_AsText(medial_axis)").show(false)
+
+ val simplifiedMedialAxis =
+
squareWithTwoHolesSimplified.first().getAs[org.locationtech.jts.geom.Geometry](0)
+ assert(simplifiedMedialAxis != null, "Simplified medial axis should not be
null")
+ }
}
