Programming Turn-by-turn Navigation

dejo · Jan 21, 2013, 02:04 PM

I'd like to look into programming some turn-by-turn navigation, or as I like to call it: navigation tracking. That is, you have a route, how do you detect that the user stays on that route. Does anybody know of any good resources that go into algorithms and such for this? Is rolling-your-own completely nuts? Thoughts? Suggestions?

KoolStar · Jan 21, 2013, 02:36 PM

I might look into some of the open source mapping items such as open maps or some other providers. Some have build libraries that you could look at to get an idea.

xArtx · Jan 21, 2013, 04:30 PM

You took a turn that does not end at the next node expected in the route that
was found and stored with the recursive algorithm that found the shortest route
(before one way streets, and tolls etc. enters into it).

I don't know what liberty you have with Apple maps, but if it's your own GPS
program, the difficulty is in the auto routing, and maybe lock to road depending on the platform,
not checking the user is on the route.

dejo · Jan 21, 2013, 04:41 PM

Quote:

Originally Posted by xArtx

I don't know what liberty you have with Apple maps, but if it's your own GPS
program, the difficulty is in the auto routing, and maybe lock to road depending on the platform,
not checking the user is on the route.

I've found solutions for routing; it's for the tracking that I don't find a lot of information readily available.

xArtx · Jan 21, 2013, 05:09 PM

So as you're following your route, your program is checking off each node
as it is passed at every intersection where a turn is required.
Ignore points in a polyline that only represent bends in the road and not intersections.

At least for Garmin maps (and I suspect every other data map), roads that
intersect or join always have exactly the same coordinates where they meet,
so your node list can be a structure containing the coordinate pairs for intersections of the route.

http://computer.howstuffworks.com/ro...algorithm3.htm

In the above example, the preferred route is A,B,D,E.
If you took the wrong turn at node D, and headed back toward node C,
it is easy to determine you are on a line (road) that does not connect node E.
Your GPS doesn't check that you took a left turn at node D,
it checks that you are still connected to the path that ends in the next node.

I think a commercial GPS gives a little bit of time to reroute to allow for GPS
error which is ok because you weren't going to do a 180 on the road and head
back in most cases. you need to reroute from node C.

Jan 21, 2013, 02:04 PM	#1
dejo Demi-God (Moderator) Join Date: Sep 2004 Location: Colorado	Programming Turn-by-turn Navigation I'd like to look into programming some turn-by-turn navigation, or as I like to call it: navigation tracking. That is, you have a route, how do you detect that the user stays on that route. Does anybody know of any good resources that go into algorithms and such for this? Is rolling-your-own completely nuts? Thoughts? Suggestions? __________________ My iOS Apps: a.k.a., DreamStream I support the MacRumors Blood Drive!
	0

Jan 21, 2013, 02:36 PM	#2
KoolStar macrumors Demi-God Join Date: Oct 2006 Location: Kentucky	I might look into some of the open source mapping items such as open maps or some other providers. Some have build libraries that you could look at to get an idea. __________________ 2.4 MacBook Aluminum 480GB SSD/750GB Optibay 8GB RAM CE \| MacBook 2.4 SR 4GB, 320GB HD \| PB G4 1.67 \| 15 TiBook-DVI 800 iPhone 4S 16GB \| iPhone 5 32GB
	0

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Jan 21, 2013, 04:30 PM	#3
xArtx macrumors 6502 Join Date: Mar 2012	You took a turn that does not end at the next node expected in the route that was found and stored with the recursive algorithm that found the shortest route (before one way streets, and tolls etc. enters into it). I don't know what liberty you have with Apple maps, but if it's your own GPS program, the difficulty is in the auto routing, and maybe lock to road depending on the platform, not checking the user is on the route.
	0

Jan 21, 2013, 05:09 PM	#5
xArtx macrumors 6502 Join Date: Mar 2012	So as you're following your route, your program is checking off each node as it is passed at every intersection where a turn is required. Ignore points in a polyline that only represent bends in the road and not intersections. At least for Garmin maps (and I suspect every other data map), roads that intersect or join always have exactly the same coordinates where they meet, so your node list can be a structure containing the coordinate pairs for intersections of the route. http://computer.howstuffworks.com/ro...algorithm3.htm In the above example, the preferred route is A,B,D,E. If you took the wrong turn at node D, and headed back toward node C, it is easy to determine you are on a line (road) that does not connect node E. Your GPS doesn't check that you took a left turn at node D, it checks that you are still connected to the path that ends in the next node. I think a commercial GPS gives a little bit of time to reroute to allow for GPS error which is ok because you weren't going to do a 180 on the road and head back in most cases. you need to reroute from node C.
	0


MacRumors Forums > Apple Systems and Services > Programming > iPhone/iPad Programming