Find rectangles that contain point – Efficient Algorithm

12
votes

Good afternoon.

My situation:

  • In two-dimensional space.
  • Input: a set of rectangles (overlapping rectangles too).
    • Rectangles coordinates are integer type.
    • There are not any constraints on rectangle-size and rectangle-location (only extent of integer).
    • No rectangles have width=0 or height=0.
  • I need to find: all rectangles that contain entered point (with integer coordinates).

Find rectangles that contain entered point.

Questions:

  • What is the efficient structure to keep rectangles?
  • What alghorithm is efficient in this case?
    • And what algorithm is efficient only for adding rectangles without removing?

Thanks :-).

5
algorithmcomputational-geometry
Are there any constraints on the location of the point, or on the size or position of the rectangles? Can the point be at any (floating-point) position, or only on a fixed grid? Can the rectangles have a minimum and maximum size? - Li-aung Yip
Thanks, I will edit question. - Nanik
Also related - stackoverflow.com/questions/16583908/… - sashoalm

5 Answers

21
votes

R-Tree is the best data structure suitable for this use case. R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons. The information of all rectangles can be stored in tree form so searching will be easy

Wikipedia page, short ppt and the research paper will help you understand the concept.

enter image description here

3
votes

In java you can use shape.contains

But in general, assuming a rectangle is defined by (x,y,width,height) you do

if (pt.x >= x && pt.x <= x + width && pt.y >= y && pt.y <= y + height) ...

If you have all your rectangles in a collection you can iterate over the collection and find the ones that contain the point

3
votes

It seems that your set of rectangles may be dynamic ("...for adding rectangles..."). In this case - 2D Interval tree could be the solution.

2
votes

Here is a simple solution.

  1. Define a grid on your plane.
  2. Each cell maintains two lists: the rectangles that completely cover this cell and the rectangles that partially cover this cell.
  3. On each insertion, put the ID of the target rectangle into all the involved cell lists.
  4. On each query, locate the cell that contains the target point, output the completely cover list and run a scan on the partially cover list.
2
votes

A rectangle (left, top, right, bottom) contains a point (x, y) if left < x < right and top < y < bottom (assuming coordinates increase going downwards, which is the case with most hardware i've seen; if your coordinates increase going upwards, the more traditionally mathematical case, swap top and bottom). You're not going to get much more efficient than that for the test.

If you consider a rectangle as "containing" a point if it's on the border as well, then replace all the <s with <=.

As for what to do with the collection of rectangles...i dunno. I'd think a list sorted by the coordinates of the corners would do something, but i'm not really seeing much benefit to it...at most, you'd be cutting your list of stuff to check by half, on average (with the worst case still requiring checking everything). Half of a whole freaking lot can still be a whole lot. :)