# How do algorithms load pieces of maps?

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.

-
Hi Nav, Given your comment on my answer, do you mind editing your question to include more detail about the data you have, and the representation you're getting it in? For an example of something with more clarity: "I'm looking to find the three nearest roads/railroads to the mouse pointer. The road data is stored as a list of points and a list of edges that connect pairs of points, which is in turn broken into rectangular datafiles along a tiling scheme..." (This is pure supposition, but that level of detail will make it easier to answer with something other than a guess.) – Dan S. Dec 9 '10 at 16:29
@Dan: Edited. I've also answered my own question below based on something I found. I've heard the Hilbert curve is more 'optimised' than QuadTree (don't know how it's better optimised though). Besides, Berkeleys database seems a quick way of querying for tiles. Comments are welcome if you know about these methods of storage and access. – Nav Dec 10 '10 at 10:15

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)

-

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.
-
I'm not working with tile images. The algorithm I'm writing deals purely with lat-long points. The 'pieces' of maps I'm loading are only sections containing road-networks and/or railroad networks (maybe vegetation boundary vectors much later). The road network within these sections will be processed by my algorithm. I'm sorry if I used the word 'tile' inappropriately. Maybe 'map-section-for-roads' would be more appropriate. – Nav Dec 9 '10 at 6:33
I think "vector segment" might describe your situation. Are your segments the size of what you will load? Are you looking for a way to convert mouse points to lat,lon? – Brad Nesom Dec 9 '10 at 15:23
@Brad: My answer is 'no' to all your questions :) I've edited my question; I guess I didn't ask my question clearly enough. – Nav Dec 10 '10 at 10:16

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.