Cài đặt thuật toán Delaunay Triangulation trong lập trình

Delaunay Triangulation là một trong những thuật toán cơ bản và quan trọng trong lĩnh vực đồ họa máy tính và hình học tính toán. Nó được sử dụng rộng rãi để tạo ra mạng lưới tam giác từ tập hợp các điểm trong không gian phẳng (2D). Mạng lưới này có tính chất đặc biệt là không có điểm nào nằm bên trong đường tròn ngoại tiếp của bất kỳ tam giác nào trong mạng lưới. Dưới đây là các bước cài đặt thuật toán Delaunay Triangulation trong lập trình.

Các bước thực hiện thuật toán

1. Khởi tạo mạng lưới ban đầu: Bắt đầu bằng cách tạo một tam giác bao phủ tất cả các điểm cần tri giác hóa. Điều này thường được thực hiện bằng cách thêm các điểm cực trị (vertex cực lớn hoặc cực nhỏ) để đảm bảo rằng tất cả các điểm khác nằm trong tam giác này.

2. Thêm từng điểm vào mạng lưới: Đối với mỗi điểm trong tập hợp điểm, xác định tam giác chứa điểm đó và tách tam giác thành ba tam giác mới, mỗi tam giác mới có đỉnh trùng với điểm mới thêm vào.

3. Xử lý tính chất Delaunay: Kiểm tra và sửa đổi các tam giác để đảm bảo không có điểm nào nằm bên trong đường tròn ngoại tiếp của bất kỳ tam giác nào, thường được thực hiện bằng Flip-edge (đảo cạnh).

Cấu trúc dữ liệu

Để triển khai Delaunay Triangulation, cần thiết lập các cấu trúc dữ liệu như điểm (point), cạnh (edge), và tam giác (triangle). Các cấu trúc này sẽ giúp quản lý và thao tác trên các đối tượng hình học dễ dàng hơn.

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

class Edge:
    def __init__(self, p1, p2):
        self.p1 = p1
        self.p2 = p2

class Triangle:
    def __init__(self, p1, p2, p3):
        self.p1 = p1
        self.p2 = p2
        self.p3 = p3
        self.edges = [Edge(p1, p2), Edge(p2, p3), Edge(p3, p1)]

Triển khai thuật toán

Dưới đây là một đoạn mã Python minh họa cách cài đặt thuật toán Delaunay Triangulation cơ bản.

def circum_circle_contains(triangle, point):
    ax, ay = triangle.p1.x, triangle.p1.y
    bx, by = triangle.p2.x, triangle.p2.y
    cx, cy = triangle.p3.x, triangle.p3.y
    dx, dy = point.x, point.y

    A = [[ax, ay, ax**2 + ay**2, 1],
         [bx, by, bx**2 + by**2, 1],
         [cx, cy, cx**2 + cy**2, 1],
         [dx, dy, dx**2 + dy**2, 1]]
    
    det = np.linalg.det(A)
    return det > 0

def delaunay_triangulation(points):
    # Tạo tam giác siêu lớn bao phủ tất cả các điểm
    p1 = Point(-1e6, -1e6)
    p2 = Point(1e6, -1e6)
    p3 = Point(0, 1e6)
    triangles = [Triangle(p1, p2, p3)]

    for point in points:
        bad_triangles = []
        for triangle in triangles:
            if circum_circle_contains(triangle, point):
                bad_triangles.append(triangle)

        # Tạo polygon bằng cách lấy tất cả các cạnh của bad_triangles
        polygon = []
        for triangle in bad_triangles:
            for edge in triangle.edges:
                shared = False
                for other in bad_triangles:
                    if other != triangle and edge in other.edges:
                        shared = True
                        break
                if not shared:
                    polygon.append(edge)
        
        # Loại bỏ các tam giác xấu
        triangles = [t for t in triangles if t not in bad_triangles]

        # Tạo các tam giác mới từ polygon
        for edge in polygon:
            new_triangle = Triangle(edge.p1, edge.p2, point)
            triangles.append(new_triangle)

    return triangles

Kết luận

Triangulation Delaunay là một thuật toán mạnh mẽ trong nhiều ứng dụng từ mô phỏng khoa học, đồ họa máy tính cho đến phân tích dữ liệu địa lý. Việc hiểu và triển khai được thuật toán này đem lại nhiều lợi ích thiết thực trong việc xử lý các bài toán liên quan đến hình học trên máy tính.