Convex Hull ด้วย Divide and Conquer Algorithm ใน C++

ภาพรวม

Divide and Conquer Convex Hull แบ่งจุดเป็นสองครึ่ง หา Hull ของแต่ละครึ่ง แล้ว Merge สอง Hull เข้าด้วยกัน

อัลกอริทึม

1. Divide: แบ่งจุดเป็นซ้าย/ขวา (เรียงตาม X ก่อน)
2. Conquer: หา Hull ของแต่ละครึ่งแบบ Recursive (Base Case: ≤ 5 จุด ใช้ Brute Force)
3. Merge: หา Upper Tangent และ Lower Tangent ระหว่างสอง Hull แล้วรวม

ขั้นตอนสำคัญ: Tangent Finding

• Upper Tangent: เส้นที่สัมผัส Hull ทั้งสอง ด้านบน (ทั้งสอง Hull อยู่ข้างล่าง)
• Lower Tangent: เส้นที่สัมผัส Hull ทั้งสอง ด้านล่าง (ทั้งสอง Hull อยู่ข้างบน)
• ใช้ Orientation Test (Cross Product) เดินหา Tangent แบบ Walking Algorithm

โค้ดตัวอย่าง (C++) - สรุปโครงสร้างหลัก

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

using Point = pair<int, int>;
Point mid;  // Center for sorting

int quad(Point p) {  // Quadrant for polar sort
    if (p.first >= 0 && p.second >= 0) return 1;
    if (p.first <= 0 && p.second >= 0) return 2;
    if (p.first <= 0 && p.second <= 0) return 3;
    return 4;
}

int orientation(Point a, Point b, Point c) {
    long long val = 1LL * (b.second - a.second) * (c.first - b.first) -
                    1LL * (c.second - b.second) * (b.first - a.first);
    if (val == 0) return 0;
    return (val > 0) ? 1 : -1;  // 1: CW, -1: CCW
}

bool compare(Point p1, Point q1) {
    Point p = {p1.first - mid.first, p1.second - mid.second};
    Point q = {q1.first - mid.first, q1.second - mid.second};
    int qp = quad(p), qq = quad(q);
    if (qp != qq) return qp < qq;
    return 1LL * p.second * q.first < 1LL * q.second * p.first;
}

// Merger: หา Upper/Lower Tangent และรวม Hull
vector<Point> merger(vector<Point> a, vector<Point> b) {
    // ... (Implementation หา Tangents แบบ Walking)
    // Return merged hull
}

// Brute Force สำหรับ Base Case (≤ 5 points)
vector<Point> bruteHull(vector<Point> a) {
    // ... (ตรวจสอบทุกคู่จุด ว่าจุดอื่นอยู่ข้างเดียวกันหมด)
}

// Main Divide Function
vector<Point> divide(vector<Point> a) {
    if (a.size() <= 5) return bruteHull(a);

    vector<Point> left(a.begin(), a.begin() + a.size()/2);
    vector<Point> right(a.begin() + a.size()/2, a.end());

    vector<Point> leftHull = divide(left);
    vector<Point> rightHull = divide(right);

    return merger(leftHull, rightHull);
}

int main() {
    vector<Point> points = {{0,0}, {1,-4}, {-1,-5}, {-5,-3}, {-3,-1}, {-1,-3}, {-2,-2}, {-1,-1}, {-2,-1}, {-1,1}};
    sort(points.begin(), points.end());
    auto hull = divide(points);
    for (auto p : hull) cout << p.first << " " << p.second << endl;
    return 0;
}

ผลลัพธ์

Convex Hull:
-5 -3
-1 -5
1 -4
0 0
-1 1

Complexity Analysis

• Time: O(n log n) (T(n) = 2T(n/2) + O(n) สำหรับ Merge)
• Space: O(n) (Recursion Stack + Hull Storage)
• Base Case Brute Force: O(1) สำหรับ n ≤ 5

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

• Merge Step เป็นหัวใจสำคัญ - ต้องหา Tangents ถูกต้อง
• Upper Tangent: เดินจาก Rightmost ของ Left Hull และ Leftmost ของ Right Hull
• Lower Tangent: เดินจาก Rightmost ของ Left Hull และ Leftmost ของ Right Hull (ทิศตรงข้าม)
• การ Sort จุดตาม X ก่อน Divide สำคัญมาก (Divide ตาม X-Median)
• ในทางปฏิบัติ Monotone Chain (Andrew's Algorithm) ใช้ง่ายกว่าและเร็วกว่าคงที่

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

• Computational Geometry, GIS, Computer Vision, Robotics
• Collision Detection, Pattern Recognition, Image Processing