Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

I am looking for a description of algorithm which allows me to detect key turning points on the road amongs a set of all given points.

I've ilustrated my problem on the below image:

Green spots: those are the starting and ending point of a route.

Blue spots: those are the key points which should be detected by the algorithm.

Red dots: This is the data about the road that has been driven.

Could someone point me to the algorithm name or publication that deals with this problem?

Thanks in advance.

Road

share|improve this question
1  
Is this part of a homework assignment? –  Aron Ahmadia Jun 13 '12 at 11:57
    
No, I've finished school quite a while ago ;-) –  Wodzu Jun 13 '12 at 12:36
    
In that case, please give us a little more context. The problem and level of detail you've presented so far is something that is routinely covered in introductory Artificial Intelligence and even Calculus courses. If you're stuck, I suggest you look up critical points and think about how they or the derivative of your vector-valued function $(x,y) = f(t)$ might help you isolate the points of interest. –  Aron Ahmadia Jun 13 '12 at 13:20
    
Thank you Aron. I wanted to abstract the problem as much as possible. To give you more detail: I have in my car a device which records (with a given interval) geographical coordinates of its (car) position. There is like 2000 such points(red dots) per route. Now, basing on this data I would like to extract critical points(blue spots) and pass them to GPS device which is planning a route. You can call the blue spots a waypoints that must be visited when planning a route via GPS. Hope it is more clear now? –  Wodzu Jun 13 '12 at 13:42
    
Any time you have a critical turning point, there is a near 90 degree turn, with respect to the past 5 or so data points. Have you tried incorporating this into your detection algorithm? –  Paul Jun 13 '12 at 14:12
show 3 more comments

2 Answers 2

You can combine the turning information (derivative of x/y over time) with speed information (derivative of position over time). The rationale is that on critical points you need to slow down and then accelerate again.

But the best way would be, as Aron said, to compare your path with a map and detect when you have passed a crossing.

BTW, do your key points really need to be turning points? The GPS navigator should be able to find the turning points itself when you supply it your vias.

share|improve this answer
    
Thanks, as to first paragraph of your answer: this will work unless car is moving with a constant speed. But the idea with crossing detection might work. My key points do not have to be the turning points, but the GPS navigator should construct the same route as the one which is marked by red dots - streets that vehicle will be driving on should be the same. –  Wodzu Jun 14 '12 at 9:35
    
As I see it, you are solving two problems: 1. error correction (mapping red dots to streets), and 2. data compression (choosing a minimal subset of your points sufficient to describe the route). So that's how I'd try to solve them: First find out (by comparing with the map) which street you are on and then pick some points on that street. Taking only the crossings where you took a turn might not always work, however, because there might be alternative routes, including additional turns which are faster, so your GPS could choose them. –  Igor F. Jun 14 '12 at 10:06
add comment

@Wodzu: this is a problem from radar data processing for tracking generally unfriendly items. Try searching for algorithms like IMM (interacting multiple models). Book "Adaptive Filtering and Change Detection" by Gustafsson (ISBN 0471492876) gives quite a bit of useful background on the field in general.

In general (zero apriori information on likely routes) case you would use Kalman filter; however, for a road network you can deduce several hypotheses on where the car is going, and IMM (and its sister algos) based on continuous pathfinding solutions would be of more value here. If you don't have to be real-time and have the whole dataset handy, there exist even better statistical techniques (see a bunch of Q/As at Cross-Validated SE).

EDIT: What I have left out at first: GPS does not have a neat error distribution, please be aware that there are some nasty properties (both in position and velocity errors).

share|improve this answer
    
Thank you for your answer. I need to analyze historical data (red dots) so there is no need for real time processing and I have all the data which I need. I'll try to find the book you recommended to me, thanks. +1 –  Wodzu Oct 29 '12 at 15:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.