[prev] 26 [next]

Query with R-trees

Designed to handle space queries and "where-am-I" queries.

"Where-am-I" query: find all regions containing a given point P:

  • start at root, select all children whose subregions contain P
  • if there are zero such regions, search finishes with P not found
  • otherwise, recursively search within node for each subregion
  • once we reach a leaf, we know that region contains P
Space (region) queries are handled in a similar way
  • we traverse down any path that intersects the query region