# Determining similarity between paths (sets of ordered coordinates).

With limited knowledge of mathematics, I am not sure what tags to use for this question.

I have a path on a 2D surface called $(p1)$. A path consists of a set of ordered $(x,y)$ coordinates. By ordered I mean the first line segment in a path would be $(x1,y1) to (x2,y2)$, the second line segment would be $(x2,y2) to (x3,y3)$ and so on. So these ordered points create a shape and direction of travel similar to what you would see on top-down Google Maps view.

I need to match this path $(p1)$ against some other arbitrary paths to determine which one is the closest to the original path $(p1)$ in terms of shape and direction of travel. The number of line segments making up each path could be arbitrary by the way so there needs to be a way of handling tolerance.

Not sure what this is called but I have explored some LQE techniques such as the Kalman Filter in vain. What I am looking for is analysing a static set of ordered points against another rather than progressive prediction.

I am not sure what constructs can represent similarity between paths. Any guidance would be highly appreciated.

• You could use the Fréchet distance, but that might be too generic. What do your paths represent? – Chris Culter Aug 2 '13 at 22:01
• Thanks @ChrisCulter. The original paths $(p1,p2, etc.)$ represent the expected path of travel for vehicles. This is hand-drawn over a map. The arbitrary paths are actual vehicle coordinates. So I need to take each vehicle and determining which predefined path is it most likely travelling on. – Raheel Khan Aug 2 '13 at 22:46
• @ChrisCulter: Could you elaborate how to go about implementing this measure as an algorithm. It seems to be what I am looking for but mathematical notation is beyond me. A little narration would go a long way. Thanks in advance. – Raheel Khan Aug 2 '13 at 22:51
• You could also try the Hausdorff distance, which is much easier to implement (here's pseudocode, though it needs modification to work for non-convex polygons). The main difference is that the Fréchet distance considers backtracking, so if I go back and forth on some part of the path, it increases my Fréchet distance but not my Hausdorff distance to the path. – Rahul Aug 3 '13 at 4:44
• Sure, the Hausdorff distance is incredibly general. It works for closed polygons, open paths, filled shapes, and in fact arbitrary sets of points. The only computational primitive you need is to be able to compute $d(x,Y)$, the distance from an arbitrary point $x$ in the plane to its nearest point on a shape $Y$. – Rahul Aug 4 '13 at 8:34