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