โปรแกรม C++ ใช้ Graham Scan หา Convex Hull

Convex Hull คือพื้นที่ปิดที่เล็กที่สุดที่สามารถครอบคลุมจุดข้อมูลทั้งหมดได้ อัลกอริทึม Graham's Scan จะหาจุดมุมของ Convex Hull โดยเริ่มจากเลือกจุดที่ต่ำที่สุด จุดนั้นคือจุดเริ่มต้นของ Convex Hull จุดยอดที่เหลือ n-1 จุดจะถูกจัดเรียงตามทิศทางทวนเข็มนาฬิกาจากจุดเริ่มต้น หากมีจุด 2 จุดขึ้นไปที่สร้างมุมเท่ากัน ให้ลบจุดที่มีมุมเดียวกันทั้งหมดยกเว้นจุดที่ไกลที่สุดจากจุดเริ่มต้น

จากจุดที่เหลือ ให้ push เข้า stack และนำรายการออกจาก stack ทีละรายการ เมื่อการวางแนวไม่ใช่ทวนเข็มนาฬิกาสำหรับจุดบนสุดของ stack จุดที่สองจากบนสุด และจุดที่เลือกใหม่ points[i] หลังจากตรวจสอบแล้ว ให้ insert points[i] เข้า stack

Input: ชุดจุด {(-7,8), (-4,6), (2,6), (6,4), (8,6), (7,-2), (4,-6), (8,-7),(0,0), (3,-2),(6,-10),(0,-6),(-9,-5),(-8,-2),(-8,0),(-10,3),(-2,2),(-10,4)}
Output: จุดขอบเขต Convex Hull: (-9, -5) (-10, 3) (-10, 4) (-7, 8) (8, 6) (8, -7) (6, -10)

อัลกอริทึม

findConvexHull(points, n)

Input: ชุดจุด และจำนวนจุด

Output: จุดขอบเขตของ Convex Hull

Begin
    minY := points[0].y
    min := 0
    for i := 1 ถึง n-1 ทำ
        y := points[i].y
        ถ้า y < minY หรือ minY = y และ points[i].x < points[min].x แล้ว
            minY := points[i].y
            min := i
        จบ if
    จบ for
    สลับ points[0] และ points[min]
    p0 := points[0]
    จัดเรียง points จาก points[1] ถึงจุดสุดท้าย
    arrSize := 1
    for i := 1 ถึง n ทำ
        เมื่อ i < n-1 และ (p0, points[i], points[i+1]) เป็น collinear ทำ
            i := i + 1
        จบ while
        points[arrSize] := points[i]
        arrSize := arrSize + 1
    จบ for
    ถ้า arrSize < 3 แล้ว
        return cHullPoints
    จบ if
    push points[0] เข้า stack
    push points[1] เข้า stack
    push points[2] เข้า stack
    for i := 3 ถึง arrSize ทำ
        while จุดบนสุดของ stack, จุดใต้จุดบนสุด และ points[i] ไม่ได้หมุนทวนเข็มนาฬิกา ทำ
            ลบจุดบนสุดออกจาก stack
        จบ while
        push points[i] เข้า stack
    จบ for
    while stack ไม่ว่าง ทำ
        เพิ่มจุดบนสุดของ stack เข้า cHullPoints
        pop จาก stack
    จบ while
End

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

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

struct point {
    int x, y;
};

point p0; // ใช้สำหรับเปรียบเทียบจุดอีกสองจุด

point secondTop(stack<point> &stk) {
    point tempPoint = stk.top();
    stk.pop();
    point res = stk.top(); // ได้จุดที่สองจากบนสุด
    stk.push(tempPoint); // push จุดบนสุดเดิมกลับไป
    return res;
}

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

int direction(point a, point b, point c) {
    int val = (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
    if (val == 0)
        return 0; // collinear
    else if(val < 0)
        return 2; // ทิศทางทวนเข็มนาฬิกา
    return 1; // ทิศทางตามเข็มนาฬิกา
}

int comp(const void *point1, const void*point2) {
    point *p1 = (point*)point1;
    point *p2 = (point*)point2;
    int dir = direction(p0, *p1, *p2);
    if(dir == 0)
        return (squaredDist(p0, *p2) >= squaredDist(p0, *p1))?-1 : 1;
    return (dir==2)? -1 : 1;
}

vector<point> findConvexHull(point points[], int n) {
    vector<point> convexHullPoints;
    int minY = points[0].y, min = 0;
    for(int i = 1; i<n; i++) {
        int y = points[i].y;
        // หาจุดที่ต่ำที่สุดหรือซ้ายสุด
        if((y < minY) || (minY == y) && points[i].x < points[min].x) {
            minY = points[i].y;
            min = i;
        }
    }
    swap(points[0], points[min]); // สลับจุด min ไปที่ตำแหน่ง 0
    p0 = points[0];
    qsort(&points[1], n-1, sizeof(point), comp); // จัดเรียงจุดจากตำแหน่ง 1 ถึงจุดสุดท้าย
    
    int arrSize = 1; // ใช้สำหรับระบุตำแหน่งในอาร์เรย์ที่ปรับปรุงแล้ว
    for(int i = 1; i<n; i++) {
        // เมื่อมุมของจุดที่ i และ (i+1) เท่ากัน ให้ลบจุด
        while(i < n-1 && direction(p0, points[i], points[i+1]) == 0)
            i++;
        points[arrSize] = points[i];
        arrSize++;
    }
    
    if(arrSize < 3)
        return convexHullPoints; // ต้องมีจุดอย่างน้อย 3 จุด คืนรายการว่าง
    
    // สร้าง stack และเพิ่มจุดแรก 3 จุดเข้า stack
    stack<point> stk;
    stk.push(points[0]); 
    stk.push(points[1]); 
    stk.push(points[2]);
    
    for(int i = 3; i<arrSize; i++) {
        // สำหรับจุดยอดที่เหลือ
        while(direction(secondTop(stk), stk.top(), points[i]) != 2)
            stk.pop(); // เมื่อจุดบนสุด จุดที่สองจากบนสุด และจุดที่ i ไม่ทำการเลี้ยวซ้าย ให้ลบจุด
        stk.push(points[i]);
    }
    
    while(!stk.empty()) {
        convexHullPoints.push_back(stk.top()); // เพิ่มจุดจาก stack
        stk.pop();
    }
    
    return convexHullPoints;
}

int main() {
    point points[] = {{-7,8},{-4,6},{2,6},{6,4},{8,6},{7,-2},{4,-6},{8,-7},{0,0},
                      {3,-2},{6,-10},{0,-6},{-9,-5},{-8,-2},{-8,0},{-10,3},{-2,2},{-10,4}};
    int n = 18;
    vector<point> result;
    result = findConvexHull(points, n);
    cout << "Boundary points of convex hull are: "<<endl;
    vector<point>::iterator it;
    for(it = result.begin(); it!=result.end(); it++)
        cout << "(" << it->x << ", " <<it->y <<") ";
}

ผลลัพธ์

Boundary points of convex hull are: (-9, -5) (-10, 3) (-10, 4) (-7, 8) (8, 6) (8, -7) (6, -10)