Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.
Sign up to join this community
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).
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.
Different kinds of operations upon map data will require different storage formats for optimal results. Consider, for example, the following three tasks:
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.
