`ConcaveHullOfPolygons` can produce disconnected result - Githubissues

locationtech / jts

The JTS Topology Suite is a Java library for creating and manipulating vector geometry.

Other

1.94k stars 441 forks source link

`ConcaveHullOfPolygons` can produce disconnected result #948

Open dr-jts opened 1 year ago

dr-jts commented 1 year ago

ConcaveHullOfPolygons can produce a disconnected MultiPolygon output in some situations. This is contrary to the stated contract for this class.

This is due to a design limitation in the current code. It can be fixed by ensuring that triangle removal does not disconnect the triangulation.

Notes

It might be nice to provide an option to allow disconnected output, if this is desired (also for ConcaveHull for points).

Example

MULTIPOLYGON (((10 20, 20 20, 20 10, 10 10, 10 20)), ((20 30, 30 30, 30 20, 20 20, 20 30)), ((80 90, 90 90, 90 80, 80 80, 80 90)))

Result for Length Ratio = 0.1

MULTIPOLYGON (((20 30, 30 30, 30 20, 20 10, 10 10, 10 20, 20 30)), ((90 90, 90 80, 80 80, 80 90, 90 90)))