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)
Press return to continue

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

advertisement
advertisement

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

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.