我正在使用 python 及其数据科学相关库进行轨迹分析项目。我计划实施 Frechet 距离算法进行轨迹分析，每个轨迹都有 (x,y) 坐标序列以及时间戳、速度、连续点之间的距离等。
如果有在该领域和轨迹分析方面有经验的人，我会请求是否可以提供一些有用的链接，用于 Frechet Distance 的 Python 实现。我的最终目标是聚类相似的轨迹（位置和方向）。
Frechet距离的Python实现
计算科学
Python
数据分析
高性能计算
2021-12-06 17:25:04
2个回答
我意识到这个问题是不久前提出的，但我最近也需要 Freschet 距离。我找不到 Python 的任何实现，所以我根据“Thomas Eiter 和 Heikki Mannila”的论文“计算离散 Frechet 距离”编写了自己的实现，并认为我会分享它以供将来参考。
它是用 Cython 编写的（另存为 frechet.pyx）
# Julius Bier Kirkegaard 2017
# Based on "Computing Discrete Frechet Distance" by "Thomas Eiter and Heikki Mannila".
#cython: boundscheck=False
#cython: wraparound=False
import numpy as np
cimport numpy as np
from libc.math cimport sqrt, cos, sin
cdef double d(double p, double q):
return (p - q)*(p - q)
cdef double c(int i, int j, double* P, double* Q, double* ca, int N):
cdef int index = i*N+j
cdef double d_t = d(P[i], Q[j])
cdef double m1, m2
if ca[index] > -1:
return ca[index]
elif i == 0 and j == 0:
ca[index] = d(P[i], Q[j])
elif i > 0 and j == 0:
if d_t > ca[(i-1)*N+j]:
ca[index] = d_t
else:
ca[index] = ca[(i-1)*N+j]
elif i == 0 and j > 0:
if d_t > ca[i*N+(j-1)]:
ca[index] = d_t
else:
ca[index] = ca[i*N+(j-1)]
elif i > 0 and j > 0:
m1 = c(i - 1, j, P, Q, ca, N)
m2 = c(i, j - 1, P, Q, ca, N)
if m2 < m1:
m1 = m2
m2 = c(i - 1, j - 1, P, Q, ca, N)
if m2 < m1:
m1 = m2
if d_t > m1:
ca[index] = d_t
else:
ca[index] = m1
else:
ca[index] = 1e50
return ca[index]
def frechet(np.ndarray[np.float64_t,ndim=1,
negative_indices=False,
mode='c'] P,
np.ndarray[np.float64_t,ndim=1,
negative_indices=False,
mode='c'] Q):
cdef np.ndarray[np.float64_t,ndim=2,
negative_indices=False,
mode='c'] ca = np.zeros((len(P), len(Q))) - 1
return c(len(P)-1, len(Q)-1, &P[0], &Q[0], &ca[0,0], ca.shape[0])
这是一个例子：
import pyximport; pyximport.install()
from frechet import frechet
import numpy as np
P = np.arange(5, dtype=np.float64)
Q = 2*np.arange(7, dtype=np.float64)
print P, Q
ca = frechet(P, Q)
print ca
print (P[-1] - Q[-1])**2
Tyler Reddy 最近在 youtube 上的 pycon2017 教程中有一个讨论https://youtu.be/ETJc3NfU9aA?t=9540（2:39.00 ），他讨论了在 scipy.spatial 中实现 Frechet 距离。它还没有完成，但他运行了一个他用 Python 包装的实现。