# C++ Program to Find the Convex Hull using Graham Scan Algorithm

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.

1. `// A C++ program to find convex hull of a set of points`
2. `// Refer http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/`
3. `// for explanation of orientation()`
4. `#include <iostream>`
5. `#include <stack>`
6. `#include <stdlib.h>`
7. `using namespace std;`
8. ` `
9. `struct Point`
10. `{`
11. `        int x;`
12. `        int y;`
13. `};`
14. ` `
15. `Point p0;`
16. ` `
17. `// A utility function to find next to top in a stack`
18. `Point nextToTop(stack<Point> &S)`
19. `{`
20. `    Point p = S.top();`
21. `    S.pop();`
22. `    Point res = S.top();`
23. `    S.push(p);`
24. `    return res;`
25. `}`
26. ` `
27. `// A utility function to swap two points`
28. `int swap(Point &p1, Point &p2)`
29. `{`
30. `    Point temp = p1;`
31. `    p1 = p2;`
32. `    p2 = temp;`
33. `}`
34. ` `
35. `// A utility function to return square of distance between p1 and p2`
36. `int dist(Point p1, Point p2)`
37. `{`
38. `    return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);`
39. `}`
40. ` `
41. `int orientation(Point p, Point q, Point r)`
42. `{`
43. `    int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);`
44. ` `
45. `    if (val == 0)`
46. `        return 0; // colinear`
47. `    return (val > 0) ? 1 : 2; // clock or counterclock wise`
48. `}`
49. ` `
50. `// A function used by library function qsort() to sort an array of`
51. `// points with respect to the first point`
52. `int compare(const void *vp1, const void *vp2)`
53. `{`
54. `    Point *p1 = (Point *) vp1;`
55. `    Point *p2 = (Point *) vp2;`
56. ` `
57. `    // Find orientation`
58. `    int o = orientation(p0, *p1, *p2);`
59. `    if (o == 0)`
60. `        return (dist(p0, *p2) >= dist(p0, *p1)) ? -1 : 1;`
61. ` `
62. `    return (o == 2) ? -1 : 1;`
63. `}`
64. ` `
65. `// Prints convex hull of a set of n points.`
66. `void convexHull(Point points[], int n)`
67. `{`
68. `    // Find the bottommost point`
69. `    int ymin = points[0].y, min = 0;`
70. `    for (int i = 1; i < n; i++)`
71. `    {`
72. `        int y = points[i].y;`
73. ` `
74. `        // Pick the bottom-most or chose the left most point in case of tie`
75. `        if ((y < ymin) || (ymin == y && points[i].x < points[min].x))`
76. `            ymin = points[i].y, min = i;`
77. `    }`
78. ` `
79. `    // Place the bottom-most point at first position`
80. `    swap(points[0], points[min]);`
81. ` `
82. `    // Sort n-1 points with respect to the first point.  A point p1 comes`
83. `    // before p2 in sorted ouput if p2 has larger polar angle (in`
84. `    // counterclockwise direction) than p1`
85. `    p0 = points[0];`
86. `    qsort(&points[1], n - 1, sizeof(Point), compare);`
87. ` `
88. `    // Create an empty stack and push first three points to it.`
89. `    stack<Point> S;`
90. `    S.push(points[0]);`
91. `    S.push(points[1]);`
92. `    S.push(points[2]);`
93. ` `
94. `    // Process remaining n-3 points`
95. `    for (int i = 3; i < n; i++)`
96. `    {`
97. `        // Keep removing top while the angle formed by points next-to-top,`
98. `        // top, and points[i] makes a non-left turn`
99. `        while (orientation(nextToTop(S), S.top(), points[i]) != 2)`
100. `            S.pop();`
101. `        S.push(points[i]);`
102. `    }`
103. ` `
104. `    // Now stack has the output points, print contents of stack`
105. `    while (!S.empty())`
106. `    {`
107. `        Point p = S.top();`
108. `        cout << "(" << p.x << ", " << p.y << ")" << endl;`
109. `        S.pop();`
110. `    }`
111. `}`
112. ` `
113. `// Driver program to test above functions`
114. `int main()`
115. `{`
116. `    Point points[] = { { 0, 3 }, { 1, 1 }, { 2, 2 }, { 4, 4 }, { 0, 0 },`
117. `            { 1, 2 }, { 3, 1 }, { 3, 3 } };`
118. `    int n = sizeof(points) / sizeof(points[0]);`
119. `    cout << "The points in the convex hull are: \n";`
120. `    convexHull(points, n);`
121. `    return 0;`
122. `}`

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)

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