Sweep Line Algorithm

Hello Coders! In this post we will discuss about the Sweep Line Algorithm in C++. Before we move forward let us first understand what is a sweep line.

Introduction – Sweep Line Algorithm

What is a sweep line?

A sweep line is an imaginary vertical line that is swept across the plane in the right direction. That’s why the algorithms based on this concept are sometimes also called plane sweep algorithms. We sweep the line based on some events, in order to discretize the sweep.

In computational geometry, a sweep line algorithm or plane sweep algorithm is an algorithmic paradigm that uses a conceptual sweep line(as discussed above) or sweep surface to solve various problems in the Euclidean space. It is one of the key techniques in computational geometry.

One more thing to note is that the efficiency of this technique depends on the data structures we use. Generally, we can use set in C++ but sometimes we require some extra information to be stored, so we go for a balanced binary tree.

Closest Pair

Problem: Find the closest pair of points in the given array of N distinct points.

This problem can basically be solved by comparing all pairs of points, but then its complexity is O(N2). So, we need a better algorithm for this. Here, we’ll discuss it using the line sweep technique. For this problem, we can consider the points in the array as our events. And in a set, we store the already visited points sorted by y coordinate.
So, first, we sort the points in the x-direction as we want our line to move towards the right.
Now, considering we have processed the points from 1 to N-1, and suppose h be the shortest distance. For the Nth point, we want to find points whose distance from the Nth point is less than or equal to h.

Flow

sweep line algorithm
  1. First, we have sorted the array of points on x coordinates.
  2. Then we inserted the first point in the pnts array to the set box. Note we have defined py as the first in the pair, so the set will be sorted by y coordinates.
  3. In the loop, for each point in pnts, we are removing the points to the left of the current point whose x coordinate has more distance than h(the current minimum distance) from xN. This loop runs for overall O(N) as we have only N elements in the set. The complexity is O(logN). So, the overall complexity of this loop is O(N∗log N)
  4. In the second for loop, we are iterating over all points whose x coordinates lie in [xN−h,xN] and y coordinates lie in [yN−h,yN+h]. Finding the lower_bound takes O(logN) and this loop runs at most 5 times.
  5. For each point, insert it into the set. This step takes O(logN).
    So, the overall time complexity of the algorithm is O(N∗log N)

Code in C++

#define px second
#define py first
typedef pair<long long, long long> pairll;
pairll pnts [MAX];
int compare(pairll a, pairll b)
{ 
        return a.px<b.px; 
}
double closest_pair(pairll pnts[],int n)
{
        sort(pnts,pnts+n,compare);
        double best=INF;
        set<pairll> box;
        box.insert(pnts[0]);
        int left = 0;
        for (int i=1;i<n;++i)
        {
            while (left<i && pnts[i].px-pnts[left].px > best)
                box.erase(pnts[left++]);
            for(typeof(box.begin()) it=box.lower_bound(make_pair(pnts[i].py-best, pnts[i].px-best));it!=box.end() && pnts[i].py+best>=it->py;it++)
                best = min(best, sqrt(pow(pnts[i].py - it->py, 2.0)+pow(pnts[i].px - it->px, 2.0)));
            box.insert(pnts[i]);
        }
        return best;
}

Union Of Rectangles

Problem: Given a set of N axis-aligned rectangles(edges of rectangles parallel to the x-axis or y-axis), find the area of the union of all of the rectangles. A rectangle is represented by two points, one lower-left point, and one upper-right point.
The events for this problem are the vertical edges. When we encounter a left edge, we do some action and when we encounter a right edge, we do some other action. The left edge is represented by the lower-left point and the right edge by the upper-right point.

Flow

The area swept at any instance is = Δy * Δx where Δy is the length of the sweep line which is actually cut by the rectangle(s) (sum of the vertical lengths of the orange region, in the figure below) and Δx is the distance between two events of this sweep line.
But here we just know which are the rectangles intersecting the sweep line. So, here we have a new problem: how to find the length of the sweep line cut by the rectangles?

The solution to this problem is pretty the same we have been doing by now. We use the line sweep technique to find this but this time we apply it 90 degrees rotated, i.e., we sweep a horizontal line from bottom to up.

The events for this sweep line would be the horizontal edges of the active rectangles(rectangles cut by vertical sweep line). When we encounter a bottom horizontal edge of an active rectangle, we increment the counter (counter here maintains the number of rectangles that overlap at the current time) and we decrement it on the top horizontal edge of the active rectangle.

When the counter becomes zero from some non-zero value, we have found the cut length of the vertical sweep line, so we add the area to our final answer.

Code in C++

