How do algorithms load pieces of maps?

Question

If the user moves the mouse pointer to the top left corner of the screen, I want my software to auto-load the three tiles that are closest to the mouse pointer. My assumptions are that the smaller are the map tiles to be loaded, the lesser tiles I will have to load. The question is,

1. whether there is any existing logic that I can use for this loading (something people have used already, since I need a flexible way to ) and ...
2. ...a flexible way to store the loaded tiles in C++?. My app is in C++, and I'm planning to store each tile as either a class or a struct. Is there an existing way/a better way to do it?

EDIT: Responding to Dan: I'm still in fact-finding stage, and currently only have a map with roads stored as lines, where each line is composed of a list of line segments specified by a starting lat-long and an ending lat-long. I'm open to using any tiling scheme, but in a simple way, I'm visualizing the map to be divided into a grid of small squares, so the squares/tiles close to the mouse pointer and containing road segments should be loaded into memory. My algorithm would then process the loaded tiles to find the angle of the road and to check if the road forms a junction with other roads etc. My algorithm can't afford to wait for too many loading operations from the hard-disk. The priority is knowing how to store information so that I'll have them in the RAM as quick as possible. Whether to pre-calculate the tile area and store the tiles in a database or whether to extract square portions from the map and cache them in the RAM was a decision I was trying to take when I posted this question.

Answer 1

Map tile structures are structured identically to a quadtree, where the root tile has four sub-tiles, each of those has four sub-sub tiles, etc. There's a simple formula to get the path/tilename for the tile you need. (The link describes OpenStreetMap / Tilecache's naming scheme.)

For the n nearest neighbors to a tile at zoom level y, maintain a list of three 'candidate' tiles, then:

zoomlevel = 0
while zoomlevel < y:
   for each candidate tile:
       for each of its four children:
           if the child is one of the closest three seen so far, make it a candidate
   zoomlevel += 1
return the three candidate tiles

WRT data structures/storing the tiles, my suggestions are to:

• (a) generate the quadtree/tile name on demand; since they're identical every time there's no need to actually have in-memory objects to represent them. (It'll waste a huge chunk of memory to store the full tree out to a fairly deep depth..)
• (b) your bigger concern / where you ought to do some thinking is in caching and uncaching the tile images themselves. Hopefully there's a nice component for your platform you can just reuse.

Answer 2

I would suggest you precalculate bounding-boxes for your road-segmensts and store them into a QuadTree structure. In the quadtree you only store the bounding-box and identifier for each roadsegment.

You can then load the complete Quadtree into memory of your client and for each mouse-move query the quadtree what segments are within a given buffer-distance. The result from this query is a list of road-segment id:s, these id:s can then be used to load segments from your backend into memory.

Querying a QuadTree is a fast operation that can be done for every mousemove...

The memory footprint of a QuadTree is quite linear against the number of roadsegments you have.. (depending on implementation you need about 5-10 integer values per road-segment)

Answer 3

I didn't see anything about C++, but tilecache.org may be what you are looking for. Or possibly more info here (openlayers)? Not sure if you are looking for this type of information or not.

Sorry the second link is a link to a mail archive with a link. Bad posture but...

Answer 4

I've just come across something called the Hilbert Curve which is similar to QuadTree. Better than having server-based databases, is to have a database on the hard-disk, with embedded queries (means that queries are available as libraries, and will be embedded with the exe). This makes queries faster. Your entire database is stored as a single file, which makes it easier to manage.

I haven't tried any of the above; just put it up here to hear from you if this is a good way to do it or so that this may help someone.