CODEWITHSUNDEEP
algorithmdata-structuresintervalspseudocode
Mr Sukhe
Mr Sukhe

Reputation: 77

to find if any overlapping rectangles exist in n number of rectangles

Assume that each rectangle is rectilinearly oriented (sides parallel to the x- and y-axes), so that we represent a rectangle by its minimum and maximum xand y-coordinates. Give an O.n lg n/-time algorithm to decide whether or not a set of n rectangles so represented contains two rectangles that overlap. Your algorithm need not report all intersecting pairs, but it must report that an overlap exists if one rectangle entirely covers another, even if the boundary lines do not intersect.

my solution: Let R be an array containing rectangles represented as (x_int, y_int) where x_int represents interval [x1, x2] and y_int represents interval [y1, y2] if the 4 cornesrs of rectacle are (x1, y1), (x1, y2), (x2, y1) and (x2, y2).Let the indexing start from 1. this solution is based on the fact that two rectangles overlap if and only if their x_int overlap and y_int overlap.

FindOverlap(R, n):
  T = IntervalTree()   // T is a interval tree capable of checking if a given
                       // interval is overlapping with any interval in the tree
                       // and inserting interval in the tree in log(n) time.
  for i in [1,n]:
      x_int, y_int = R[i][1], R[i][2]

      interval_Index = T.IntervalSearch(x_int)  // Returns 0 if there is no interval 
                                           // in T which overlaps x_int , else 
                                           // returns index of the interval which
                                           // overlaps x_int 
      if interval_Index != 0:

          if R[interval_Index][2] overlaps y_int:

              return i, interval_Index

      T.InsertInterval(x_int, i)          // inserts interval x_int into T with 
                                          //associated index i
  return False

Is there anything wrong in this ? Will this algorithm work correctly?

Upvotes: 1

Views: 836

Answers (2)

Matt Timmermans
Matt Timmermans

Reputation: 59194

Here's a scan line algorithm that meets the requirements:

You'll need a binary search tree (BST) that keeps rectangles ordered by min X coordinate, and a priority queue that keeps rectangles ordered by max Y coordinate.

  1. Sort the rectangles by min Y coordinate: O(N log N)
  2. Iterate through the rectangles in min Y order. For each one:
    1. Remove all rectangles with max Y coordinates less than the new rect min Y from both the priority queue and the BST: O(N log N) all together
    2. Insert the new rectangle into the BST. If you detect that its X interval overlaps with the rectangles to its left or right in the BST, then you've found an overlap and you're done. This step also takes O(N log N) all together.
    3. Insert the new rectangle into the priority so that you know when to remove it in step 2.1. Again O(N log N)

Upvotes: 2

Nelfeal
Nelfeal

Reputation: 13269

Building on @Matt Timmermans's comment: this does not work because you could have a situation where three rectangles overlap in X, and only the last two overlap in Y. In this case, you only check for overlap in Y between the third and the first, not between the third and the second.

Moreover, if you try checking all rectangles that overlap the current one in X for overlap in Y, you end up in O(N^2) complexity in the worst case: imagine all N rectangles overlap in X but only the last two overlap in Y.

What you need is a two-dimensional interval tree, that is an interval tree in X where each node also contains an interval tree in Y for the subtree. Insertion and query are still O(log N), which makes the whole algorithm O(N log N).

Upvotes: 1

Related Questions