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?


2 Answers 2


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.

  • 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
    Commented Jul 25, 2010 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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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