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$

closed as unclear what you're asking by Ethan Bolker, John Bentin, KonKan, user99914, hardmath Mar 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.

  • 1
    $\begingroup$ Use a Quadtree? $\endgroup$ – Jaap Scherphuis Mar 8 '18 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 '18 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$ – Jaap Scherphuis Mar 8 '18 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 '18 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 '18 at 15:38
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$

Not the answer you're looking for? Browse other questions tagged or ask your own question.