#define MAX 1000
struct event 
{
    int ind; // Index of rectangle in rects
    bool type; // Type of event: 0 = Lower-left ; 1 = Upper-right
    event() {};
    event(int ind, int type) : ind(ind), type(type) {};
};
struct point 
{
    int x, y;
};
point rects [MAX][12]; // Each rectangle consists of 2 points: [0] = lower-left ; [1] = upper-right
bool compare_x(event a, event b) { return rects[a.ind][a.type].x<rects[b.ind][b.type].x; }
bool compare_y(event a, event b) { return rects[a.ind][a.type].y<rects[b.ind][b.type].y; }
int union_area(event events_v[],event events_h[],int n,int e)
{
       //n is the number of rectangles, e=2*n , e is the number of points (each rectangle has two points as described in declaration of rects)
        bool in_set[MAX]={0};int area=0;
        sort(events_v, events_v+e, compare_x);  //Pre-sort of vertical edges
        sort(events_h, events_h+e, compare_y); // Pre-sort set of horizontal edges
        in_set[events_v[0].ind] = 1;
        for (int i=1;i<e;++i) 
        { // Vertical sweep line
                event c = events_v[i];
                int cnt = 0; // Counter to indicate how many rectangles are currently overlapping
                // Delta_x: Distance between current sweep line and previous sweep line
                int delta_x = rects[c.ind][c.type].x - rects[events_v[i-1].ind][events_v[i-1].type].x;
                int begin_y;
                if (delta_x==0){
                        in_set[c.ind] = (c.type==0);
                        continue;
                }
                for (int j=0;j<e;++j)
                        if (in_set[events_h[j].ind]==1)          //Horizontal sweep line for active rectangle
                        {
                                if (events_h[j].type==0)                //If it is a bottom edge of rectangle
                                {
                                        if (cnt==0) begin_y = rects[events_h[j].ind][0].y; // Block starts
                                        ++cnt;                 //incrementing number of overlapping rectangles
                                }
                                else             //If it is a top edge
                                {
                                        --cnt;     //the rectangle is no more overlapping, so remove it
                                        if (cnt==0)                     //Block ends
                                        {
                                                int delta_y = (rects[events_h[j].ind][13].y-begin_y);//length of the vertical sweep line cut by rectangles
                                                area+=delta_x * delta_y;
                                        }
                                }
                        }
                in_set[c.ind] = (c.type==0);//If it is a left edge, the rectangle is in the active set else not
        }
    return area;
}

The complexity of the algorithm can be easily seen to be O(N2). The complexity can be reduced by some other data structures such as BST instead of a boolean array.

By now, we hope you would have understood somewhat how to use this technique.

Convex Hull

Problem: Let S be a set of points. Then, the convex hull is the smallest convex polygon that covers all the points of S.
There exists an efficient algorithm for convex hull (Graham Scan) but here we discuss the same idea except for we sort based on x coordinates instead of the angle.

Flow

  1. Sort the points of P by x-coordinate (in case of a tie, sort by y-coordinate).
  2. Initialize U and L as empty lists.
  3. The lists will hold the vertices of upper and lower hulls respectively.
  4. for i = 1, 2, …, n: while L contains at least two points and the sequence of the last two points of L and the point P[i] does not make a counter-clockwise turn:
  5. remove the last point from L
  6. append P[i] to L
  7. for i = n, n-1, …, 1: while U contains at least two points and the sequence of the last two points of U and the point P[i] does not make a counter-clockwise turn:
  8. remove the last point from U
  9. append P[i] to U
  10. Remove the last point of each list (it’s the same as the first point of the other list). Concatenate L and U to obtain the convex hull of P.
  11. Points in the result will be listed in counter-clockwise order.

Code in C++

struct Point {
        double x, y;
};
bool compare(Point a,Point b)
{
        return a.x<b.x || (a.x==b.x && a.y<b.y);
}
//Returns positive value if B lies to the left of OA, negative if B lies to the right of OA, 0 if collinear
double cross(const Point &O, const Point &A, const Point &B)
{
        return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
//Returns a list of points on the convex hull
vector<Point> convex_hull(vector<Point> P)
{
        int n = P.size(), k = 0;
        vector<Point> H(2*n);
        sort(P.begin(), P.end(),compare);
        // Build lower hull
        for (int i = 0; i < n; ++i) {
                while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
                H[k++] = P[i];
        }

        // Build upper hull
        //i starts from n-2 because n-1 is the point which both hulls will have in common
        //t=k+1 so that the upper hull has atleast two points to begin with
        for (int i = n-2, t = k+1; i >= 0; i--) {
                while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
                H[k++] = P[i];
        }
        //the last point of upper hull is same with the fist point of the lower hull
        H.resize(k-1);
        return H;
}

The complexity of this algorithm is O(N∗logN) because of sorting. It may seem to be O(N2) because of the while loop inside but this loop runs for overall O(N) as we are deleting points in this loop and we have only N points, so it gives O(N).

Conclusion

Hope you find this post helpful. We have discussed the Sweep Line Algorithm and how to implement it. We hope that you found it easy to understand.

Stay tuned for more posts and updates. Until then, Happy Coding!

Leave a Comment

Your email address will not be published. Required fields are marked *