Comparing a "path" (or GPS trail) of a vehicle.

Question

Hi Guys,

I have a bit of a difficult algorithm question, I can't find any suitable algorithm from a lot of searching, so I am hoping that someone here on stackoverflow might know the answer.

I have a set of x,y coordinates for a vehicle as it moves through a 2D space, the coordinates are recorded at "decision points" in the time period (i.e. they have stopped and made a determination of where to move next).

What I want to do is find a mechanism for comparing these trails efficiently (i.e. not going through each point individually). Compounding this is that I am interested in the "pattern" of their movement, not necessarily the individual points they went to. This means that the "path" is considered the same if you reflect it around an axis, or if you rotate it by 90,180 or 270 degrees.

Basically I am trying to distil some sort of "behaviour" to the way they move through the space, then examine the different "behaviours" for classification purposes.

Cheers,

Aidan

Answer 1

Hey,

This may be way more complicated than you're looking for, but it sounds like what the guys did at astrometry.net may be similar to what you're looking for. Essentially, you can upload a picture of some stars, and it will figure out the position in the sky it belongs, along with rotation, you may be able to use similar pattern matching in what you're looking for.

They have a great pdf explaining how it works here, and apparently you can email them and they'll send you the source code (details are in the pdf).

Edit: apparently you can download the code directly here.

Hope it helps.

Answer 2

there are several approaches you could make:

Using vector paths and translation matricies together with two algorithms, The A* (a star) algorithm ( to locate best routes from what are called greedy functions ), and the "nearest neighbour" algorithm --- these are both commonly used for comparing path efficiencies for routes.

you may not know it but the issue you have is known as the "travelling salesman" problem and has many many approaches.

so look up

traveling salesman problem A* Nearest neighbour

also look at

Random walk algorithm - for the most basic approach

for a learned behaviour approach try neural networks "ANN" or genetic algorithms

the mathematics for this type of problem are covered under what is called "graph theory"

Answer 3

It seems that basically what is needed is some metric to compare two(N in general) paths and choose the best one? If that's the case then I'd suggest plain statistics. I'd start with heading(orientation) histogram, relative(relative to previous heading) heading histogram and so on. Other thing comes to mind - distance/orientation between points covariance. Or just simply make up some kind of "statistics"(number of turns, etc.) and compare those paths using that.