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

[Martin Davis]

Well, it looks like there is a possible bug in the GEOS
DiscreteFrechetDistance class.  This line:

https://git.osgeo.org/gitea/geos/geos/src/branch/main/src/algorithm/distance/DiscreteFrechetDistance.cpp#L112

should probably be

       ca[i][j] = p_ptDist;

And indeed that gives the expected answer of 3.

Working on a fix now, and will file a GEOS issue.

On Fri, Sep 17, 2021 at 10:43 AM Martin Davis <mtnclimb at gmail.com> wrote:

> 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/028d5ac6/attachment.html>