Gift Wrapping Algorithm (Jarvis March) หา Convex Hull ใน C++

Gift Wrapping Algorithm (หรือ Jarvis March) เป็นอัลกอริทึมสำหรับหา Convex Hull (凸包) ของชุดจุดใน 2 มิติ โดยการ "ห่อของขวัญ" รอบจุดต่างๆ

หลักการทำงาน

1. หาจุดที่อยู่ซ้ายสุด (lowest x) เริ่มต้น
2. จากจุดปัจจุบัน หาจุดถัดไปที่ทำมุม "ซ้ายสุด" (counter-clockwise) เท่าที่สุด
3. ทำซ้ำจนกลับมาที่จุดเริ่มต้น
4. Complexity: O(nh) โดย n = จำนวนจุด, h = จำนวนจุดบน hull

ฟังก์ชัน Orientation Test

สำคัญที่สุดคือการตรวจสอบทิศทางของจุด 3 จุด (p, q, r):

• 0: จุดสามจุดอยู่บนเส้นตรงเดียวกัน (collinear)
• 1: Clockwise (CW)
• 2: Counter-clockwise (CCW) - นี่คือที่เราต้องการ

สูตร: val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y)

ตัวอย่างโค้ด

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Point {
    int x, y;
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// คืนค่า: 0=collinear, 1=clockwise, 2=counterclockwise
int orientation(const Point& p, const Point& q, const Point& r) {
    long long val = 1LL * (q.y - p.y) * (r.x - q.x) - 
                    1LL * (q.x - p.x) * (r.y - q.y);
    if (val == 0) return 0;
    return (val > 0) ? 1 : 2;
}

vector<Point> convexHull(vector<Point> points) {
    int n = points.size();
    if (n < 3) return points; // ต้องมีอย่างน้อย 3 จุด
    
    vector<Point> hull;
    
    // 1. หาจุดซ้ายสุด (smallest x, ถ้าเท่ากัน smallest y)
    int leftmost = 0;
    for (int i = 1; i < n; ++i) {
        if (points[i].x < points[leftmost].x || 
            (points[i].x == points[leftmost].x && points[i].y < points[leftmost].y)) {
            leftmost = i;
        }
    }
    
    // 2. เริ่มห่อจากจุดซ้ายสุด
    int p = leftmost, q;
    do {
        hull.push_back(points[p]);
        
        // หาจุดถัดไป q ที่ทำมุม CCW มากที่สุด
        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);
    
    return hull;
}

int main() {
    vector<Point> points = {
        {0, 4}, {2, 1}, {2, 3}, {4, 1}, 
        {3, 0}, {1, 1}, {7, 6}
    };
    
    vector<Point> hull = convexHull(points);
    
    cout << "จุดบน Convex Hull:" << endl;
    for (const auto& pt : hull) {
        cout << "(" << pt.x << ", " << pt.y << ")" << endl;
    }
    
    return 0;
}

ผลลัพธ์

จุดบน Convex Hull:
(0, 4)
(1, 1)
(3, 0)
(4, 1)
(7, 6)

การปรับปรุงและข้อควรระวัง

• Collinear points: อัลกอริทึมนี้อาจไม่รวมจุดที่อยู่บนเส้นขอบ (แก้ได้โดยเพิ่มเงื่อนไข distance)
• Duplicate points: ควรลบจุดซ้ำก่อนประมวลผล
• Large coordinates: ใช้ long long ป้องกัน overflow ใน orientation test
• Better algorithms: Graham Scan (O(n log n)), QuickHull (เฉลี่ย O(n log n)) เร็วกว่าสำหรับ n ใหญ่

การประยุกต์ใช้

• Computer vision: shape analysis, object detection
• GIS: boundary detection, map simplification
• Robotics: collision avoidance, path planning
• Game development: mesh generation, visibility testing