Abstract. This paper describes a fast parallel algorithm for constructing Delaunay triangulation. It belongs to the class of incremental construction algorithm. The bottleneck of these algorithms is finding a triangle which inserted point is inside. The triangle searching is speeded-up by using dynamic uniform grid. Topology model is used to represent triangle network. Parallel solution is implemented based on the separation of the set points into independent groups. The time complexity in real situation is almost linear. The performance of presented algorithm is very fast.
I. GIỚI THIỆU
Bài toán xây dựng lưới tam giác là một trong các bài toán cơ bản trong hình học tính toán và nó được sử dụng trong rất nhiều lãnh vực như hệ thống thông tin địa (GIS), phần tử hữu hạn, đồ họa máy tính và đa phương tiện… Theo các nghiên cứu hiện nay, độ phức tạp hầu hết các giải thuật xây dựng lưới tam giác Delaunay thường là O(NlogN) [9] và được chia thành các hướng tiếp cận sau:
Hướng tiếp cận chia để trị.
Đầu tiên, tập điểm đầu vào được chia thành các tập con, thực hiện xây dựng lưới tam giác cho mỗi tập con rồi hợp nhất lại để tạo ra lưới tam giác kết quả cuối cùng. Tuy nhiên, phần hợp nhất các kết quả con thường cài đặt khá phức tạp. Giải pháp này được đề cập bởi Dwyer trong công trình [10].
Hướng tiếp sử dụng dòng quét.
Giải thuật theo hướng tiếp cận này đã được đưa ra bởi Fortune [3], sau đó được tổng hợp lại bởi de Berg trong công trình [11]. Fortune đã phát triển giải thuật xây dựng đồ thị đối ngẫu giữa lưới tam giác Delaunay và sơ đồ Voronoi. Việc cài đặt giải thuật là khá phức tạp.
Hướng tiếp cận thêm từng điểm tuần tự [4], [5], [12].
Các giải thuật thuộc hướng tiếp cận này khá đơn giản để cài đặt.
Giả sử chúng ta có lưới tam giác Delaunay được xây dựng từ i-1 điểm. Điểm thứ i sẽ được thêm vào lưới tam giác theo cách sau:
- Xác định tam giác chứa điểm i mới thêm vào lưới.
- Phân rã tam giác đó thành các tam giác con thuộc lưới và hiệu chỉnh thỏa điều kiện Delaunay.
Click chuột để xem chi tiết