3
$\begingroup$

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

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Is this part of a homework assignment? $\endgroup$
    – Aron Ahmadia
    Commented Jun 13, 2012 at 11:57
  • $\begingroup$ No, I've finished school quite a while ago ;-) $\endgroup$
    – Wodzu
    Commented Jun 13, 2012 at 12:36
  • $\begingroup$ 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. $\endgroup$
    – Aron Ahmadia
    Commented Jun 13, 2012 at 13:20
  • $\begingroup$ 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? $\endgroup$
    – Wodzu
    Commented Jun 13, 2012 at 13:42
  • $\begingroup$ 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? $\endgroup$
    – Paul
    Commented Jun 13, 2012 at 14:12

2 Answers 2

Reset to default
3
$\begingroup$

@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).

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – Wodzu
    Commented Oct 29, 2012 at 15:49
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Wodzu
    Commented Jun 14, 2012 at 9:35
  • $\begingroup$ 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. $\endgroup$
    – Igor F.
    Commented Jun 14, 2012 at 10:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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