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

[Regina Obe]

Doesn’t look like Martin’s response made it to mobilitydev list probably because he’s not on the list so forwarding.

 

From: geos-devel [mailto:geos-devel-bounces at lists.osgeo.org] On Behalf Of Martin Davis
Sent: Friday, September 17, 2021 4:09 PM
To: GEOS Development List <geos-devel at lists.osgeo.org>
Subject: Re: [geos-devel] [Mobilitydb-dev] Problem with ST_FrechetDistance in PostGIS/GEOS

 

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 <mailto: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 <mailto: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 <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 <mailto: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 <mailto: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/mobilitydb-dev/attachments/20210918/ef7e596c/attachment.html>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: Untitled attachment 00011.txt
URL: <http://lists.osgeo.org/pipermail/mobilitydb-dev/attachments/20210918/ef7e596c/attachment.txt>