Application: Searching Maps
How do we determine some subset of a 2D map to draw on a screen, without searching the whole map? For instance, we have an in-car navigation system, with limited CPU power, but a street level map of the whole state. We want to display the streets in our immediate vicinity on the car's display screen.
We can treat the map as a collection of line segments on a plane. Even more complicated structures can be broken into segments.
Problem: Given a rectangular window region defined by two points, p1 (top left) and p2 (bottom right), return all segments from some global set that intersect this window.
Naive solution: We can construct a 1D interval tree for each dimension, using the projection of each segment onto the X and Y axes respectively:
Read full article from Two dimensional binary searching
No comments:
Post a Comment