The intersection area of ​​axis-aligned rectangles

Question

• Each rectangle consists of 4 such doubles: (x0, y0, x1, y1)

• The edges are parallel to the x and y axes

• They are placed randomly - they can touch the edges, overlap or have no contact

I need to find the area formed by their overlap - the entire area in the canvas that covers more than one rectangle (for example, with two rectangles, this will be the intersection)

I understand that I need to use a sweep algorithm. Should I use a tree structure? What is the easiest way to use the sweep algorithm for this problem?

Answer 1

At first blushing it seems that the O (n ^ 2) algorithm should be simple, since we can just check all pairwise points. However, this will create a double counting problem, since all points that are in 3 rectangles will be counted 3 times! Realizing that the O (n ^ 2) algorithm now does not look bad. If you can come up with a trivial O (n ^ 2) algorithm, send a message.

Here is the 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 one x_value value, two y_values ​​and the identifier of the rectangle from which this point came]

• For n rectangles, first create 2n points as described above using the x_left and x_right values ​​of the rectangle.

• Create a list of points and sort them by x_value value. It takes O time (n log n)

• Start from the left (index 0), use the card that you need to put when you see the beginning, and delete when you see the 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 all rectangles have an overlapping x axis, but may or may not overlap along the y axis. This is actually the same as this algorithm, we just use transverse data structures, since now we are interested in the y axis.