CODEWITHSUNDEEP
algorithmcomputational-geometry
Mauricio
Mauricio

Reputation: 41

Area of intersection of axis-aligned rectangles

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?

Upvotes: 4

Views: 2267

Answers (1)

Josh
Josh

Reputation: 189

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.

Upvotes: 2

Related Questions