Cài đặt thuật toán Convex Hull (Jarvis March) trong lập trình

Trong lập trình, thuật toán Convex Hull (Jarvis March) là một phương pháp cơ bản để tìm tập hợp lồi của một tập hợp điểm trong không gian hai chiều. Tập hợp lồi của một tập hợp điểm là hình đa giác lồi nhỏ nhất chứa tất cả các điểm trong tập hợp đó. Jarvis March còn được gọi là thuật toán Gift Wrapping bởi cách tiếp cận của nó giống như quá trình gói quà.

Ý tưởng của thuật toán

Thuật toán bắt đầu từ điểm trái nhất trong số các điểm đầu vào và sau đó liên tục chọn các điểm sao cho tất cả các điểm khác đều nằm ở phía bên trái của đoạn thẳng được tạo từ điểm hiện tại đến điểm mới chọn. Quá trình này tiếp tục cho đến khi trở về điểm xuất phát ban đầu.

Các bước thực hiện

1. Chọn điểm bắt đầu: Chọn điểm có hoành độ nhỏ nhất (trái nhất). Nếu có nhiều điểm có cùng hoành độ, chọn điểm có tung độ nhỏ nhất.
2. Lựa chọn điểm tiếp theo: Từ điểm hiện tại, tìm điểm tiếp theo sao cho tất cả các điểm còn lại đều nằm ở phía bên trái của đoạn thẳng nối từ điểm hiện tại tới điểm tiếp theo.
3. Lặp lại: Lặp lại bước 2 cho đến khi trở về điểm bắt đầu.

Cài đặt thuật toán

Dưới đây là một ví dụ mã cài đặt thuật toán Jarvis March bằng ngôn ngữ Python.

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def orientation(p, q, r):
    # Tính giá trị hướng của ba điểm
    val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y)
    if val == 0:
        return 0  # Thẳng hàng
    elif val > 0:
        return 1  # Phải
    else:
        return 2  # Trái

def convex_hull(points):
    # Số điểm đầu vào
    n = len(points)
    if n < 3:
        return
    
    # Tạo một danh sách mảng kết quả
    hull = []
    
    # Tìm điểm trái nhất
    l = 0
    for i in range(1, n):
        if points[i].x < points[l].x:
            l = i
    
    p = l
    while True:
        hull.append(points[p])
        
        # Tìm điểm q sao cho tất cả các điểm nằm bên trái của đoạn pq
        q = (p + 1) % n
        for i in range(n):
            if orientation(points[p], points[i], points[q]) == 2:
                q = i
        
        p = q
        
        if p == l:
            break
    
    return hull

# Ví dụ dữ liệu điểm
points = [Point(0, 3), Point(2, 2), Point(1, 1), Point(2, 1), Point(3, 0), Point(0, 0), Point(3, 3)]
hull = convex_hull(points)

# In kết quả
for point in hull:
    print(f"({point.x}, {point.y})")

Phân tích độ phức tạp

Thuật toán Jarvis March có độ phức tạp thời gian O(n*h) với n là số lượng điểm và h là số lượng điểm trên bao lồi. Điều này có nghĩa rằng nó đặc biệt hiệu quả khi số lượng điểm trên bao lồi nhỏ so với tổng số điểm, tuy nhiên, nó có thể trở nên kém hiệu quả khi số lượng điểm trên bao lồi gần bằng với tổng số điểm.

Ứng dụng

Thuật toán này ứng dụng rộng rãi trong các lĩnh vực như đồ họa máy tính, robot và hệ thống GIS (hệ thống thông tin địa lý) để tìm kiếm vùng không gian nhỏ nhất bao quanh một tập hợp các điểm dữ liệu.

Trên đây là tóm lược về việc cài đặt thuật toán Jarvis March để tìm bao lồi của một tập hợp điểm. Hy vọng rằng thông tin này sẽ hữu ích cho bạn trong việc hiểu và triển khai thuật toán này trong các dự án lập trình của mình.