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 <[email protected]> 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:[email protected]] *On > Behalf Of *Esteban Zimanyi > *Sent:* Saturday, September 11, 2021 4:35 AM > *To:* [email protected] > *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 > [email protected] > https://lists.osgeo.org/mailman/listinfo/geos-devel >
_______________________________________________ geos-devel mailing list [email protected] https://lists.osgeo.org/mailman/listinfo/geos-devel
