4

  • Each rectangle is comprised of 4 doubles like this: (x0,y0,x1,y1)

  • The edges are parallel to the x and y axes

  • They are randomly placed - they may be touching at the edges, overlapping , or not have any contact

I need to find the area that is formed by their overlap - all the area in the canvas that more than one rectangle "covers" (for example with two rectangles, it would be the intersection)

I understand I need to use sweep line algorithm. Do I have to use a tree structure? What is the easiest way of using sweep line algorithm for this problem?

Camille Goudeseune
  • 2,934
  • 2
  • 35
  • 56
Mauricio
  • 41
  • 2
  • Possible duplicate of [What is an Efficient algorithm to find Area of Overlapping Rectangles](https://stackoverflow.com/questions/244452/what-is-an-efficient-algorithm-to-find-area-of-overlapping-rectangles) – LeppyR64 Aug 29 '17 at 14:40

1 Answers1

2

At first blush it seems that an O(n^2) algorithm should be straightforward since we can just check all pairwise points. However, that would create the problem of double counting, as all points that are in 3 rectangles would get counted 3 times! After realizing that, an O(n^2) algorithm doesn't look bad to me now. If you can think of a trivial O(n^2) algorithm, please post.

Here is an O(n^2 log^2 n) algorithm.

Data structure: Point (p) {x_value, isBegin, isEnd, y_low, y_high, rectid}

[For each point, we have a single x_value, two y_values, and the ID of the rectangle which this point came from]

  1. Given n rectangles, first create 2n points as above using the x_left and x_right values of the rectangle.

  2. Create a list of points, and sort it on x_value. This takes O(n log n) time

  3. Start from the left (index 0), use a map to put when you see a begin, and remove when you see an end point.

In other words:

Map m = new HashMap();  // rectangles overlapping in x-axis
for (Point p in the sorted list) {
    if (p.isBegin()) {
        m.put(p);  // m is keyed off of rectangle id
        if (s.size() >= 2) {
            checkOverlappingRectangles(m.values())
        }
    } else {
        m.remove(p);  // So, this takes O(log n) time
    }
}

Next, we need a function that takes a list of rectangles, knowing that the all the rectangles have overlapping x axis, but may or may not overlap on y axis. That is in fact same as this algorithm, we just use a transverse data structures since we are interested in y axis now.

Josh
  • 189
  • 12
  • Josh, Thanks for your answer. Could you explain what is mapping, how to use a map. Which language you've wrote the code? –  Mar 29 '11 at 16:38
  • @mauricio I just used the inbuilt map structure in Java. TreeMap is another option, which I believe is an implementation of red black trees, and supports O(log n) insert, search and delete operations. – Josh Mar 30 '11 at 22:37