Crash in concaveHullByLengthRatio

[pramsey]

Reported on postgis-users and confirmed directly in GEOS. Here's a test case

diff --git a/tests/unit/algorithm/hull/ConcaveHullTest.cpp b/tests/unit/algorithm/hull/ConcaveHullTest.cpp
index f805a3d79..49e476300 100644
--- a/tests/unit/algorithm/hull/ConcaveHullTest.cpp
+++ b/tests/unit/algorithm/hull/ConcaveHullTest.cpp
@@ -298,6 +298,16 @@ void object::test<19>()
         "POLYGON ((20 90, 40 96, 56 95, 80 90, 90 70, 95 45, 90 20, 80 10, 60 15, 45 5, 20 10, 10 20, 5 40, 11 60, 20 70, 20 90), (40 80, 15 45, 21 30, 40 20, 70 20, 80 40, 80 60, 70 80, 40 80))" );
 }
 
+// postgis-users report
+template<>
+template<>
+void object::test<20>()
+{
+    checkHullByLengthRatio(
+        "MULTIPOINT ((113.56577197798602 22.80081530883069),(113.565723279387 22.800815316487014),(113.56571548761124 22.80081531771092),(113.56571548780202 22.800815317674463),(113.56577197817877 22.8008153088047),(113.56577197798602 22.80081530883069))",
+        0.75,
+        "POLYGON EMPTY"); // Change this
+}
 

[dr-jts]

Confirmed this is an issue in JTS as well.

The problem is that the input points are almost "flat". This produces very thin triangles, and the triangulation algorithm is unable to form a valid triangulation. Specifically, the triangulation is not edge-connected (it has a node which partitions the triangles into two sets). This causes an error when traversing the triangulation in the concave hull algorithm.

This is caused by a known issue, which was partially fixed by #728. Clearly, an even larger frame size is required for this case. This probably only happens when the input points are very "flat". In this situation, it seems reasonable to simply return the convex hull.

The problem is detectable and can be converted to an exception. A null-pointer check can be done here, and an exception thrown.

Given this, potential workarounds are:

• simply return the convex hull
• use a more robust (but slower) triangulation algorithm (this is experimental)

Even better is to detect that the Delaunay triangulation is incorrect, and return the convex hull. It might even be possible to fix the triangulation. This would be nice to have in the Delaunay Triangulation algorithm as well.

[dr-jts]

A geosop command to reproduce:

bin/geosop -a "MULTIPOINT ((113.56577197798602 22.80081530883069),(113.565723279387 22.800815316487014),(113.56571548761124 22.80081531771092),(113.56571548780202 22.800815317674463),(113.56577197817877 22.8008153088047),(113.56577197798602 22.80081530883069))" concaveHull 0.75

[dr-jts]

The crash stack:

