<div dir="ltr">Well, it looks like there is a possible bug in the GEOS DiscreteFrechetDistance class.  This line:<div><br></div><div><a href="https://git.osgeo.org/gitea/geos/geos/src/branch/main/src/algorithm/distance/DiscreteFrechetDistance.cpp#L112">https://git.osgeo.org/gitea/geos/geos/src/branch/main/src/algorithm/distance/DiscreteFrechetDistance.cpp#L112</a><br></div><div><br></div><div>should probably be</div><div><br></div><div>       ca[i][j] = p_ptDist;<br></div><div><br></div><div>And indeed that gives the expected answer of 3.</div><div><br></div><div>Working on a fix now, and will file a GEOS issue.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Sep 17, 2021 at 10:43 AM Martin Davis <<a href="mailto:mtnclimb@gmail.com">mtnclimb@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">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.<div><br></div><div>The GEOS code is here:  <a href="https://git.osgeo.org/gitea/geos/geos/src/branch/main/src/algorithm/distance/DiscreteFrechetDistance.cpp" target="_blank">https://git.osgeo.org/gitea/geos/geos/src/branch/main/src/algorithm/distance/DiscreteFrechetDistance.cpp</a></div><div>The JTS code is here: <a href="https://github.com/locationtech/jts/blob/ff6476cd8fe4e4ee85304ebc049d05a7cafc3c00/modules/core/src/main/java/org/locationtech/jts/algorithm/distance/DiscreteFrechetDistance.java" target="_blank">https://github.com/locationtech/jts/blob/ff6476cd8fe4e4ee85304ebc049d05a7cafc3c00/modules/core/src/main/java/org/locationtech/jts/algorithm/distance/DiscreteFrechetDistance.java</a></div><div><br></div><div>MobilityDB can compare with their algorithm and see if there is a bug.   Or else provide their source code to allow us to compare?</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Sep 16, 2021 at 2:09 PM Regina Obe <<a href="mailto:lr@pcorp.us" target="_blank">lr@pcorp.us</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div lang="EN-US"><div><p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">I do get 2.23606 on PostGIS so we are in agreement there.<u></u><u></u></span></p><p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"><u></u> <u></u></span></p><p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">As to what the right answer is I have no clue and reading math equations gives me a headache.<u></u><u></u></span></p><p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"><u></u> <u></u></span></p><p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">I’ve added geos-develop to mailing list for comment.<u></u><u></u></span></p><p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"><u></u> <u></u></span></p><p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">Thanks,<u></u><u></u></span></p><p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">Regina<u></u><u></u></span></p><p class="MsoNormal"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"><u></u> <u></u></span></p><div style="border-top:none;border-right:none;border-bottom:none;border-left:1.5pt solid blue;padding:0in 0in 0in 4pt"><div><div style="border-right:none;border-bottom:none;border-left:none;border-top:1pt solid rgb(225,225,225);padding:3pt 0in 0in"><p class="MsoNormal"><b><span style="font-size:11pt;font-family:Calibri,sans-serif">From:</span></b><span style="font-size:11pt;font-family:Calibri,sans-serif"> Mobilitydb-dev [mailto:<a href="mailto:mobilitydb-dev-bounces@lists.osgeo.org" target="_blank">mobilitydb-dev-bounces@lists.osgeo.org</a>] <b>On Behalf Of </b>Esteban Zimanyi<br><b>Sent:</b> Saturday, September 11, 2021 4:35 AM<br><b>To:</b> <a href="mailto:mobilitydb-dev@lists.osgeo.org" target="_blank">mobilitydb-dev@lists.osgeo.org</a><br><b>Subject:</b> [Mobilitydb-dev] Problem with ST_FrechetDistance in PostGIS/GEOS<u></u><u></u></span></p></div></div><p class="MsoNormal"><u></u> <u></u></p><div><div><div><p class="MsoNormal">Dear Regina<u></u><u></u></p><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">We started the implementation of the discrete Frechet distance in MobilityDB and found out that we obtain a different result than PostGIS/GEOS.<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><div><p class="MsoNormal">test=# select frechetDistance(tgeompoint '[Point(1 1)@2000-01-01, Point(2 2)@2000-01-02, Point(3 1)@2000-01-03]',<br>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]');<br> frechetdistance<br>-----------------<br>               3<br>(1 row)<br><br>test=# select ST_FrechetDistance(geometry 'Linestring(1 1,2 2,3 1)',<br>test(#   geometry 'Linestring(1 4,2 3,3 4,4 3)');<br> st_frechetdistance<br>--------------------<br>   2.23606797749979<br>(1 row)<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div></div><div><p class="MsoNormal">We used the simple algorithm referenced in the PostGIS manual<u></u><u></u></p></div><div><p class="MsoNormal"><a href="https://postgis.net/docs/ST_FrechetDistance.html" target="_blank">https://postgis.net/docs/ST_FrechetDistance.html</a><u></u><u></u></p></div><div><p class="MsoNormal">and according to our understanding the correct result is 3.<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">Indeed the matrix of Euclidean distances between a vertex of the first linestring and a vertex of the second linestring is as follows<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">3.6 2.23 2.23<br>3.6 2.23 3<br>2.23 1 2.23<br>3 2.23 3.6 <br><br>And the matrix of the computation of the Frechet distance (ca in the algorithm) is as follows<br><br>3.6 3 3<br>3.6 3 3<br>3 3 3<br>3 3 3.6<br><br>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.<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">Many thanks<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">Esteban<u></u><u></u></p></div><div><p class="MsoNormal"><u></u> <u></u></p></div></div></div></div></div></div></div>_______________________________________________<br>
geos-devel mailing list<br>
<a href="mailto:geos-devel@lists.osgeo.org" target="_blank">geos-devel@lists.osgeo.org</a><br>
<a href="https://lists.osgeo.org/mailman/listinfo/geos-devel" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailman/listinfo/geos-devel</a><br>
</blockquote></div>
</blockquote></div>