[SciPy-Dev] New feature - discrete Frechet distance for scipy.spatial.distance

[Tyler Reddy]

There are a few Python implementations of discrete Frechet around (i.e., in
MDA:
https://www.mdanalysis.org/docs/documentation_pages/analysis/psa.html#MDAnalysis.analysis.psa.discrete_frechet
). 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.

One thing that would be really impressive is if we could get a subquadratic
implementation of discrete Frechet ( i.e.,
http://epubs.siam.org/doi/abs/10.1137/130920526 ), 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.

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.

On 22 January 2018 at 05:33, Spiros Denaxas <s.denaxas at gmail.com> wrote:

> Dear SciPy devs,
>
> 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.
>
> 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.
>
> Spiros
>
> [1] https://github.com/spiros/discrete_frechet
> [2] http://www.kr.tuwien.ac.at/staff/eiter/et-archive/cdtr9464.pdf
>
>
>
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at python.org
> https://mail.python.org/mailman/listinfo/scipy-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20180122/29bb634a/attachment.html>