Thuật toán Jarvis March (Convex Hull)

Giới thiệu

Thuật toán Jarvis March được dùng để phát hiện các điểm góc của bao lồi (convex hull) từ một tập hợp điểm dữ liệu cho trước.

Bắt đầu từ điểm bên trái nhất của tập dữ liệu, ta giữ các điểm trong bao lồi bằng cách quay ngược chiều kim đồng hồ. Từ điểm hiện tại, ta có thể chọn điểm tiếp theo bằng cách kiểm tra hướng của các điểm đó từ điểm hiện tại. Khi góc lớn nhất, điểm đó được chọn. Sau khi hoàn tất tất cả các điểm, khi điểm tiếp theo là điểm bắt đầu, dừng thuật toán.

Đầ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) (6, -10) (8, -7) (8, 6) (-7, 8) (-10, 4) (-10, 3)

Thuật toán

findConvexHull(points, n)
Đầu vào: Các điểm, số lượng điểm.
Đầu ra: Các điểm góc của bao lồi.

Begin
    start := points[0]
    for each point i, do
        if points[i].x < start.x, then
            // lấy điểm bên trái nhất
            start := points[i]
    done
    current := start
    thêm điểm start vào tập kết quả.
    định nghĩa tập colPts để lưu các điểm thẳng hàng
    while true, do
        // bắt đầu vòng lặp vô hạn
        next := points[i]
        for all points i except 0th point, do
            if points[i] = current, then
                bỏ qua phần tiếp theo, sang lần lặp tiếp theo
            val := tích chéo của current, next, points[i]
            if val > 0, then
                next := points[i]
                xóa mảng colPts
            else if cal = 0, then
                if next gần current hơn points[i], then
                    thêm next vào colPts
                    next := points[i]
                else
                    thêm points[i] vào colPts
        done
        thêm tất cả mục trong colPts vào kết quả
        if next = start, then
            break vòng lặp
        chèn next vào kết quả
        current := next
    done
    return result
End

Ví dụ (C++)

#include <iostream>
#include <set>
#include <vector>
using namespace std;

struct point {
    // định nghĩa điểm cho mặt phẳng 2d
    int x, y;
    bool operator==(point p2) {
        if(x == p2.x && y == p2.y)
            return 1;
        return 0;
    }
    bool operator<(const point &p2)const {
        // hàm so sánh giả dùng để sắp xếp trong set
        return true;
    }
};

int crossProduct(point a, point b, point c) {
    // tìm vị trí của c từ vectơ ab
    int y1 = a.y - b.y;
    int y2 = a.y - c.y;
    int x1 = a.x - b.x;
    int x2 = a.x - c.x;
    return y2*x1 - y1*x2;  // nếu kết quả < 0, c ở bên trái, > 0 c ở bên phải, = 0 a,b,c thẳng hàng
}

int distance(point a, point b, point c) {
    int y1 = a.y - b.y;
    int y2 = a.y - c.y;
    int x1 = a.x - b.x;
    int x2 = a.x - c.x;
    int item1 = (y1*y1 + x1*x1);
    int item2 = (y2*y2 + x2*x2);
    if(item1 == item2)
        return 0;  // khi b và c cùng khoảng cách từ a
    else if(item1 < item2)
        return -1;  // khi b gần a hơn
    return 1;  // khi c gần a hơn
}

set<point> findConvexHull(point points[], int n) {
    point start = points[0];
    for(int i = 1; i < n; i++) {
        // tìm điểm bên trái nhất để bắt đầu
        if(points[i].x < start.x)
            start = points[i];
    }
    point current = start;
    set<point> result;  // set dùng để tránh nhập điểm trùng lặp
    result.insert(start);
    vector<point> *collinearPoints = new vector<point>();
    while(true) {
        point nextTarget = points[0];
        for(int i = 1; i < n; i++) {
            if(points[i] == current)  // khi điểm chọn là điểm hiện tại, bỏ qua phần còn lại
                continue;
            int val = crossProduct(current, nextTarget, points[i]);
            if(val > 0) {  // khi điểm i ở bên trái
                nextTarget = points[i];
                collinearPoints = new vector<point>();  // reset điểm thẳng hàng
            } else if(val == 0) {  // nếu ba điểm thẳng hàng
                if(distance(current, nextTarget, points[i]) < 0) { // thêm điểm gần hơn vào danh sách thẳng hàng
                    collinearPoints->push_back(nextTarget);
                    nextTarget = points[i];
                } else {
                    collinearPoints->push_back(points[i]); // khi điểm i gần hơn hoặc bằng nextTarget
                }
            }
        }
        vector<point>::iterator it;
        for(it = collinearPoints->begin(); it != collinearPoints->end(); it++) {
            result.insert(*it);  // thêm tất cả điểm trong collinear points vào result set
        }
        if(nextTarget == start)  // khi điểm tiếp theo là start nghĩa là khu vực đã được bao phủ
            break;
        result.insert(nextTarget);
        current = nextTarget;
    }
    return result;
}

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;
    set<point> result;
    result = findConvexHull(points, n);
    cout << "Boundary points of convex hull are: " << endl;
    set<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) (6, -10) (8, -7) (8, 6) (-7, 8) (-10, 4) (-10, 3)