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.

Following is the example df with "voygID" and respective x, y coordinates. (I am not including timestamp, speed, etc columns here, as I assume it wont be required in implementing Frechet distance)

     voygID         x             y
 0   1             -7.935513     5.103579
 1   1             -7.935781     5.103300
 2   1             -7.936354     5.102726
 3   1             -7.935915     5.102802
 4   2             -7.935306     5.103424
 5   2             -7.945678     5.119876
 6   2             -7.954764     5.128738
 7   3             -7.954888     5.138898
 8   3             -7.955897     5.149808
 9   3             -7.965789     5.156789
 10  3             -7.983457     5.198610

In the above data frame (x,y) forms the coordinate data and all the points belonging to the same "voygID" forms one separate trajectory; Therefore in the above df rows(0-3) belonging to voygID = 1 is one trajectory, while points belonging to voygID = 2 is another trajectory and so on. There are thousands of trajectories each with 100s of points.

Now, I want to implement Frechet Distance to compare each trajectory with another and group the similar curves/ trajectories together and form different clusters.

I would kindly request if anyone who has experience in this field, can provide with some useful links for Python implementation of Frechet Distance to do the above task.

Also, I am open to other similarity measure methods like "Dynamic Time Warping" or "Longest common subsequence". Please suggest me if there are preprogrammed python implementations are available.

  • $\begingroup$ Check the module spatial in SciPy, I have used it to compute Haussdorf distances before. $\endgroup$
    – nicoguaro
    May 24 '17 at 4:35