Thuật toán Graham Scan (Convex Hull)

Giới thiệu

Bao lồi (convex hull) là vùng đóng tối thiểu 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, trước 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 n-1 còn lại đượ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 stack. Và loại bỏ các mục từ stack lần lượt, khi hướng không phải ngược chiều kim đồng hồ cho điểm đỉnh stack, đ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 stack.

Đầu vào và Đầu ra

Đầu vào: Tậ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 các điểm, số lượng điểm.
Đầu ra: Các điểm biên của bao lồi.

Begin
    minY := points[0].y
    min := 0
    for i := 1 to n-1 do
        y := points[i].y
        if y < minY or minY = y and points[i].x < points[min].x, then
            minY := points[i].y
            min := i
    done
    hoán đổi points[0] và points[min]
    p0 := points[0]
    sắp xếp points từ points[1] đến cuối
    arrSize := 1
    for i := 1 to n, do
        khi i < n-1 và (p0, points[i], points[i+1]) thẳng hàng, do
            i := i + 1
        done
        points[arrSize] := points[i]
        arrSize := arrSize + 1
    done
    if arrSize < 3, then
        return cHullPoints
    đẩy points[0] vào stack
    đẩy points[1] vào stack
    đẩy points[2] vào stack
    for i := 3 to arrSize, do
        while đỉnh stack, phần tử dưới đỉnh và points[i] không ở
            xoay ngược chiều kim đồng hồ, do
            xóa phần tử đỉnh khỏi stack
        done
        đẩy points[i] vào stack
    done
    while stack không rỗng, do
        mục đỉnh stack chèn vào cHullPoints
        pop từ stack
    done
End

Ví dụ (C++)

#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 để so sánh 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 phần tử đỉnh trước lại
    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;  // ngược chiều kim đồng hồ
    return 1;  // cù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 trái nhất
        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 về vị trí 0
    p0 = points[0];
    qsort(&points[1], n-1, sizeof(point), comp);  // sắp xếp điểm từ vị trí 1 đến cuối
    int arrSize = 1;  // dùng để định vị 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 stack và thêm ba điểm đầu tiên vào stack
    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 rẽ trái, loại bỏ điểm
        stk.push(points[i]);
    }
    while(!stk.empty()) {
        convexHullPoints.push_back(stk.top());  // thêm điểm từ 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 << ") ";
}

Kết quả

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