Graham Scan算法求解二维凸包

一、凸包及其概念

凸包（Convex Hull）是计算几何中的一个重要概念。在一个实数向量空间中，对于给定的点集，凸包是指包含这些点的最小凸多边形。在二维平面上，凸包可以形象地理解为用一个橡皮圈将所有点紧紧包裹起来，橡皮圈最终形成的形状就是凸包。

二、Graham Scan算法原理

Graham Scan算法是一种高效的凸包求解算法，其时间复杂度为 (O(n \log n))。其核心思想是通过极角排序和栈操作来逐步构建凸包。具体步骤如下：

寻找基准点：在所有点中找到纵坐标最小的点，若纵坐标相同，则取横坐标最小的点，记为基准点 ( p_0 )。该点一定在凸包上。
极角排序：将除基准点外的其他点按照与基准点的极角进行排序。极角是指从基准点出发，逆时针旋转到目标点的角度。若极角相同，则按距离基准点的远近排序。
构建凸包：使用栈来构建凸包。先将基准点和排序后的第一个点入栈。然后依次处理排序后的每个点，对于当前点，检查其与栈顶两个点形成的向量方向。如果形成的是左转（逆时针），则将当前点入栈；如果是右转（顺时针），则弹出栈顶点，继续检查，直到形成左转或栈中只剩一个点。

三、代码实现

以下是使用C++实现的Graham Scan算法代码：

#include <iostream>
#include <stack>
#include <stdlib.h>
using namespace std;struct Point {int x, y;
};// A global point needed for sorting points with reference
// to the first point. Used in compare function of qsort()
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
void 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 distSq(Point p1, Point p2) {return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are collinear
// 1 --> Clockwise
// 2 --> Counterclockwise
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;  // collinearreturn (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 orientationint o = orientation(p0, *p1, *p2);if (o == 0)return (distSq(p0, *p2) >= distSq(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 pointint ymin = points[0].y, min = 0;for (int i = 1; i < n; i++) {int y = points[i].y;// Pick the bottom-most or choose the left// most point in case of tieif ((y < ymin) || (ymin == y && points[i].x < points[min].x)) {ymin = points[i].y;min = i;}}// Place the bottom-most point at first positionswap(points[0], points[min]);// Sort n-1 points with respect to the first point.// A point p1 comes before p2 in sorted output if p2// has larger polar angle (in counterclockwise// direction) than p1p0 = points[0];qsort(&points[1], n - 1, sizeof(Point), compare);// If two or more points make same angle with p0,// Remove all but the one that is farthest from p0// Remember that, in above sorting, our criteria was// to keep the farthest point at the end when more than// one points have same angle.int m = 1; // Initialize size of modified arrayfor (int i = 1; i < n; i++) {// Keep removing i while angle of i and i+1 is same// with respect to p0while (i < n - 1 && orientation(p0, points[i], points[i + 1]) == 0)i++;points[m] = points[i];m++;  // Update size of modified array}// If modified array of points has less than 3 points,// convex hull is not possibleif (m < 3) return;// 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 pointsfor (int i = 3; i < m; i++) {// Keep removing top while the angle formed by// points next-to-top, top, and points[i] makes// a non-left turnwhile (S.size() > 1 && orientation(nextToTop(S), S.top(), points[i]) != 2)S.pop();S.push(points[i]);}// Now stack has the output points, print contents of stackwhile (!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]);convexHull(points, n);return 0;
}