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
|