axis‐aligned rectangles intersection

Question

I need an algorithm that takes an unsorted array of axis aligned rectangles and returns any pair of rectangles that overlaps

Each rectangle has two variables, coordinates of the upper-left corner and the bottom-right corner

Answer 1

Here is a brief description of the intersection algorithm presented in DuduAlul's link.

The solution requires the usage of a search tree capable of performing range queries. A range query asks for all items with values between K1 and K2, and it should be an O(R+log N) operation, where N is the total number of tree items, and R is the number of results.

The algorithm uses the sweep approach:

1) Sort all left and right rectangle edges, according to their X value, into list L.

2) Create a new empty range search tree T, for Y ordering of rectangle tops/bottoms

3) Create a new empty result set RS of unique rectangle pairs

4) Traverse L in ascending order. For all V in L:

   If V.isRightEdge()

      T.remove(V.rectangle.top)

      T.remove(V.rectangle.bottom)

   else

       For all U in T.getRange(V.rectangle.top, V.rectangle.bottom)

         RS.add(<V.rectangle, U.rectangle>)

      T.add(V.rectangle.top)

      T.add(V.rectangle.bottom)

5) return RS

---

The time complexity is O(R + N log N) where R is the actual number of intersections.

-- EDIT --

I just figured out that the solution is not fully correct - the intersection test in tree T misses some cases. The tree should maintain Y intervals rather than Y values, and it should ideally be an Interval Tree.

Answer 2

Sweep and prune is the method that a lot of physics engines to solve this sort of problem.

There's a good explanation in David Baraff's SIGGRAPH notes, under section 7.2 Bounding Boxes.

Answer 3

It might be a bit complicated for a job interview , depends what kind of job, It's a geometric computation kind of algorithm,

The answer can be found here: http://www.cs.princeton.edu/~rs/AlgsDS07/17GeometricSearch.pdf