[GIS] How do algorithms load pieces of maps

gmlkey-value-storestoragetiles

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.

Best Answer

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.
Related Question