We are given n axis-aligned rectangles in a 2D plane, each specified by its bottom-left and top-right coordinates.
The goal is to implement an algorithm that computes the total area covered by the union of these rectangles, as well as to draw the outer contour of their union (see the image below for reference).
To compute the area efficiently, we will use a sweep line technique combined with a segment tree, aiming for a time complexity of O(n log n).
While the contour drawing does not require the same level of efficiency, it should accurately represent the outer boundary of the union.
- For each vertical strip [xi, xi+1] where xi and xi+1 are adjacent x-coordinates corresponding to opening or closing sides of rectangles, we determine how much vertical area is covered by rectangles that span this strip (y-coverage).
- There are up to 2n−1 such vertical strips (since each of the n rectangles contributes 2 sides).
- We will use segment trees to achieve O(logn) efficiency for O(n) vertical strips, making this algorithm O(nlogn).
(Segment trees are well-suited for problems involving range updates and aggregate queries.)
The segment tree nodes will represent intervals over our y axis. Our goal is to:
- Track how many rectangles are currently covering each y-interval.
- Maintain the total y-length currently covered at each moment in the sweep.
- Insert vertical contour segments during updates when coverage changes. To extract horizontal contour edges, we repeat the entire sweep-line process but with x- and y-coordinates switched. This second sweep allows us to find the horizontal parts of the outer boundary using the same logic.
The process:
- We first sort and compress all y-values from the input rectangles to get a unique list.
- We build a segment tree over these y-intervals.
- For each sweep line event (start or end of a rectangle), we update the tree with the appropriate type (opening or closing).
- The segment tree allows us to update and query y-coverage in O(logn) time.
- For each vertical strip, we compute the total covered y-length and multiply it by the width of the strip dx = x_{i+1} − x_i to accumulate the total area.
The segment tree also helps in extracting vertical contour edges by detecting transitions where rectangle coverage changes from 0 to 1 or from 1 to 0.
- Generating two events per rectangle (open and close) → O(n)
- Sorting the events → O(n log n)
- Preprocessing y-values (sorting and deduplication) → O(n log n)
- Segment tree updates per event → O(log n), for n events O(n log n)
Thus, the overall time complexity is O(n log n) for computing the union area.
The contour extraction is also O(n log n): Vertical edges are detected during the initial sweep. Horizontal edges are captured during a second sweep after swapping x/y roles.
- Event priority queue for 2n events → O(n)
- Segment tree with up to 4n nodes → O(n) (Standard for a segment tree over n intervals)
- Vector of unique sorted y-coordinates → O(n)
- Vectors for storing input rectangles and resulting contour segments → O(n)
Overall space complexity is O(n).
void update(int rec_y_start, int rec_y_end, RecEventType type, int event_x,
vector<ContourSegment>& contour, bool is_horizontal);
Called for every rectangle event (opening or closing). Delegates to updateHelper to apply changes across the segment tree. Adds vertical or horizontal contour segments as needed.
void updateHelper(int current_node, int node_start, int node_end,
int rec_y_start, int rec_y_end,
RecEventType type, int event_x,
vector<ContourSegment>& contour, bool is_horizontal);
Recursive function that traverses and updates the segment tree. Updates rectangle coverage count in each affected node and total y-length covered in current segment. Detects when coverage transitions from 0→1 or 1→0 to add contour edges.
int queryTotalLength() const;
Returns the total length of the y-axis currently covered by active rectangles. This value is multiplied by the current dx to compute the contribution to the union area.
int findYPositionInSortedList(int y, const vector<int>& y_sorted_unique);
Binary search to find the index of a given y-value in the list of unique, sorted y-values. Used to convert real y-coordinates into segment tree indices.
double computeUnionArea(const vector<MyRectangle>& recs, vector<ContourSegment>& contour);
Builds the list of rectangle events. Sorts events and initializes the y-axis segment tree. Performs a vertical sweep using the segment tree to compute union area, as well as add vertical contour segments.
void horizontalContourEdges(const vector<MyRectangle>& recs, vector<ContourSegment>& contour);
Performs a second sweep by switching x/y axes. Adds horizontal contour edges based on changes in coverage. Complements vertical edges to complete the contour.
- Added a button for generating random n rectangles.
- Several predefined test cases are available (some may be commented out for testing convenience).
- Added a button for computing total area.
- The contour is drawn automatically after the area result is shown.
- We already have Draw methods for MyRectangle and ContourSegment strucs.
- Drawing is triggered by Invalidate().