Luận văn Sử dụng kỹ thuật “phễu” và “cây phễu” để tìm đường đi ngắn nhất trên bề mặt của khối đa diện

giác đơn P . Xét các đường chéo ds, ds+1, . . . , di−1 bị cắt bởi các đường gấp khúc SP (v, vi (1)) và SP (v, vi (2)). Rõ ràng, 4vv(1)s v(2)s = Rs nằm hoàn toàn trong đa giác đơn P . Giả sử rằng Ri−1 ⊂ P , khi đó miền Ri mới được tạo thành từ miền Ri−1 hợp thêm với một phần hoặc toàn bộ một tam giác (tam giác chứa cạnh di) nằm trong đa giác đơn P . Từ đó, chúng ta cũng suy ra được Ri ⊂ P . Trong trường hợp SP (v, v (j) i ) không là đường gấp khúc lồi trong thì theo bất đẳng thức tam giác (tổng của hai cạnh bao giờ cũng lớn hơn cạnh còn lại), ta luôn tìm được một đường đi ngắn nhất từ v tới vi và đường ngắn nhất đó luôn nằm trong đa giác đơn P . Điều này trái với giả thiết ban đầu khi SP (v, v (j) i ) là đường ngắn nhất từ v tới vi (xem Hình 1.10). Tính chất lồi này cũng chỉ ra rằng SP (v, v (1) i ) và SP (v, v (2) i ) bị chia nhánh nhiều nhất chỉ tại một đỉnh v, nếu chúng bị chia nhánh ở một đỉnh u1 nào đó thì nó sẽ lại gặp nhau tại một đỉnh u2 nào đó, và hai đường gấp khúc tách rời từ u1 tới u2 này phải là đường gấp khúc lồi trong. Khi đó, SPi = SP (v, v (1) i ) ∪ SP (v, v(2)i ), và v được gọi là đỉnh của hai đường gấp khúc lồi hướng trong. Ở đây, một trong hai đường gấp khúc có thể là rỗng (nhưng không thể hai đường gấp khúc đó cùng rỗng, vì v (1) i 6= v(2)i ). Nếu SP (v, v(1)i ) rỗng thì rõ ràng SP (v, v (2) i ) = di và ngược lại. Trong trường hợp này, phễu Ri suy biến không có miền trong và SPi trở thành một đường gấp khúc đơn. 14 Hình 1.10 Hình ảnh minh hoạ cho tính lồi trong của SP (s, v(j)i ). Để làm rõ được ý nghĩa của tính lồi trong, và một trong hai đường gấp khúc có thể rỗng, chúng ta sẽ cùng tìm hiểu kĩ hơn về thuật toán tìm đường đi ngắn nhất giữa hai điểm trong một đa giác đơn của Lee và Preparata trong phần dưới đây. 1.4 THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT GIỮA HAI ĐIỂM TRONG ĐA GIÁC ĐƠN Xuất phát từ một đỉnh nguồn s thuật toán sau đây xây dựng các đường SPi = SP (v, v (1) i ) ∪ SP (v, v(2)i ) chứa đường biên của phễu Ri cho tới khi tới điểm đích (tức là v (2) i ≡ t), chúng ta cùng đi xét bài toán sau: Bài toán: Xét một hình ống tay P và hai điểm cho trước s và t thuộc hình ống tay P đó. Tìm đường đi ngắn nhất từ s tới t nằm trong P . Hình 1.11 Hình ảnh minh hoạ cho bước tổng quát; hình a) uj ∈ uaua−1 . . . u0; hình b) uj ∈ uaua+1 . . . ub. 15 Algorithm 1 Thuật toán Lee và Preparata 1: Bước khởi tạo: Xây dựng SP1 bằng cách nối s với v (1) 1 và v (2) 1 . 2: Bước tổng quát : (Xây dựng SPi+1 từ SPi) Xét v là đỉnh của SPi = SP (v, v (1) i ) ∪ SP (v, v(2)i ) SPi được chia làm hai nhánh tại v Chúng ta kí hiệu hai nhánh đó là uaua+1 . . . ub và uaua−1 . . . u0 Ở đó v = ua, v (1) i = ub, v (2) i = u0 Bắt đầu duyệt từ điểm u0, u1, . . . , ub j là chỉ số nhỏ nhất sao cho v(2)i+1uj là đường tiếp tuyến của biên Ri. Chúng ta sẽ xét hai trường hợp: ˆ Trường hợp 1 : j ≤ a (xem Hình 1.11 a)) – Xoá hết các cạnh ulul+1 với 0 ≤ l ≤ j − 1. – Thêm cạnh ujv (2) i+1. ˆ Trường hợp 2 : j > a (xem Hình 1.11 b)) – Xoá hết các cạnh ujul+1 với 0 ≤ l ≤ j − 1. – Thêm cạnh ujv (2) i+1. – Miền Ri+1 sẽ nhận uj là đỉnh mới. 3: Bước kết thúc: Sau khi xây dựng được SPn−3, đường chéo dn−2 chia P thành hai miền, và một trong hai miền này sẽ chứa điểm đích t. - Gán v(2)n−2 = t. - Áp dụng bước tổng quát cho từng trường hợp với i = n−3 và SPn−2 = SP (s, v(1)n−2)∪SP (s, t). - SP (s, t) ⊂ SPn−2. Ví dụ 1.4.1. Xét một đa giác đơn P với 13 đỉnh, một điểm nguồn s và điểm đích t (xem Hình 1.12). Tìm đường đi ngắn nhất từ s tới t bằng cách sử dụng thuật toán Lee và Preparata. Hình 1.12 Đa giác đơn P = (q1, q2, . . . , q13) có điểm nguồn là s và điểm tới là t. 16 Hình 1.13 Đa giác đơn P được tam giác phân bởi các đường chéo nét đứt. Hình 1.14 Cây đối ngẫu của đa giác đơn P là đường màu đỏ. Hình 1.15 Miền P ′ màu xanh lá là hình ống tay chứa đường đi ngắn nhất từ s tới t. Hình 1.16 Phễu thứ nhất giới hạn bởi SP (s, q11), SP (s, q13) và đường chéo [q11, q13] có chóp là s. 17 Hình 1.17 Phễu thứ hai giới hạn bởi SP (s, q11), SP (s, q3) và đường chéo [q3, q11] có chóp là s. Hình 1.18 Phễu thứ ba giới hạn bởi SP (s, q11), SP (s, q4) và đường chéo [q4, q11] có chóp là s. Hình 1.19 Phễu thứ tư giới hạn bởi SP (s, q10), SP (s, q4) và đường chéo [q4, q10] có chóp là s. 18 Hình 1.20 Phễu thứ năm giới hạn bởi SP (s, q4), SP (s, q9) và đường chéo [q4, q9] có chóp là s. Hình 1.21 Phễu thứ sáu giới hạn bởi SP (s, q5), SP (s, q9) và đường chéo [q5, q9] có chóp là s. Hình 1.22 Phễu thứ bảy bị suy biến, miền trong bằng rỗng, SP (s, q9) là đường màu hồng. Hình 1.23 SP (s, t) = SP (s, q9) ∪ SP (q9, t) là đường đi ngắn nhất từ s tới t. 19 Chương 2 TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN BỀ MẶT CỦA KHỐI ĐA DIỆN Trong chương này, luận văn trình bày thủ tục lật phẳng một dãy mặt tam giác theo các cạnh chung và việc xác định đường đi ngắn nhất từ một điểm nguồn s tới các đỉnh còn lại trên bề mặt của một khối đa diện mà các mặt đã được tam giác phân trong không gian ba chiều bằng cách sử dụng một thuật toán nguồn sáng và bóng [10]. Bên cạnh đó, luận văn cũng trình bày một ví dụ minh hoạ cho thuật toán. 2.1 PHÉP LẬT Xét P là một mặt đa diện với các mặt đã được tam giác phân trong không gian ba chiều, với s là một đỉnh của khối đa diện P cần tìm ra một đường ngắn nhất từ điểm nguồn s tới các đỉnh còn lại trên bề mặt khối đa diện P . Luận văn sẽ trình bày lại một số khái niệm về dãy mặt, dãy cạnh mà Mitchell đưa ra năm 1987 [9]. F = (f1, f2, . . . , fm+1) và E = (e1, e2, · · · , em) lần lượt là một dãy các mặt và một dãy các cạnh, fi ∩ fi+1 = ei, f1 là tam tam giác chứa đỉnh nguồn s. Ngoại trừ các trường hợp cụ thể khác, các dãy mặt tam giác được đề cập đến sau đây đều dãy mặt mà các tam giác khác nhau từng đôi một. Kĩ thuật phép lật phẳng (planar unfolding) là phương pháp được sử dụng để tìm đường đi ngắn nhất. Ta thực hiện lật phẳng các mặt f1, f2, . . . , fm lần lượt theo e1, e2, . . . , em lên mặt phẳng chứa mặt fm+1. 20 Hình 2.1 Một dãy các mặt tam giác (f1, f2, . . . , fm+1) lần lượt liền kề theo các cạnh (e1, e2, · · · , em). Thủ tục của phép lật dãy mặt F được mô tả như sau [10]: Thủ tục lật phẳng 1: F = {f1}. 2: For i:=1 to m do Quay F quanh ei cho tới khi F và fi+1 cùng nằm trên một mặt phẳng và khác phía với mặt fi+1 so với cạnh ei; F := F ∪ {ei, fi+1}. 3: End Quy trình này dừng lại khi các mặt f1, f2, . . . , fm cùng nằm trên mặt phẳng chứa mặt fm+1. Ưu điểm của phép lật khi sử dụng để giải bài toán tìm đường đi ngắn nhất là giúp chúng ta đưa bài toán từ không gian ba chiều về bài toán trong không gian hai chiều mà không mất đi độ chính xác về khoảng cách giữa hai điểm trên một mặt và độ lớn các góc trong cùng một mặt phẳng. Bổ đề 2.1.1. Với một dãy mặt F = (f1, f2, · · · , fm+1) và dãy cạnh chung E = (e1, e2, · · · , em) khi thực hiện phép lật phẳng các mặt f1, f2, . . . , fm lên mặt phẳng chứa mặt phẳng fm+1 thì độ lớn của các góc trong một mặt tam giác fi và khoảng cách hai điểm p và q (với p, q ∈ fi, 1 ≤ i ≤ m+ 1) được bảo toàn. Ví dụ 2.1.1. Xét dãy mặt tam giác F = {4v0v1v2,4v1v2v3,4v1v3v4} và dãy cạnh E = {[v1, v2], [v1, v3]} như hình 2.2, các đỉnh v0(0, 0, 3), v1(0, 0, 0), v2(0,−3, 0), v3(3, 0, 0), v4(0, 0,−3). Thực hiện lật mặt phẳng mặt 4v0v1v2 và4v1v2v3 lên mặt phẳng chứa4v1v3v4 lần lượt theo dãy cạnh {[v1, v2], [v1, v3]}. 21 Hình 2.2 Minh hoạ dãy mặt tam giác {4v0v1v2 ,4v1v2v3 ,4v1v3v4}. Ta thực hiện theo đúng quy trình phép lật phẳng dãy mặt tam giác: ˆ Bước 1: Ta chọn F := {4v0v1v2}, quay F quanh cạnh [v1, v2] tới khi mặt 4v0v1v2 và mặt 4v1v2v3 cùng nằm trên một mặt phẳng và hai mặt phẳng này nằm khác phía so với cạnh v1v2. Khi đó, F := F ∪ {[v1, v2],4v1v2v3}. Nhận thấy rằng hai mặt4v0v1v2,4v1v2v3 tạo với nhau một góc ψ = 90o, khi thực hiện quay mặt chứa F lên mặt phẳng chứa 4v1v2v3 bằng ma trận quay [14] ta có thể tính được toạ độ của I[v1,v2](x ′, y′, z′) - là ảnh của của v0 sau khi lật ứng với cạnh [v1, v2], x ′, y′, z′ lần lượt là toạ độ của I[v1,v2] theo các trục Ox, Oy, Oz. Ta có x ′ y′ z′ 1  =  cosφ 0 sinφ 00 1 0 0− sinφ 0 cosφ 1 0 0 0 1  003 1  . 22 Hình 2.3 Minh hoạ phép lật mặt phẳng 4v0v1v2 lên mặt phẳng chứa 4v1v2v3 qua cạnh [v1, v2]. Mặt khác khi lật chúng ta cần mặt chứa 4v3v0v1 nằm ở mặt còn lại của cạnh v1v2 nên φ = −(180o − ψ).x ′ y′ z′ 1  = 0 0 −1 00 1 0 01 0 0 0 0 0 0 1  003 1  . Vậy toạ độ của I[v1v2] là (−3, 0, 0). ˆ Bước 2: Với F := F ∪ {[v1, v2],4v1v2v3}, quay F quanh cạnh [v2, v3] tới khi F và mặt 4v2v3v4 cùng nằm trên một mặt phẳng, F và mặt 4v2v3v4 nằm ở hai bên của cạnh [v2, v3]. Khi đó, F := F ∪ {[v2, v3],4v2v3v4}. Nhận thấy rằng F và 4v2v3v4 tạo với nhau một góc ψ = 90o, khi thực hiện quay F lên mặt phẳng chứa 4v1v2v3 ta có thể tính được toạ độ của I[v2,v3](x ′′, y′′, z′′) - là ảnh của của I[v1,v2] sau khi lật, x ′′, y′′, z′′ lần lượt là toạ độ của I[v2,v3] theo các trục Ox, Oy, Oz. 23 Hình 2.4 Minh hoạ dãy mặt tam giác {4v0v1v2 ,4v1v2v3 ,4v1v3v4}. Ta có x ′′ y′′ z′′ 1  = 1 0 0 00 cosφ − sinφ 00 sinφ cosφ 0 0 0 0 1  −300 1  . Ở đây, φ = 90o. x ′′ y′′ z′′ 1  = 1 0 0 00 0 −1 00 1 0 0 0 0 0 1  −300 1  . Vậy toạ độ của I[v2,v3] là (−3, 0, 0). 2.2 THUẬT TOÁN DÙNG NGUỒN SÁNG VÀ BÓNG Thuật toán dùng nguồn sáng và bóng là một thuật toán xác định đường đi ngắn nhất từ một điểm nguồn tới các đỉnh còn lại trên bề mặt của khối đa diện. Thuật toán sử dụng kĩ thuật lật phẳng, lật tất cả các mặt f1, f2, . . . , fm lên mặt phẳng chứa mặt fm+1 lần lượt theo các cạnh chung ei. Kí hiệu fi là ảnh của fi với 1 ≤ i ≤ m, Iei là ảnh của của điểm nguồn s lên cạnh ei với 1 ≤ i ≤ m. 24 Định nghĩa 2.2.1. [10] Hình chiếu của Iei lên cạnh ei là một đoạn thẳng nằm trên cạnh ei và được kí hiệu là Proj Iei ei sao cho đường ngắn nhất từ điểm nguồn s tới điểm t với t ∈ ProjIeiei đi qua dãy các cạnh e1, e2, . . . , ei−1 được lật thành một đoạn thẳng (hay chính là đường trắc địa). Điều này có nghĩa là với bất kì t ∈ ProjIeiei có thể nối Iei và t với nhau bằng một đoạn thẳng chỉ đi qua dãy các cạnh e1, e1, . . . , ei−1 (xem Hình 2.5). Hình 2.5 Hình chiếu của Iei lên cạnh ei. Tính chất sau về đường đi ngắn nhất [10]: 1. Một đường ngắn nhất đi qua một mặt không quá một lần. 2. Hai đường ngắn nhất không thể cắt nhau ngoại trừ tại hai điểm: điểm nguồn và điểm tới. Định nghĩa 2.2.2. [10] Nguồn sáng ứng với cạnh ei là tập hợp tất cả các đường đi ngắn nhất từ ảnh điểm nguồn s là Iei tới t với t ∈ ProjIeiei . Định nghĩa 2.2.3. [10] Bóng của hình chiếu Proj Iei−1 ei−1 trên mặt fi là miền giới hạn bởi các đường đi ngắn nhất từ ảnh nguồn Iei tới cạnh ei và các hình chiếu của ảnh nguồn Iei lên các cạnh của mặt fi chứa nguồn sáng tương ứng với cạnh ei (xem Hình 2.6). 25 Hình 2.6 Bóng của hình chiếu Proj Iei−1 ei−1 trên mặt fi. Hình 2.7 Phân tích cạnh chung e về hai phía. Phân tích một cạnh chung thành hai cạnh được định hướng sao cho ảnh nguồn chỉ có thể nằm phía bên trái của cạnh định hướng (xem Hình 2.7). Mặt nằm khác phía với cạnh định hướng được gọi là mặt bóng của cạnh định hướng đó, từ đó ta thấy được một mặt có thể là mặt bóng của ba cạnh của nó hay một mặt có thể có ba cạnh định hướng. 26 Thuật toán sau đây xây dựng một cây được gọi là cây tuần tự, một nút trong cây tuần tự này sẽ là một bộ ba và được kí hiệu là n = (e, I, ProjIee ) với Ie là ảnh nguồn của e. Ta nói nút n nằm trên cạnh e, e là cạnh của n và bóng của n là bóng của ProjIee . Xuất phát từ một điểm nguồn s, tìm tất cả các đường đi ngắn nhất từ điểm nguồn s tới các đỉnh còn lại của khối đa diện P , chúng tôi đặt ra bài toán: Bài toán: Xét một khối đa diện P mà các mặt của khối đa diện đã được tam giác phân thành m mặt (xem Định nghĩa 1.1.2), 4vpq là một mặt của khối đa diện P . Tìm đường đi ngắn nhất từ một đỉnh nguồn s tới các đỉnh còn lại của khối đa diện đó. Algorithm 2 (Thuật toán Thơ ngây) 1: root:= s; For tất cả các cạnh e đối diện với điểm nguồn s do thêm nút (e, s, e) là con của gốc s: /*e là cạnh của mặt có điểm nguồn s*/ /*s là một đỉnh của một mặt tam giác thuộc khối đa diện.*/ 2: For i:= 1 to m do /*m là số các mặt của khối đa diện sau khi các mặt đã được tam giác phân .*/ For tất cả các lá (e, I, ProjIe ) tại mức ith do Begin lật I quanh cạnh e nhận được I: /* I cùng mặt phẳng với 4vpq,*/ /* mặt bóng của cạnh e.*/ For e′ := [v, p], [q, v] tính ProjIe′ ; If ProjIe′ khác rỗng then thêm (e′, I, ProjIe′) là con của (e, I, Proj I e ). End. Ví dụ 2.2.1. Xét một khối đa diện mà các mặt đã được tam giác phân thành 6 mặt (xem Hình 2.8) và các đỉnh s(0, 0, 3), v1(0, 0, 0), v2(3, 0, 0), v3(0, 3, 0), v4(1.5, 1.5,−3). Tìm đường đi ngắn nhất từ đỉnh nguồn S tới các đỉnh còn lại trên bề mặt của khối đa diện bằng cách sử dụng thuật toán 2. Trong ví dụ này ta có thể chỉ ra được đường đi ngắn nhất trên bề mặt khối đa diện từ đỉnh S lần lượt tới các đỉnh v1 bằng 3, đường đi ngắn nhất từ s tới v2, v3 đều bằng 4.24, đường đi ngắn nhất trên bề mặt khối đa diện từ s tới v4 bằng 6.18. 27 Hình 2.8 Minh hoạ khối đa diện trong không gian ba chiều trong Ví dụ 2.2. ˆ Bước 1: Ta gán: root:= s; Các cạnh: [v1, v2], [v1, v3], [v2, v3] là các cạnh đối diện với gốc s. Khi đó: ([v1, v2], s, [v1, v2]), ([v1, v3], s, [v1, v3]), ([v2, v3], s, [v2, v3]) là con của gốc s. ˆ Bước 2: Do khối đa diện này sau khi các mặt được tam giác phân sẽ có tất cả 6 mặt nên cây chúng tôi xây dựng sẽ có 6 mức. Mức 1: Đối với ([v1, v2], s, [v1, v2]), ([v1, v3], s, [v1, v3]), ([v2, v3], s, [v2, v3]) là lá ta thực hiện lật s lần lượt quanh các cạnh [v1, v2], [v1, v3], [v2, v3] lên mặt phẳng chứa các mặt 4v1v2v3, 4v3v4v6, 4v4v5v6, 4sv1v5 và ảnh của s tương ứng trên mỗi mặt phẳng lật là I[v1,v2], I[v1,v3], I[v2,v3]. – Đối với 4sv1v3 và 4v1v3v4 sau khi đồng phẳng, ta gán e′ := [v1, v4], [v3, v4] và thực hiện tính hình chiếu Proj I[v1,v4] [v1,v4] của ảnh nguồn I[v1,v4] lên cạnh [v1, v4] và Proj I[v3,v4] [v3,v4] của ảnh nguồn I[v3,v4] lên cạnh [v3, v4]. 28 Thêm ( [v1, v4], I[v1,v4], P roj I[v1,v4] [v1,v4] ) và ( [v3, v4], I[v3,v4], P roj I[v3,v4] [v3,v4] ) là con của ([v1, v3], s, [v1, v3]). Nguồn sáng từ điểm nguồn s tới đỉnh v4 được tính bằng 6.18 và cắt cạnh [v1, v3] tại điểm có toạ độ là (0, 0.74, 0) – Đối với 4sv1v2 và 4v1v2v4 sau khi đồng phẳng, ta gán e′ := [v1, v4], [v2, v4] và thực hiện tính hình chiếu Proj I[v1,v4] [v1,v4] của ảnh nguồn I[v1,v4] lên cạnh [v1, v4] và Proj I[v2,v4] [v2,v4] của ảnh nguồn I[v2,v4] lên cạnh [v2, v4]. Thêm ( [v1, v4], I[v1,v4], P roj I[v1,v4] [v1,v4] ) và ( [v2, v4], I[v2,v4], P roj I[v2,v4] [v2,v4] ) là con của ([v1, v2], S, [v1, v2]). Nguồn sáng từ điểm nguồn s tới đỉnh v4 được tính bằng 6.18 và cắt cạnh [v1, v2] tại điểm có toạ độ là (0.74, 0, 0) – Đối với 4sv2v3 và 4v2v3v4 sau khi đồng phẳng, ta gán e′ := [v2, v4], [v3, v4] và thực hiện tính hình chiếu Proj I[v2,v4] [v2,v4] của ảnh nguồn I[v2,v4] lên cạnh [v2, v4] và Proj I[v3,v4] [v3,v4] của ảnh nguồn I[v3,v4] lên cạnh [v3, v4]. Thêm ( [v2, v4], I[v2,v4], P roj I[v2,v4] [v2,v4] ) và ( [v3, v4], I[v3,v4], P roj I[v3,v4] [v3,v4] ) là con của ([v2, v3], S, [v2, v3]). Nguồn sáng từ điểm nguồn s tới đỉnh v4 được tính bằng 6.64 và cắt cạnh [v2, v3] tại điểm có toạ độ là (1.5, 1.5, 0) Mức 2: – Đối với lá ( [v1, v4], I[v1,v4], P roj I[v1,v4] [v1,v4] ) ở mức 1 ta lại tiếp tục thực hiện việc lật I[v1,v4] quanh cạnh [v1, v4] hoặc [v3, v4] để được ảnh nguồn mới tương ứng là I[v1,v4] và I[v3,v4]. Thêm ( [v1, v2], I[v1,v2], P roj I[v1,v2] [v1,v2] ) và ( [v3, v4], I[v3,v4], P roj I[v3,v4] [v3,v4] ) là con của ( [v1, v4], I[v1,v4], P roj I[v1,v4] [v1,v4] ) . Từ đây ta sẽ tính được đường đi ngắn nhất từ ảnh nguồn I[v1,v4] tới đỉnh v2 và bằng 6 và đi qua dãy cạnh [v1, v3], [v1, v2]. – Đối với lá ( [v3, v4], I[v3,v4], P roj I[v3,v4] [v3,v4] ) ta lại tiếp tục thực hiện việc lật I[v3,v4] quanh cạnh [v2, v3] hoặc [v2, v4] để được ảnh nguồn mới 29 tương ứng là I[v2,v3] và I[v2,v4]. Thêm ( [v2, v3], I[v2,v3], P roj I[v2,v3] [v2,v3] ) và ( [v2, v4], I[v2,v4], P roj I[v2,v4] [v2,v4] ) là con của ( [v1, v4], I[v1,v4], P roj I[v1,v4] [v1,v4] ) . Từ đây ta sẽ tính được đường đi ngắn nhất từ ảnh nguồn I[v1,v4] tới đỉnh v2 và bằng 6 và đi qua dãy cạnh [v1, v3], [v3, v4] – Đối với lá ( [v1, v4], I[v1,v4], P roj I[v1,v4] [v1,v4] ) ở mức 1 ta lại tiếp tục thực hiện việc lật I[v1,v4] quanh cạnh [v1, v3] hoặc [v3, v4] để được ảnh nguồn mới tương ứng là I[v1,v3] và I[v3,v4]. Thêm ( [v1, v3], I[v1,v3], P roj I[v1,v3] [v1,v3] ) và ( [v3, v4], I[v3,v4], P roj I[v3,v4] [v3,v4] ) là con của ( [v1, v4], I[v1,v4], P roj I[v1,v4] [v1,v4] ) . Từ đây ta sẽ tính được đường đi ngắn nhất từ ảnh nguồn I[v1,v4] tới đỉnh v3 và bằng 6 và đi qua dãy cạnh [v1, v2], [v1, v4]. – Đối với lá ( [v1, v4], I[v1,v4], P roj I[v1,v4] [v1,v4] ) ở mức 1 ta lại tiếp tục thực hiện việc lật I[v1,v4] quanh cạnh [v1, v3] hoặc [v3, v4] để được ảnh nguồn mới tương ứng là I[v1,v3] và I[v3,v4]. Thêm ( [v1, v3], I[v1,v3], P roj I[v1,v3] [v1,v3] ) và ( [v3, v4], I[v3,v4], P roj I[v3,v4] [v3,v4] ) là con của ( [v1, v4], I[v1,v4], P roj I[v1,v4] [v1,v4] ) . Từ đây ta sẽ tính được đường đi ngắn nhất từ ảnh nguồn I[v1,v4] tới đỉnh v3 và bằng 6 và đi qua dãy cạnh [v1, v2], [v1, v4]. – Đối với lá ( [v2, v4], I[v2,v4], P roj I[v2,v4] [v2,v4] ) ở mức 1 ta lại tiếp tục thực hiện việc lật I[v2,v4] quanh cạnh [v2, v1] hoặc [v4, v1] để được ảnh nguồn mới tương ứng là I[v2,v1] và I[v4,v1]. Thêm ( [v2, v1], I[v2,v1], P roj I[v2,v1] [v2,v1] ) và ( [v4, v1], I[v4,v1], P roj I[v4,v1] [v4,v1] ) là con của ( [v2, v4], I[v2,v4], P roj I[v2,v4] [v2,v4] ) . Từ đây ta sẽ tính được đường đi ngắn nhất từ ảnh nguồn I[v1,v4] tới đỉnh v3 và bằng 7.88 và đi qua dãy cạnh [v2, v3], [v2, v4]. – Đối với lá ( [v3, v4], I[v3,v4], P roj I[v3,v4] [v3,v4] ) ở mức 1 ta lại tiếp tục thực hiện việc lật I[v3,v4] quanh cạnh [v3, v1] hoặc [v4, v1] để được ảnh nguồn mới tương ứng là I[v3,v1] và I[v4,v1]. Thêm ( [v3, v1], I[v3,v1], P roj I[v3,v1] [v3,v1] ) và ( [v4, v1], I[v4,v1], P roj I[v4,v1] [v4,v1] ) 30 là con của ( [v2, v4], I[v2,v4], P roj I[v2,v4] [v2,v4] ) . Từ đây ta sẽ tính được đường đi ngắn nhất từ ảnh nguồn I[v1,v4] tới đỉnh v3 và bằng 7.88 và đi qua dãy cạnh [v2, v3], [v3, v4]. Tương tự thực hiện từng bước thêm lá và tính các hình chiếu của ảnh nguồn trên cạnh tương ứng ở các mức tiếp theo ta thu được kết quả là đường đi ngắn nhất từ đỉnh nguồn s tới các đỉnh còn lại trên bề mặt của khối đa diện. Hình 2.9 Đường đi ngắn nhất là các đường màu đỏ từ đỉnh nguồn s tới các đỉnh v1, v2, v3, v4. 31 Chương 3 TÌM ĐƯỜNG ĐI NGẮN NHẤT GIỮA HAI ĐIỂM TRONG MỘT DÃY MẶT TAM GIÁC TRONG KHÔNG GIAN BA CHIỀU Chương này trình bày lại một thuật toán hữu hiệu trong việc tìm đường đi ngắn nhất giữa hai điểm trong một dãy mặt tam giác trong không gian ba chiều bằng cách sử dụng “phễu” tương ứng với các cạnh chung của dãy mặt tam giác và lật phẳng mỗi “phễu” đó. Tác giả cũng chỉ ra rằng ảnh của “phễu” sau khi lật sẽ không đè lên nhau [5]. 3.1 ĐƯỜNG TRẮC ĐỊA THẲNG NHẤT VÀ CÁC PHỄU DỌC THEO DÃY MẶT TAM GIÁC TRONG KHÔNG GIAN BA CHIỀU Một đường nối hai điểm p và q trong một dãy mặt tam giác của F = {f1, f2, . . . , fm, fm+1} là một đường gấp khúc ∪mi=0[vi, vi+1] với v0 = p, vm+1 = q, mỗi đoạn thẳng [vi, vi+1] nằm trên một tam giác nào đó của F , đỉnh vi (với 1 ≤ i ≤ m) của đường nối giữa p và q thuộc một cạnh chung trong dãy mặt F . Định nghĩa 3.1.1. [5] Một đường ∪mi=0[vi, vi+1] trong một dãy các tam giác của F = {f1, f2, . . . , fm, fm+1} với v0 = u, vm+1 = v, đoạn thẳng [vi, vi+1] nằm trên một tam giác nào đó của F , mỗi đỉnh vi của đường này thuộc cạnh chung nào đó của F được gọi là đường trắc địa thẳng nhất từ u 32 tới v trong F nếu tổng độ lớn các góc của đường này tại các đỉnh vi bằng pi. Đường trắc địa thẳng nhất như thế được kí hiệu là CF(u, v). Hình 3.1 Đường trắc địa thẳng nhất màu đỏ trên bề mặt khối lập phương tại điểm v1, v3; v1, v3 là trung điểm của các cạnh chứa nó. Chúng ta cũng có thể gọi một đoạn thẳng trên một tam giác fi là một đường trắc địa thẳng nhất. Xét điểm u là một điểm thuộc F và e = [p, q] là một cạnh chung trong F , xét s là điểm chung xa nhất của đường ngắn nhất SP (u, q) nối hai điểm u và q trong F và đường ngắn nhất SP (u, p) nối hai điểm u và p trong F tương ứng với điểm u. Kí hiệu Fpq(s) là miền con của F được bao bởi SP (s, p) và SP (s, q) và [p, q]. Định nghĩa 3.1.2. [5] Miền Fpq(s) được gọi là phễu dọc theo F tương ứng với cạnh chung [p, q], s là chóp của phễu và SP (s, p) và SP (s, q) (để ngắn gọn chúng tôi kí hiệu là B1 và B2) là biên của phễu. Trong trường hợp đơn giản, chúng tôi sẽ kí hiệu phễu là F . Từ Định nghĩa 3.1.2 có thể thấy rằng một phễu có thể được xây dựng lên từ một dãy mặt tam giác. Giả sử rằng 4vpq là một tam giác thuộc F nằm khác phía với điểm u qua cạnh chung [p, q]. Tập hợp F̂ = F ∪4pqv được gọi là miền được xử lí của F và v được gọi là điểm tới trực tiếp của F . 33 Hình 3.2 Phễu được tạo bởi biên B1 = SP (s, p) và B2 = SP (s, q) và cạnh chung [p, q]; F̂ = F ∪4pqv là miền được xử lí. Lấy u, u′ ∈ F hoặc u, u′ ∈ F̂ , việc xây dựng F̂ cũng giống như việc hình thành dãy mặt tam giác, từ đó chúng ta có thể thay thế F bằng F̂ . Khi đó, đường trắc địa thẳng nhất trong phễu mới hình thành sẽ được kí hiệu là CF̂ (u, u′). Giả sử rằng không có phễu nào rỗng thì Fpq(s) với s /∈ [p, q], B1 ∩B2 = {s}, B1 ∩ [p, q] = {p}, B2 ∩ [p, q] = {q}, chúng ta có mệnh đề sau: Mệnh đề 3.1. [5] Cho một phễu F = Fpq(u) dọc theo dãy mặt tam giác F , z /∈ [p, q], với mỗi i ∈ {1, 2} tồn tại một đường trắc địa thẳng nhất được kí hiệu là Ti trong F̂ đi qua một đỉnh của Bi và gặp đoạn [p, q] tại một điểm duy nhất. Tiếp theo, luận văn sẽ trình bày lại định lý về các phễu mới sau khi lật không bị đè lên nhau, việc này sẽ làm giảm được các bước tính toán trong quá trình tìm đường đi ngắn nhất giữa hai điểm trên dãy mặt của một tam giác. Định lý 3.1.1. [5] Ảnh của phễu Fpq(u) thông qua phép lật dọc theo dãy các cạnh của phễu lên mặt phẳng chứa tam giác 4pqv không bị đè lên nhau, các ảnh của các biên của phễu lồi hướng ra ngoài của 4u¯pq. 34 Hình 3.3 z là điểm ảnh duy nhất tương ứng với miền đơn Rz = 4zw1w2 và z′ là điểm ảnh duy nhất tương ứng với miền đơn Rz′ = 4z′w′1w′2. Chứng minh. Đầu tiên, ta cần chứng minh điểm z và ảnh của nó z¯ là duy nhất tương ứng với miền phễu chứa điểm z. Ta lấy z ∈ F \ [p, q]. Từ Mệnh đề 3.1, chúng ta giả sử rằng: w1 = T ∩ [p, q];w2 = T ∩ [p, q]. Ta gọi: Ti := CF̂ (z, wi) với i = 1, 2. Vì T1(z) và T2(z) là các đường đi trắc địa thẳng nhất và dài nhất xuất phát từ điểm z nên T1(z) và T2(z) là duy nhất. Từ đó, ta có thể thấy rằng điểm z là điểm duy nhất tương ứng với miền đơn Rz được hình thành bởi các đường trắc địa thẳng nhất T1(z) và T2(z) và [p, q]. Chính vì thế, độ lớn của tất cả các góc của một đường sẽ được bảo toàn qua phép lật phẳng và ảnh của miền Rz tức là Rz là 4z¯w1w2, dẫn tới ảnh của điểm z là z¯ cũng là duy nhất tương ứng với tam giác Rz. Giả sử tồn tại hai điểm z, z′ ∈ F \ [p, q] sao cho Rz = Rz′ thì bằng cách đưa ra số tam giác trong phễu Fpq(u) mà T1(z) và T2(z) đi qua, chúng ta có thể chứng minh được rằng T1(z) = T1(z′) và T2(z) = T2(z′) hay điểm z ≡ z′. Ta suy ra được ảnh của phễu Fpq(u) thông qua phép lật dọc theo dãy các cạnh của phễu lên mặt phẳng chứa tam giác4pqv không bị đè lên nhau. Do độ lớn của tất cả các góc của hai biên B1 và B2 được bảo toàn qua phép lật nên ảnh của hai biên của phễu đều là các đường lồi hướng ra ngoài. 35 3.2 THUẬT TOÁN TÌM CHÍNH XÁC ĐƯỜNG ĐI NGẮN NHẤT GIỮA HAI ĐIỂM DỌC THEO DÃY MẶT TAM GIÁC Thuật toán tìm chính xác đường đi ngắn nhất giữa hai điểm dọc theo dãy mặt tam giác trong không gian ba chiều được giới thiệu trong [11]. Từ Định lý 3.1.1 thuật toán được trình bày bằng việc sử dụng ý tưởng phễu tương ứng với các cạnh chung dọc theo dãy mặt tam giác và lật phẳng từng phễu đó, ta gọi thuật toán đó là NFU. Ta xét F = Fpq(u) là một phễu trong F và B1 = SP (u, p), B2 = SP (u, q) là hai biên của phễu; v là điểm tới và F̂ là miền được xử lí của F . "Phễu" được trình bày như một hàng đợi kết thúc kép mà các đỉnh được sắp xếp theo thứ tự: F = (pr, pr−1. . . . , p1, u, q1, . . . , qs−1, qs), ở đó u = p0 = q0, q = qs, [p, q] là một cạnh chung của F , B1 đi qua các đỉnh p0, p1, . . . , pr và B2 đi qua các đỉnh q0, q1, . . . , qs của F . Phễu dọc theo F tương ứng với cạnh [v, q] (cạnh chung [p, v] cũng tương tự như thế) của F là một phễu mới được xây dựng từ Fpq(u) và điểm tới v. Giả sử rằng [v, q] là một cạnh chung của F . Quy trình lật phễu mới NFU (F, v, q, u, SP (u, v)) dưới đây để xây dựng một phễu mới tương ứng với cạnh chung [v, q] theo Định lí 3.1.1. Sau khi