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

[Spiros Denaxas]

Hi Tyler

Thank you for the feedback. I agree that a 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.

What is the canonical way of specying the flavour ? the two options I can
think of are: a) scipy.spatial.distance.continuous_frechet or b)
scipy.spatial.distance.frechet(P,Q, type="continuous")

best
Spiros


On Mon, Jan 22, 2018 at 3:14 PM, Tyler Reddy <tyler.je.reddy at gmail.com>
wrote:

> 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/20180123/aea5e070/attachment.html>