Seeking Fréchet distance implementation (Python) to cluster trajectories by similarity

Question

I am working on a trajectory analysis project using Python and its data science related libraries.

I am planning to implement Fréchet distance algorithm for trajectory analysis, each trajectory has sequence of (x,y) coordinates along with timestamp, speed, dist between consecutive points, etc.

I am seeking to implement Fréchet distance to compare each trajectory with another and group the similar curves/trajectories together and form different clusters.

I would like to have some suggestions on this.

Also, I am open to other similarity measure methods like "Dynamic Time Warping" or "Longest common subsequence".

Answer 1

Interesting, haven't seen the Fréchet distance before (it seems to be the equivalent of Hausdorff distance, but for lines rather than polygons)

It looks as if there may be an implementation in the MDAnalysis library.

However, this library appears to be for analysing movements of molecules ... it's python built on numpy, but is not designed for geospatial.

It's open source, though, so you might be able to adapt its algorithms for your requirements.

Answer 2

GEOS (and therefore PostGIS) also has Frechet distance. I imagine that you can use its python interface - (pygeos).

Note that pygeos has been merged with Shapely and released as part of Shapely 2.0. So, Frechet distance is now available through Shapely.

Answer 3

A Python package has included Frechet distance with implementation using Python. https://pypi.org/project/similaritymeasures/