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:
To query the window, first perform a 1D query in the X dimension, then
perform a 1D query in the Y dimension. Intersect the two query results
to get the 2D result.
The vertical rectangle represents the result of the X range query, and the horizontal rectangle represents the result of the Y query.
Problem! With this naive method, we are still getting too
many unneccessary segments out of the query. To get the segments in
the region we are interested in, we need to process much more segments
than we actually care about. We should use a real 2D structure...like
a kD tree. There are also many other variations of search trees, see
de Berg for details.