C++ Programming Code Examples

/* Implement Graham Scan Algorithm to Find the Convex Hull 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). */ // A C++ program to find convex hull of a set of points 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; }