You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@sedona.apache.org by "chay0112 (via GitHub)" <gi...@apache.org> on 2025/11/25 21:36:46 UTC
[PR] [GH-2527] Implement concave_hull [sedona]
chay0112 opened a new pull request, #2529:
URL: https://github.com/apache/sedona/pull/2529
## Did you read the Contributor Guide?
- Yes, I have read the [Contributor Rules](https://sedona.apache.org/latest/community/rule/) and [Contributor Development Guide](https://sedona.apache.org/latest/community/develop/)
## Is this PR related to a ticket?
- Yes, and the PR name follows the format `[GH-XXX] my subject`. Closes #2527
## What changes were proposed in this PR?
- Implement concave_hull functionality
## How was this patch tested?
- Included unit and parity tests
## Did this PR include necessary documentation updates?
- Yes, I have updated the documentation.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [GH-2527] Implement concave_hull [sedona]
Posted by "petern48 (via GitHub)" <gi...@apache.org>.
petern48 commented on PR #2529:
URL: https://github.com/apache/sedona/pull/2529#issuecomment-3590761875
> Would it be acceptable to change our comparison from equals_exact to equals for polygons, so that we check geometric equality rather than strict vertex order? Or is there a recommended workaround for this situation, or something I might be missing in our test setup?
The issue is not whether we're using `equals_exact()` or `equals()`. If you give it a try, you'll see that the comparison fails either way. Despite the name, equals_exact is actually more lenient, since it supports a tolerance parameter.
<details>
<summary>Script to test using equals instead</summary>
```
import shapely
geom1 = shapely.wkt.loads("POLYGON ((1 4, 3 4, 4 4, 3 1, 4 0, 0 0, 1 1, 0 4, 1 4))")
geom2 = shapely.wkt.loads("POLYGON ((1 4, 3 4, 4 4, 4 0, 3 1, 0 0, 1 1, 0 4, 1 4))")
print(geom1.equals(geom2)) # False
print(geom1.equals_exact(geom2, 0.000001)) # False
```
</details>
<details>
<summary>Images to visualize the different results </summary>
<img width="639" height="182" alt="image" src="https://github.com/user-attachments/assets/061a5266-56f4-4a8f-a247-c9ed9d9ba683" />
<img width="654" height="193" alt="image" src="https://github.com/user-attachments/assets/e3591281-e3d3-48e2-8ad8-1c7ef1e52cde" />
</details>
As you can see above, these geometries actually are different. Why this is happening, I'm not sure. It could either be a bug in Sedona's function or a difference in algorithms or edge case behaviors. If it's a significant bug, we may want to hold off. If it's a reasonable difference in behavior that's still correct, we can add a note in the docs and merge this anyway. Either way, we need to understand what's happening before merging. I encourage you to investigate, though you're not obligated to, of course, and can continue with something else instead.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [GH-2527] Implement concave_hull [sedona]
Posted by "Copilot (via GitHub)" <gi...@apache.org>.
Copilot commented on code in PR #2529:
URL: https://github.com/apache/sedona/pull/2529#discussion_r3612236279
##########
python/sedona/spark/geopandas/base.py:
##########
@@ -712,19 +712,25 @@ def centroid(self):
return _delegate_to_geometry_column("centroid", self)
def concave_hull(self, ratio=0.0, allow_holes=False):
- """Return the concave hull of each geometry.
+ """Return a ``GeoSeries`` of geometries representing the concave hull
+ of vertices of each geometry.
- The concave hull of a geometry is a possibly concave geometry that
- encloses the input geometry.
+ A concave hull is a concave or convex `Polygon` containing all the
+ vertices in each geometry. For two vertices, the hull collapses to a
+ `LineString`; for one vertex, it collapses to a `Point`.
+
+ The hull is constructed by removing border triangles of the Delaunay
+ triangulation while their size is larger than the maximum edge length
+ ratio. The ratio is a fraction of the difference between the longest
+ and shortest edges in the triangulation.
Review Comment:
The docstring describes `ratio` as “a fraction of the difference between the longest and shortest edges in the triangulation”, but Sedona passes `ratio` directly to JTS `ConcaveHull.setMaximumEdgeLengthRatio(...)` (see common/src/main/java/org/apache/sedona/common/Functions.java). This wording is likely incorrect/misleading for users; consider aligning it with Sedona’s existing ST_ConcaveHull docs (pctConvex/max edge length ratio in [0, 1]).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [GH-2527] Implement concave_hull [sedona]
Posted by "petern48 (via GitHub)" <gi...@apache.org>.
petern48 commented on code in PR #2529:
URL: https://github.com/apache/sedona/pull/2529#discussion_r2572689417
##########
python/tests/geopandas/test_match_geopandas_series.py:
##########
@@ -722,8 +722,35 @@ def test_centroid(self):
gpd_result = gpd.GeoSeries(geom).centroid
self.check_sgpd_equals_gpd(sgpd_result, gpd_result)
+ @pytest.mark.skipif(
+ parse_version(gpd.__version__) < parse_version("0.14.0"),
+ reason="geopandas concave_hull requires version 0.14.0 or higher",
+ )
def test_concave_hull(self):
- pass
+ for geom in self.geoms:
+ sgpd_result = GeoSeries(geom).concave_hull()
+ gpd_result = gpd.GeoSeries(geom).concave_hull()
+ self.check_sgpd_equals_gpd(sgpd_result, gpd_result)
+
+ # Test slightly complex geometry for different ratio and allow_holes settings
+ geom = [
+ Polygon(
+ [(0, 0), (0, 4), (1, 4), (1, 1), (3, 1), (3, 4), (4, 4), (4, 0), (0, 0)]
+ )
+ ]
+ for ratio, allow_holes in [(0.5, True), (1.0, True)]:
+ sgpd_result = GeoSeries(geom).concave_hull(
+ ratio=ratio, allow_holes=allow_holes
+ )
+ gpd_result = gpd.GeoSeries(geom).concave_hull(
+ ratio=ratio, allow_holes=allow_holes
+ )
+ self.check_sgpd_equals_gpd(sgpd_result, gpd_result)
+
+ mixed = [self.points[1], self.linestrings[1], self.polygons[1], None]
+ sgpd_result = GeoSeries(mixed).concave_hull()
+ gpd_result = gpd.GeoSeries(mixed).concave_hull()
+ self.check_sgpd_equals_gpd(sgpd_result, gpd_result)
Review Comment:
```suggestion
```
I don't think this test is necessary. We're already testing all of those cases separately in the `for geom in self.geoms` above. The function is executed on each geometry separately, so whether they're mixed together or not doesn't matter.
##########
python/tests/geopandas/test_match_geopandas_series.py:
##########
@@ -722,8 +722,35 @@ def test_centroid(self):
gpd_result = gpd.GeoSeries(geom).centroid
self.check_sgpd_equals_gpd(sgpd_result, gpd_result)
+ @pytest.mark.skipif(
+ parse_version(gpd.__version__) < parse_version("0.14.0"),
+ reason="geopandas concave_hull requires version 0.14.0 or higher",
+ )
def test_concave_hull(self):
- pass
+ for geom in self.geoms:
+ sgpd_result = GeoSeries(geom).concave_hull()
+ gpd_result = gpd.GeoSeries(geom).concave_hull()
+ self.check_sgpd_equals_gpd(sgpd_result, gpd_result)
Review Comment:
We should test multiple ratio values here, not just the default of 0.0. We could do something like: Do one third of the iterations w/ 0.0, then the next third w/ 0.5, and the last third w/ 1.0. (Note the range of valid values for this argument is [0, 1].
Then also test allow_holes below (as you already are doing).
##########
python/tests/geopandas/test_geoseries.py:
##########
@@ -1238,7 +1238,34 @@ def test_centroid(self):
self.check_sgpd_equals_gpd(result, expected)
def test_concave_hull(self):
- pass
+ s = GeoSeries(
+ [
+ Polygon([(0, 0), (1, 1), (0, 1)]),
+ LineString([(0, 0), (1, 1), (1, 0)]),
+ MultiPoint([(0, 0), (1, 1), (0, 1), (1, 0), (0.5, 0.5)]),
+ MultiPoint([(0, 0), (1, 1)]),
+ Point(0, 0),
+ ],
+ crs=3857,
+ )
+
+ result = s.concave_hull()
Review Comment:
Would be nice to have a test for allow_holes=True in this file too. But we should first get to the bottom of the errors.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [GH-2527] Implement concave_hull [sedona]
Posted by "jiayuasu (via GitHub)" <gi...@apache.org>.
jiayuasu commented on code in PR #2529:
URL: https://github.com/apache/sedona/pull/2529#discussion_r3612176295
##########
python/tests/geopandas/test_match_geopandas_series.py:
##########
@@ -722,8 +722,35 @@ def test_centroid(self):
gpd_result = gpd.GeoSeries(geom).centroid
self.check_sgpd_equals_gpd(sgpd_result, gpd_result)
+ @pytest.mark.skipif(
+ parse_version(gpd.__version__) < parse_version("0.14.0"),
+ reason="geopandas concave_hull requires version 0.14.0 or higher",
+ )
def test_concave_hull(self):
- pass
+ for geom in self.geoms:
+ sgpd_result = GeoSeries(geom).concave_hull()
+ gpd_result = gpd.GeoSeries(geom).concave_hull()
+ self.check_sgpd_equals_gpd(sgpd_result, gpd_result)
+
+ # Test slightly complex geometry for different ratio and allow_holes settings
+ geom = [
+ Polygon(
+ [(0, 0), (0, 4), (1, 4), (1, 1), (3, 1), (3, 4), (4, 4), (4, 0), (0, 0)]
+ )
+ ]
+ for ratio, allow_holes in [(0.5, True), (1.0, True)]:
+ sgpd_result = GeoSeries(geom).concave_hull(
+ ratio=ratio, allow_holes=allow_holes
+ )
+ gpd_result = gpd.GeoSeries(geom).concave_hull(
+ ratio=ratio, allow_holes=allow_holes
+ )
+ self.check_sgpd_equals_gpd(sgpd_result, gpd_result)
+
+ mixed = [self.points[1], self.linestrings[1], self.polygons[1], None]
+ sgpd_result = GeoSeries(mixed).concave_hull()
+ gpd_result = gpd.GeoSeries(mixed).concave_hull()
+ self.check_sgpd_equals_gpd(sgpd_result, gpd_result)
Review Comment:
Removed the mixed-geometry case. The separate per-geometry fixtures remain as the parity coverage.
##########
python/tests/geopandas/test_match_geopandas_series.py:
##########
@@ -722,8 +722,35 @@ def test_centroid(self):
gpd_result = gpd.GeoSeries(geom).centroid
self.check_sgpd_equals_gpd(sgpd_result, gpd_result)
+ @pytest.mark.skipif(
+ parse_version(gpd.__version__) < parse_version("0.14.0"),
+ reason="geopandas concave_hull requires version 0.14.0 or higher",
+ )
def test_concave_hull(self):
- pass
+ for geom in self.geoms:
+ sgpd_result = GeoSeries(geom).concave_hull()
+ gpd_result = gpd.GeoSeries(geom).concave_hull()
+ self.check_sgpd_equals_gpd(sgpd_result, gpd_result)
Review Comment:
Updated the parity loop to split the geometry fixtures across ratios 0.0, 0.5, and 1.0 as suggested.
##########
python/tests/geopandas/test_geoseries.py:
##########
@@ -1238,7 +1238,34 @@ def test_centroid(self):
self.check_sgpd_equals_gpd(result, expected)
def test_concave_hull(self):
- pass
+ s = GeoSeries(
+ [
+ Polygon([(0, 0), (1, 1), (0, 1)]),
+ LineString([(0, 0), (1, 1), (1, 0)]),
+ MultiPoint([(0, 0), (1, 1), (0, 1), (1, 0), (0.5, 0.5)]),
+ MultiPoint([(0, 0), (1, 1)]),
+ Point(0, 0),
+ ],
+ crs=3857,
+ )
+
+ result = s.concave_hull()
Review Comment:
Added direct and parity coverage with allow_holes=True using an asymmetric MultiPoint fixture that produces one interior ring. The earlier symmetric fixture no longer reproduces with current JTS and GEOS stacks; tied boundary triangles can be processed in different orders, so the replacement avoids that ambiguity while retaining strict geometry equality.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [GH-2527] Implement concave_hull [sedona]
Posted by "jiayuasu (via GitHub)" <gi...@apache.org>.
jiayuasu commented on code in PR #2529:
URL: https://github.com/apache/sedona/pull/2529#discussion_r3612360528
##########
python/sedona/spark/geopandas/base.py:
##########
@@ -712,19 +712,25 @@ def centroid(self):
return _delegate_to_geometry_column("centroid", self)
def concave_hull(self, ratio=0.0, allow_holes=False):
- """Return the concave hull of each geometry.
+ """Return a ``GeoSeries`` of geometries representing the concave hull
+ of vertices of each geometry.
- The concave hull of a geometry is a possibly concave geometry that
- encloses the input geometry.
+ A concave hull is a concave or convex `Polygon` containing all the
+ vertices in each geometry. For two vertices, the hull collapses to a
+ `LineString`; for one vertex, it collapses to a `Point`.
+
+ The hull is constructed by removing border triangles of the Delaunay
+ triangulation while their size is larger than the maximum edge length
+ ratio. The ratio is a fraction of the difference between the longest
+ and shortest edges in the triangulation.
Review Comment:
Reworded this in fef658e1da3 to state that ratio determines the maximum edge-length threshold by interpolating between the shortest and longest Delaunay edges. This keeps the documented JTS semantics while removing the ambiguous comparison between triangle size and a dimensionless ratio.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [GH-2527] Implement concave_hull [sedona]
Posted by "chay0112 (via GitHub)" <gi...@apache.org>.
chay0112 commented on PR #2529:
URL: https://github.com/apache/sedona/pull/2529#issuecomment-3582578833
Hi @petern48
I'm encountering a test failure in our Sedona/GeoPandas parity suite for concave_hull(Passing in my local). The error is due to the vertex order of polygons returned by Sedona and GeoPandas being different, even though the polygons are geometrically identical. Our current comparison uses equals_exact, which might be sensitive to vertex order:
`=========================== short test summary info ============================
FAILED tests/geopandas/test_match_geopandas_series.py::TestMatchGeopandasSeries::test_concave_hull - ValueError: Geometry equality check failed for POLYGON ((1 4, 3 4, 4 4, 3 1, 4 0, 0 0, 1 1, 0 4, 1 4)) and POLYGON ((1 4, 3 4, 4 4, 4 0, 3 1, 0 0, 1 1, 0 4, 1 4))`
[https://github.com/apache/sedona/actions/runs/19687051539/job/56394868966?pr=2529](url)
Would it be acceptable to change our comparison from equals_exact to equals for polygons, so that we check geometric equality rather than strict vertex order? Or is there a recommended workaround for this situation, or something I might be missing in our test setup?
Thank you for your guidance!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [GH-2527] Implement GeoPandas concave_hull [sedona]
Posted by "jiayuasu (via GitHub)" <gi...@apache.org>.
jiayuasu merged PR #2529:
URL: https://github.com/apache/sedona/pull/2529
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@sedona.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org