Graham Scan Algorithm in C++

This is a C++ Program to implement Graham Scan algorithm. Graham’s scan is a method of computing the convex hull of a finite set of points in the plane with time complexity O(n log n).

Here is source code of the C++ Program to Implement Graham Scan Algorithm to Find the Convex Hull. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

// A C++ program to find convex hull of a set of points

// Refer http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/

```
// for explanation of orientation()
```
```
#include <iostream>
```
```
#include <stack>
```
```
#include <stdlib.h>
```
```
using namespace std;
```
```
 
```
```
struct Point
```
```
{
```
```
        int x;
```
```
        int y;
```
```
};
```
```
 
```
```
Point p0;
```
```
 
```

// A utility function to find next to top in a stack

```
Point nextToTop(stack<Point> &S)
```
```
{
```
```
    Point p = S.top();
```
```
    S.pop();
```
```
    Point res = S.top();
```
```
    S.push(p);
```
```
    return res;
```
```
}
```
```
 
```

// A utility function to swap two points

```
int swap(Point &p1, Point &p2)
```
```
{
```
```
    Point temp = p1;
```
```
    p1 = p2;
```
```
    p2 = temp;
```
```
}
```
```
 
```

// A utility function to return square of distance between p1 and p2

```
int dist(Point p1, Point p2)
```
```
{
```

    return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);

```
}
```
```
 
```

int orientation(Point p, Point q, Point r)

```
{
```

    int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);

```
 
```
```
    if (val == 0)
```
```
        return 0; // colinear
```

    return (val > 0) ? 1 : 2; // clock or counterclock wise

```
}
```
```
 
```

// A function used by library function qsort() to sort an array of

// points with respect to the first point

int compare(const void *vp1, const void *vp2)

```
{
```
```
    Point *p1 = (Point *) vp1;
```
```
    Point *p2 = (Point *) vp2;
```
```
 
```
```
    // Find orientation
```
```
    int o = orientation(p0, *p1, *p2);
```
```
    if (o == 0)
```

        return (dist(p0, *p2) >= dist(p0, *p1)) ? -1 : 1;

```
 
```
```
    return (o == 2) ? -1 : 1;
```
```
}
```
```
 
```

// Prints convex hull of a set of n points.

```
void convexHull(Point points[], int n)
```
```
{
```
```
    // Find the bottommost point
```
```
    int ymin = points[0].y, min = 0;
```
```
    for (int i = 1; i < n; i++)
```
```
    {
```
```
        int y = points[i].y;
```
```
 
```

        // Pick the bottom-most or chose the left most point in case of tie

        if ((y < ymin) || (ymin == y && points[i].x < points[min].x))

            ymin = points[i].y, min = i;

```
    }
```
```
 
```

    // Place the bottom-most point at first position

```
    swap(points[0], points[min]);
```
```
 
```

    // Sort n-1 points with respect to the first point.  A point p1 comes

    // before p2 in sorted ouput if p2 has larger polar angle (in

    // counterclockwise direction) than p1

```
    p0 = points[0];
```

    qsort(&points[1], n - 1, sizeof(Point), compare);

```
 
```

    // Create an empty stack and push first three points to it.

```
    stack<Point> S;
```
```
    S.push(points[0]);
```
```
    S.push(points[1]);
```
```
    S.push(points[2]);
```
```
 
```
```
    // Process remaining n-3 points
```
```
    for (int i = 3; i < n; i++)
```
```
    {
```

        // Keep removing top while the angle formed by points next-to-top,

        // top, and points[i] makes a non-left turn

        while (orientation(nextToTop(S), S.top(), points[i]) != 2)

```
            S.pop();
```
```
        S.push(points[i]);
```
```
    }
```
```
 
```

    // Now stack has the output points, print contents of stack

```
    while (!S.empty())
```
```
    {
```
```
        Point p = S.top();
```

        cout << "(" << p.x << ", " << p.y << ")" << endl;

```
        S.pop();
```
```
    }
```
```
}
```
```
 
```

// Driver program to test above functions

```
int main()
```
```
{
```

    Point points[] = { { 0, 3 }, { 1, 1 }, { 2, 2 }, { 4, 4 }, { 0, 0 },

            { 1, 2 }, { 3, 1 }, { 3, 3 } };

    int n = sizeof(points) / sizeof(points[0]);

    cout << "The points in the convex hull are: \n";

```
    convexHull(points, n);
```
```
    return 0;
```
```
}
```

Output:

$ g++ GrahamScan.cpp
$ a.out
 
The points in the convex hull are: 
(0, 3)
(4, 4)
(3, 1)
(0, 0)
 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

« Prev - C++ Program to Find the Area of a Triangle Using Determinants

» Next - C++ Program to Implement Levenshtein Distance Computing Algorithm

Related Posts:

Recommended Articles: