ST_ConcaveHull() is giving strange results in some specific cases

Question

I'm playing around with ST_ConcaveHull() (baked on top of GEOS) in the hope of solving a small PostGIS problem that I have.

I'll got straight to the point.

This is working:

SELECT
  ST_ConcaveHull(
    ST_LineMerge(
      ST_GeomFromText(
        'MULTILINESTRINGZ(
          (2684042.5558077096 1247835.7133034348 461,
           2684031.2842591000 1247831.8972207694 463),
          (2684031.2842591004 1247831.8972207694 463,
           2684009.6507170842 1247838.4790956799 465),
          (2684009.6507170842 1247838.4790956799 465,
           2684027.4938191720 1247820.1675839284 464),
          (2684027.4938191720 1247820.1675839284 464,
           2684038.0447123488 1247803.6790970158 462)
        )', 2056)
    ), 0.4);

=>

Please notice that this is only working with at least GEOS 3.11, otherwise it raises:

ERROR:  Cannot ST_Collect geometries with differing dimensionality.
CONTEXT:  PL/pgSQL function _st_concavehull(geometry) line 67 at assignment

while this is giving a strange result:

SELECT
  ST_ConcaveHull(
    ST_LineMerge(
      ST_GeomFromText(
        'MULTILINESTRINGZ(
          (2684042.5558077096 1247835.7133034348 461,
           2684031.2842591000 1247834.8972207694 463),
          (2684031.2842591004 1247834.8972207694 463,
           2684009.6507170842 1247838.4790956799 465),
          (2684009.6507170842 1247838.4790956799 465,
           2684027.4938191720 1247820.1675839284 464),
          (2684027.4938191720 1247820.1675839284 464,
           2684038.0447123488 1247803.6790970158 462)
        )', 2056)
    ), 0.4);

=>

The only difference is in the Y coordinate of the second point, where I simply added +3m: from 1247831 to 1247834 (on both the 2nd and 3rd lines of the points set).

Please also notice the gap on those lines: 2684031.2842591000 (line 2) and 2684031.2842591004 (line 3).
If I set them both with 2684031.2842591000, the results of these two queries both give a valid polygon.

Edits

You can play with a param_pctconvex values in the range [0, 0.5], the result is the same.

With a value between [0.6, 0.7] it seems to be OK.

With a value between [0.8, 0.9] it closes the top side with a straight line:

With a value of 1 it's a pure convex hull (in that case, a triangle).

I was expecting a value close to 0 to give the best results as the doc states:

Choosing a suitable value depends on the nature of the input data, but often values between 0.3 and 0.1 produce reasonable results.

But apparently this "nature" of the input data disturbs the results in case there is some kind of tiny hole in the multilinestring, even so it's roughly 15m away:

Version info

 PostgreSQL 15rc1 (Debian 15~rc1-1.pgdg110+1) on x86_64-pc-linux-gnu,
    compiled by gcc (Debian 10.2.1-6) 10.2.1 20210110, 64-bit

 POSTGIS="3.4.0dev 3.3.0rc2-148-gb8d78a0dc" [EXTENSION]
   PGSQL="150"
   GEOS="3.12.0dev-CAPI-1.18.0"
   PROJ="9.2.0"
   LIBXML="2.9.10"
   LIBJSON="0.15"
   LIBPROTOBUF="1.3.3"
   WAGYU="0.5.0 (Internal)" TOPOLOGY

Using (at the time of writing):

docker pull postgis/postgis:15rc1-master

Answer 1

The Concave Hull is computed based on the Delaunay Triangulation of the input vertices. The discrepancy in this case is caused by a different DT being produced due to the change in location of the second point. Both of the triangulations contain "sliver" triangles due to the very small distance between two of the input vertices. However, in one DT the slivers are arranged in a way that leaves one of them present in the output as a "spike", whereas in the other they are all merged with adjacent triangles.

Note that technically speaking both outputs are correct, in that they are both polygons which contain the set of input vertices, and are "tighter" than the convex hull of the points. That is the primary criteria that the Concave Hull algorithm is designed to satisfy.

Unfortunately this explanation doesn't provide any clues on how to make this situation more uniform. The bottom line is that Concave Hulls are useful in some applications, but less so in others.