Thuật toán bao lồi (Convex Hull) trong C++: Lý thuyết và cài đặt chi tiết

Từ khóa chính: thuật toán bao lồi, convex hull, Graham scan, Andrew’s monotone chain, C++, xử lý hình học

🔗 Xem thêm:
Kỹ thuật dựng góc chữ nhật (Wikipedia)
Kỹ thuật dựng góc chữ nhật
Wiki: Convex Hull

Mục lục

1. Thuật toán bao lồi là gì?

Thuật toán bao lồi (Convex Hull) là một trong những thuật toán quan trọng nhất trong lĩnh vực hình học tính toán. Bài toán bao lồi yêu cầu tìm ra bao lồi nhỏ nhất bao trọn tập hợp các điểm trong mặt phẳng. Bao lồi là một đa giác lồi sao cho tất cả các điểm nằm bên trong hoặc trên biên của nó. Một cách hình tượng, nếu bạn đặt một sợi dây cao su quanh tập điểm, bao lồi chính là hình dạng mà sợi dây tạo thành khi ôm sát các điểm ngoài cùng.

1.1 Ứng dụng của thuật toán bao lồi

Xử lý ảnh và nhận diện đối tượng.
Phân tích hình học trong bản đồ số và định vị.
Lập trình đồ họa và xử lý va chạm.
Tối ưu hóa không gian và các thuật toán GIS.
Trong sinh học tính toán: bao lồi giúp xác định vùng hoạt động của các chuỗi DNA hoặc vùng hoạt động của protein.
Trong học máy (Machine Learning): một số thuật toán phân loại và phân cụm dữ liệu có thể sử dụng bao lồi để xác định ranh giới lớp.

2. Các thuật toán phổ biến giải bài toán bao lồi

Có nhiều cách giải bài toán bao lồi, trong đó phổ biến nhất là:

Graham Scan – sắp xếp theo góc và dựng đa giác theo chiều ngược kim đồng hồ.
Andrew’s Monotone Chain – phiên bản đơn giản hơn dựa trên sắp xếp điểm theo tọa độ x.
Jarvis March – còn gọi là thuật toán Gift Wrapping.
QuickHull – một biến thể của thuật toán phân tách nhanh.

2.1 Độ phức tạp

Các thuật toán như Graham Scan và Monotone Chain đều có độ phức tạp \(O(n \log n)\) do bước sắp xếp điểm ban đầu. Một số thuật toán như Jarvis March có độ phức tạp \(O(nh)\) với \(h\) là số điểm thuộc bao lồi.

3. Cài đặt thuật toán bao lồi trong C++

3.1 Cấu trúc dữ liệu cần thiết

Sử dụng cấu trúc `Point` để lưu trữ tọa độ điểm, và hàm tính tích có hướng để xác định thứ tự rẽ trái/phải. Cần lưu ý là trong bài toán này, thứ tự điểm rất quan trọng, đặc biệt là để tránh chọn nhầm điểm khi có nhiều điểm đồng phương.

3.1.1 Struct điểm và toán tử so sánh

struct Point {
    int x, y;
    bool operator < (const Point& p) const {
        return x < p.x || (x == p.x && y < p.y);
    }
};

3.1.2 Hàm tích có hướng

int cross(const Point& O, const Point& A, const Point& B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

3.2 Cài đặt thuật toán Andrew (Monotone Chain)

Andrew’s Monotone Chain là thuật toán hiệu quả, dễ cài đặt và cho kết quả ổn định. Bằng cách sắp xếp điểm và duyệt qua hai chiều (lower hull và upper hull), thuật toán này đảm bảo không có điểm dư thừa hoặc sai lệch.

vector convexHull(vector& P) {
    int n = P.size(), k = 0;
    if (n <= 3) return P;
    sort(P.begin(), P.end());
    vector H(2*n);

    for (int i = 0; i < n; ++i) {
        while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
        H[k++] = P[i];
    }

    for (int i = n-2, t = k+1; i >= 0; --i) {
        while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
        H[k++] = P[i];
    }

    H.resize(k-1);
    return H;
}

4. Ví dụ minh họa và thực hành

Cho tập điểm: (0, 3), (2, 2), (1, 1), (2, 1), (3, 0), (0, 0), (3, 3). Kết quả bao lồi là các điểm đi theo chiều ngược kim đồng hồ: (0, 0), (3, 0), (3, 3), (0, 3).

Bạn có thể thử nghiệm trên các nền tảng online như GeeksForGeeks, HackerRank hoặc tạo giao diện vẽ điểm bằng C++/OpenGL để trực quan hơn. Việc kết hợp trực quan hóa giúp nắm vững hướng rẽ trái/phải và diễn biến thuật toán.

5. Tối ưu và xử lý biên

Trong thực tế, bạn có thể gặp các điểm trùng nhau hoặc điểm đồng phương. Cần lọc bỏ các điểm trùng để tránh kết quả sai. Ngoài ra, nên xử lý các bài toán thực tế với kiểu dữ liệu `double` nếu yêu cầu độ chính xác cao, đặc biệt khi làm việc với tọa độ bản đồ hoặc hình học máy tính trong không gian ba chiều.

6. Tổng kết

Thuật toán bao lồi là công cụ mạnh mẽ để xử lý các bài toán hình học phẳng. Trong C++, việc cài đặt khá dễ dàng nhờ hỗ trợ từ STL. Convex Hull không chỉ là một bài toán kinh điển mà còn ứng dụng mạnh mẽ trong khoa học dữ liệu, GIS, đồ họa, AI và học máy.

Việc hiểu rõ thuật toán này sẽ giúp bạn giải quyết tốt các bài toán về không gian, khoảng cách, va chạm, và tối ưu vùng hoạt động trong không gian hai chiều hoặc ba chiều. Đây là kiến thức bắt buộc với bất kỳ ai theo đuổi lĩnh vực khoa học máy tính hoặc khoa học dữ liệu.