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

[Tyler Reddy]

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/00cffc8c/attachment.html>