📐 Bộ tạo tam giác hóa Delaunay

Tam giác hóa Delaunay của một tập điểm là cách chia tam giác sao cho không có điểm nào nằm trong đường tròn ngoại tiếp của bất kỳ tam giác nào. Tính chất đường tròn ngoại tiếp rỗng này khiến nó tối đa hóa góc nhỏ nhất trên mọi tam giác, nhờ đó tránh được các tam giác dài và mảnh mà những cách chia khác thường tạo ra. Nó được đặt theo tên nhà toán học Nga Boris Delaunay, người đã giới thiệu khái niệm này vào năm 1934, và là lựa chọn hàng đầu khi cần các tam giác có hình dạng tốt.

Tam giác hóa Delaunay là đối ngẫu của sơ đồ Voronoi. Nếu nối mọi cặp điểm có các ô Voronoi chung một cạnh, bạn sẽ thu được chính xác tam giác hóa Delaunay. Nói cách khác, mỗi cạnh Delaunay cắt một cạnh Voronoi, và mỗi tam giác tương ứng với một đỉnh Voronoi tại tâm ngoại tiếp của nó. Bật lớp phủ Voronoi để xem cả hai cấu trúc cùng lúc và quan sát cách các ô và tam giác khớp nhau.

Tam giác hóa Delaunay xuất hiện rộng khắp trong khoa học và kỹ thuật: tạo địa hình và lưới cho bản đồ và game, phân tích phần tử hữu hạn nơi các tam giác có chất lượng tốt giúp mô phỏng ổn định, nội suy không gian cho dữ liệu rời rạc, và đồ họa máy tính cùng tái dựng 3D nơi các đám mây điểm được chuyển thành bề mặt. Các bảo đảm về chất lượng khiến nó trở thành lựa chọn mặc định để biến các điểm rời rạc thành một lưới hữu dụng.