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實現
分享到:
閱讀更多 半杯茶的小酒杯 的文章
