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

Thuật toán Jarvis March (còn gọi là Gift Wrapping) được sử 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 ngoài cùng bên trái của tập dữ liệu, chúng ta giữ các điểm trong bao lồi bằng cách xoay ngược chiều kim đồng hồ. Từ điểm hiện tại, chúng 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 thành 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: 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) (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.

Bắt đầu
    start := points[0]
    Với mỗi điểm i, thực hiện
        Nếu points[i].x < start.x, thì
            // lấy điểm ngoài cùng bên trái
            start := points[i]
    Kết thúc
    current := start
    Thêm điểm bắt đầu vào tập kết quả.
    Định nghĩa tập colPts để lưu các điểm thẳng hàng
    Lặp vô tận (while true), thực hiện
        next := points[i]
        Với tất cả các điểm i trừ điểm 0, thực hiện
            Nếu points[i] = current, thì
                Bỏ qua phần tiếp theo, chuyển sang lần lặp tiếp theo
            val := tích chéo của current, next, points[i]
            Nếu val > 0, thì
                next := points[i]
                Xóa mảng colPts
            Ngược lại nếu val = 0, thì
                Nếu next gần current hơn points[i], thì
                    Thêm next vào colPts
                    next := points[i]
                Ngược lại
                    Thêm points[i] vào colPts
        Kết thúc
        Thêm tất cả các mục trong colPts vào kết quả
        Nếu next = start, thì
            Thoát vòng lặp
        Chèn next vào kết quả
        current := next
    Kết thúc
    Trả về kết quả
Kết thúc

Mã ví dụ

#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 ngoài cùng bên trái để 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 các đ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 tập kết quả 
        } 
        if(nextTarget == start) //khi điểm tiếp theo là điểm bắt đầu nghĩa là vùng đã đượ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 << "Các điểm biên của bao lồi là: " << endl; 
    set<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) (6, -10) (8, -7) (8, 6) (-7, 8) (-10, 4) (-10, 3)