Find rectangles that contain point – Efficient Algorithm

Question

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

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 :-).

Answer 1

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

Answer 2

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.

Answer 3

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