MỘT THUẬT TOÁN TUẦN TỰ ĐỂ XÂY DỰNG LƯỚI TAM GIÁC DELAUNAY=A SEQUENTIAL ALGORITHM FOR CONSTRUCTING THE DELAUNAY TRIANGULATION

0 Người đánh giá. Xếp hạng trung bình 0

Tác giả: Minh Đức Trịnh

Ngôn ngữ: vie

Ký hiệu phân loại:

Thông tin xuất bản: Tạp chí Khoa học và Công nghệ - Đại học Thái Nguyên, 2024

Mô tả vật lý: tr.14 - 21

Bộ sưu tập: Metadata

ID: 478871

Thêm vào giỏ

Bài toán xây dựng lưới tam giác Delaunay là một trong các bài toán cơ bản trong hình học tính toán. Lưới tam giác Delaunay đã được sử rộng rãi trong hình học tính toán và được mở rộng sang nhiều lĩnh vực khác như hệ thống thông tin địa lý (GIS), mô hình hóa địa hình, đồ họa máy tính và đa phương tiện, phần tử hữu hạn, nhận dạng mẫu... Do đó, việc phát triển các thuật toán nhanh và hiệu quả để xây dựng lưới tam giác Delaunay ngày càng trở nên quan trọng. Có nhiều thuật toán tuần tự được cài đặt một cách hiệu quả để xây dựng tam giác Delaunay. Trong bài báo này, chúng tôi trình bày một thuật toán tuần tự để xây dựng lưới tam giác Delaunay của một tập điểm phẳng hữu hạn dựa trên chiến lược chia để trị. Cụ thể, chúng tôi đưa ra một vùng giới hạn để loại bỏ đi các điểm không cần thiết cho việc kiểm tra tiêu chí đường tròn trong quá trình ghép nối hai lưới tam giác Delaunay trong hai tập con liền kề nhau. Tính hiệu quả của thuật toán đề xuất được chứng minh bằng việc so sánh sự thực thi của nó với một sự cài đặt xây dựng lưới tam giác Delaunay được đưa ra bởi O’Rourke. Các kết quả thực nghiệm chỉ ra rằng sự cài đặt thuật toán chúng tôi thu được sự tăng tốc tốt hơn đáng kể so với sự cài đặt của O’Rourke.The problem of constructing Delaunay triangulation is one of the important problems in Computational Geometry. The Delaunay triangulation has been used widely in computational geometry and extended to other multi-purpose domains, for example, GIS, terrain modelling, computer graphics, pattern recognition, finite element analysis… As a result, developing fast and effective algorithms to construct the Delaunay triangulation is becoming more and more important. There are a variety of sequential algorithms implemented effectively for constructing the Delaunay triangulation. In this paper, we present a sequential algorithm for constructing the Delaunay triangulation of a finite planar point set based on divide-and-conquer stratery. In particular, we use a restricted area of the examination of points for testing the circle criterion. The efficiency of the proposed algorithm is verified by comparing its performance with the Delaunay triangulation procedure given by O’Rourke. The results show that the implementation of our algorithm significantly achieves better speedups over O’Rourke’s code.

1. Đọc trực tuyến

1. Đọc trực tuyến

Tạo bộ sưu tập với mã QR