turn left turn right commands in map [closed]

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 8 years ago.

I have implemented a code that uses Dijktra's Algorithm. Thanks to Dijkstra I can print the shortest path from the desired source to desired destination. However, what I want to do is to add a feature that tells us directions with turn left , turn right commands.

Examples:

From A to D:

Let's say A is located in street 1 , B is located at street 2 and D is located 60 meters left of the street 2.

From A to D:

Go to Street 2 . Turn left . Go about 60 meters .It will be on your left.

I need your ideas. Thank you!

Answer 1

To generate driving instructions from a path, you need to store additional information with the graph:

For each road, its length. This is straightforward

For each crossroad, the relation between each pair of incident roads.

You could store the azimuth of each road around the crossroad (road 1-2 goes west from intersection 1), then generate the driving instructions from the relative angle between two roads, type of the crossroad (normal / roundabout) and the topological ordering and relative angles of all other roads.

This approach has the benefit of more compact representation, but it needs more programming.

Alternatively, you could store the relation between each pair separately. This is more reliable (only a human could truly comprehend the complexities of each possible crossroad type in the world), but it's more manual to update (after all, a little AI could in theory defer the crossroad type, even if with errors).

If you have a huge map, you'll want to stick to the first approach. If you are building the map manually, you may prefer the second one - just be sure to not actually store strings with each road pair (unless they're interned by the language), or your memory demands might skyrocket. This needs extra attention when serializing the map to a file (again, a ZIP compression might alleviate that to a great extend, if you opt for that).

If your map is only concerned about simple 4-way crossroads, then the information stored with each pair is simply a left/straight/right enum (approach #2), or just an ordering of the edges around the crossroad (approach #1) where some roads may be null.

For example, your crossroad could (simplest case, approach #1) look like

private Road[] roads = new Road[4];

public enum Direction{
  Left, Straight, Right, Back;
  // utility methods
}

public Direction getDir (Road from, Road to){
  // input checking stripped for clarity
  int iFrom = roads.indexOf(from);
  int iTo = roads.indexOf(to);
  // more input checking
  int iDiff = (iFrom - iTo) % 4;
  if(iDiff < 0) iDiff +=4 ;
  return Direction.getRelative90(iDiff);
  //Direction.getRelative90 is just a switch statement.
}

For generating the directions, use the information stored with the map. Remember to concatenate roads (sum up their lengths) that logically follow (no instructions at that intersection = implicit "go straight" - several roads might follow into one, but only one should follow from each), the rest is straightforward.