Question: 2D range overlap (window query)
1
gravatar for tuom.larsen
4.1 years ago by
tuom.larsen10
tuom.larsen10 wrote:

Hello!

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:

Fast Interval Intersection Methodologies

What Is The Quickest Algorithm For Range Overlap?

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?

Thank you in advance!

data-structure algorithm • 1.1k views
ADD COMMENTlink modified 4.1 years ago • written 4.1 years ago by tuom.larsen10

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.

ADD REPLYlink written 4.1 years ago by Devon Ryan90k

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".

ADD REPLYlink written 4.1 years ago by tuom.larsen10
1
gravatar for Sean Davis
4.1 years ago by
Sean Davis25k
National Institutes of Health, Bethesda, MD
Sean Davis25k wrote:

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.

Edit: as Devon points out, an R-tree is one of the best approaches to these types of problems.  http://en.wikipedia.org/wiki/R-tree

ADD COMMENTlink modified 4.1 years ago • written 4.1 years ago by Sean Davis25k
Please log in to add an answer.

Help
Access

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
Powered by Biostar version 2.3.0
Traffic: 802 users visited in the last hour