Graham Scan算法求解二维凸包

一、凸包及其概念

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

二、Graham Scan算法原理

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

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

三、代码实现

以下是使用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;  // collinear
    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 (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 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 choose 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 output if p2
    // has larger polar angle (in counterclockwise
    // direction) than p1
    p0 = 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 array
    for (int i = 1; i < n; i++) {
        // Keep removing i while angle of i and i+1 is same
        // with respect to p0
        while (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 possible
    if (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 points
    for (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 turn
        while (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 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]);
    convexHull(points, n);
    return 0;
}

四、总结

Graham Scan算法是一种经典的计算几何算法，用于求解二维平面上点集的凸包。它通过极角排序和栈操作，高效地构建凸包，时间复杂度为 $O(n\log n)$。该算法在计算机图形学、图像处理、碰撞检测等领域有广泛的应用。