# Similarity between two or more trajectories

I have the data of trucks (http://www.chorochronos.org/).

This data are gps coordinates of multiple trajectories of trucks in Athens.

I have to calculate the similarity between the trajetories, in order to delete those that are very similar!

Red And Green are similar, but blue, black and (red or green) are different trajectories. I want to delete one of the similares, red or green.

Data are in points (geometry , lat and long , x and y)(coordinates gps), the image are examples of trajectories

• What happens if red and green are similar, and green and black are similar, but red and black are not similar? Also, how do you define "similar" - is it a proportion of the line falling within a distance of the other line, or some other metric? – phloem Oct 7 '14 at 23:00
• I just want to stay with trajectories that are different from the others. The trajetories are gps coordinates, not lines... – user2883056 Oct 7 '14 at 23:33
• You have tags for postgis and postgresql but do not mention either in your question body. While tagging is important, if you are using those products, I strongly recommend recording them in the body of your question because, after glancing at the title, this will be the section of your question that gets all the attention. – PolyGeo Oct 7 '14 at 23:46
• I agree with @phloem - the key question is "how do you define similar"? All routes go from A-B, so they are 'similar' in that sense. You need to provide more information on how you'll evaluate a successful outcome – Stephen Lead Oct 8 '14 at 1:33

A really easy, but not fantastic measure is to get the Hausdorff distance between each combination, which is done with the ST_HausdorffDistance function. Using approximate LineStrings from your figure, these are all shown in blue, and the Hausdorff distance is shown for one of the pairs of lines in red:

And the query to sort the 6 combinations in descending order:

``````WITH data AS (
SELECT 'blue' AS name, 'LINESTRING (60 200, 110 290, 200 320, 330 320, 430 240, 450 200)'::geometry AS geom
UNION SELECT 'black', 'LINESTRING (60 200, 120 270, 235 297, 295 207, 450 200)'::geometry
UNION SELECT 'green', 'LINESTRING (60 200, 280 190, 450 200)'::geometry
UNION SELECT 'red', 'LINESTRING (60 200, 150 210, 257 195, 360 210, 430 190, 450 200)'::geometry)
SELECT a.name || ' <-> ' || b.name AS compare, ST_HausdorffDistance(a.geom, b.geom)
FROM data a, data b WHERE a.name < b.name
ORDER BY ST_HausdorffDistance(a.geom, b.geom) DESC;

compare     | st_hausdorffdistance
-----------------+----------------------
blue <-> green  |                  130
blue <-> red    |                  125
black <-> blue  |     110.102502131467
black <-> green |     104.846289061163
black <-> red   |     97.9580173908678
green <-> red   |     15.2677257073823
(6 rows)
``````

So it works fine for this example, but it isn't a great or robust technique for clustering lines, since the only metric is the single point with the greatest distance, rather than comparing the differences of complete lines. There are much better methods, but they will be more complicated.

• Nice answer. I would have probably used something like ST_Interpolate point and then calculated the average distances for each set of related points as a naive approach. What did you have in mind by much better methods? – John Powell Oct 8 '14 at 10:53
• @JohnBarça better methods would be to compare spatial statistics of the coverage of each line. One method would rasterise each line, do a Gaussian blur with the raster, then determine the correlation of coincident raster values from each combination. A method based on ST_Segmentize and ST_Interpolate tools would work too. – Mike T Oct 8 '14 at 19:54

I don't have access to PostGres/PostGIS, but here is how I would go about it in ArcGIS (or other).

1. Calculate the length of the original lines into a static column
2. Buffer your lines according to how you define "similar". Do not dissolve buffers. Resulting buffers will have FID equal to original line.
3. Intersect buffers and original lines. Resulting layer will identify FIDs participating in that particular intersection (for example, "FID_lines" and "FID_buff").
4. Dissolve layer from #3 by the two original FID columns and the original length column
5. Ignore resulting lines which have the same value for the two original FID columns using a definition query, or other means (of course a line buffered and intersected with its own buffer will fully overlap).
6. Add a numerical column and populate it with the new length
7. Divide the new length with the original length (into a new column) to get a ratio of the original line that falls into the buffer of each nearby line.
8. Inspect the values for the ratio. Keep those that you have defined as "similar enough". For example, perhaps a line falling within the buffer of another line for 75% of its length is similar enough, perhaps your cutoff is 50% agreement, etc.