Problem with ST_FrechetDistance in PostGIS/GEOS ?

[ezimanyi]

We started the implementation of the discrete Frechet distance in MobilityDB and found out that we obtain a different result than PostGIS/GEOS.

test=# select frechetDistance(tgeompoint '[Point(1 1)@2000-01-01, Point(2 2)@2000-01-02, Point(3 1)@2000-01-03]',
tgeompoint '[Point(1 4)@2000-01-01, Point(2 3)@2000-01-02, Point(3 4)@2000-01-03, Point(4 3)@2000-01-04]');
 frechetdistance
-----------------
               3
(1 row)

test=# select ST_FrechetDistance(geometry 'Linestring(1 1,2 2,3 1)',
test(#   geometry 'Linestring(1 4,2 3,3 4,4 3)');
 st_frechetdistance
--------------------
   2.23606797749979
(1 row)

We used the simple algorithm referenced in the PostGIS manual ​https://postgis.net/docs/ST_FrechetDistance.html and according to our understanding the correct result is 3.

Intuitively, thinking of the Frechet distance as a man walking a dog on a leash, if the distance between the first two points is 3, the result cannot be less than 3.

[mdavis]

Perhaps you have a more "batteries include" implementation of Frechet Distance.

The PostGIS algorithm (coming from GEOS) is a Discrete Frechet Distance implementation. It works better if the geometry is densified via the optional third argument:

SELECT ST_FrechetDistance(
  'Linestring(1 1,2 2,3 1)',                                                  
  'Linestring(1 4,2 3,3 4,4 3)', .01);
 st_frechetdistance 
--------------------
 2.9800000000000004

[mdavis]

This does look like a bug. Filed as ​GEOS-1128.

[mdavis]

Fixed in GEOS 3.10, 3.9 3.8.