Line Sweep

Concept

Imagine passing a line all the way from y =0 or x=0 or y=some max num or x= some num , all the way to the opposite direction as shown below.

Applications

• Intersections between line segments
• Rectangle areas

Consider the following problem:

You are given a 2D array of axis-aligned rectangles. Each rectangle[i] = [xi1, yi1, xi2, yi2] denotes the ith rectangle where (xi1, yi1) are the coordinates of the bottom-left corner, and (xi2, yi2) are the coordinates of the top-right corner.

Calculate the total area covered by all rectangles in the plane. Any area covered by two or more rectangles should only be counted once.

Return the total area. Since the answer may be too large, return it modulo 109 + 7.

Points to remember

1. We perform a line sweep from y=0 to y=max height in the following manner

2. We need to make sure that the x and y co-ordinates fully encompass inside our line sweep

Complexity O(n²)

int rectangleArea(vector<vector<int>>& rect) {
        set<int>ys;
        for(auto r:rect)
        {
            ys.insert(r[1]);
            ys.insert(r[3]);
        }
        sort(rect.begin(),rect.end());
        
        long long res=0;
        long long mod=pow(10,9)+7;
        int prev_y=0;
        for(auto y:ys)
        {
            long long height=y-prev_y;
            long long start=rect[0][0],end=rect[0][0];
            for(auto r:rect)
            {
                if(r[1]<=prev_y&&r[3]>=y)
                {
                    if(r[0]>start)
                    {
                        res+= height*(end-start)%mod;
                        start=r[0];
                        end=r[2];                        
                    }
                    else
                        end=max(end,(long long)r[2]);
                }
            }
            res+=height*(end-start)%mod;
            prev_y=y;
        }
        return res;
    }