Find points that contained by set of retangle

Question

Input:

• A set of rectangles (overlapping rectangles too) and a set of point.
• Coordinates are integer type.
• Rectangle 's sides parallel to axis

Output:

All points inside any rectangles given

---

What is the efficient algorithm and data structure should I use ? Thanks.

Answer 1

You can use a sweep line algorithm: Sort the points by X coordinate. Introduce events when rectangles enter or leave the sweep line (the X coordinates of their left and right border). The rectangles currently intersecting the sweepline are a set of intervals when projected onto the sweep line, so they can be maintained using an interval tree or segment tree (the latter only after Y coordinate compression, but you can do that as a preprocessing step).

With that setup, for every point you just need to check whether it intersects one of the intervals maintained by your data structure.

Runtime: O((n+m) log (n+m))

Answer 2

2d segment tree (example here) is effective data structure to check if points are inside of any rectangle

Answer 3

The best idea I can come up with would be to check for every point (x,y) whether it is contained in any rectangle (l,t,w,h), yielding a runtime bound of O(nm) where n is the number of points and m is the number of rectangles.