Trình tạo phân chia tam giác Delaunay

Trình tạo Phân chia Tam giác Delaunay biến bất kỳ tập hợp điểm 2D nào thành phân chia tam giác duy nhất giúp tối đa hóa góc trong nhỏ nhất — tiêu chuẩn vàng cho mô hình hóa địa hình, tạo lưới phần tử hữu hạn, nội suy láng giềng gần nhất và các lớp học hình học tính toán. Dán các tọa độ (hoặc chọn một mẫu khởi đầu nhanh), và công cụ sẽ chạy thuật toán Bowyer-Watson ở phía máy chủ, tô màu từng tam giác theo chất lượng của nó và hiển thị thuộc tính đường tròn ngoại tiếp trống, bao lồi và đối ngẫu Voronoi khi có yêu cầu.

Cách đọc lưới được tạo

Điều gì làm cho trình tạo Delaunay này trở nên khác biệt

Phân chia tam giác Delaunay là gì?

Cho một tập hợp các điểm 2D, thường có nhiều cách để nối chúng thành một phân chia tam giác (một sự phủ kín hoàn toàn bao lồi của chúng bằng các tam giác không chồng chéo hoặc có khoảng hở). Phân chia tam giác Delaunay, được đặt theo tên của nhà toán học người Nga Boris Delaunay (1934), là phân chia thỏa mãn thuộc tính đường tròn ngoại tiếp trống: đối với mỗi tam giác trong lưới, đường tròn đi qua ba đỉnh của nó không chứa bất kỳ điểm đầu vào nào khác. Thuộc tính duy nhất này dẫn đến một hệ quả đáng chú ý: trong tất cả các phân chia tam giác của cùng một tập hợp điểm, phân chia tam giác Delaunay tối đa hóa góc trong nhỏ nhất. Nói một cách dễ hiểu, nó tạo ra các tam giác "mập" và "cân bằng" nhất có thể.

Thuật toán Bowyer-Watson hoạt động như thế nào

1. Bao quanh tất cả các điểm đầu vào bằng một siêu tam giác rất lớn.
2. Chèn từng điểm đầu vào một tại một thời điểm. Đối với mỗi điểm mới, hãy tìm mọi tam giác hiện có mà đường tròn ngoại tiếp của nó chứa điểm mới — đây là những tam giác "xấu".
3. Loại bỏ các tam giác xấu. Lỗ hổng mà chúng để lại có ranh giới đa giác.
4. Nối điểm mới với mọi cạnh của ranh giới đó, hình thành các tam giác mới.
5. Sau khi tất cả các điểm được chèn vào, hãy loại bỏ bất kỳ tam giác nào vẫn chạm vào đỉnh của siêu tam giác. Những gì còn lại là phân chia tam giác Delaunay của tập hợp điểm ban đầu.

Nơi phân chia tam giác Delaunay được sử dụng

• Mô hình hóa địa hình (GIS): các mẫu cao độ (thường có khoảng cách không đều, giống như các trạm địa hình) được kết nối thành một Mạng tam giác không đều (TIN) cho các truy vấn cao độ, đổ bóng và trực quan hóa 3D.
• Phân tích phần tử hữu hạn: các tam giác Delaunay có hình dáng tốt mang lại các giải pháp số ổn định cho các phương trình vi phân phân mục trong cơ học, truyền nhiệt và điện từ học.
• Đồ họa máy tính: tạo lưới để kết xuất, tạo khung xương cho nhân vật và địa hình theo quy trình — sự đảm bảo "không có tam giác quá nhọn" của Delaunay giúp tránh các hiện tượng kéo giãn vân bề mặt.
• Nội suy láng giềng tự nhiên: các bề mặt mượt mà được tái tạo từ các mẫu rải rác bằng cách tính toán các láng giềng tự nhiên của mỗi điểm truy vấn thông qua đối ngẫu Voronoi.
• Các lớp học hình học tính toán: một thuật toán chuẩn mực có mối liên hệ sâu sắc với bao lồi, sơ đồ Voronoi, định vị điểm và chia để trị.
• Các phần mềm cắt lát in 3D và đường dẫn dao CNC: Delaunay 2D (và họ hàng 3D của nó, phân chia tứ diện Delaunay) là nền tảng của nhiều chiến lược cắt lát và điền đầy (infill).

