locationtech / jts

The JTS Topology Suite is a Java library for creating and manipulating vector geometry.
Other
1.99k stars 443 forks source link

ConcaveHullOfPolygons does not handle shells nested inside holes #1080

Closed dr-jts closed 1 month ago

dr-jts commented 2 months ago

The ConcaveHullOfPolygons class does not handle MultiPolygons with shells nested inside holes. It produces an error in this situation: Unable to find shell join index with interior join line.

Example

MULTIPOLYGON (((1 9, 9 9, 9 1, 1 1, 1 9), (2 8, 8 8, 8 2, 2 2, 2 8)), ((3 3, 4 7, 7 4, 3 3)))
image

Analysis

This is because the code to create the "frame" does not check for shells inside holes, and thus does not remove them.

The fix is to remove polygon elements which lie inside another element shell.

Originally reported as https://trac.osgeo.org/postgis/ticket/5665.