Chương 1 Một số phương pháp chia lưới tự động không cấu trúc 1.1 Phương pháp chia lưới Delaunay Triangulation 1.1 Giới thiệu Phương pháp Delaunay Triangulation là một trong các phương pháp chia lưới không cấu trúc đã được phát triển từ rất sớm [8]. Phương pháp này dựa trên tiêu chuẩn Delaunay (hay còn gọi là tiêu chuẩn vòng tròn ngoại tiếp trống): Siêu cầu của mỗi đơn hình trong không gian n - chiều được xác định bởi n + 1 điểm trong đó không có bất kỳ điểm nút nào khác của lưới. Ví dụ trong không gian ba chiều, bốn đỉnh của một tứ diện xác định một mặt cầu và mặt cầu này không chứa các điểm nút khác của lưới tứ diện. Trong không gian hai chiều, hệ tam giác thu được dựa trên tiêu chuẩn Delaunay được gọi là hệ tam giác Delaunay.
Hệ tam giác này được áp dụng rất phổ biến trong thực hành vì chúng có các đặc điểm tối ưu sau: • Các tam giác Delaunay là các tam giác xấp xỉ đều; • Góc lớn nhất của tam giác được cực tiểu hóa; • Góc nhỏ nhất của tam giác được cực đại hóa. Với các đặc điểm này hệ tam giác Delaunay sẽ không bị quá biến dạng hoặc quá méo mó. Tiêu chuẩn Delaunay không đưa ra bất kỳ một sự chỉ dẫn nào như là các điểm lưới nên được định nghĩa và liên kết với nhau như thế nào? Một hạn chế nữa của tiêu chuẩn Delaunay đó là có khả năng không thể áp dụng tiêu chuẩn này trên toàn bộ miền tính toán với các tam giác biên xác định trước. Nhược điểm này đưa ra hai cách tiếp cận chia lưới tam giác có bảo toàn liên kết biên và vẫn áp dụng tiêu chuẩn Delaunay.
Trong cách tiếp cận thứ nhất tiêu chuẩn Delaunay được bỏ qua tại các điểm gần biên và hệ quả TIEU LUAN MOI download6: skknchat@gmail.com là biên của lưới trước vẫn còn nguyên vẹn. Để kết hợp với kỹ thuật này, các điểm được thêm vào dưới dạng một sơ đồ để đảm bảo không xảy ra sự phá hủy biên. Cách tiếp cận thứ hai, áp dụng tiêu chuẩn Delaunay trên toàn miền tính toán, sau đó khôi phục lại biên ban đầu bằng cách bỏ đi các đơn hình nằm bên ngoài miền tính toán [1]. Có rất nhiều thuật toán tạo lưới không cấu trúc dựa trên tiêu chuẩn De- launay, chẳng hạn có một số thuật toán sử dụng phương pháp chia lưới có cấu trúc tạo ra sự phân bố các điểm nút lưới trước sau đó các điểm nút lưới này được kết nối để thu được các tam giác thỏa mãn các tiêu chuẩn hình học nào đó (tương đương với tiêu chuẩn Delaunay).
Tuy nhiên thuật toán chúng ta hay sử dụng là thuật toán Bowyer - Watson. Thuật toán này có thể áp dụng với không gian n - chiều bất kỳ. Thuật toán bắt đầu từ một hệ tam giác của một vài điểm, sau đó tiếp tục tại mỗi bước ta thêm các điểm mới vào hệ tam giác hiện tại và tái thiết lập hệ tam giác một cách địa phương. Quá trình này cho phép chúng ta cải thiện được chất lượng lưới trong khuôn khổ của tiêu chuẩn Delaunay.
Điểm khác biệt của thuật toán này là vị trí các điểm và các liên kết được tính toán một cách đồng thời.2 Cơ sở hình học • Định nghĩa ô lồi Một ô lồi n - chiều S là một bao lồi của n + k điểm P1 ,. Như vậy S bao gồm các điểm x ∈ Rn thỏa mãn n+k x = ∑ αi Pi , i =1 n+k ∑ αi = 1, 1 ≥ αi ≥ 0. i =1 Gọi tất cả các điểm Pl của tập Pi , i = 1, ., n + k nằm trên biên của S là các đỉnh của ô lồi S. Một mặt m - chiều của ô lồi n - chiều S (n > m) được gọi là bao lồi của m + 1 đỉnh Pl , và bao lồi này không chứa bất kỳ một đỉnh nào khác của S.
Ta nói ô S là lồi mạnh nếu nó không có hai mặt bất kỳ cùng nằm trong mặt phẳng m - chiều với mọi m < n Nếu P là một điểm nằm trong ô lồi mạnh S với các đỉnh P1 , ., Pn+k thì n+k n+k P = ∑ αi Pi , ∑ αi = 1, αi ≥ 0, i = 1, ., n + k, i =1 i =1 TIEU LUAN MOI download7: skknchat@gmail.1: Ô lồi (bên trái) và ô tứ diện lồi mạnh (bên phải) • Đơn hình và các ô đơn hình Một phần tử đơn giản nhất n - chiều được sử dụng để rời rạc hóa miền tính toán được gọi là một ô n - chiều. Ô này là bao của n + 1 điểm x1 , ., xn+1 mà không cùng nằm trong bất kỳ mặt phẳng (n − 1) - chiều nào. Những ô như thế được gọi là các đơn hình. Như vậy một đơn hình được tạo nên bởi các điểm x ∈ Rn thỏa mãn n +1 x = ∑ αi xi , i = 1, ., n + 1, i =1 n +1 ∑ αi = 1, αi ≥ 0, i =1 Đơn hình này là một ô lồi mạnh có các đỉnh là x1 ,.
Chẳng hạn một đơn hình ba chiều là một tứ diện có các đỉnh là x1 , x2 , x3 , x4 , một đơn hình hai chiều là một tam giác, đơn hình một chiều là một đoạn thẳng. Mỗi mặt m - chiều của đơn hình là một đơn hình m - chiều được định nghĩa qua m + 1 đỉnh. Điểm x là một điểm trong của đơn hình nếu α > 0 với mọi i = 1,. Trong thực hành, để rời rạc hóa miền tính toán, ta hay sử dụng các ô lồi có các mặt biên là các đơn hình.
Những ô như vậy được gọi là các ô đơn hình., n, là số mặt đơn hình i - chiều của S, và N0 là số đỉnh của S. ( l − m + 1) , m ≥ 1, = 1, m m! 0 TIEU LUAN MOI download8: skknchat@gmail.com • Tính nhất quán của lưới Bằng một phép rời rạc phù hợp chúng ta thu được một tập hợp các điểm V ∈ Rn và một tập các ô lồi mạnh T thỏa mãn các điều kiện sau: 1. Tập hợp các đỉnh của các ô của T trùng với V; 2. Nếu hai ô khác nhau S1 và S2 giao nhau, thì miền giao nhau đó là mặt chung của cả hai ô.2: Các ô giao nhau chấp nhận được (a) và không chấp nhận được (b, c, d) Tập hợp các ô của một phép rời rạc phù hợp tạo thành một miền kết nối đơn giản n - chiều.
Gọi Ni , i > 0 là số lượng các mặt biên i - chiều của miền rời rạc, N0 là số đỉnh của biên, theo định lý Euler ta có: n −1 ∑ (−1)i Ni = 1 + (−1)n−1 i =0 biểu thức trên được sử dụng để xác định tính nhất quán của lưới. • Lưới tổ ong Dirichlet Xét một tập tùy ý gồm các điểm Pi , i = 1, 2, ., N trong một miền xác định n - chiều. Với mỗi điểm Pi chúng ta xác định một miền V ( Pi ) trong Rn bao gồm các điểm có khoảng cách tới Pi nhỏ hơn tới các điểm Pj khác. Vi = x ∈ Rn | d ( x, Pi ) ≤ d x, Pj , i 6= j, j = 1, ., N , trong đó d( a, b) là khoảng cách giữa hai điểm a, b.
Các miền Vi này được gọi là các khối đa diện Voronoi. Do các khối đa diện là giao của các bán không gian nên chúng là các đa diện lồi, nhưng không cần thiết là bị chặn. Mặt biên chung của hai Voronoi của hai điểm V ( Pi ) và V ( Pj ) là một đa giác (n − 1) - chiều. Cặp điểm Pi và Pj được gọi là cặp cấu hình nếu các khối đa diện Voronoi của chúng có một mặt chung.
Bằng cách kết nối các điểm kề nhau ta sẽ thu được một lưới. Trong lưới này, tập hợp n + 1 điểm cùng kề với một điểm khác tạo thành một đơn hình n - chiều. Tâm của bất kỳ một đơn hình nào cũng sẽ là TIEU LUAN MOI download9: skknchat@gmail.com một đỉnh của sơ đồ Voronoi. Siêu cầu của mỗi đơn hình là rỗng, có nghĩa là không có bất kỳ điểm nào ở bên trong siêu cầu vì nếu có một điểm nào đó ở bên trong siêu cầu thì điểm này sẽ gần tâm hơn các điểm khác của siêu cầu.
Do đó tập hợp các đơn hình được xây dựng từ lưới tổ ong Dirichlet theo cách này tạo thành một lưới tổ ong mới thỏa mãn tiêu chuẩn Delaunay. Biên của hệ tam giác Delaunay được xây dựng theo sơ đồ Voronoi là các bao lồi của tập hợp các điểm Pi. Ta có thể coi phép đặt tam giác Delaunay và lưới tổ ong Dirichlet là các đối ngẫu hình học của nhau trong ý nghĩa là với mỗi đơn hình Si sẽ tồn tại một đỉnh Pi của lưới tổ ong và ngược lại, với mỗi miền Voronoi V ( Pj ) cũng tồn tại một đỉnh Pj của hệ tam giác. Thêm vào đó, với mỗi cạnh của hệ tam giác sẽ tồn tại tương ứng (n − 1) phân đoạn của lưới tổ ong.3 Thiết lập hệ tam giác ban đầu Vì các điểm lưới được đưa vào một cách tuần tự, nên lưới ban đầu rất thô, số lượng các nút lưới ít và các phần tử lưới là các tam giác rất lớn.
Ví dụ trong không gian hai chiều chúng ta có thể tạo ra lưới ban đầu bằng cách chia một hình vuông nằm trong miền tính toán (hoặc chứa miền tính toán) thành hai tam giác. Sau đó các điểm bên trong và các điểm biên được thêm vào một cách liên tiếp để xây dựng các tam giác liên tiếp cho đến khi miền xấp xỉ đạt được các yêu cầu cần thiết. Một trong các yêu cầu đó là hệ tam giác ban đầu phải bảo toàn biên, tức là tất cả các cạnh biên đều được chứa trong hệ tam giác ban đầu. Một cách tự nhiên để thỏa mãn yêu cầu trên là ta quy định trước các điểm nút trên biên bằng các phương tiện của thuật toán Bowyer - Watson.
Tuy nhiên không có gì đảm bảo rằng hệ tam giác Delaunay xây dựng từ tập hợp các điểm biên sẽ có biên được bảo toàn. Để khắc phục vấn đề này ta lặp đi lặp lại việc chèn một điểm lưới mới tại trung điểm của các cạnh biên bị thiếu để thu được các tam giác biên. Một cách khác để duy trì tính nguyên vẹn của biên là chúng ta loại bỏ tất cả các điểm có thể làm cho liên kết biên bị phá vỡ.