Chương trình C++ triển khai thuật toán Graham Scan tìm bao lồi

Bao lồi (Convex hull) là khu vực kín nhỏ nhất có thể bao phủ tất cả các điểm dữ liệu cho trước.

Thuật toán Graham Scan sẽ tìm các điểm góc của bao lồi. Trong thuật toán này, đầu tiên chọn điểm thấp nhất. Điểm đó là điểm bắt đầu của bao lồi. Các đỉnh còn lại n-1 được sắp xếp dựa trên hướng ngược chiều kim đồng hồ từ điểm bắt đầu. Nếu hai hoặc nhiều điểm tạo thành cùng một góc, thì loại bỏ tất cả các điểm cùng góc đó trừ điểm xa nhất từ điểm bắt đầu.

Từ các điểm còn lại, đẩy chúng vào ngăn xếp (stack). Và loại bỏ các mục từ ngăn xếp một cách tuần tự, khi hướng không phải ngược chiều kim đồng hồ cho điểm đỉnh ngăn xếp, điểm thứ hai từ đỉnh và điểm mới chọn points[i], sau khi kiểm tra, chèn points[i] vào ngăn xếp.

Đầu vào: Tập hợp điểm: {(-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)} 
Đầu ra: Các điểm biên của bao lồi là: (-9, -5) (-10, 3) (-10, 4) (-7, 8) (8, 6) (8, -7) (6, -10)

Thuật toán

findConvexHull(points, n)

Đầu vào: Tập hợp điểm, số lượng điểm.

Đầu ra: Các điểm biên của bao lồi.

Bắt đầu
    minY := points[0].y
    min := 0
    Với i := 1 đến n-1 thực hiện
        y := points[i].y
        Nếu y < minY hoặc (minY = y và points[i].x < points[min].x), thì
            minY := points[i].y
            min := i
    Kết thúc
    Hoán đổi points[0] và points[min]
    p0 := points[0]
    Sắp xếp points từ points[1] đến cuối
    arrSize := 1
    Với i := 1 đến n, thực hiện
        Khi i < n-1 và (p0, points[i], points[i+1]) thẳng hàng, thực hiện
            i := i + 1
        Kết thúc
        points[arrSize] := points[i]
        arrSize := arrSize + 1
    Kết thúc
    Nếu arrSize < 3, thì
        Trả về cHullPoints
    Đẩy points[0] vào ngăn xếp
    Đẩy points[1] vào ngăn xếp
    Đẩy points[2] vào ngăn xếp
    Với i := 3 đến arrSize, thực hiện
        Trong khi đỉnh ngăn xếp, mục dưới đỉnh và points[i] không ở
        xoay ngược chiều kim đồng hồ, thực hiện
            Xóa phần tử đỉnh khỏi ngăn xếp
        Kết thúc
        Đẩy points[i] vào ngăn xếp
    Kết thúc
    Khi ngăn xếp không rỗng, thực hiện
        Mục đỉnh ngăn xếp vào cHullPoints
        Lấy ra khỏi ngăn xếp
    Kết thúc
Kết thúc

Mã ví dụ

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

struct point { 
    //định nghĩa điểm cho mặt phẳng 2D 
    int x, y; 
}; 

point p0; //dùng cho hai điểm khác 

point secondTop(stack<point> &stk) { 
    point tempPoint = stk.top(); 
    stk.pop(); 
    point res = stk.top(); 
    //lấy phần tử thứ hai từ đỉnh 
    stk.push(tempPoint); 
    //đẩy lại đỉnh trước đó 
    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; 
    //thẳng hàng 
    else if(val < 0) 
        return 2; 
    //hướng ngược chiều kim đồng hồ 
    return 1; 
    //hướng chiều kim đồng hồ 
} 

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; 
        //tìm điểm thấp nhất hoặc ngoài cùng bên trái 
        if((y < minY) || (minY == y) && points[i].x < points[min].x) { 
            minY = points[i].y; 
            min = i; 
        } 
    } 
    swap(points[0], points[min]); 
    //hoán đổi điểm min đến vị trí 0 
    p0 = points[0]; 
    qsort(&points[1], n-1, sizeof(point), comp); 
    //sắp xếp các điểm từ vị trí 1 đến cuối 
    int arrSize = 1; 
    //dùng để định vị các mục trong mảng đã sửa đổi 
    for(int i = 1; i < n; i++) { 
        //khi góc của phần tử i và (i+1) giống nhau, loại bỏ điểm 
        while(i < n-1 && direction(p0, points[i], points[i+1]) == 0) 
            i++; 
        points[arrSize] = points[i]; 
        arrSize++; 
    } 
    if(arrSize < 3) 
        return convexHullPoints; 
    //phải có ít nhất 3 điểm, trả về danh sách rỗng. 
    //tạo ngăn xếp và thêm ba điểm đầu tiên vào ngăn xếp 
    stack<point> stk; 
    stk.push(points[0]); stk.push(points[1]); stk.push(points[2]); 
    for(int i = 3; i < arrSize; i++) { 
        //cho các đỉnh còn lại 
        while(direction(secondTop(stk), stk.top(), points[i]) != 2) 
            stk.pop(); 
        //khi đỉnh, đỉnh thứ hai và điểm i không tạo vòng quay trái, loại bỏ điểm 
        stk.push(points[i]); 
    } 
    while(!stk.empty()) { 
        convexHullPoints.push_back(stk.top()); 
        //thêm điểm từ ngăn xếp 
        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 << "Các điểm biên của bao lồi là: " << endl; 
    vector<point>::iterator it; 
    for(it = result.begin(); it != result.end(); it++) 
        cout << "(" << it->x << ", " << it->y << ") "; 
}

Kết quả

Các điểm biên của bao lồi là: (-9, -5) (-10, 3) (-10, 4) (-7, 8) (8, 6) (8, -7) (6, -10)