ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN Nguyễn Thị Thủy CÁC PHƯƠNG PHÁP TẠO LƯỚI TỰ ĐỘNG VÀ
ỨNG DỤNG TRONG TÍNH TOÁN CƠ HỌC LUẬN VĂN THẠC SỸ KHOA HỌC Hà Nội – 2011
ĐẠI HỌC QUỐC GIA HÀ NỘI
Mục lục
Lời cảm ơn 1
Lời mở đầu 4
1 Một số phương phá p chia lưới tự động không cấu trúc 6
1.1 Phương pháp chia lưới Delaunay Triangulation . . . . . . . . . . 6
1.1.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.2 Cơ sở hình học . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.3 Thiết lập hệ tam giá c ban đầu . . . . . . . . . . . . . . . . 10
1.1.4 Thuật toán Bowyer - Watson . . . . . . . . . . . . . . . . 10
1.1.5 Các phương pháp chèn điểm mới . . . . . . . . . . . . . 13
1.1.6 Hạn chế hình dạng của hệ tam giác Delaunay . . . . . . 18
1.1.7 Phép chia lưới Delaunay triangulation trong không gian
ba chiều . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.2 Phương pháp tịnh t i ến b i ên (Advancing Front) . . . . . . . . . . 21
1.2.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.2.2 Điều khiển lưới . . . . . . . . . . . . . . . . . . . . . . . . 22
1.2.3 Thuật toán AFT . . . . . . . . . . . . . . . . . . . . . . . . 25
1.2.4 Sự thích n ghi và không gian tham số . . . . . . . . . . . . 35
1.2.5 Cải th i ện chất lượng lưới . . . . . . . . . . . . . . . . . . 36
1.3 Phương pháp tạo lưới không cấu trúc sử dụng thuật toán chèn
điểm tự động và tái kết nối địa phương . . . . . . . . . . . . . . 37
1.3.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.3.2 Phương pháp chia lưới AFLR . . . . . . . . . . . . . . . . 38
1.4 Các phương pháp chồn g tạo lưới tứ giác và lục giác . . . . . . . 45
1.4.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
1.4.2 Các phương pháp chồn g . . . . . . . . . . . . . . . . . . . 46
1.5 Một số phương pháp đang được phát triển . . . . . . . . . . . . 52
2 Áp dụng trong một số bài toán cơ học 54
2.1 Bài toán 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.2 Bài toán 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
qua các ánh xạ lưới mà kh ô ng l àm thay đổi bản chất của chương trình số. Khó
khăn trong việc thực hiện phương pháp này nằm trong việc tạo ra các nút lưới
nhất là khi có nhiều vật cản bên trong miền tính toán.
Không giống như lưới có cấu trúc, các nút lưới và các ô lưới của lưới
không cấu trúc không phải là giao của các đường thẳn g song song. M ột ưu
điểm của lưới không cấu trúc là các điểm nút có thể đặt trên biên của miền
tính toán vì vậy khi áp dụng các phương pháp số thì lưới không cấu trúc cho
độ chính xác cao hơn. Hơn thế nữa, lưới không cấu trúc cho phép các phần tử
có kích thước khác nhau vì vậy có th ể biểu diễn chính xác biên của miền tính
toán mà không cần một số lượng quá lớn các nút lưới và ô lưới.
Khi miền tính toán có hình dạng phức tạp thì so với lưới có cấu trúc , lưới
không cấu trúc có thể giúp cải thiện độ chính xác của nghiệm tổng thể, lưới
không cấu trúc cũng đã được chứng mi nh là có khả năng thích nghi cao hơn
trong các bài toán biên chuyển dịch hoặc dòng nhất thời.
Về nguyên tắc, lưới không cấu trúc có thể bao gồm các ô có hình dạng
bất kỳ, đượ c xây dựng bằng cách kết nối một điểm cho trước đến một số tùy
ý các điểm khác, nhưng nói chung là được hợp thành từ các tam giác và tứ
giác trong không gian hai chiều, c ác t ứ diện và lục giác trong không gian ba
chiều. Ưu điểm của các lưới này l à chúng có khả năng thích nghi bằng cách
cho phép chèn thêm các điểm mới vào, do đó chúng có thể làm việc với các
miền tính toán có hình dạng phức tạp.
Ở thời điểm hiện tại phương pháp chia lưới không cấu trúc đã được áp
dụng trong khôn g g i an ba chiều. Tuy nhiên phương pháp chia lưới không
cấu trúc dựa trên tam giác Delaunay thường xuyên được sử dụng nhất và đã
được chứng minh là có khả năng thích nghi cao, phù hợp với các miền tính
toán phức tạp. Các lưới này cho phép bổ sung thêm các nút lưới mới vào hệ
tam giác đã tồn tại chỉ ảnh hưởng đến cấu trúc lưới địa phương mà không
ảnh hưởng đến cấu trúc lưới tổng thể.
Trong luận văn này giới thiệu hai phương pháp chia lưới không cấu trúc
hay được sử dụng: phương pháp chia lưới Delaunay Triangulation và phương
á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 t rước . Nhược điểm này đưa ra hai cách tiếp cận chia lưới t am 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ả
6
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 để th u đượ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.
1.1.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 P
1
, , P
n+k
(k>1) m à
các điểm này không cùng nằm trong một m ặt phẳng (n −1) - chiều. Như vậy
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 t ron g ô lồi mạnh S với các đỉnh P
1
, , P
n+k
thì
P =
n+k
∑
i=1
α
i
P
i
,
n+k
∑
i=1
α
i
= 1, α
i
≥ 0, i = 1, , n + k,
7
Hình 1.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 x
1
đơn hình ba chiều là một tứ diện có các đỉnh là x
1
, x
2
, x
3
, x
4
, 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, , n + 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.
Gọi N
i
, i = 1, , n, là số mặt đơn hình i - chiều của S, và N
0
là số đỉnh của
S. Ta có
n−1
∑
i=k
(
−1
)
i
i + 1
)
m!
, m ≥ 1,
l
0
= 1,
8
• 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 ∈ R
n
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 S
1
và S
2
giao nha u, thì miền giao nhau đó là m ặt
chung của cả hai ô.
Hình 1.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 N
i
, i > 0 là số lượng các m ặt biên i - chiều của miền rời rạc, N
0
j
khác.
V
i
=
x ∈ R
n
|
d
(
x, P
i
)
≤ d
x, P
j
, i = j, j = 1, , N
,
trong đó d(a, b) là khoảng cách giữa hai điểm a, b. Các miền V
i
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(P
i
) và V(P
j
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.
1.1.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 m i ề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 tron g 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 c hứa trong hệ ta m 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 ng uyê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ỡ.
1.1.4 Thuật toán Bowyer - Watson
Có nhiều thuật toán cho việc phân chia tam giác Delaunay chủ yếu trong
trường hợp hai chiều. Tuy nhiên thuật toán được sử dụng phổ biến nhất trong
thực hành là thuật toán Bowyer - Watson [6]. Thuật toán này t hêm các điểm
một cách tuần tự vào hệ tam giác Delaunay đã có, thường thì bắt đầu từ một
hệ tam giác rất đơn giản (chẳng hạn là một tam giác lớn) mà nó bao bọc tất cả
các điểm (giả sử có i điểm) sẽ được dùng để tạo hệ lưới tam giác Delaunay.
Gọi T
i
là tập hợp các tam giác và B
i
tiếp chứa điểm x
i+1
, hệ tam giác mới thu được bằng cách xóa các cạnh bên
trong của các tam giác hợp thành S và nối điểm x
i+1
với t ất cả các đỉnh của S .
Ví dụ ta có năm điểm x
1
, x
2
, x
3
, x
4
, x
5
như hình vẽ.
Điểm mới chèn vào x
6
nằm bên trong một tam giác và cũng nằm bên
trong hai đường tròn ngoại ti ếp. Trong trường hợp này S là tứ diện x
2
x
3
x
4
x
5
.
Xóa cạnh trong x
Trong hình vẽ bên dưới, điểm mới chèn vào x
6
nằm bên trong đường tròn
ngoại ti ếp tam giác x
1
x
2
x
5
(tập S chỉ có một tam giác). Cạnh x
1
x
2
có thể n hìn
11
thấy được từ x
6
, vì vậy cạnh này bị xóa đi và hệ tam giác mới thu được bằng
cách nối x
6
với các đỉnh của x
1
, x
2
, x
5
và x
3
.
• Trường hợp 3: x
với các đỉnh x
1
,
x
2
và x
3
. Rõ ràng các đường tròn ngoại tiếp của các tam giác x
1
x
2
x
6
và x
2
x
3
x
6
không ch ứa ba điểm nút còn lại vì vậy tính chất đường tròn ngoại tiếp được
thỏa mãn.
Khi thêm một điểm mới vào hệ tam giác Delaunay, hệ tam giác mớ i sẽ
được đánh giá theo một vài tiêu chuẩn hình học và vật lý.
12
• Tiêu chuẩn hình học: Các tam giác phải trơn, nhẵn và có kích thước, hình
dạng tương tự nhau.
• Tiêu chuẩn vật lý: Mật độ điểm lưới t ron g miền tính toán phải ít hơn mật
độ điểm lưới là ngh i ệm của phương trình vi phân từng phần.
1.1.5 Các phương pháp chèn điểm mới
Hệ tam giác Delaunay ban đầu dựa trên việc lựa chọn các điểm biên và
trị của a, b hoặc c và tỉ lệ khía cạnh càng lớn. Với ý nghĩa đó tỉ lệ khía cạnh đo
độ gầy của một tam giác. Như vậy ta có thể đưa ra danh sách các tam giác có
chất lượng xấu bằng cách
• Thêm vào danh sách các tam giác có diện tích lớn hơn 1.5 lần diện tích
của tam giác đều có cạnh là cạnh lớn nhất của tam giác đó. Bước này sẽ
loại bỏ tất cả các tam giác có diện tích lớ n.
13
Hình 1.3: Đường tròn ng oại tiếp và đường tròn nội tiếp của tam giác ABC
• Thêm vào danh sách các tam giác có bán kính đường tròn ngoại tiếp lớn
và tỉ lệ khía cạnh cao. Như vậy cá c tam giác nhỏ nhưng có tỉ lệ khía cạnh
cao ở gần biên sẽ được giữ l ại.
Tiêu chuẩn để đánh giá t ỉ lệ khía cạnh cao là dựa vào kinh nghiệm, thông
thường tỉ lệ khía cạnh tiêu chuẩn là 1.5. Đ ây là tỉ lệ khía cạnh của tam giác cân
có góc ở đỉnh nằm trong khoảng 24 −104
o
.
Sử dụng ý tưởng trên thuật toán t hêm điểm mới vào tâm đường tròn
ngoại tiếp tam giác được tiến hành theo các bước sau đây:
(i) Thiết lập hệ tam giác ban đầu sử dụng c ác điểm b i ên dữ liệu và thuậ t
toán Bowyer - Watson.
(ii) Xắp xếp các tam giác theo chất lượng của chún g , chọn ra danh sách
các tam giác có c hất lượng xấu, bắt đầu từ tam giác có chất lượng xấu nhất.
(iii) Lấy tam giác đ ầu tiên trong danh sách và thêm một điểm mới vào vị
trí tâm đường tròn n g o ại tiếp .
(iv) Chia lại sử dụng thuật toán Bowyer - Watson.
(v) Thêm các tam giác m ới vào danh sách chất lượng xấu nếu chúng
không đủ tốt.
Tuy nhiên khi sử dụng thuật toán này chèn điểm mới vào t âm đường tròn
ngoại tiếp của tam giác được lựa chọn, có hai trường hợp sau đây cần phải
loại bỏ:
Thuật toán bắt đầu bằn g việc xét các tam giác chưa được chấp nhận, có
một cạnh chung với tam giác đã được chấp nhận và ta chọn tam giác c ó bán
kính đường tròn ngoại tiếp lớn nhất.
Trong hình vẽ trên ta có tam giác ABD là tam giác chưa được chấp nhận
với bán kính đường tròn ngo ại tiếp là R
ABD
và tam giác ABC là tam g i á c đã
được chấp n hận. Cạnh chung AB được gọi là cạnh hoạt động. Đoạn thẳng
Voronoi của hai tam giác này là đo ạn EF (E, F lần l ượt là tâm đường tròn
ngoại tiếp tam giác ABD và ABC), EF⊥AB, EF ∩ AB = {M}.
Bây giờ ta thêm điểm X vào vị trí nào đó trên đoạ n EF sao cho tam giác
ABD sẽ được thay thế bằng tam giác được chấp nhận ABX.
Kí hiệu f
M
là giá trị của f (X) tại M. Đặt
AM = p, MF = q.
+) Nếu X ≡ F thì bán kính của đường tròn ngoại tiếp tam giác ABX là
(p
2
+ q
2
)/2q. Vì bán kính nhỏ nhất của bất kí đường tròn nào qua hai điểm A
và B l à p (đường t ròn tâm M), d o đó ta có:
(p
2
+ q
2
)/2q ≥ p
+) Nếu f
M
2
− p
2
(2.1.1)
Trong cả hai trường hợ p ta đều có:
R
ABX
= min
max
(
f
M
, p
)
,
p
2
+ q
2
/2q
(2.1.2)
+) Nếu f
M
< p < 1.5 f
M
và q > p thì điểm X sẽ được chọn sao cho
N
, giả sử q > p
0
và R
AYX
= f
N
. Theo phương trình (2.1.1)
và (2.1.2) ta có:
NY = d
1
= f
N
+
( f
N
)
2
−(p
1
)
2
(2.1.3)
16
⇒ tan θ =
d
1
p
1
◦
< tan θ < 67.5
◦
Hình 1.5: Chèn điểm vào đoạn thẳng Voronoi
Nếu AY được chọn là cạnh hoạt động tiếp theo, chúng ta có:
(AY)
2
= (2p
2
)
2
= (p
1
)
2
+ (d
1
)
2
và sử dụng phương trình (2.1.3) ta thu được
(
p
2
)
2
=
1
2
(
2
<
p
2
p
1
<
1 +
1
√
2
17
Nếu quá trình này được lặp lại với giả thiết f gần như bằng hằ ng số thì ta
có các bước tổng quát như sau:
(
p
n+1
)
2
=
1
2
(
f
N
)
2
+ f
n
)
2
(2.1.5)
Giá trị của p
n
hội tụ đến giá trị p. Theo (2.1.4) ta có
p
f
N
2
=
1
2
1 +
1 −
p
f
N
2
)
là tập h ợ p các tam giác có đường
tròn ngoại tiếp chứa điểm P. Γ(P) được gọi là hố Delaunay. Chú ý rằng P là
điểm duy nhất nằm trong Γ(P). Thật vậy, giả sử A là một đỉnh của ít nhất một
tam giác trong Γ(P). Nếu có một tam giác S /∈ Γ(P) nhận A l à một đỉnh thì
A không phải là điểm trong của Γ(P). Vì vậy chún g ta cần chỉ ra rằng tồn tại
một tam giác như thế.
Gọi {S
i
} là tập hợp các tam giác nhận A là một đỉnh và C
i
là đường tròn
ngoại tiếp tươn g ứng với tam giác S
i
. S
i
∈ Γ(P) nếu điểm mới chèn vào nằm
bên trong C
i
. Vì vậy, một đỉnh A là điểm trong c ủa Γ(P) nếu các điểm P nằm
bên trong ∩C
i
. Tuy nhiên nếu A là một điểm trong c ủa Γ(P) thì m i ền bên
18
Hình 1.6: Minh họa thành phần chủ yếu
trong của ∩C
i
là rỗng vì vậy A chỉ có thể là điểm nằm trên tất cả các đường
tròn của {S
i
Chúng ta giả thiết các tam giác nhất định của hệ tam giác Delaunay là cố định,
đặc biệt là các tam giác liền kề biên. Kí hiệu tập hợp các tam giác đó là
¯
T. Các
tam giác của
¯
T không tham gia trong việc xây dựng các hố Delaunay, tức là
nếu hố được tạo ra từ sự ra đời của một điểm mới có chứa một hoặc nhiều
tam giác cố định thì chúng ta hạn chế chỉ tái kết nối trong phần của hố không
chứa bất kỳ một tam giác cố định nào. Kí hiệu Υ(P) là phần này của hố thì
Υ(P) = Γ(P) −
¯
T. Kí hiệu Υ
P
là miền kết n ối đơn giản lớn nhất của Υ(P) có
chứa P. Tương tự Υ
P
được gọi là thành phần chủ yếu của Υ(P), Υ
P
chỉ tồn tại
nếu điểm P không nằm bên trong bất kỳ một tam giác nào của
¯
T.
Tương tự chúng ta cũng chứng minh được tất cả các cạnh biên của Υ
P
đều nhìn thấy từ P và các đỉnh của Υ
P
đều được kết nối với P, do đó xây d ựng
được hệ tam giác hạn chế mà các tam giác cố định của
¯
Thuật toán trên có một nhược điểm là không b ảo toàn được bề mặt biên
của miền tính toán. Để khắ c phục hạn chế này ta phải đưa ra các hạn chế đối
với hệ tam giác Delaunay. Các hạn chế đối với hệ tam giác Delaunay trong
không gian ba chiều cũng tương tự như trong không gian ha i chiều.
• Đối với cách ti ếp cận thứ nhất: các tứ diện có các mặt hợp thàn h bề m ặ t
biên được giữ nguyên trong quá trình tái kết nối. Các tứ diện biên này
được thiết lập ngay từ hệ phép đặt t am giác Delaunay ban đầu. C ác bước
tiếp theo là ch èn điểm mới vào, xác định một h ố hình sao có chứa điểm
đó và tái kết n ố i các cạnh của hố đó. Lưới thu được b ảo toàn bi ên và các
tam giác nhỏ bên trong thỏ a mãn tiêu chuẩn Delaunay.
• Đối với cách tiếp cận thứ hai: Thuật toán bắt đầu bằng việc xác định các
điểm nút trên biên, kết nối các điểm này để tạo ra bề mặt của h ệ tam giác
20
biên. Sau đó xây dựng hệ tam giác D elaunay mới bằng cách chèn các
điểm bên trong và áp dụng thuật toán Bowyer - Watson. Sau bước này,
các tứ diện cắt bề mặt biên sẽ được biến đổi để khôi phục lại biên. Nếu
có một mặt biên kh ông hiện diện ở phép đặt tam giác Delaunay mới, đó
là do các cạnh và các mặt của tứ diện của p hép đặt tam giác Delaunay cắt
mặt bi ên này. Vì một mặt được tạo nên từ ba cạnh, nên để khô i phục lại
một mặt ta phải khôi phục lại ba cạnh trước. Quá trình khôi phục lại cạnh
biên bao gồm các bước sau: Đầu tiên, ta tìm các tứ diện giao với các cạnh
của mặt, sau đó, thiết lập tiêu chuẩn giao nhau c ủa mỗi tứ diện với các
cạnh biên, ch o phép thực hiện c ác phép biến đổi trực ti ếp để khôi phục
lại cạnh biên. Các tứ diện được biến đổi một cách địa phương thành các
tứ diện mới có hiện diện các cạnh yêu cầu. Để khôi phục lại các mặt biên
ta cũng thực hiện quá trình t ương tự.
1.2 Phương pháp tịnh tiến biên (Advancing Front)
1.2.1 Giới thiệu
Trong một số bài toán, v i ệc sử dụng ph ương pháp Delaunay Triangulatio n
có thể thu được lưới không thỏa mãn. Chẳng hạn như bài toán xác định dòng
• Tạo ra một lưới nền ban đầu.
Để thu được lưới với các đặc điểm yêu cầu, ta cần chỉ rõ sự phân bố
không gian của các tham số lưới phù hợp trên lưới nền.
Kích thước, hình dạng và hướng của ô lưới tam giác được mô tả bởi một
tập hợp gồm 3 tham số độc lập:
Hình 1.7: Các th am số mô tả của phần tử tam giác
• Tham số kích thước δ ;
• Tham số kéo dãn s;
• Tham số định hướn g Φ được liên hệ với 2 véct ơ trực giaos vàn
Để định nghĩa một ô lưới ta định nhập bốn tham số đầu vào(δ, s, n
x
, n
y
)
trong đó n
x
, n
y
lần lượt là hình chiếu vuông góc củan trên các trục ox, oy. Các
giá trị c ủa bốn tham số này cần được chỉ rõ tại mỗi nút của lưới nền. Lưới nền
ban đầu thường do người sử dụng tạo ra và có thể kh á không mịn đặc biệt là
đối với các miền tính toán phức tạp. Ví dụ một lưới nền có thể chỉ gồm một
22
phần tử hoặc hai phần tử tam giác, tuy nhiên lưới nền cần phải thỏa mãn yêu
cầu về sự bi ến đổi tuyến tính của các tham số trong miền tính toán. Lưới nền
không nhất thiết phải trùng khít với miền tính toán. Trong trường hợp không
có lưới nền được cung cấp thì một lưới nền mặc định sẽ được tạo ra dựa trên
các quy tắc thực ng hiệm bao gồm hai phần tử ta m giác yêu cầu đồng nhất
mật độ lưới. Giá t rị tham số kích thước δ được lấy bằng 5% chiều dài đường
chéo của lưới nền và lưới đầu tiên được tạo ra sẽ là lưới nền cho lưới tiếp th eo.
D −x
c
ln 2
x ≥ x
c
trong đó δ
1
, D, và x
c
là các tham số được đưa thêm vào để có thể điều khiển
sự biến đổi của kích thước tam giác δ tại S. Hình 1.8 là đồ thị sự phụ thuộc
của δ(x) vào các tham số δ
1
, D, và x
c
.
Hình 1.8: Sự phụ thuộc của δ(x) vào các th am số δ
1
, D, và x
c
.
• Thuật toán tìm kiếm
Để nội suy các tham số lưới từ lưới nền (trong không gia n hai chiều), ta
cần địn h vị tam giác của lưới nền mà có một đi ểm cho trước nằm trong miền
23
xác định bằng cách tính toán diện tích tọa độ của điểm đó. Giả sử ta có một
tam giác có các đỉnh được đánh nhãn lần lượt là 1, 2, 3. Kí hiệu ∆123 là diện
tích của tam giác này, d i ện tích của tam giác sẽ dương nếu thứ tự 1, 2, 3 ngược
< 0. Như vậy
nếu điểm P nằm bên ngoài tam giác 123 thì có ít nhất một di ện tích tọa độ âm.
Vì vậy, nếu cho trước một điểm P(x
P
, y
P
), chúng ta sẽ lấy một tam giác
24
Copyright: Tài liệu đại học ©