Convex Hull ด้วย Jarvis's Algorithm (Gift Wrapping) ใน C++

ภาพรวม

Convex Hull คือ Polygon คล محدบที่เล็กที่สุดที่ครอบจุดทั้งหมด (บนขอบหรือในภายใน)

Jarvis's Algorithm (Gift Wrapping) เริ่มจากจุดซ้ายสุด แล้ว "ห่อของขวัญ" โดยเลือกจุดที่ทำมุม South-most (Clockwise) ซ้ำจนกลับจุดเริ่มต้น

อัลกอริทึม

1. หาจุดซ้ายสุด (Leftmost Point) → เริ่มต้น
2. จากจุดปัจจุบัน p หาจุด q ที่ทำให้จุดอื่นๆ อยู่ทางขวาของเส้น p→q (Counter-clockwise orientation)
3. เพิ่ม q เข้า Hull, ตั้ง p = q
4. ทำซ้ำจน p กลับมาจุดเริ่มต้น

Orientation Test

สำหรับจุด p, q, r คำนวณ Cross Product:

val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y)
val = 0  → Collinear
val > 0  → Clockwise
val < 0  → Counter-clockwise

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

#include <bits/stdc++.h>
using namespace std;

struct Point { int x, 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;          // Collinear
    return (val > 0) ? 1 : 2;        // 1: Clockwise, 2: Counter-clockwise
}

void convexHull(Point points[], int n) {
    if (n < 3) return;

    vector<Point> hull;

    // 1. หาจุดซ้ายสุด
    int leftmost = 0;
    for (int i = 1; i < n; i++)
        if (points[i].x < points[leftmost].x)
            leftmost = i;

    // 2. Gift Wrapping
    int p = leftmost, q;
    do {
        hull.push_back(points[p]);
        q = (p + 1) % n;
        for (int i = 0; i < n; i++) {
            if (orientation(points[p], points[i], points[q]) == 2)
                q = i;
        }
        p = q;
    } while (p != leftmost);

    // Output
    for (const auto& pt : hull)
        cout << "(" << pt.x << ", " << pt.y << ")\n";
}

int main() {
    Point points[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1}, {3, 0}, {0, 0}, {3, 3}};
    int n = sizeof(points) / sizeof(points[0]);
    convexHull(points, n);
    return 0;
}

ผลลัพธ์

(0, 3)
(0, 0)
(3, 0)
(3, 3)

Complexity Analysis

• Time: O(n × h) (h = จำนวนจุดบน Hull, สูงสุด n → O(n²) Worst Case)
• Space: O(h) สำหรับเก็บ Hull
• ดีกว่า Graham Scan เมื่อ h << n (Hull เล็ก)

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

• เรียกว่า Gift Wrapping เพราะคล้ายการห่อของขวัญด้วยเชือก
• Output จุดเรียงตาม Counter-Clockwise Order
• จัดการ Collinear Points: โค้ดนี้เลือกจุดไกลสุด (อาจต้องปรับตามโจทย์)
• สำหรับ n ใหญ่และ h ใหญ่ ใช้ Graham Scan หรือ Monotone Chain (O(n log n))