MỘT THUẬT TOÁN TUẦN TỰ ĐỂ XÂY DỰNG LƯỚI TAM GIÁC DELAUNAY

Trịnh Minh Đức

doi:10.34238/tnu-jst.9487

MỘT THUẬT TOÁN TUẦN TỰ ĐỂ XÂY DỰNG LƯỚI TAM GIÁC DELAUNAY

Thông tin bài báo

Ngày nhận bài: 28/12/23 Ngày hoàn thiện: 28/03/24 Ngày đăng: 29/03/24

Các tác giả

Trịnh Minh Đức , Trường Đại học Công nghệ thông tin và Truyền thông – ĐH Thái Nguyên

Tóm tắt

Bài toán xây dựng lưới tam giác Delaunay là một trong các bài toán cơ bản trong hình học tính toán. Lưới tam giác Delaunay đã được sử rộng rãi trong hình học tính toán và được mở rộng sang nhiều lĩnh vực khác như hệ thống thông tin địa lý (GIS), mô hình hóa địa hình, đồ họa máy tính và đa phương tiện, phần tử hữu hạn, nhận dạng mẫu... Do đó, việc phát triển các thuật toán nhanh và hiệu quả để xây dựng lưới tam giác Delaunay ngày càng trở nên quan trọng. Có nhiều thuật toán tuần tự được cài đặt một cách hiệu quả để xây dựng tam giác Delaunay. Trong bài báo này, chúng tôi trình bày một thuật toán tuần tự để xây dựng lưới tam giác Delaunay của một tập điểm phẳng hữu hạn dựa trên chiến lược chia để trị. Cụ thể, chúng tôi đưa ra một vùng giới hạn để loại bỏ đi các điểm không cần thiết cho việc kiểm tra tiêu chí đường tròn trong quá trình ghép nối hai lưới tam giác Delaunay trong hai tập con liền kề nhau. Tính hiệu quả của thuật toán đề xuất được chứng minh bằng việc so sánh sự thực thi của nó với một sự cài đặt xây dựng lưới tam giác Delaunay được đưa ra bởi O’Rourke. Các kết quả thực nghiệm chỉ ra rằng sự cài đặt thuật toán chúng tôi thu được sự tăng tốc tốt hơn đáng kể so với sự cài đặt của O’Rourke.

Từ khóa

Lưới tam giác Delaunay; Sơ đồ Voronoi;Lưới tam giác; Chia để trị; Hình học tính toán

Toàn văn:

PDF

Tài liệu tham khảo

[1] K. H. Huebner, D. L. Dewhirst, D. E. Smith, and T. G. Byrom, The Finite Element Method for Engineers. Wiley, New York, NY, USA, 2001.

[2] L. Tang, C. Ren, Z. Liu, and Q. Li, “A Road Map Refinement Method Using Delaunay Triangulation for Big Trace Data,” ISPRS International Journal of Geo-Information, vol. 6, no. 2, pp. 141-153, 2017.

[3] M. Flores, G. Torres, G. García, and M. Licona, “Fingerprint verification methods using delaunay triangulations,” International Arab Journal of Information Technology, vol. 14, pp. 346-354, 2017.

[4] S. Fortune, “A sweepline algorithm for Voronoi diagrams,” Algorithmica, vol. 2, pp. 153-174, 1987.

[5] R. A. Dwyer, “A faster divide-and-conquer algorithm for constructing Delaunay triangulations,” Algorithmica, vol. 2, pp. 137-151, 1987.

[6] L. Guibas and J. Stolfi, “Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams,” ACM Transactions on Graphics, vol. 4, no. 2, pp. 74-123, 1985.

[7] P. Green and R. Sibson, “Computing Dirichlet tessellations in the plane,” Computer Journal, vol. 21, pp. 168-173, 1977.

[8] M. -B.Chen, T. -R. Chuang, and J. -J. Wu, “Parallel divide-and-conquer scheme for 2D Delaunay
triangulation,” Concurrency and Computation: Practice and Experience, vol. 18, pp. 1595-1612, 2006.

[9] P. T. An and L. H. Trang, “A Parallel Algorithm Based on Convexity for the Computing
of Delaunay Tessellation,” Numerical Algorithms, vol. 59, no. 3, pp. 347–357, 2012.

[10] W. Wu, Y. Rui, F. Su, L. Cheng, and J. Wang, “Novel parallel algorithm for constructing Delaunay triangulation based on a twofold-divide-and-conquer scheme,” GIScience & Remote Sensing, vol. 51, no. 5, pp. 537-554, 2014.

[11] D. T. Lee and B. J. Schachter, “Two Algorithms for Constructing a Delaunay Triangulation,” International Journal of Computer and Information Sciences, vol. 9, no. 3, pp. 219-242, 1980.

[12] M. I. Shamos and D. Hoey, “Closest-point Problems,” Proceedings of the 16th Annual Symposium on Foundations of Computer Science, 1975, pp. 151-162.

[13] P. T. An, “Method of orienting curves for determining the convex hull of a finite set of points in the plane,” Optimization, vol. 59, no. 2, pp. 175-179, 2010.

[14] J. O’Rourke, Computational Geometry in C, Second edition. Cambridge University Press, 1998.

[15] M. de Berg, Computational Geometry Algorithms and Applications. Springer, Germany, 2000.

[16] A. Okabe, B. Boots, and K. Sugihara, Spatial Tessellations: Concepts and Applications of voronoi Diagrams, First edition, John Winley and Sons Ltd, 1992.

DOI: https://doi.org/10.34238/tnu-jst.9487

Các bài báo tham chiếu

Hiện tại không có bài báo tham chiếu



Ghi nhớ