Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I was asked this in an interview test. I did okay on the test but didn't know enough to answer this question. I am curious to know what data structures I can use to query the data quickly.

Basically the idea is there would be road sections (lines, made up of points) stored in some kind of data structure. It should be quick to query which road sections (or points) are within a certain distance from a point (radius).

share|improve this question
    
To really learn more, I would read up on: cgal.org, then look at these projects: cgal.org/projects.html#gis, find the one that resembles what you want, and then study the usage of API and finally the makeup of API. –  Job May 3 '11 at 22:55
add comment

2 Answers

up vote 14 down vote accepted

The typical way to store geographic data is with a spatial data structure such as an R-tree (or some variant, such as R+tree, R*tree, etc.) This is how geographic data types are normally implemented in GIS-capable RDBMS. (I know both Microsoft's SQL Server 2008 and PostGIS use R-trees for the geographic types.) They meet all of the basic requirements you've described, and trivially support intersection, location, distance, and other query types.

Depending on the type of data, you may also find such things as kD-trees, quad-trees, octrees, bounding volume hierarchies (including axis-aligned bounding box trees), etc. in common use. This is actually much more commonplace in 3D games, since the size and shape of an object is more relevant to intersection queries. They're less often used for GIS than R-trees.

share|improve this answer
    
+1 for quad-trees and gaming references. –  Machado May 4 '11 at 0:56
add comment

Different kinds of operations upon map data will require different storage formats for optimal results. Consider, for example, the following three tasks:

  1. Given a point, find the road nearest that point
  2. Given a geographical area of a certain size, find all the roads which are within that area.
  3. Given two roads, find the shortest route between them.

The differences in requirements are sufficiently great that unless one will need to accommodate "live" changes to the map, one will likely be better off with storing three separate copies of the data--each optimized for one of the above tasks--than trying to come up with a format which can handle all three tasks well.

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.