# 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**

- 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;

}