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

[Spiros Denaxas]

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/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/95ee3b27/attachment-0001.html>