# Efficient way to check if a rectangle intersects with other rectangles [closed]

I've been searching for algorithms that calculate whether two rectangles intersect each other. There are several solutions to this problem. However, I would love to know if there is an efficient way to find if a rectangle intersects with any other rectangle from a set of multiple rectangles.

The naive approach would be to call intersect(rectA, rectB) for each and every rectangle in the set. However, due to processing restrictions that will not be possible in my case.

I wonder if there is an algorithm that given a rectangle can determine in logn if there is any other rectangle that intersects with it.

The set can have 10.000 rectangles and I want to avoid comparing it with each and every of them.

## closed as unclear what you're asking by Ethan Bolker, John Bentin, KonKan, user99914, hardmathMar 8 '18 at 22:45

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• Use a Quadtree? – Jaap Scherphuis Mar 8 '18 at 15:49
• It's not clear to me if you're looking for an algorithm that , given a rectangle, finds whether or not it intersects any other rectangle ; or an algorithm that stops as soon as you found two rectangles in the set that intersect? – krirkrirk Mar 8 '18 at 15:50
• Are you looking for intersections or overlaps? I.e. is a rectangle allowed to lie fully inside another or not? For overlapping rectangles, the quadtree is useful. – Jaap Scherphuis Mar 8 '18 at 15:59
• Two main variants of this problem are for rectangles with sides parallel to the coordinate axes and for rectangles with "arbitrary orientation". You have not addressed this issue in posing the Question. – hardmath Mar 8 '18 at 20:58
• Thank you guys for the comments :) krirkrirk: I want the algorithm to stop as soon as there is a rectangle that intersects with the input rectangle hardmath: the sides are parallel to the axes JaapSchrphuis: both cases – ppoliani Mar 10 '18 at 15:38