Dual Sweep Line Technique
2D Intervals (Rectangles) Union

Customer Support: admin@thealgorists.com

Feedback:
We are listening to your every feedback,
and taking action to constantly improve your learning experience.
If you have any feedback, please use this form:
https://thealgorists.com/Feedback.
 If you are a student, email to admin@thealgorists.com to get special student discount.
Prerequisite: Fundamentals of Sweep Line Algorithm
In this article, we will see how Sweep Line Technique can be used to compute union of rectangles.
Let's suppose a list of (axisaligned) rectangles and each rectangle is represented as [x1, y1, x2, y2] , where (x1, y1) are the coordinates of the bottomleft corner, and (x2, y2) are the coordinates of the topright corner of the i^{th} rectangle.
Our objective is to find the total area covered by all rectangles in the plane.
This problem can be solved very easily using Sweep Line technique, using the concepts of events and active events. However, to solve this problem we would need Dual Sweep Line Technique, where we will have to sweep line along both xaxis and yaxis. The algorithm and code below explains the technique very well.
Algorithm:
Here we are calculating union of all given rectangles. So any area in the 2D plane should be calculated only once, which means we should be careful about any area that is overlapped by two or more rectangles, because they need to be included only once.
A union B = A + B  (A intersection B).
So what we can do is:

We can sweep a horizontal line from bottom to top as we see the horizontal lines of
the rectangles (marking start/bottom and end/topend of a rectangle)
we calculate the area till that ycoordinate level. So at the end, by the time we
reach the top most horizontal line(s) and are done processing the top most ycoordinate level, we will be
done calculating the whole area.
For every level, we calculate the area till that level only once even when we have more than one horizontal line at the same level (ycoordinate).

For every level we sweep a vertical line from left to right and calculate the
width of the rectangles present at that level.
So from above, we see we need to do line sweep in both vertical and horizontal direction.For every line sweep operation along yaxis, whenever we find at least one new event present at that level (ycoordinate) we do a horizontal line sweep along xaxis to measure the total widths of all the rectangles present at that level (ycoordinate).
To achieve this, we need to keep track of the WIDTH and HEIGHT of every rectangle. Since we will be sweeping line from bottom to top, we need to have the base (ycoordinate) and topend (ycoordinate) of the rectangles as event along with their width (start xcoordinate and end xcoordinate for that rectangle).
18  H ___________ G    16       14   I____ L       12   ____   P______ O J K  10       M_____ N  8     D______________ C  6           4   E__________F    2  A______________B  _____________________________________ 0 2 4 6 8 10 11 12
This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.
Related MustRead Topics:
 1d Range Search
 Closest Pair
 Convex Hull

2D Intervals Union
& Skyline Problem  Overlapping 1D Intervals
 Merging Overlapping 1D Intervals
 Separating Overlapping 1D Intervals
The above content is written by:
Abhishek Dey
A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More
Microsoft  University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn