Drawing Routes with iPhone

Question

Hi there,

I am trying to make an iPhone application which can draw a path between two points (similar to Google Maps) but instead of the map i want to use any other image as a background, this path between the two points might not be straight and there might be multiple paths to get from one point to another then I want to draw the shortest path between the two points.

I tried using the CGContext & CGPath but I got stacked.

Can you help me plz.

Thanx,

Ghaith

Answer 1

I think you're looking for UIBezierPath. You can add simple lines/polygons with something like:

UIBezierPath* path = [UIBezierPath bezierPath];
[aPath moveToPoint:CGPointMake(50.0, 50.0)];
[aPath addLineToPoint:CGPointMake(10.0, 10.0)];
[aPath addLineToPoint:CGPointMake(10.0, 50.0)];
[aPath closePath];

You can also, of course, add curves (bezier ones!) and other shapes. Then to draw it use the [aPath stroke] call in your view's drawRect method.

For more information see the iPad Programming Guide

Answer 2

Thanx samkass for the answer, I know about UIBezierPath and how to use it, but I might didn't explain what I exactly need. my application is similar to a Map but with an image in the background which is replacing the map, in that image i have only some dedicated areas that can connect the two point (similar to roads in a Map) and when connecting two points I want the Path to be through these drawable areas only.

Hope that explains clearer what I need and thanx for the help again.

Ghaith

Answer 3

This seems like a problem that's not really related to drawing the route.

You want to find the shortest path from one point to another, given certain criteria - where you can and cannot move, for example. I don't see this problem as something you can solve with drawing, but with actually calculating the different possible ways and then compare them. When you have decided which is the best route. Drawing is pretty simple.

How you would go by deciding I'm actually not sure - sorry 'bout that. But you should probably have a look at some shortest path algorithms. But that probably means you have to represent the underlying image as a pattern, or a series of nodes but graphical problems are not my cup of tea, so I'm not really sure how.

Just a side note - If the number of possible ways of getting from point A to point B are great, this can become a computational problem, and you have to make sure that the iPhone can manage.

(this should probably be a comment somewhere, but since I can't yet and I still wanted to share my two cents, it became an answer.)

Edit:

I just thought of really naive aproach! - for fun mostly, but I couldn't keep myself from posting.

Suppose you have a representation of the image. What parts can't be traveled on and what parts can be. Each pixel that can be travelled on is represented by a 1, and every other pixel is represented by a 0. Thus the pixels represented by 1s can be seen as nodes on which we can travel.

Each node can reach, at most, 8 other nodes - the adjacent pixels. And the weight of travelling between any two nodes could be set as 1. But we have to account that travelling in a diagonal is a greater distance so that weight should be sqrt(2).

Now we have a great bunch of nodes - each with weights in between them. From here we can apply a djikstra-algorithm to find the best route. (maybe some other algorithm is more beneficial at this point - but djikstras is the only one I'm familiar with).

hum, wonder how bad of a solution this would be. ... again, you probably don't want this solution...

EDIT 2:

I will say this again that this is probably not the best way to do this! You should seriously ask someone with more experience in algorithms and in graphical problems. - This was something I thought of at 3am and was mostly for laughs.

Answer 4

Hi Storm,

Thanx alot for the answer and the idea u came with, let me tell u here what I have done in the past few hours:

I put an image in the background, Using CGContext and CGPath in Objective-C i hard coded the areas that can be a part of any path later on, let us call these areas as Walkable Areas. Now let's assume that I want to go from Point A (140,100) to Point B (240,200), these two points are connected through many straight lines. to know the shortest path, I am going through all the possible paths, I am doing so by checking all the points that are surrounding the current point A (140,100) then I am checking [ (139,99), (139,100), (139,101), (140,99), (140,101), (141,99), (141,100), (141,101) ], and registering in an array all the possibilities and then calculating the shortest path by checking the minimum count of points to connect A and B and then draw the path using CGPath, which worked great with me. but that is useful only when the connection between A and B is with straight lines, if I have to cover the diagonal lines which can be in any angle then here is the big MISS, how I should scan all the pixels surrounding a point? I will be almost in an endless loop and the calculation time will be in hours (that if iPhone memory can handle it).

Anyway, for sure I have to read about the alogarithm you told about, but just wanted here to tell my story and how it is progressing.

Thanx.

Answer 5

If your question is about calculating routes instead of drawing routes, that's a whole different problem. The standard algorithm for finding efficient routes through a given space are the "A*" (pronounced A-star) algorithms, which are typically what real-time strategy games use when you click a unit and tell it to "go there". It's also got many uses in AI when searching for a transition through a space.

It's not easy to get right, though. It might be easier to find a good game engine that already includes an A* implementation and integrate that into your software.

Answer 6

Thanx to all, I already resolved it by using CGPath and CGContext, I will be posting the code after the final touches and testing.