Datastructure for googlemap like application?

Question

Hi

I am doing a maprouting application. Several people have suggested me, that I do a datastructure where I split the map in a grid. In theory it sounds really good, but I am not to sure because of the bad performance I get when I implement it.

In the worst case you have to draw every road. If you divide the map in a grid, the sum of roads in all the cells in the grid, will be much larger than if you put all roads in a list.(each cell must have more roads than actually needed if a road goes through it).

If I have to zoom in I can see some smartness in using a grid, but if I keep it in a list I can just decrease the numbers of roads each time I zoom in. As it is now(by using the list) it is not really fast, so I am all for making it faster. But in practice dividing in a grid makes it slower for me.

Any suggestigion for what datastructure I should be using and/or what I might be doing wrong?

Answer 1

If you want it to go quick, you might be better off organizing your roads in to major and minor roads.

Use the list of minor roads to find a route to the nearest major road. Use the major roads to get you near the destination. Then go back to the minor roads to complete the route.

Without a split like this, there are a heck of a lot of roads to search, most of which are quite slow routes.

Answer 2

google does not draw each road every time the screen is refreshed. They used pre-drawn tiles of the map. They can redraw them as needed. e.g. when there is a map update. They even use transparent overlays, stacks of tiles to add and remove layers of details.

Very clever, but very simple.

You may want to look at openlayers javascript library. Free and can do just about anything you need to do with a map.

Maptraction JS is also available - its not as complete as OpenLayers

Answer 3

See this question for related information:

http://stackoverflow.com/questions/430142/what-algorithms-compute-directions-from-point-a-to-point-b-on-a-map

Somebody who writes this kind of software for a living has answered it.

Also for rendering see:

http://stackoverflow.com/questions/222716/what-is-the-best-way-to-read-represent-and-render-map-data

I'm not quite sure if you're trying to do routing quick or rendering!

Answer 4

More optimal then using a grid as your spatial data structure, might be a quadtree because it logarithmically breaks down the map. And from studying the source, my guesstimate is that google uses (that or) a similar data structure.

As for getting directions, you might want to look in to hierarchical path finding to approximate the direction at first and to speed up the process; generic path finding algorithms tend to be quite slow at that level of complexity.