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.
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
python: splichte, ideasman42
c++: cgal
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