Dual Sweep Line Technique
2D Intervals (Rectangles) Union

Algorithms and Data Structures: TheAlgorist.com

System Design: SystemsDesign.Cloud

Low Level Design: LowLevelDesign.io
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.
Indepth Algorithm Discussion and Code Implementation:
This is a Premium Content.
Please subscribe to Algorithms course to access the solution.
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
Instructor:
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