[geos-devel] [Mobilitydb-dev] Problem with ST_FrechetDistance in PostGIS/GEOS

[Martin Davis]

I agree with the analysis that there might be a problem with the Frechet
Distance algorithm in GEOS.  Although, there is a recent PR against JTS for
Frechet Distance with a different codebase, and it produces the same result
as the GEOS code.  So this is puzzling.

The GEOS code is here:
https://git.osgeo.org/gitea/geos/geos/src/branch/main/src/algorithm/distance/DiscreteFrechetDistance.cpp
The JTS code is here:
https://github.com/locationtech/jts/blob/ff6476cd8fe4e4ee85304ebc049d05a7cafc3c00/modules/core/src/main/java/org/locationtech/jts/algorithm/distance/DiscreteFrechetDistance.java

MobilityDB can compare with their algorithm and see if there is a bug.   Or
else provide their source code to allow us to compare?

On Thu, Sep 16, 2021 at 2:09 PM Regina Obe <lr at pcorp.us> wrote:

> I do get 2.23606 on PostGIS so we are in agreement there.
>
>
>
> As to what the right answer is I have no clue and reading math equations
> gives me a headache.
>
>
>
> I’ve added geos-develop to mailing list for comment.
>
>
>
> Thanks,
>
> Regina
>
>
>
> *From:* Mobilitydb-dev [mailto:mobilitydb-dev-bounces at lists.osgeo.org] *On
> Behalf Of *Esteban Zimanyi
> *Sent:* Saturday, September 11, 2021 4:35 AM
> *To:* mobilitydb-dev at lists.osgeo.org
> *Subject:* [Mobilitydb-dev] Problem with ST_FrechetDistance in
> PostGIS/GEOS
>
>
>
> Dear Regina
>
>
>
> 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.
>
>
>
> Indeed the matrix of Euclidean distances between a vertex of the first
> linestring and a vertex of the second linestring is as follows
>
>
>
> 3.6 2.23 2.23
> 3.6 2.23 3
> 2.23 1 2.23
> 3 2.23 3.6
>
> And the matrix of the computation of the Frechet distance (ca in the
> algorithm) is as follows
>
> 3.6 3 3
> 3.6 3 3
> 3 3 3
> 3 3 3.6
>
> Could you please have a look ? If you confirm that there is a problem I
> will post a ticket in PostGIS and/or GEOS mailing lists.
>
>
>
> Many thanks
>
>
>
> Esteban
>
>
> _______________________________________________
> geos-devel mailing list
> geos-devel at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/geos-devel
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20210917/00af5eb1/attachment-0001.html>