Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If I use a quad-tree to index my map data, how does it cope with a road that goes from one end of the map to the other?

What other sort of indexes should I consider to get round this problem?

share|improve this question
i think you mean quad-tree? – matt wilkie Jul 23 '10 at 22:59
up vote 4 down vote accepted

It would depend on the spatial distribution. I would recommend quad-tree only for a somewhat uniform data set such as parcels for an inner city region. If you have concentrations of small features in certain areas I would go with a more dynamic tree structure such as an r-tree. There are even cases where depending on the data it may be better to not index spatially at all such as when the time to rummage through the index is greater than just going over each feature individually checking MBRs or when the majority of features are within the restrictive bounds for a majority of the requests.

share|improve this answer
Agreed; R-tree & derivatives generally beat out quadtrees etc for spatial types that can't be abstracted as point features. Wikipedia as usual has a decent intro to the topic – WolfOdrade Jul 25 '10 at 18:53

You can store the points forming the road each in the proper quadrant on the quadtree. You can then search for the pieces of the road you are currently interested in, as there's usually no need to retrieve the whole road.

You'd have to use an additional map to store the metadata for the road, and have a little info duplicated (the map key) on each of the road points. That map can contain a pointer to all the points of the road, in case you need to operate on the whole line instead of a subset.

share|improve this answer

Your Answer


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.