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

[CJ Carey]

Frechet distance is pretty similar to Dynamic Time Warping, which has also
been requested for inclusion in scipy:
https://github.com/scipy/scipy/issues/7638

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.

On Tue, Jan 23, 2018 at 11:41 AM, Spiros Denaxas <s.denaxas at gmail.com>
wrote:

> Thanks - will do.
> Spiros
>
> On Tue, Jan 23, 2018 at 3:27 PM, Tyler Reddy <tyler.je.reddy at gmail.com>
> wrote:
>
>> 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.
>>
>> On 23 January 2018 at 02:38, Spiros Denaxas <s.denaxas at gmail.com> wrote:
>>
>>> 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/doc
>>>> s/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
>>>>>
>>>>>
>>>>
>>>
>>
>
> _______________________________________________
> 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/236c429e/attachment-0001.html>