1
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Use a Quadtree? $\endgroup$ Mar 8, 2018 at 15:49
  • $\begingroup$ 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? $\endgroup$
    – krirkrirk
    Mar 8, 2018 at 15:50
  • $\begingroup$ 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. $\endgroup$ Mar 8, 2018 at 15:59
  • $\begingroup$ 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. $\endgroup$
    – hardmath
    Mar 8, 2018 at 20:58
  • $\begingroup$ 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 $\endgroup$
    – ppoliani
    Mar 10, 2018 at 15:38

1 Answer 1

2
$\begingroup$

You can try a line segment intersection algorithm, chapter 2 of 'Computational Geometry: Algorithms and Applications, 2nd Ed' has a pretty intuitive description of the problem. If you don't have access to that reference you can look for the Bentley–Ottmann algorithm, there are some open-source implementation

You can also use an interval tree which allows you to check for overlap in intervals: in your case, the projection of the vertices of the rectangle onto an axis

$\endgroup$
0

Not the answer you're looking for? Browse other questions tagged .