Delaunay so với Voronoi: Two Sides of the Same Coin

Sơ đồ Voronoi phân chia mặt phẳng thành một ô cho mỗi điểm đầu vào, trong đó mỗi ô chứa mọi thứ gần với điểm của nó hơn bất kỳ điểm nào khác. Nối các điểm có ô chung ranh giới, bạn sẽ nhận được chính xác phân chia tam giác Delaunay. Ngược lại, tâm đường tròn ngoại tiếp của các tam giác Delaunay kề nhau, được nối bằng các đoạn thẳng, sẽ tạo thành các cạnh Voronoi. Bật "Đối ngẫu Voronoi" trên công cụ này để xem các đường nét đứt màu cam được phủ trên cùng một biểu đồ — mỗi cạnh Delaunay cắt chính xác một cạnh Voronoi ở các góc vuông.

Chất lượng, Tam giác nhọn và Tinh chỉnh lưới

Delaunay tối đa hóa góc trong nhỏ nhất toàn cục, nhưng nó không thể sửa chữa một sự phân bố điểm vốn dĩ đã tệ. Nếu các điểm đầu vào của bạn gần như thẳng hàng, tụ lại một chỗ hoặc để lại các vùng trống lớn, một số tam giác vẫn sẽ bị nhọn (góc nhỏ nhất dưới 20°). Cách khắc phục là chèn điểm Steiner: các thuật toán như thuật toán Ruppert và thuật toán Chew thứ hai sẽ lặp đi lặp lại việc thêm các điểm mới tại tâm đường tròn ngoại tiếp của các tam giác nhọn, phân chia lại tam giác mỗi lần, cho đến khi mọi tam giác đều đáp ứng giới hạn chất lượng mục tiêu. Trình tạo này hiển thị cho bạn biết tam giác nào bị nhọn để bạn biết nơi cần thêm các điểm Steiner nếu muốn có một lưới mịn hơn.

Ví dụ thực tế

Nhấp vào mẫu thiết lập sẵn "Hình tròn + trung tâm". Công cụ này đặt 18 điểm xung quanh một vòng tròn và 1 điểm ở tâm, rồi phân chia tam giác chúng. Kết quả là một dải hình quạt hoàn hảo gồm 18 tam giác cân gặp nhau tại tâm — mỗi tam giác có các góc 10° ở vành và 80°–80° ở tâm. Góc nhỏ nhất xấu nhất là 10°, tất cả các tam giác đều được gắn cờ là nhọn, và biểu đồ tần suất hiển thị mọi thứ trong nhóm 0°–10°. Ví dụ này là một trường hợp giảng dạy tuyệt vời: ngay cả phân chia tam giác tối ưu Delaunay vẫn có thể có các tam giác nhọn khi dữ liệu đầu vào ép buộc chúng. Bây giờ hãy nhấp vào "Đám mây ngẫu nhiên" — cùng một thuật toán tạo ra các tam giác có hình dáng đẹp vì các điểm được trải đều, và biểu đồ tần suất dịch chuyển sang bên phải.

Các quan niệm sai lầm phổ biến

• "Phân chia tam giác Delaunay là duy nhất": thường là đúng, nhưng nếu bốn điểm đầu vào cùng nằm trên một đường tròn, sẽ có hai phân chia tam giác Delaunay hợp lệ cho nhóm đó. Trình tạo sẽ chọn một cách nhất quán.
• "Nhiều điểm hơn luôn có nghĩa là chất lượng tốt hơn": việc thêm các điểm có vị trí kém có thể tạo ra các tam giác nhọn mới. Các thuật toán điểm Steiner đặt các điểm mới một cách cẩn thận — tại các tâm đường tròn ngoại tiếp — nhờ đó chất lượng chắc chắn sẽ được cải thiện.
• "Delaunay giống như bao lồi": không phải. Bao lồi là ranh giới bên ngoài; phân chia tam giác Delaunay lấp đầy phần bên trong bằng các tam giác.
• "Tất cả các phân chia tam giác trông đều giống nhau": sự khác biệt là rất lớn. Việc "lật cạnh" khỏi một cạnh Delaunay có thể biến một tam giác 25° thành một tam giác 5°. Bản đồ nhiệt chất lượng của công cụ giúp bạn thấy rõ sự khác biệt này.

Các câu hỏi thường gặp