Ví dụ Convex Hull (Bao lồi) - Thuật toán Jarvis March

Ở đây chúng ta xem ví dụ về convex hull (bao lồi). Cho tập hợp các điểm. Nhiệm vụ tạo đa giác bằng ít điểm nhất để bao phủ tất cả các điểm cho trước. Phần này dùng thuật toán Jarvis March để tìm convex hull.

Thuật toán Jarvis March dùng để phát hiện các điểm góc của bao lồi từ tậ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, chọn điểm tiếp theo bằng cách kiểm tra định 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 duyệt hết đ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

Input – 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)}

Output – Các điểm biên của convex hull:

(-9, -5) (6, -10) (8, -7) (8, 6) (-7, 8) (-10, 4) (-10, 3)

Thuật toán

findConvexHull(points, n)
Input: Các điểm, số điểm. Output: Điểm góc của convex hull.
Begin
    start := points[0]
    for each point i, do
        if points[i].x < start.x then start := points[i]  // điểm trái nhất
    done
    current := start
    add start vào tập kết quả
    define colPts để lưu điểm thẳng hàng
    while true do
        next := points[0]
        for all points i except 0th, do
            if points[i] == current then continue
            val := cross product của current, next, points[i]
            if val > 0 then
                next := points[i]
                clear colPts
            else if val == 0 then
                if next gần current hơn points[i] thì add next vào colPts, next := points[i]
                else add points[i] vào colPts
        done
        add tất cả colPts vào kết quả
        if next == start then break
        insert 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 {
    int x, y;
    bool operator==(point p2) { return x == p2.x && y == p2.y; }
    bool operator<(const point &p2) const { return true; } // dummy cho set
};

int crossProduct(point a, point b, point c) {
    int y1 = a.y - b.y, y2 = a.y - c.y;
    int x1 = a.x - b.x, x2 = a.x - c.x;
    return y2*x1 - y1*x2; // <0: c bên trái, >0: c bên phải, =0: thẳng hàng
}

int distance(point a, point b, point c) {
    int y1 = a.y - b.y, y2 = a.y - c.y;
    int x1 = a.x - b.x, x2 = a.x - c.x;
    int item1 = y1*y1 + x1*x1;
    int item2 = y2*y2 + x2*x2;
    if(item1 == item2) return 0;
    else if(item1 < item2) return -1;
    return 1;
}

set<point> findConvexHull(point points[], int n) {
    point start = points[0];
    for(int i=1; i 0) { nextTarget = points[i]; collinearPoints = new vector<point>(); }
            else if(val == 0) {
                if(distance(current, nextTarget, points[i]) < 0) {
                    collinearPoints->push_back(nextTarget);
                    nextTarget = points[i];
                } else collinearPoints->push_back(points[i]);
            }
        }
        for(auto it = collinearPoints->begin(); it != collinearPoints->end(); it++)
            result.insert(*it);
        if(nextTarget == start) 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 = findConvexHull(points, n);
    cout << "Boundary points of convex hull are: " << endl;
    for(auto 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)