#0  0x0000ffff84e02210 in geos::triangulate::tri::Tri::getIndex(geos::triangulate::tri::Tri const*) const () from /home/[erchen.cz/pgsql15/lib/libgeos.so.3.11.2](http://erchen.cz/pgsql15/lib/libgeos.so.3.11.2)
#1  0x0000ffff84ce74c0 in geos::algorithm::hull::HullTriangulation::nextBorderTri(geos::algorithm::hull::HullTri*) ()
  from /home/[erchen.cz/pgsql15/lib/libgeos.so.3.11.2](http://erchen.cz/pgsql15/lib/libgeos.so.3.11.2)
#2  0x0000ffff84ce7698 in geos::algorithm::hull::HullTriangulation::traceBoundary(geos::triangulate::tri::TriList<geos::algorithm::hull::HullTri>&) ()
  from /home/[erchen.cz/pgsql15/lib/libgeos.so.3.11.2](http://erchen.cz/pgsql15/lib/libgeos.so.3.11.2)
#3  0x0000ffff84ce79d4 in geos::algorithm::hull::HullTriangulation::traceBoundaryPolygon(geos::triangulate::tri::TriList<geos::algorithm::hull::HullTri>&, geos::geom::GeometryFactory const*) ()
  from /home/[erchen.cz/pgsql15/lib/libgeos.so.3.11.2](http://erchen.cz/pgsql15/lib/libgeos.so.3.11.2)
#4  0x0000ffff84ce1f28 in geos::algorithm::hull::ConcaveHull::toGeometry(geos::triangulate::tri::TriList<geos::algorithm::hull::HullTri>&, geos::geom::GeometryFactory const*) () from /home/[erchen.cz/pgsql15/lib/libgeos.so.3.11.2](http://erchen.cz/pgsql15/lib/libgeos.so.3.11.2)
#5  0x0000ffff84ce29d4 in geos::algorithm::hull::ConcaveHull::getHull() ()
  from /home/[erchen.cz/pgsql15/lib/libgeos.so.3.11.2](http://erchen.cz/pgsql15/lib/libgeos.so.3.11.2)
#6  0x0000ffff8e54818c in GEOSConcaveHull_r ()
  from /home/[erchen.cz/pgsql15/lib/libgeos_c.so.1](http://erchen.cz/pgsql15/lib/libgeos_c.so.1)

[jorisvandenbossche]

Another (I assume similar) example reported in shapely/shapely#1873:

$ geosop -a "MULTIPOINT ((584245.72096874 7549593.72686167), (584251.71398371 7549594.01629478), (584242.72446125 7549593.58214511), (584230.73978847 7549592.9760418), (584233.73581213 7549593.13045099), (584236.7318358 7549593.28486019), (584239.72795377 7549593.43742855), (584227.74314188 7549592.83423486))" concaveHull 0.0
Segmentation fault (core dumped)

The crash backtrace grom gdb (based on the original shapely reproducer):

Thread 1 "python" received signal SIGSEGV, Segmentation fault.
geos::triangulate::tri::Tri::getIndex (this=this@entry=0x0, tri=tri@entry=0x555555e77b40) at /home/joris/scipy/repos/geos/src/triangulate/tri/Tri.cpp:312
312	    if ( tri0 == tri )
(gdb) bt
#0  geos::triangulate::tri::Tri::getIndex (this=this@entry=0x0, tri=tri@entry=0x555555e77b40) at /home/joris/scipy/repos/geos/src/triangulate/tri/Tri.cpp:312
#1  0x00007ffff70a1496 in geos::algorithm::hull::HullTriangulation::nextBorderTri (triStart=<optimized out>) at /home/joris/scipy/repos/geos/src/algorithm/hull/HullTriangulation.cpp:163
#2  0x00007ffff70a1c19 in geos::algorithm::hull::HullTriangulation::traceBoundary (triList=...) at /home/joris/scipy/repos/geos/src/algorithm/hull/HullTriangulation.cpp:131
#3  0x00007ffff70a212e in geos::algorithm::hull::HullTriangulation::traceBoundaryPolygon (triList=..., factory=0x7ffff726f220 <geos::geom::GeometryFactory::getDefaultInstance()::defInstance>)
    at /home/joris/scipy/repos/geos/src/algorithm/hull/HullTriangulation.cpp:107
#4  0x00007ffff709b74f in geos::algorithm::hull::ConcaveHull::toGeometry (this=this@entry=0x7fffffff9260, triList=..., factory=<optimized out>)
    at /home/joris/scipy/repos/geos/src/algorithm/hull/ConcaveHull.cpp:419
#5  0x00007ffff709ca62 in geos::algorithm::hull::ConcaveHull::getHull (this=this@entry=0x7fffffff9260) at /home/joris/scipy/repos/geos/src/algorithm/hull/ConcaveHull.cpp:176
#6  0x00007ffff729c35c in operator() (__closure=<optimized out>) at /home/joris/scipy/repos/geos/capi/geos_ts_c.cpp:1251
#7  execute<GEOSConcaveHull_r(GEOSContextHandle_t, const geos::geom::Geometry*, double, unsigned int)::<lambda()> > (f=..., extHandle=0x5555560e56b0) at /home/joris/scipy/repos/geos/capi/geos_ts_c.cpp:427
#8  GEOSConcaveHull_r (extHandle=0x5555560e56b0, g1=0x5555560e9850, ratio=<optimized out>, allowHoles=0) at /home/joris/scipy/repos/geos/capi/geos_ts_c.cpp:1247
#9  0x00007ffff72d2133 in concave_hull_func () from /home/joris/scipy/repos/shapely/shapely/lib.cpython-311-x86_64-linux-gnu.so

[dr-jts]

Another (I assume similar) example reported in shapely/shapely#1873:

Thanks. This is the same issue - an invalid Delaunay Triangulation is produced, which causes the Concave Hull algorithm to fail.

[dr-jts]

Further research reveals that the fundamental problem is with the Delaunay Triangulation code. It is missing some logic to properly handle the "frame points" used in the algorithm. Hopefully this can be fixed soon.

[dr-jts]

Interesting that so many of the reports are coming from use of the Concave Hull code. Good to know it's being used, anyway.

[dr-jts]

Fixed by #953