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

clusteringdistancepythonspatial-cluster

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

Best Answer

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.

Related Solutions

[GIS] Test case for geo-distance implementation

To design a test, you need specifications. For this kind of work that would mean, at a minimum

Quantifying the accuracy to expect of the result.
Indicating the domain of the function: that is, over which longitudes, latitudes, and distances it is designed to operate.

For instance, the method in the presentation you reference will fail when trying to find points near either pole. More subtly, it might fail for non-small distances: when the distance is great enough to change the cosine of the latitude appreciably, watch out!

To really stress an algorithm, there's nothing like analyzing it to find its weak points. In addition to problems at the poles and with non-small distances, a check of the formulas suggests it will have problems at points near the periphery of the search radius, due to the crude approximations used (69 miles for one degree and a spherical earth model with radius 3956 miles). This is why you must specify the intended accuracy in order to design a useful test.

For some applications--especially those mentioned in the presentation--these limitations are unimportant. That means you won't have to test them!

Because this approach relies heavily on the built-in SQL capabilities, you ought to consider assuming they work correctly. (Otherwise we're talking about testing your SQL implementation, which is a different and much more ambitious project.) With this assumption, and assuming you can live with the inaccuracies and limitations built into this approach, the principal thing to test is that the pre-screening by a rectangular search doesn't eliminate points that should be included in the result. In addition to carefully chosen cases to test for this, consider creating random datasets: there's nothing like random data to uncover problems nobody has ever even thought of. I would favor randomly picking a valid (lat, lon) for a central location, randomly picking a valid distance, randomly populating a large number of nearby (lat, lon) points and a large number of other points scattered all over the globe, and comparing the output of your procedure to output generated by a GIS using accurate formulas (or at least to a brute-force computation of all the distances).

QGIS Analysis – Find Mean Distance Between Cluster Center and Points

On the layer with the center point, you can use QGIS expressions. Get an array of the points from the same cluster using array_foreach and then for each of these points create create a line to the center and get it's length. You get an array of lengths. With array_mean, calculate the mean. This is how the expression looks like:

array_mean (
    array_foreach (
        overlay_nearest('points', $geometry, limit:=-1),
        length (
            make_line (
                $geometry,
                @element
            )
        )
    )
)

Based on the data you have and how it is structured, you have to include a condition so that only points belonging to the same center are considered.

From the red center point, the expression generates a line to each of the white dots from the points layer, measures the length and gets the mean. The lines itself that you see here are generated with an expression based on this one with Geometry generator, see on the right side:

Best Answer

Related Solutions

[GIS] Test case for geo-distance implementation

QGIS Analysis – Find Mean Distance Between Cluster Center and Points

Related Question