DANH MỤC CÁC BẢNG . . . . . . . . . . . . . . . . . . . . . . . 2
DANH MỤC CÁC HÌNH VẼ . . . . . . . . . . . . . . . . . . . . . 3
MỞ ĐẦU 4
1 TẬP LỒI TRỰC GIAO VÀ BAO LỒI TRỰC GIAO CỦA MỘT TẬP
TRONG MẶT PHẲNG SỐ 6
1.1 TẬP LỒI VÀ BAO LỒI CỦA MỘT TẬP . . . . . . . . . . . . 6
1.2 TẬP LỒI TRỰC GIAO VÀ BAO LỒI TRỰC GIAO CỦA MỘT
TẬP TRONG MẶT PHẲNG SỐ . . . . . . . . . . . . . . . . 8
2 THUẬT TOÁN CỦA BISWAS, BHOWMICK, SARKAR VÀ BHATTACHARYA TÌM BAO LỒI TRỰC GIAO CỦA MỘT ĐA GIÁC
LƯỚI TRONG MẶT PHẲNG SỐ 12
2.1 CÁC QUY TẮC . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 THUẬT TOÁN . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 VÍ DỤ MINH HỌA . . . . . . . . . . . . . . . . . . . . . . . 28
41 trang |
Chia sẻ: honganh20 | Ngày: 05/03/2022 | Lượt xem: 335 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Luận văn Tìm bao lồi trực giao của một đa giác lưới trong mặt phẳng số, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
.., xk ∈ S thì
x =
k∑
j=1
λjx
j, λj ≥ 0,∀j = 1, 2, ..., k,
k∑
j=1
λj = 1.
Giả sử λk > 0, đặt ξ =
k−1∑
j=1
λj . Khi đó, 0 < ξ < 1 và
x =
k−1∑
j=1
λjx
j + λkx
k = ξ
k−1∑
j=1
λj
ξ
xj + λkx
k.
Do
k−1∑
j=1
λj
ξ
= 1 và
λj
ξ
> 0 với mọi j = 1, 2, ..., k−1 nên theo giả thuyết quy
nạp điểm
8y :=
k−1∑
j=1
λj
ξ
xj ∈ S.
Ta có x = ξy + λkxk.
Do ξ > 0, λk > 0 và ξ + λk =
k∑
j=1
λj = 1 nên x là một tổ hợp lồi của hai
điểm y và xk đều thuộc S.
Vậy x ∈ S.
Hình 1.2: Tập không lồi
Mệnh đề 1.1.2. (xem [11]) Nếu A, B là các tập lồi trong Rn , C là lồi trong
Rm , thì các tập sau là lồi:
A ∩B := {x|x ∈ A, x ∈ B},
αA+ βB := {x|x = αa+ βb, a ∈ A, b ∈ B,α, β ∈ R},
A× C := {x ∈ Rm+n|x = (a, c) : a ∈ A, c ∈ C}.
Định nghĩa 1.1.3. Bao lồi của một tập S là giao của tất cả các tập lồi chứa S.
Nhận xét 1.1.1. Bao lồi của tập S là tập lồi nhỏ nhất chứa S. Bao lồi của một
tập hữu hạn điểm P trong Rn là một đa giác lồi trong Rn.
1.2 TẬP LỒI TRỰC GIAO VÀ BAO LỒI TRỰC GIAO CỦA MỘT TẬP
TRONG MẶT PHẲNG SỐ
Định nghĩa 1.2.1. (xem [12]) Một tập hợp S ⊂ R2 được gọi là lồi trực giao
nếu giao của nó với mọi đường thẳng đứng và mọi đường nằm ngang là một tập
9lồi.
Hình 1.3: Tập lồi trực giao (a), (b), (c) và tập không lồi trực giao (d), (e)
Trong Hình 1.3, có ba tập là lồi trực giao ((a), (b), (c)) và hai tập không là
lồi trực giao ((d), (e)) do giao của tập (d) này với đường nằm ngang nét đứt và
tập (e) với đường thẳng đứng nét đứt là hai đoạn thẳng.
Chú ý 1.2.1. Tập lồi trực giao có thể không liên thông. Ví dụ là tập (c) trong
Hình 1.3.
Nhận xét 1.2.1. (xem [12]) (Tính chất của tập lồi trực giao)
(i) Giao của các tập lồi trực giao là một tập lồi trực giao.
(ii) Mọi tập lồi đều là lồi trực giao.
(iii) Một tập không liên thông là lồi trực giao nếu và chỉ nếu mọi thành phần
liên thông của nó là lồi trực giao và không có đường thẳng đứng hoặc
đường nằm ngang nào giao với hơn một thành phần liên thông của nó.
Định nghĩa 1.2.2. (xem [12]) Bao lồi trực giao của một tập là giao của tất cả
các tập lồi trực giao chứa tập đó.
Hình 1.4 cho hai ví dụ về bao lồi trực giao của tập liên thông ((a), (b)) và hai
ví dụ về bao lồi trực giao của tập không liên thông ((c), (d)).
Nhận xét 1.2.2. (xem [12]) (Tính chất của bao lồi trực giao)
10
Hình 1.4: Bao lồi trực giao của một số tập
(i) Bao lồi trực giao của một tập là tập lồi trực giao bé nhất chứa tập đó.
(ii) Một tập là lồi trực giao nếu và chỉ nếu bao lồi trực giao của nó là chính
nó.
(iii) Bao lồi trực giao của một tập là một tập con của bao lồi của tập đó.
Nhận xét 1.2.3. Bao lồi trực giao của một tập là duy nhất.
Định nghĩa 1.2.3. (xem [9])
Một lướiG là một tập hợp gồm một số đường nằm ngang cách đều nhau, một
số đường thẳng đứng cách đều nhau và tất cả các giao điểm của chúng, ở đó
khoảng cách giữa hai đường nằm ngang liên tiếp và hai đường thẳng đứng liên
tiếp là như nhau.
Kích thước lưới g là khoảng cách giữa hai đường nằm ngang liên tiếp (hoặc
hai đường thẳng đứng liên tiếp).
Điểm lưới là điểm giao nhau của một đường nằm ngang và một đường thẳng
đứng.
Định nghĩa 1.2.4. Mặt phẳng số là mặt phẳng được gắn thêm một lưới.
Định nghĩa 1.2.5. (xem [9]) P là một đa giác lưới khi nó là một đa giác có mỗi
đỉnh là một điểm lưới và mỗi cạnh đều song song với một trong hai trục tọa độ.
Trong luận văn này, với mục tiêu trình bày lại việc tìm bao lồi trực giao của
một đa giác lưới, khi đó bao lồi trực giao của một đa giác lưới được định nghĩa
như sau
11
Định nghĩa 1.2.6. (xem [9]) Bao lồi trực giao của một đa giác lưới S, kí hiệu
OH(S), là đa giác lưới có diện tích nhỏ nhất sao cho
(i) Mỗi điểm p ∈ S đều nằm trong OH(S).
(ii) Giao củaOH(S) với bất kì đường nằm ngang hoặc đường thẳng đứng nào
là rỗng hoặc là một đoạn thẳng duy nhất.
12
CHƯƠNG 2
THUẬT TOÁN CỦA BISWAS, BHOWMICK, SARKAR VÀ
BHATTACHARYA TÌM BAO LỒI TRỰC GIAO CỦA MỘT ĐA GIÁC
LƯỚI TRONGMẶT PHẲNG SỐ
Trong chương này, chúng ta xét bài toán tìm bao lồi trực giao của một đa giác
lưới cho trước. Để giải bài toán này, nhóm của Biswas, Bhowmick, Sarkar và
Bhattacharya đã xây dựng một số quy tắc sau đây.
2.1 CÁC QUY TẮC
Cho q là một điểm lưới và một đa giác lưới S. Việc phân loại điểm lưới q dựa
trên số ô có một đỉnh là q,Q1−Q4, nằm trong đa giác lưới S (ở đóQi là là góc
phần tư thứ i, i = 1, . . . , 4) và sự sắp xếp của chúng (Hình 2.1).
Hình 2.1: Các loại đỉnh khác nhau của một đa giác lưới
Nếu số ô nằm trong đa giác lưới S là i, thì q được phân loại thành các lớp Ci
như sau:
13
C0 : Không có ô nào nằm trong đa giác lưới. Khi đó, q không phải là một đỉnh.
C1 : Chỉ có một ô nằm trong đa giác lưới (Hình 2.1 (a)). Khi đó q là một đỉnh
của đa giác lưới S và được phân loại là một đỉnh 90.
C2 : Có đúng hai ô nằm trong đa giác lưới. Trong trường hợp này có thể có hai
cách sắp xếp khác nhau.
(i) Hai ô đó nằm trong đa giác lưới là liền kề. Khi đó, q là một điểm cạnh
(Hình 2.1 (d)).
(ii) Hai ô nằm trong đa giác lưới là chéo nhau. Khi đó, q là một đỉnh 270
(Hình 2.1 (c)). Nhận xét, trong bốn cạnh có đầu mút là q sẽ có hai cạnh
được sử dụng để xác định hướng di chuyển (qua q) để q trở thành một
đỉnh 270. Ví dụ, nếu q là điểm cuối của một cạnh đi xuống, thì cạnh
đi ra từ q sẽ hướng sang trái (đường nét liền). Tương tự, nếu q là điểm
cuối của một cạnh đi lên, thì cạnh tiếp theo sẽ hướng sang phải (đường
nét đứt).
C3 : Có đúng ba ô nằm trong đa giác lưới (Hình 2.1 (b)). Khi đó q là một đỉnh
của đa giác lưới S và q là một đỉnh 270.
C4 : Tất cả bốn ô đều nằm trong đa giác lưới. Khi đó q không phải là một đỉnh.
Như vậy, một điểm lưới có thể là một đỉnh hoặc không. Nếu điểm lưới q là
một đỉnh của đa giác lưới, thì q có thể là một đỉnh 90 hoặc là một đỉnh 270.
Ngược lại, nếu q không phải là một đỉnh, thì q có thể là một điểm trên cạnh của
bao lồi trực giao, hoặc là một điểm nằm bên trong đa giác lưới, hoặc là nằm bên
ngoài đa giác lưới. Do đó, trong luận văn này, một đỉnh loại 1 là một đỉnh 90 (1
×90o) và một đỉnh loại 3 là một đỉnh 270 (3 ×90o) để dễ kí hiệu.
Một đỉnh vi được biểu diễn bởi một bộ ba. Trong đó ti (=1 hoặc
3) là loại đỉnh, di là hướng di chuyển từ đỉnh vi đến đỉnh vi+1 và li là chiều dài
đoạn đường (nằm ngang hoặc thẳng đứng) từ vi đến vi+1. Các hướng di chuyển
di từ vi có thể có các giá trị 0, 1, 2 hoặc 3 cho biết tương ứng các hướng đi
14
sang phải, lên trên, sang trái hoặc xuống dưới. Hướng di chuyển di được xác
định bởi hướng di chuyển trước đó di−1 (hướng di chuyển từ vi−1 đến vi) và
loại đỉnh vi và được cho bởi công thức di = (di−1 + ti) mod 4. Khi di được
tính toán, điểm lưới tiếp theo được xác định bởi loại của nó. Do đó, quá trình di
chuyển từ vi đến vi+1 kết thúc khi trở về đỉnh bắt đầu. Để xác định đỉnh bắt đầu,
chúng tôi giả sử rằng nó là điểm trên cùng bên trái p0(i0, j0) của đa giác lưới
S. Điểm p0 là điểm trên cùng bên trái khi và chỉ khi với mỗi điểm p(i, j) ∈ S
thì j i0. Khi đó tọa độ của điểm bắt đầu vs được cho
bởi is = (di0/ge − 1)× g, js = (bj0/gc+ 1)× g (ở đây, g là kích thước lưới).
Kiểu ts của đỉnh bắt đầu được xác định bởi số ô lân cận nằm trong đa giác lưới.
Hướng bắt đầu từ vs được cho bởi công thức ds = (2 + ts) mod 4.
Hình 2.2: Vùng lõm do hai đỉnh loại 3 liên tiếp, tạo ra nhiều đoạn thẳng với một
đường thẳng đứng (trái) và một đường nằm ngang (phải)
Trong quá trình di chuyển, nếu gặp hai đỉnh loại 3 liên tiếp, thì nó cho chúng
ta biết có một vùng lõm xuất hiện và nó không thỏa mãn tính lồi trực giao. Ví
dụ trong Hình 2.2 là hai mẫu như trên mà giao điểm của một đường thẳng đứng
hoặc một đường nằm ngang l với đa giác lưới có nhiều hơn một đoạn. Do đó,
mục tiêu của chúng ta là xác định những vùng như vậy và suy ra các cạnh của
bao lồi trực giao sao cho các tính chất lồi trực giao được bảo đảm. Mặt khác,
các mẫu 13, 31 và 11 không tạo thành vùng lõm và do đó không vi phạm các
tính chất của lồi trực giao. Bởi vì lí do này nên trong thuật toán của Biswas,
Bhowmick, Sarkar và Bhattacharya, bao lồi trực giao thu được khi không có hai
15
đỉnh loại 3 liên tiếp (mẫu 33) xuất hiện trong chuỗi danh sách các đỉnh (xem
Chương 2, Mục 2.2).
Cho v0, v1, v2, v3 và v4 là năm đỉnh liên tiếp mà cần phải sử dụng quy tắc
để loại bỏ vùng lõm, trong đó v4 là đỉnh mới cập nhật còn bốn đỉnh v0 . . . v3
đã được cập nhật trước đó. Do quy tắc loại bỏ vùng lõm chỉ được áp dụng khi
xuất hiện hai đỉnh loại 3 liên tiếp, Biswas, Bhowmick, Sarkar và Bhattacharya
đã thiết kế hai bộ quy tắc tùy thuộc vào đỉnh tiếp theo mẫu 33 là 1 hay 3. Trong
luận văn này, chúng tôi quy ước hai đỉnh loại 3 liên tiếp là v2 và v3, đỉnh v1
thuộc loại 1, đỉnh v0 có thể thuộc loại 1 hoặc cũng có thể thuộc loại 3. Đối với
thuật toán này, Biswas, Bhowmick, Sarkar và Bhattacharya quy ước luôn bắt
đầu từ một đỉnh loại 1. Sử dụng quy ước này để đảm bảo rằng luôn có một đỉnh
loại 1 trước hai đỉnh loại 3 liên tiếp. Một đỉnh giả sẽ được đưa ra trước đỉnh bắt
đầu để xử lí tình huống khi hai đỉnh loại 3 xuất hiện ngay sau đỉnh bắt đầu.
Định nghĩa 2.1.1. [9] Mẫu 1331 là một mẫu biểu diễn một đỉnh loại 1, sau đó
là hai đỉnh loại 3 liên tiếp, theo sau là một đỉnh loại 1.
Hai đỉnh loại 3 liên tiếp trong mẫu 1331 cho chúng ta một vùng lõm. Để loại
bỏ vùng lõm này, dựa vào mối quan hệ độ dài các cạnh l1 và l3, chúng ta có ba
trường hợp dưới đây ([9]) (Hình 2.3, 2.4, 2.5):
• Quy tắc R11 (Áp dụng khi l1 = l3) (Hình 2.3): Các đỉnh v1, v2, v3 và v4 bị
loại bỏ và độ dài v0 được sửa lại thành l0 + l2 + l4.
• Quy tắc R12 (Áp dụng khi l1 > l3) (Hình 2.4): Các độ dài l1 và l2 được sửa
lại lần lượt là l1 − l3 và l2 + l4. Các đỉnh v3 và v4 bị loại bỏ.
• Quy tắc R13 (Áp dụng khi l1 < l3) (Hình 2.5): Các đỉnh v1 và v2 bị loại
bỏ. Các độ dài l0 và l3 được sửa lại lần lượt là l0 + l2 và l3 − l1.
Chú ý 2.1.1. Trong ba quy tắc R11, R12, R13 loại t0 của đỉnh t0 vẫn không
thay đổi, điều này đúng và không gây ra vấn đề khi v0 là đỉnh giả.
16
Hình 2.3: Quy tắc R11 cho mẫu 1331
Hình 2.4: Quy tắc R12 cho mẫu 1331
17
Hình 2.5: Quy tắc R13 cho mẫu 1331
Định nghĩa 2.1.2. [9] Mẫu 1333 là một mẫu biểu diễn một đỉnh loại 1, sau đó
là ba đỉnh loại 3 liên tiếp.
Để loại bỏ vùng lõm với mẫu này chúng ta có các quy tắc như sau ([9])(Hình
2.6, 2.7, 2.8):
• Quy tắc R21 (Áp dụng khi l1 < l3) (Hình 2.6): Các đỉnh v1 và v2 bị loại
bỏ. Các độ dài l0 và l3 được sửa lại lần lượt là l0 + l2 và l3 − l1.
• Quy tắc R22 (Áp dụng khi l1 ≥ l3 và d = d2) (Hình 2.7): Bắt đầu từ đỉnh
v4. Gọi v là đỉnh hiện tại đang xét. Gọi lH là đường nằm ngang đi qua v2,
lV là đường thẳng đứng đi qua v4. Quy tắc chỉ được áp dụng khi v nằm dưới
nửa mặt phẳng xác định bởi lH đồng thời nằm bên trái nửa mặt phẳng xác
định bởi lV . Hai biến l′ và l” được khởi tạo với giá trị ban đầu lần lượt là
l1 − l3 và l4 được dùng để xác định xem v có ra khỏi vùng lõm của mẫu
này hay không. Độ dài l′ và l” được cập nhật dựa theo hướng đi của v. Nếu
hướng đi từ v, kí hiệu là d, giống với hướng đi từ v1 (nghĩa là d = d1), thì
l′ được cập nhật thành l′ = l′+ l. Ở đó l là độ dài đường đi từ v. Ngược lại,
nếu hướng đi từ v giống với hướng đi từ v3 (nghĩa là d = d3), thì l′ được
18
cập nhật thành l′ = l′ − l. Tương tự, l” được cập nhật thành l” = l” + l
nếu hướng đi từ v giống hướng đi từ v4 (nghĩa là d = d4) và l” = l” − l
nếu hướng đi từ v giống hướng đi từ v2 (nghĩa là d = d2). Quá trình này
được thực hiện cho đến khi l′ < l1 − l3 và l” < l2. Kết thúc quá trình độ
dài l1 được cập nhật thành l′ và độ dài l2 được cập nhật thành l2 − l”. Các
đỉnh v3 và v4 bị loại bỏ.
• Quy tắc R23 (Áp dụng khi l1 ≥ l3 và d = d3) (Hình 2.8): Tương tự như
luật R22, hai biến l′ và l” được khởi tạo. Quá trình này được thực hiện cho
đến khi l′ < l1 − l3 và l” < l2. Kết thúc quá trình đỉnh v4 bị loại bỏ và độ
dài l1, l2 và l3 lần lượt được cập nhật thành l1 = l1 − l3, l2 = l2 − l” và
l3 = l1 − l3 − l′.
Hình 2.6: Quy tắc R21 cho mẫu 1333
Chú ý 2.1.2. Mỗi quy tắc cho mẫu 1331 loại bỏ một vùng lõm tùy thuộc vào độ
dài l1 và l3. Trong khi đó, mỗi quy tắc cho mẫu 1333 chỉ loại bỏ vùng lõm khi
đỉnh cuối cùng ra khỏi vùng lõm đồng thời sử dụng toàn bộ độ dài l0, l1, l2, l3,
l4.
19
Hình 2.7: Quy tắc R22 cho mẫu 1333
Hình 2.8: Quy tắc R23 cho mẫu 1333
20
Các quy tắc trên được phát hiện và áp dụng khi di chuyển xung quanh biên
của đa giác lưới. Danh sách L được khởi tạo với một đỉnh giả. Quá trình bắt
đầu từ đỉnh trên cùng bên trái của đa giác lưới. Trong quá trình, mỗi đỉnh mới
được truy cập sẽ được thêm vào danh sách L. Sau đó, năm đỉnh cuối cùng trong
danh sách của L sẽ được kiểm tra. Nếu xuất hiện vùng lõm thì một trong các
quy tắc loại bỏ vùng lõm cho mẫu 1331 và 1333 được áp dụng, sau đó, một lần
nữa năm đỉnh cuối cùng của L được kiểm tra. Nếu không, thêm đỉnh tiếp theo
vào danh sách của L, sau đó kiểm tra năm đỉnh cuối cùng. Quá trình thực hiện
cho đến khi đỉnh bắt đầu được xét đến lần thứ hai. Kết thúc thuật toán L là danh
sách chứa các đỉnh của bao lồi trực giao.
2.2 THUẬT TOÁN
Algorithm 1 Sơ lược về thuật toán
Các bước:
1: Tìm đỉnh bắt đầu, vs
2: for (TRUE) do
3: Tìm đỉnh tiếp theo, vn
4: Cho đỉnh này vào danh sách L (Bắt đầu là tập rỗng)
5: if loại bốn đỉnh cuối trong danh sách L là mẫu 1331 then
6: áp dụng quy tắc R11, R12 hoặc R13
7: else
8: if loại bốn đỉnh cuối trong danh sách L là mẫu 1333 then
9: áp dụng quy tắc R21, R22 hoặc R23
10: while vn 6= vs
Sơ lược về thuật toán của Biswas, Bhowmick, Sarkar và Bhattacharya được
đưa ra trong Algorithm 1. Bắt đầu từ đỉnh vs. Trong vòng lặp do-while, đỉnh
tiếp theo vn được xác định và cho vào danh sách L. Nếu bốn đỉnh cuối trong
danh sách L có mẫu 1331 thì áp dụng một trong các quy tắc R11, R12, R13.
Tương tự, một trong các quy tắc R21, R22, R23 được áp dụng khi bốn đỉnh
21
cuối cùng trong danh sách L có mẫu 1333. Vòng lặp do-while được tiếp tục cho
đến khi cập nhật tới đỉnh vs lần hai.
Algorithm 2 Thuật toán Otho-Hull(S, g, vs)
Các bước:
1: L[1]← vd, k ← 2
2: L[k].d = ds, L[k].t = ts, ←
3: for (TRUE) do
4: ← Next-Vertex(S, i, j, L[k].d, g)
5: while (TRUE) do
6: if (k ≥ 5) then
7: if (L[k − 3]..L[k].t = 1331) then
8: k ← Apply-R1(L, k)
9: else
10: if (L[k − 3]..L[k].t = 1333) then
11: ← Apply-R2(L, k, i, j, g)
12: else break
13: k ← k + 1
14: L[k].d← d, L[k].t← t
15: while ( 6=)
Thuật toán Otho-Hull [9] đưa ra danh sách sắp xếp các đỉnh của bao lồi trực
giao của một đa giác lưới. Nó lấy đa giác lưới S, kích thước lưới g và đỉnh bắt
đầy vs như là tham số đầu vào. Danh sách L được khởi tạo với một đỉnh giả vd.
Độ dài cạnh từ vd được đặt bằng 0 và hướng đi của vd không có ý nghĩa trong
thuật toán. Đỉnh giả là bắt buộc vì quy tắc luôn được áp dụng cho một chuỗi
năm đỉnh. Một tình huống có thể xảy ra là vs luôn thuộc loại 1 và tiếp theo
sau là hai đỉnh loại 3 và một đỉnh loại 1 dẫn đến mẫu 1331 và l1 > l3. Khi đó
quy tắc R21 được áp dụng (trên năm đỉnh liên tiếp) trong đó yêu cầu một đỉnh
giả. Trong mỗi lần vòng lặp do-while (Bước 3− 15), đỉnh tiếp theo được thêm
vào L. Nếu danh sách L chứa nhiều hơn năm đỉnh (Bước 6), thì mẫu được hình
thành bởi bốn đỉnh cuối cùng các đỉnh trong L được kiểm tra. Các đỉnh v4, v3,
22
v2, v1 và v0 được đề cập đến ở Mục 2.1 tương ứng với các đỉnh được biểu thị bởi
L[k], L[k− 1], L[k− 2], L[k− 3] và L[k− 4], ở đó L[k] là đỉnh được truy cập
gần nhất. Nếu mẫu ứng với loại của L[k]...L[k − 3] là 1331 thì quy tắc dùng
để loại bỏ vùng lõm là áp dụng Apply-R1 [9] (Bước 7-8). Quy trình Apply-R1
trả về giá trị cập nhật của k. Tương tự, nếu mẫu ứng với dạng 1333 thì quy tắc
dùng để loại bỏ vùng lõm là áp dụng Apply-R2 [9] (Bước 10-11). Apply-R2 trả
về cho chúng ta k và . Nếu việc loại bỏ vùng lõm được thực hiện, thuật
toán tiếp tục đánh giá bốn đỉnh cuối cùng sau khi loại bỏ (Bước 5-12) đế kiểm
tra xem có giảm thêm không. Mặt khác, khi không có quy tắc nào được áp dụng
(Bước 12) nó sẽ thoát ra vòng lặp While và đánh giá đỉnh tiếp theo. Biến k luôn
luôn trỏ đến đỉnh cuối cùng của danh sách L và được tăng lên với lượt truy cập
của mỗi đỉnh. Quy trình Next-Vertex [9] tính toán độ dài tương ứng với L[k].
Nó cũng tính hướng d và loại t của đỉnh tiếp theo. Giá trị của k được tăng lên ở
bước 13 và d, t được chỉ định để tăng lên L[k]. Thuật toán kết thúc (Bước 15)
khi tọa độ trùng với .
Algorithm 3 Quy trình Next-Vertex(S, i, j, d, g)
Các bước:
1: m← 0, r ← 0, l← 0
2: while (TRUE) do
3: (i, j)← d∗(i, j)
4: for h← 1 to 4 do
5: if Qh(i, j) ∩ S 6= ∅ then
6: m← m+ 1, r ← r + h
7: if r ∈ {4, 6} vàm = 2 then t← 3
8: else
9: ifm ∈ {0, 2, 4} then t← 0
10: else t← m
11: d← (t+ d) mod 4, l← l + g
12: if t 6= 0 then break
13: return
23
Trong quy trình Next-Vertex, trong vòng lặp While (Bước 2-12), đỉnh tiếp
theo được tính từ đỉnh hiện tại . Các tọa độ của điểm lưới tiếp theo
được xác định trong Bước 3. Bước 4-11 xác định xem điểm lưới có phải một
đỉnh (loại 1 hoặc 3) hoặc một điểm cạnh hay không. Thuật toán tiếp tục đánh
giá các điểm lưới tiếp theo cho đến khi đạt được đỉnh L[k + 1]. Khi thuật toán
tiến tới đỉnh tiếp theo, chiều dài được tăng thêm bởi g (Bước 11). Quy trình cho
ta loại và hướng của đỉnh L[k + 1] và chiều dài l từ đỉnh hiện tại L[k] đến đỉnh
tiếp theo L[k + 1]. Các tọa độ của điểm lưới tiếp theo được tính (Bước 3) dựa
trên hướng d từ (i, j). Nếu hướng di chuyển sang phải (d = 0) hoặc sang trái
(d = 2) thì tọa độ y vẫn không thay đổi và tọa độ x được tăng (d = 0) hoặc
giảm (d = 2) theo g. Nếu hướng di chuyển lên trên (d = 1) hoặc xuống dưới
(d = 3) thì tọa độ y được giảm (d = 1) hoặc tăng (d = 3) trong khi tọa độ x
giữ nguyên. Nói cách khác, với d = 0, ←; với d = 2,
←; với d = 1, ←; với d = 3,
←.
Trong quy trình Apply-R1, nếu độ dài của các đỉnh L[k − 3] và L[k − 1] là
giống nhau (Bước 1), thì độ dài của L[k − 4] được sửa lại như trong Bước 2.
Phần đuôi của danh sách được đặt lại thành k − 4 (Bước 3) khi bốn đỉnh cuối
cùng được xóa theo quy tắc R11, tương tự quy tắc R12 và R13 được thực hiện
lần lượt theo Bước 4-8 và Bước 9-14. Trong khi áp dụng quy tắc R13, các đỉnh
L[k − 3] (v1) và L[k − 2] (v2) bị xóa bỏ, các đỉnh L[k − 1] (v3) và L[k] (v4)
được gán lại là L[k − 3] và L[k − 2] tương ứng (Bước 12-13). Đuôi của danh
sách k được đặt lại thành k − 2 vì có hai đỉnh đã bị xóa (Bước 14). Giá trị của
k được đặt lại tương ứng k − 4 (Bước 3) và k − 2 (Bước 8). Quy trình trả về và
cập nhật cho chúng ta giá trị k trong Bước 15.
Quy trình Apply-R2 thực hiện bộ quy tắc thứ hai cho mẫu 1333. Quy tắc
R21 được áp dụng khi l1 < l3 (Bước 1-6). Mặt khác, khi l1 ≥ l3 (Bước 8), hai
biến l′ và l” được khởi tạo (Bước 9). Vòng lặp While (Bước 11-19) được lặp lại
miễn là điều kiện l′ ≥ l1− l3 hoặc điều kiện l” ≥ l2 còn thỏa mãn. Trong vòng
lặp While, đỉnh tiếp theo được truy cập và các giá trị l′ và l” được sửa đổi tùy
24
Algorithm 4 Quy trình Apply-R1(L, k)
Các bước:
1: if L[k − 3].l = L[k − 1].l then
2: L[k − 4].l← L[k − 4].l + L[k − 2].l + L[k].l
3: k ← k − 4
4: else
5: if L[k − 3].l > L[k − 1].l then
6: L[k − 3].l← L[k − 3].l − L[k − 1].l
7: L[k − 2].l← L[k − 2].l + L[k].l
8: k ← k − 2
9: else
10: L[k − 1].l← L[k − 1].l − L[k − 3].l
11: L[k − 4].l← L[k − 4].l + L[k − 2].l
12: L[k − 2]← L[k]
13: L[k − 3]← L[k − 1]
14: k ← k − 2
15: return k
25
Algorithm 5 Quy trình Apply-R2(L, k, i, j, g)
1: if L[k − 3].l < L[k − 1].l then
2: L[k − 1].l← L[k − 1].l − L[k − 3].l
3: L[k − 4].l← L[k − 4].l + L[k − 2].l
4: L[k − 2]← L[k]
5: L[k − 3]← L[k − 1]
6: k ← k − 2
7: else
8: l′ ← L[k − 3].l − L[k − 1], l”← L[k].l
9: d← L[k].d
10: while l′ ≥ L[k − 3].l − L[k − 1].l hoặc l” ≥ L[k − 2].l do
11: ← Next-Vertex (S, i, j, d, g)
12: if d = dk−3 then l′ ← l′ + l
13: else
14: if d = dk−1 then l′ ← l′ − l
15: else
16: if d = dk then l”← l” + l
17: else
18: if d = dk−2 then l”← l”− l
19: if d = dk−2 then
20: L[k − 2].l← L[k − 2].l − l”
21: L[k − 3].l← l′
22: k ← k − 2
23: else
24: if d = dk−1 then
25: L[k − 3].l← L[k − 3].l − L[k − 1].l
26: L[k − 2].l← L[k − 2].l − l”
27: L[k − 1].l← L[k − 3].l − L[k − 1].l − l′
28: k ← k − 1
29: return
26
theo hướng đi của đỉnh đó. Nếu hướng đi này giống hướng đi của L[k− 3] thì l′
được cập nhật thành l′ + l; nếu hướng đi này giống hướng đi của L[k− 1] thì l′
được cập nhật thành l′ − l (Bước 13-15). Tương tự l” cũng được sửa đổi (Bước
16-19). Do đó, mỗi lần đỉnh mới được truy cập, tham số l′ và l” cũng được sửa
đổi. Khi thoát khỏi vòng lặp While, hai quy tắc R22 và R23 được áp dụng tùy
theo hướng di chuyển của đỉnh hiện tại. Nếu hướng di chuyển này giống hướng
của từ L[k − 2] (Bước 20), thì R22 được áp dụng (Bước 20-23). Nếu hướng đi
này giống hướng đi từ L[k − 1], thì R23 được áp dụng (Bước 24-29). Giá trị
của k được điều chỉnh lại thành k − 2 (Bước 23) cho quy tắc R22 và cho k − 1
(Bước 29) cho quy tắc R23. Quy trình trả về k và (Bước 30).
Mệnh đề 2.2.1. [9] Cho đa giác lưới S nằm trong lướiG có cỡ g. Khi đó, thuật
toán của Biswas, Bhowmick, Sarkar và Bhattacharya cho chúng ta chính xác
bao lồi trực giao của S trên lưới G.
Chứng minh. Thuật toán là chính xác vì bao lồi trực giao được tạo ra bởi thuật
toán Otho-Hull tuân thủ tính lồi trực giao qua mỗi bước đồng thời bao lồi trực
giao tạo ra bởi thuật toán có diện tích tối thiểu. Thật vậy, chúng ta thấy rằng, nếu
p nằm trên một đường lưới và nằm bên trái đa giác lưới S, thì 0 < dT (p, S) =
h ≤ g (ở đó dT (p, q) = max{|ip−iq|, |jp−jq|} là kí hiệu của khoảng cách trực
giao giữa hai điểm p(ip, jp) và q(iq, jq); dT (p, S) = min{dT (p, q), q ∈ S}). Vì
khi h > g thì trong bốn ô Q1, . . . , Q4 không có ô nào nằm trong đa giác lưới
S. Khi đó, mỗi ô nằm bên trái đường đi xung quanh đa giác lưới S và mỗi ô
tự do (bốn ô liền kề đều không nằm trong đa giác lưới S) nằm bên phải đường
đi. Các ô tự do nằm trong bao lồi trực giao khi và chỉ khi các quy tắc loại bỏ
vùng lõm được áp dụng. Rõ ràng, từ các quy tắc Mục 2.1 thì số lượng các ô tự
do trong bao lồi trực giao là tối thiểu.
Để chỉ ra rằng, giao điểm của bao lồi trực giao với bất kì đường nằm ngang
hoặc đường thẳng đứng (đường lưới hoặc không là đường lưới) nào đều là rỗng
hoặc là duy nhất một đoạn thẳng, chúng ta chỉ cần quan sát đa giác cuối cùng
không chứa hai đỉnh loại 3 liên tiếp. Theo các quy tắc loại bỏ vùng lõm (ngoại
trừ quy tắc R21 và quy tắc R23), kết quả của mỗi quy tắc không chứa hai đỉnh
27
loại 3 liên tiếp. Kết quả của R21 hoặc R23 có mẫu 33 ở cuối được loại bỏ tùy
thuộc vào đỉnh tiếp theo. Trong lần lặp lại cuối cùng, đỉnh cuối cùng được truy
cập trùng với đỉnh bắt đầu. Đỉnh này thuộc loại 1 và do đó một trong các quy
tắc R11, R12, R13 được áp dụng. Khi kết thúc thuật toán chúng ta không có
hai đỉnh loại 3 liên tiếp.
Mệnh đề 2.2.2. [9] Thuật toán của Biswas, Bhowmick, Sarkar và Bhattacharya
có độ phức tạp thời gian là O(n) với n là số đỉnh của đa giác lưới S.
Chứng minh. Do xuất phát từ một đa giác lưới, nên một ô bất kì nằm trong đa
giác lưới S có đỉnh là điểm lưới q được xác định bởi giao điểm của đa giác lưới
và bốn cạnh tương ứng của ô đó. Đối với mỗi cạnh, giao điểm có thể kiểm tra
trong thời gian O(g). Do đó, để kiểm tra một ô bất kì có nằm trong đa giác lưới
hay không cần thời gian 4×O(g) = O(g).
Trong quá trình di chuyển của các điểm lưới nằm trên biên đa giác lưới,
chúng ta truy cập từng điểm qi từ điểm qi−1 bằng cách sử dụng thông tin về
giao điểm của đa giác lưới và các cạnh tại qi−1. Ví dụ, Hình 2.1 (a), nếu qi−1
là loại đỉnh thuộc loại 1 và đã được truy cập hướng di−1 (hướng từ trên xuống)
(đã biết trước đó thông qua đỉnh qi−2), thì qi được truy cập từ cạnh nằm ngang
của qi−1. Do đó số lượng điểm lưới được truy cập trong khi di chuyển trực giao
theo đường biên của đa giác lưới được giới hạn bởi O(n/g), ở đó n là số đỉnh
của đa giác lưới S. Chú ý rằng, với một đa giác lưới, n là số cố định. Do đó
độ phức tạp để truy cập tất cả các đỉnh là O(n/g).O(g) = O(n). Chúng ta
thấy, mỗi đỉnh trên đường biên của đa giác lưới được truy cập một lần (Hình
2.1 (a),(b),(d)) hoặc hai lần (Hình 2.1 (c)). Thời gian dùng để phát hiện và loại
bỏ mẫu chứa hai đỉnh loại 3 liên tiếp (gồm các loại của bốn đỉnh cuối cùng
trong danh sách L) mất thời gian O(1) và sử dụng quy tắc loại bỏ vùng lõm
nếu cần thiết. Nếu loại của hai đỉnh cuối cùng trong danh sách L không chứa
hai đỉnh loại 3 liên tiếp thì thời gian cần để truy cập một đỉnh mới là O(1).
Nếu loại của hai đỉnh cuối cùng trong danh sách L có dạng là 33 thì cần thời
gian O(1) để áp dụng quy tắc loại bỏ vùng lõm nếu cần thiết. Số lần giảm tối
đa được giới hạn bởi O(n/g)− 4 vì nhiều nhất O(n/g) đỉnh được cập nhật và
28
bao lồi trực giao ít nhất là bốn đỉnh. Do đó, tổng số hoạt động được giới hạn
bởi (O(n/g)− 4).O(1) = O(n/g). Như vậy, tổng thời gian để tìm bao lồi trực
giao của một đa giác lưới là O(n) +O(n/g) = O(n). Lưu ý rằng, ở đây giá trị
của g có thể thay đổi và giá trị nhỏ nhất của g là 1.
2.3 VÍ DỤ MINH HỌA
Hình 2.9: Bao lồi trực giao (đường nét liền đậm) của một đa giác lưới có đường
viền là nét liền nhạt
Một
Các file đính kèm theo tài liệu này:
luan_van_tim_bao_loi_truc_giao_cua_mot_da_giac_luoi_trong_ma.pdf