<div dir="ltr"><div>Oh yeah, I forgot about that proposal!<br><br></div>Here's what the first author of the subquadratic Frechet paper had to say when I asked him about implementations (hopefully they don't mind me sharing!):<br><br>"I am not aware of such a code, and I am not sure whether it's worth
the effort for a variety of reasons. n^2 algorithm is so simple that
it will perform significantly better even for polygonal chains with
tens of thousands of vertices. <br>
<br>
In practice, dynamic time warping does a better job in measuring
similarity and outside CG community (eg. computer vision,
compuational biology, speech recognition) DTW is often used instead
of Frechet. <br>
<br>
I have a paper in the ACM-GIS conference this year on approximation
algorithms for DTW, with an implementation.<br>
The approx algorithm performs better than the quadratic DP algorithm
when the number of vertices is a few thousand or more.<br>
<br>
-Pankaj"<br></div><div class="gmail_extra"><br><div class="gmail_quote">On 23 January 2018 at 13:01, CJ Carey <span dir="ltr"><<a href="mailto:perimosocordiae@gmail.com" target="_blank">perimosocordiae@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Frechet distance is pretty similar to Dynamic Time Warping, which has also been requested for inclusion in scipy: <a href="https://github.com/scipy/scipy/issues/7638" target="_blank">https://github.com/<wbr>scipy/scipy/issues/7638</a><div><br></div><div>AFAIK, there's no current effort to add DTW, but I suspect it would make sense to have both it and Frechet variants in a similar namespace.</div></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Jan 23, 2018 at 11:41 AM, Spiros Denaxas <span dir="ltr"><<a href="mailto:s.denaxas@gmail.com" target="_blank">s.denaxas@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Thanks - will do.<span class="m_7982096459438742877HOEnZb"><font color="#888888"><div>Spiros</div></font></span></div><div class="m_7982096459438742877HOEnZb"><div class="m_7982096459438742877h5"><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Jan 23, 2018 at 3:27 PM, Tyler Reddy <span dir="ltr"><<a href="mailto:tyler.je.reddy@gmail.com" target="_blank">tyler.je.reddy@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">I guess both call signatures have tradeoffs. What I did with directed_hausdorff looks more like "a," so you can probably start with that for now. I'd encourage you to start drafting a (work in progress) pull request -- you can progressively chip away at docstring, unit tests, cythonization (if this is helpful or you haven't already), maybe a concise asv performance benchmark to accompany it, etc.<br></div><div class="m_7982096459438742877m_5998833108844027053HOEnZb"><div class="m_7982096459438742877m_5998833108844027053h5"><div class="gmail_extra"><br><div class="gmail_quote">On 23 January 2018 at 02:38, Spiros Denaxas <span dir="ltr"><<a href="mailto:s.denaxas@gmail.com" target="_blank">s.denaxas@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi Tyler<div><br></div><div>Thank you for the feedback. I agree that a <span style="color:rgb(0,0,0);font-size:12.8px">subquadratic implementation would be really cool but I havent seen one either and just by glancing at the paper realize that this would take a substantial amount of effort. </span></div><div><span style="color:rgb(0,0,0);font-size:12.8px"><br></span></div><div><font color="#000000"><span style="font-size:12.8px">What is the canonical way of specying the flavour ? the two options I can think of are: a) scipy.spatial.distance.continu<wbr>ous_frechet or b) scipy.spatial.distance.frechet<wbr>(P,Q, type="continuous") </span></font></div><div><font color="#000000"><span style="font-size:12.8px"><br></span></font></div><div><font color="#000000"><span style="font-size:12.8px">best</span></font></div><span class="m_7982096459438742877m_5998833108844027053m_2171434047698866609HOEnZb"><font color="#888888"><div><font color="#000000"><span style="font-size:12.8px">Spiros</span></font></div><div><font color="#000000"><span style="font-size:12.8px"><br></span></font></div></font></span></div><div class="m_7982096459438742877m_5998833108844027053m_2171434047698866609HOEnZb"><div class="m_7982096459438742877m_5998833108844027053m_2171434047698866609h5"><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jan 22, 2018 at 3:14 PM, Tyler Reddy <span dir="ltr"><<a href="mailto:tyler.je.reddy@gmail.com" target="_blank">tyler.je.reddy@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div>There are a few Python implementations of discrete Frechet around (i.e., in MDA: <a href="https://www.mdanalysis.org/docs/documentation_pages/analysis/psa.html#MDAnalysis.analysis.psa.discrete_frechet" target="_blank">https://www.mdanalysis.org/doc<wbr>s/documentation_pages/analysis<wbr>/psa.html#MDAnalysis.analysis.<wbr>psa.discrete_frechet</a> ). Most of them use the quadratic time complexity dynamic programming approach, and it seems you have used that as well. I think there's probably interest in incorporating discrete Frechet in scipy since we already have directed_hausdorff, which is thematically similar.<br><br></div>One thing that would be really impressive is if we could get a subquadratic implementation of discrete Frechet ( i.e., <a href="http://epubs.siam.org/doi/abs/10.1137/130920526" target="_blank">http://epubs.siam.org/doi/abs/<wbr>10.1137/130920526</a> ), but these algorithms seem to be extraordinarily complicated -- indeed the authors of the paper I cited there are not aware of any working implementations in the wild & when I asked one I think they suggested it wasn't worth implementing because for most input data sizes the much simpler algorithm will still win. Perhaps this sort of thing could be summarized in the docstring.<br><br></div>There are quite a few different flavors of Frechet distance (continuous, homotopic, weak, etc.). From a design standpoint it might makes sense to have some kind of keyword to allow expansion for those in the future.<br></div></div><div class="gmail_extra"><br><div class="gmail_quote"><div><div class="m_7982096459438742877m_5998833108844027053m_2171434047698866609m_5294365496433501426h5">On 22 January 2018 at 05:33, Spiros Denaxas <span dir="ltr"><<a href="mailto:s.denaxas@gmail.com" target="_blank">s.denaxas@gmail.com</a>></span> wrote:<br></div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div class="m_7982096459438742877m_5998833108844027053m_2171434047698866609m_5294365496433501426h5"><div dir="ltr">Dear SciPy devs, <div><br></div><div>I recently decided to clean up and package a Python implementation [1] for calculating the discrete Frechet distance [2] between two polygonal curves that I had lying around.</div><div><br></div><div>I was thinking this could potentially be a useful addition to scipy.spatial.distance. More than happy to do a pull request if you think it will be useful.</div><div><br></div><div>Spiros</div><div><br></div><div>[1] <a href="https://github.com/spiros/discrete_frechet" target="_blank">https://github.com/spiros/<wbr>discrete_frechet</a></div><div>[2] <a href="http://www.kr.tuwien.ac.at/staff/eiter/et-archive/cdtr9464.pdf" target="_blank">http://www.kr.tuwien.ac.at<wbr>/staff/eiter/et-archive/cdtr94<wbr>64.pdf</a></div><div><br></div><div><br></div></div>
<br></div></div>______________________________<wbr>_________________<br>
SciPy-Dev mailing list<br>
<a href="mailto:SciPy-Dev@python.org" target="_blank">SciPy-Dev@python.org</a><br>
<a href="https://mail.python.org/mailman/listinfo/scipy-dev" rel="noreferrer" target="_blank">https://mail.python.org/mailma<wbr>n/listinfo/scipy-dev</a><br>
<br></blockquote></div><br></div>
</blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div><br>______________________________<wbr>_________________<br>
SciPy-Dev mailing list<br>
<a href="mailto:SciPy-Dev@python.org" target="_blank">SciPy-Dev@python.org</a><br>
<a href="https://mail.python.org/mailman/listinfo/scipy-dev" rel="noreferrer" target="_blank">https://mail.python.org/mailma<wbr>n/listinfo/scipy-dev</a><br>
<br></blockquote></div><br></div>
</div></div></blockquote></div><br></div>