Convex Hull ด้วย Graham Scan Algorithm ใน C++

ภาพรวม

Graham Scan เป็นอัลกอริทึม Convex Hull แบบคลาสสิก O(n log n) ขั้นตอน:

1. หาจุด Bottom-most (Lowest Y, แล้ว Leftmost X) → p0
2. เรียงจุดอื่นๆ ตาม Polar Angle เทียบกับ p0 (ใช้ Cross Product)
3. ลบจุด Collinear ที่อยู่ระหว่างทาง (เก็บจุดไกลสุด)
4. ใช้ Stack สร้าง Hull: Push 3 จุดแรก, แล้วสำหรับจุดต่อไป Pop จนกว่าจะเป็น Left Turn

โค้ดตัวอย่าง (C++)

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;

struct Point { int x, y; };

Point p0;  // Global pivot for sorting

Point nextToTop(stack<Point>& S) {
    Point p = S.top(); S.pop();
    Point res = S.top();
    S.push(p);
    return res;
}

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;    // 1: CW, 2: CCW
}

int distSq(Point p1, Point p2) {
    return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
}

int compare(const void* vp1, const void* vp2) {
    Point* p1 = (Point*)vp1;
    Point* p2 = (Point*)vp2;
    int o = orientation(p0, *p1, *p2);
    if (o == 0) return (distSq(p0, *p2) >= distSq(p0, *p1)) ? -1 : 1;
    return (o == 2) ? -1 : 1;  // CCW first
}

void convexHull(Point points[], int n) {
    // 1. Find bottom-most point
    int ymin = points[0].y, minIdx = 0;
    for (int i = 1; i < n; i++) {
        int y = points[i].y;
        if (y < ymin || (y == ymin && points[i].x < points[minIdx].x)) {
            ymin = y; minIdx = i;
        }
    }
    swap(points[0], points[minIdx]);
    p0 = points[0];

    // 2. Sort by polar angle
    qsort(&points[1], n-1, sizeof(Point), compare);

    // 3. Remove collinear points (keep farthest)
    int m = 1;
    for (int i = 1; i < n; i++) {
        while (i < n-1 && orientation(p0, points[i], points[i+1]) == 0) i++;
        points[m++] = points[i];
    }
    if (m < 3) return;

    // 4. Graham Scan with Stack
    stack<Point> S;
    S.push(points[0]); S.push(points[1]); S.push(points[2]);

    for (int i = 3; i < m; i++) {
        while (orientation(nextToTop(S), S.top(), points[i]) != 2)
            S.pop();
        S.push(points[i]);
    }

    // Output (Reverse order from stack)
    while (!S.empty()) {
        Point p = S.top(); S.pop();
        cout << "(" << p.x << ", " << p.y << ")" << endl;
    }
}

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;
}

ผลลัพธ์

(0, 3)
(4, 4)
(3, 1)
(0, 0)

Complexity Analysis

• Time: O(n log n) (Sorting Dominates)
• Space: O(n) (Stack + Sorted Array)

คำอธิบายเพิ่มเติม

• ใช้ qsort (C-style) เพื่อความเร็ว สามารถใช้ std::sort กับ Lambda ได้
• Polar Angle Sorting ใช้ Cross Product แทน Atan2 (เร็วกว่า, ไม่มี Precision Issue)
• Collinear Handling: เก็บจุดไกลสุดจาก p0, ลบจุดกลาง
• Stack เก็บ Hull Points ใน Counter-Clockwise Order
• Output จาก Stack จะเป็น Reverse Order (Top = Last Point)

Graham Scan vs Monotone Chain

ข้อแนะนำ

สำหรับ Competitive Programming และการใช้งานจริง แนะนำ Monotone Chain (Andrew's Algorithm) มากกว่า เพราะโค้ดสั้นกว่า เร็วกว่า และง่ายต่อการ Debug