GEOSTopologyPreserveSimplify returns invalid geometry (47 examples provided)

[jmealo]

GEOSTopologyPreserveSimplify can return invalid geometry (see attached 47 test cases). Our current fix is to check if the value returned is valid, if not, we re-run with tolerance / 10 until we get a valid shape. Our default tolerance is 0.01 if that's of relevance.

47 Test fixtures in .geojson files that cause GEOSTopologyPreserveSimplify to return invalid geometry:
https://github.com/user-attachments/files/17261209/network_as_polygon_edgecase.zip

tree -sh output of the zip:

[ 192]  .
├── [1.3K]  geojson
│   ├── [2.0M]  network-as-polygon-edgecase-1.geojson
│   ├── [983K]  network-as-polygon-edgecase-10.geojson
│   ├── [1.8M]  network-as-polygon-edgecase-11.geojson
│   ├── [1.0M]  network-as-polygon-edgecase-12.geojson
│   ├── [2.3M]  network-as-polygon-edgecase-13.geojson
│   ├── [2.1M]  network-as-polygon-edgecase-14.geojson
│   ├── [3.1M]  network-as-polygon-edgecase-15.geojson
│   ├── [1.4M]  network-as-polygon-edgecase-16.geojson
│   ├── [1.7M]  network-as-polygon-edgecase-17.geojson
│   ├── [1.1M]  network-as-polygon-edgecase-18.geojson
│   ├── [2.1M]  network-as-polygon-edgecase-19.geojson
│   ├── [2.8M]  network-as-polygon-edgecase-20.geojson
│   ├── [1.2M]  network-as-polygon-edgecase-21.geojson
│   ├── [1.1M]  network-as-polygon-edgecase-22.geojson
│   ├── [1007K]  network-as-polygon-edgecase-23.geojson
│   ├── [992K]  network-as-polygon-edgecase-24.geojson
│   ├── [1.2M]  network-as-polygon-edgecase-25.geojson
│   ├── [1.2M]  network-as-polygon-edgecase-26.geojson
│   ├── [1.4M]  network-as-polygon-edgecase-27.geojson
│   ├── [2.8M]  network-as-polygon-edgecase-28.geojson
│   ├── [1010K]  network-as-polygon-edgecase-29.geojson
│   ├── [1.2M]  network-as-polygon-edgecase-30.geojson
│   ├── [1.6M]  network-as-polygon-edgecase-31.geojson
│   ├── [1.1M]  network-as-polygon-edgecase-32.geojson
│   ├── [1.1M]  network-as-polygon-edgecase-33.geojson
│   ├── [2.8M]  network-as-polygon-edgecase-34.geojson
│   ├── [1.5M]  network-as-polygon-edgecase-35.geojson
│   ├── [3.9M]  network-as-polygon-edgecase-36.geojson
│   ├── [1.3M]  network-as-polygon-edgecase-37.geojson
│   ├── [1.0M]  network-as-polygon-edgecase-38.geojson
│   ├── [1.2M]  network-as-polygon-edgecase-39.geojson
│   ├── [2.3M]  network-as-polygon-edgecase-40.geojson
│   ├── [1.9M]  network-as-polygon-edgecase-41.geojson
│   ├── [2.8M]  network-as-polygon-edgecase-42.geojson
│   ├── [2.7M]  network-as-polygon-edgecase-43.geojson
│   ├── [1.8M]  network-as-polygon-edgecase-44.geojson
│   ├── [1.8M]  network-as-polygon-edgecase-45.geojson
│   ├── [2.5M]  network-as-polygon-edgecase-46.geojson
│   └── [1.1M]  network-as-polygon-edgecase-47.geojson
└── [ 17M]  network_as_polygon_edgecase.zip

A test harness with pytest testing this functionality via Shapely is available here: shapely/shapely#2165

Related to:
shapely/shapely#2165

[dr-jts]

Which version of GEOS is causing this issue?

There were fixes to TopologyPreservingSimplifier in 3.13 (#986 and #1110).

[pramsey]

Here's the sample set in WKT for easier consumption. One was invalid and I have omitted it.

wkt.txt.gz

[pramsey]

And all of the valid inputs produce valid outputs when run in PostGIS against the latest GEOS.
@dr-jts do you recall if the fix was back-ported into earlier release branches? I see the main change GH-1012 in 3.12.2 but not earlier than that, and the second fix GH-1110 is not released yet.

[dr-jts]

do you recall if the fix was back-ported into earlier release branches?

It looks like #1012 and #1110 are only in 3.12.x and on, not in earlier versions. AFAIK they can be backported further (at least to 3.11)

[jmealo]

For Shapely 1.8.4:
Geos Version: 3.10.3

For Shapely: 2.0.6 (Stable):
Geos Version: 3.11.4

We're on Shapely 1.8.4 (I know, I know, very old, there were some breaking changes in Shapely 2.x, but since that didn't resolve this bug, we stuck with 1.8.4... for now).

We'd gladly upgrade to the next 2.x release if it includes the latest GEOS with this fix :)

[pramsey]

Back-ported to 3.11 at 5297e1e

[jmealo]

@pramsey: That was fast! 🥳

.▀█▀.█▄█.█▀█.█▄.█.█▄▀　█▄█.█▀█.█─█
─.█.─█▀█.█▀█.█.▀█.█▀▄　─█.─█▄█.█▄█

[dr-jts]

@jmealo Thank you, for finding and reporting the problem. And for uncovering a further bug in the #1012 fix! (Which showed up only in JTS - but both projects will get the fix, of course. Stay tuned...)