I'm in search for an algorithm/data structure which would enable efficient "window query" over a set of rectangles (2D). That is, given many (possibly overlapping) rectangles report all the ones overlapped by a given query rectangle. In 1D, this is known as interval intersection or range overlap. I found two very interesting posts here:
So I was wondering that perhaps someone could have an idea on how to approach this problem. I know about R-trees but perhaps there are some additional suitable data structures?
You'll want to post this to stackoverflow, which has a more CS-centric community. For what it's worth, my go to structure would also be an R-tree (or variant thereof) for this sort of task.
Unfortunately, I cannot think of a way how to make the "intersection" efficient, i.e. better than O(n). What I mean by that is consider the following example:
▢▢▢▢▢▢▢▢▢▢▢▢▢▢▢▢▢▢
and if the window overlaps just one of the rectangles I first would have to report everything along the "x" axis only to discard most of the result in the "y query".
If you really have just rectangles, then perhaps two 1-D indices are all that is needed? An intersection with the rectangle will mean intersection with both the x-extent and the y-extent, each of which can be represented by a 1-D index. There are multiple implementations of very performant 1-D indexing in various languages.
You'll want to post this to stackoverflow, which has a more CS-centric community. For what it's worth, my go to structure would also be an R-tree (or variant thereof) for this sort of task.
Thanks a lot for the reply!
Unfortunately, I cannot think of a way how to make the "intersection" efficient, i.e. better than O(n). What I mean by that is consider the following example:
▢▢▢▢▢▢▢▢▢▢▢▢▢▢▢▢▢▢
and if the window overlaps just one of the rectangles I first would have to report everything along the "x" axis only to discard most of the result in the "y query".