Python implementation for Frechet Distance

Question

I am working on a trajectory analysis project using python and its data science related libraries. I am planning to implement Frechet Distance algorithm for trajectory analysis, each trajectory has sequence of (x,y) coordinates along with timestamp, speed, dist between consecutive points, etc.

I would kindly request if anyone who has experience with in this field and trajectory analysis, can provide with some useful links for Python implementation of Frechet Distance. My ultimate goal is to cluster the similar trajectories (location and direction wise).

Answer 1

I realize this question was asked a while ago, but I recently needed the Freschet distance as well. I couldn't find any implementations for Python, so I wrote my own based on the paper: "Computing Discrete Frechet Distance" by "Thomas Eiter and Heikki Mannila", and thought I would share it for future reference.

It's written in Cython (save as 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])

Here's an example:

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

Answer 2

There is a discussion in Tyler Reddy's very recent pycon2017 tutorial on youtube https://youtu.be/ETJc3NfU9aA?t=9540 (at 2:39.00) where he discusses implementing the Frechet Distance in scipy.spatial. It is not done yet but he runs an implementation that he has wrapped in Python.