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

Việc tìm bao lồi (Convex Hull) của một tập hợp các điểm trong không gian hai chiều là một bài toán quan trọng trong hình học tính toán và có nhiều ứng dụng thực tế. Một trong những thuật toán phổ biến để giải quyết bài toán này là thuật toán Graham Scan. Sau đây, chúng ta sẽ tìm hiểu cách cài đặt thuật toán này trong lập trình.

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

Thuật toán Graham Scan được thiết kế để xây dựng bao lồi từ một tập hợp các điểm bằng các bước cơ bản sau:

1. Chọn điểm gốc (pivot point): Điểm có y thấp nhất. Nếu có nhiều điểm có y thấp nhất, chọn điểm có x thấp nhất trong số đó.
2. Sắp xếp các điểm theo góc cực so với điểm gốc.
3. Duyệt qua các điểm đã sắp xếp và xây dựng bao lồi bằng cách duy trì một ngăn xếp để theo dõi các điểm là đỉnh của bao lồi.

2. Chi tiết cài đặt

Dưới đây là cách cài đặt thuật toán Graham Scan trong ngôn ngữ lập trình Python.

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

    def __repr__(self):
        return f"({self.x}, {self.y})"

# Tìm điểm gốc
def find_pivot(points):
    pivot = points[0]
    for p in points[1:]:
        if (p.y < pivot.y) or (p.y == pivot.y and p.x < pivot.x):
            pivot = p
    return pivot

# Tính góc giữa hai điểm với điểm gốc
def polar_angle(p0, p1):
    return (p1.y - p0.y) / (p1.x - p0.x) if p1.x != p0.x else float('inf')

# Kiểm tra xem ba điểm có tạo thành một vòng quay trái hay không
def ccw(p0, p1, p2):
    return (p1.x - p0.x) * (p2.y - p0.y) > (p1.y - p0.y) * (p2.x - p0.x)

# Hàm chính cài đặt thuật toán Graham Scan
def graham_scan(points):
    pivot = find_pivot(points)
    points.sort(key=lambda p: (polar_angle(pivot, p), (p.x - pivot.x)**2 + (p.y - pivot.y)**2))

    hull = [pivot]
    for point in points:
        while len(hull) > 1 and not ccw(hull[-2], hull[-1], point):
            hull.pop()
        hull.append(point)
    
    return hull

# Các điểm đầu vào
points = [Point(0, 3), Point(2, 2), Point(1, 1), Point(2, 1), Point(3, 0), Point(0, 0), Point(3, 3)]
hull = graham_scan(points)

print("Các điểm tạo thành bao lồi là:")
for point in hull:
    print(point)

3. Giải thích chi tiết

• Lớp Point: Xác định một điểm trong không gian hai chiều với các thuộc tính x và y.
• Chọn điểm gốc: Hàm find_pivot duyệt qua tất cả các điểm để tìm điểm có y thấp nhất (và x thấp nhất nếu có nhiều điểm có y bằng nhau).
• Sắp xếp điểm theo góc cực: Hàm polar_angle tính toán góc giữa hai điểm so với điểm gốc. Các điểm sau đó được sắp xếp theo góc cực và khoảng cách từ điểm gốc.
• Thuật toán chính: Hàm graham_scan sử dụng một ngăn xếp để theo dõi các điểm tạo thành bao lồi. Khi thêm mỗi điểm mới vào, chúng ta kiểm tra xem nó có tạo thành một góc quay trái với hai điểm trước đó hay không. Nếu không, loại bỏ điểm giữa khỏi ngăn xếp vì nó không thuộc bao lồi.

Qua đây, chúng ta đã có một cái nhìn tổng quan về cách cài đặt và hoạt động của thuật toán Graham Scan. Hy vọng rằng bài viết này sẽ giúp ích cho bạn trong việc áp dụng thuật toán này trong các dự án của mình.