Fréchet distance(弗雷歇距离)是法国数学家Maurice René Fréchet在1906年提出的一种路径空间相似性计算方法。
直观的理解，Fréchet distance就是狗绳距离：主人走路径A，狗走路径B，他们行进的速度可能不同，但是不允许backtracking，各自走完这两条路径过程中所需要的最短狗绳长度。
Fréchet distance不仅考虑了曲线的空间位置，同时还考虑了曲线中形状点的顺序。
数学描述
给定Curve 1:
和Curve 2:
Fréchet distance定义如下:
Frechet Distance
α是将[0,1]映射到[a,b]连续非降函数，β是将[0,1]映射到[a',b']连续非降函数。
实际计算中，用多边形曲线逼近连续曲线，转化为Discrete Frechet Distance。
假设多边形曲线为P，Q；
要计算P和Q的Fréchet distance，要先找到对应的点对序列
其中
为了保证点的顺序，对于所有的i=1,2,...q令
然后计算对应点对的最大距离:
longest link
离散弗雷歇距离(Discrete Frechet Distance)的计算如下:
离散弗雷歇距离
离散弗雷歇距离(Discrete Frechet Distance)算法
Discrete Frechet Distance Algorithm
python实现
分享到:
閱讀更多 半杯茶的小酒杯 的文章
