0
$\begingroup$

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).

$\endgroup$
  • 4
    $\begingroup$ You might be better off with your question if you defined in mathematical terms the problem you want to solve, rather than just in words. $\endgroup$ – Wolfgang Bangerth May 22 '17 at 22:57
  • $\begingroup$ May this help: discrete_frechet. $\endgroup$ – Herpes Free Engineer Jun 8 '17 at 13:42
7
$\begingroup$

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
$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.