Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

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.

share|improve 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
add comment

4 Answers

up vote 1 down vote accepted

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)

share|improve this answer
add comment

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.
share|improve this answer
    
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
add comment

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

share|improve this answer
    
Thanks, but I'm not working with tile images. Am working exclusively with the nodes of a road network. All my algorithm needs to know is which road-nodes are present in a certain region which I wish to load. My question is how these points will be stored (In C++) and recognized as squares or sections of the map. I'm sure there would be an efficient way to do it... –  Nav Dec 9 '10 at 6:37
    
If I read right here - You might index your nodes against the map sections. You have not described your data storage, perhaps that would help someone know which direction to advise. –  Brad Nesom Dec 9 '10 at 15:26
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.