Thử tìm kiếm một thuật toán thiết kế các mặt cong

Tạp chí Khoa học – Công nghệ Thủy sản số 01/2007 Trường Đại học Nha Trang 52 VẤN ĐỀ TRAO ĐỔI THỬ TÌM KIẾM MỘT THUẬT TOÁN THIẾT KẾ CÁC MẶT CONG PGS.TS Nguyễn Quang Minh Khoa Cơ khí - Trường ĐH Nha Trang Trong bài báo đặt vấn đề tìm kiếm một thuật toán dùng vào mục đích thiết kế các mặt cong có thể cần thiết trong ứng dụng công nghệ cao CNC. Các kết quả bước đầu nhận được trên cơ sở phát triển nghiên cứu ứng dụng về hàm hoá bề mặt lý thuyết vỏ tàu thuỷ của chính Tác giả. Các ý kiến thảo luận làm rõ triển vọng áp dụng của ý tưởng đặt ra. 1. TỔNG QUAN Bài toán thiết kế, thay vì xấp xỉ trong nghĩa trực tiếp một mặt cong đặt ra ở đây có ý nghĩa thực tế và cần thiết, thậm chí trong nhiều trường hợp cần đến như phương tiện quan trọng, chẳng hạn trong các lĩnh vực công nghệ cao CNC. Một mặt cong, một cách chung nhất, có thể xem như tập hợp các đường cong phẳng - tiết diện của chính mặt cong đó với các mặt phẳng (P) được lựa chọn phù hợp. Nếu vậy, một cách tự nhiên có thể nghĩ rằng thuật toán thiết kế mặt cong tốt nhất nên đưa từ mô hình toán không gian về mô hình biểu diễn toán học chính xác các đường cong phẳng. Đơn giản là vì một khi bài toán thiết kế một đường cong cho trên mặt phẳng (P) bất kỳ đã được giải quyết, toàn bộ mặt cong cho trước đương nhiên có thể nhận được bằng cách tịnh tiến hoặc quay hợp lý các mặt phẳng (P) đó. Theo cách tiếp cận trực tiếp như vậy, bài toán đặt ra về thuật toán thiết kế một mặt cong có thể giải quyết không mấy khó khăn, ứng dụng mô hình toán xấp xỉ quen thuộc, đó là mô hình bài toán điều kiện biên, cách giải quyết được thể hiện qua các bước gồm: - Chọn dạng hàm cơ sở - Áp dụng mọi điều kiện biên và xác lập số lượng thích hợp các phương trình căn cứ theo các điều kiện đó - Giải hệ phương trình điều kiện biên và biện luận các kết quả Để có thể đạt các kết quả xấp xỉ mong muốn cần có số các điểm thuộc đường cong giữ vai trò các điều kiện biên đủ lớn. Hàm cơ sở thông thường được chọn dưới dạng đa thức luỹ thừa bậc n viết tổng quát như dưới đây: ∑= = = nk k k k yax 0 (1) và dạng chi tiết hoá: n n n n YaYaYaYaYaYaaX +++++++= −− 1144332210 ... (2) Với X,Y- là các toạ độ của các điểm cho trong hệ toạ độ lựa chọn XOY, k = 0, 1, 2, 3, n-1, n. Dễ nhận xét rằng biểu thức (2) cùng lắm chỉ có thể dùng để tính toán gần đúng một hình cong mà ít hiệu quả trong các mục đích thiết kế đường cong đó. Phương pháp spline do Alberg. J. đề nghị nửa thế kỷ trước đây, được nghiên cứu áp dụng rộng rãi trên toàn thế giới nhằm khắc phục một phần nhược điểm của đa thức luỹ thừa (2) . Tuân theo nguyên tắc cơ bản đó là Tạp chí Khoa học – Công nghệ Thủy sản số 01/2007 Trường Đại học Nha Trang 53 đường cong hàm hoá được chia làm nhiều đoạn ngắn, mỗi đoạn có thể xấp xỉ theo các hàm đơn giản, phổ biến nhất thường chọn parabol bậc 3 viết tổng quát như dưới đây: (4) ∑= = −−= 3' 0' ' 1'',' )( k k k jjkjj yycx với j = (j'-1), j', (j'+1) J' = 1, 2, 3,, k-1 Nhờ những lợi thế cơ bản của nó trong lập trình, phương pháp spline đang được ứng dụng trong nhiều lĩnh vực khoa học công nghệ và đem lại những thành tựu quan trọng. Mặc dù vậy, phương pháp spline xấp xỉ toán học các đường cong phẳng cũng không thể được đánh giá như một công cụ hiệu quả nhất trong các mục đích thiết kế nghiêm túc. Trong bài báo này chúng tôi giới thiệu một số kết quả phát triển từ nghiên cứu biểu diễn toán học bề mặt tàu thuỷ, vốn cũng là một vật thể có những đặc điểm riêng, hy vọng có thể áp dụng như giải thuật lập trình thiết kế và chế tạo chính xác một mặt cong theo từng mục đích cụ thể. 2. MỘT SỐ KẾT QUẢ MỚI NGHIÊN CỨU XẤP XỈ CÁC ĐƯỜNG CONG PHẲNG Trên hình 1 minh hoạ mô hình toán lớp các đường cong phẳng 1a, 1b, 1c nằm trên mặt phẳng P trong quan hệ khác nhau đối với hệ toạ độ lựa chọn XOY. Tất cả các đường cong như vậy được cho bằng tập hợp các điểm rời rạc (Xi , Yi), i = 0, 1, 2, 3, 4, 5, , n-1, n. O Hình 1 Sơ đồ các đường cong phẳng - đối tượng xấp xỉ toán học Về phương pháp, yêu cầu thiết kế các đường cong khác với chỉ đơn giản vẽ lại một đường cong cho trước là ở chỗ đòi hỏi, không chỉ áp dụng các điều kiện biên trong nghĩa thông thường, mà quan trọng hơn phải khai thác và áp dụng các điều kiện biên một cách hợp lý nhất, đảm bảo không chỉ tính phù hợp đối với từng trường hợp cụ thể, mà phải tiện lợi áp dụng đối với mọi đường cong thuộc lớp đang xét - đối tượng của bài toán xấp xỉ. Yêu cầu nói trên chỉ có thể là hiện thực nhờ việc sử dụng được các đặc điểm hình học quan trọng nhất được gọi là các yếu tố điều khiển. Tạp chí Khoa học – Công nghệ Thủy sản số 01/2007 Trường Đại học Nha Trang 54 Có thể chứng tỏ rằng tồn tại 4 yếu tố có chức năng điều khiển như vậy, được xem như tập hợp các điều kiện cần để thông qua đó thiết kế chính xác các đường cong, căn cứ vào các yêu cầu thiết kế khác nhau. Các yếu tố như vậy gồm có: • Toạ độ điểm đầu (X0, Y0) • Toạ độ điểm cuối (Xt, Yt) • Diện tích hình cong Dt được tạo bởi đường cong cho trước với trục Toạ độ X = 0, X = 0, và các đường thẳng Y = Yt, và X = Xt • Momen tĩnh Mox của diện tích nói trên ứng với trục hoành Thật vậy, giả sử kết quả xấp xỉ toán học chính xác một đường cong cho tương ứng như trên hình 1 tìm được dưới dạng một hàm liên tục: )(YfX = Khi đó các biểu thức viết theo các điều kiện biên như mô tả ở trên có thể viết dễ dàng như dưới đây: (5.1) 00 )( XYf = (5.2) tt YXf =)( (5.3) DtdyYfXdy yt y yt y == ∫∫ 00 )( và : (5.4) ox yt y yt y MYdyYfXYdy == ∫∫ 00 )( Hiển nhiên các điều kiện (5.1) và (5.2) phải được đảm bảo đầu tiên. Điều kiện (5.3) đảm bảo để các đường cong hàm hoá được, tương ứng với các điểm đầu và cuối đã cho, tạo thành với trục tọa độ các hình cong có cùng một diện tích Dt. Điều kiện cuối cùng (5.4) chứa một ưu thế thiết kế đặc biệt rất cần được khai thác đó là cho phép chọn ra từ tập hợp các đường cong, nhận được trên cơ sở 3 điều kiện biên đầu tiên, chính xác đường cong phải tìm như một nghiệm duy nhất của bài toán thiết kế. Trên cơ sở các biểu thức (3), (5.1) ÷ (5.4) có thể dễ dàng thiết lập hệ 4 phương trình mô tả 4 điều kiện biên giữ vai trò như các yếu tố điều khiển, nghiệm của hệ các phương trình đó cho các hệ số ai thuộc biểu thức luỹ thừa bậc 3: (6) 33 2 210 YaYaYaXX +++= được xác định theo các biểu thức sau đây: )32( 7 1 1 DtXh a t += (7) )158( 7 4 22 tXMxDth a +−×−= (8) và )126( 7 20 33 tXMxDth a +−= (9) trong đó : 02 2 00 ; 2/ ; yyh h hyMxMx h hyDDt t −=−=−= (10) Biểu thức (6) cùng với các biểu thức (7) ÷ (10) tỏ ra rất đơn giản, có thể áp dụng để thiết kế các đường cong với các điều kiện được cho theo (4). Tuy nhiên những gì nói ở trên mới chỉ bao gồm các điều kiện cần tối thiểu. Để cho bổ sung các điều kiện “đủ”, đòi hỏi phải xác định các đặc điểm của hình cong giới hạn bởi đường cong - đối tượng hàm hoá, cho phép phân biệt nó với mọi đương cong cùng lớp còn lại, chẳng hạn đó là tính liên tục, tính biến thiên, góc tạo bởi các tiếp tuyến với đường cong vẽ tại nhiều điểm khác nhau, đặc biệt tại hai điểm đầu và cuối. Sau cùng và có lẽ cũng là quan trọng nhất đó là đường cong có bao nhiêu điểm uốn trong miền xác định [y0,yt]. Chẳng hạn có thể nhận xét ngay rằng biểu thức (6) chỉ làm việc khi đường cong đối tượng hàm hoá cho trước chỉ có 1 điểm uốn, vì đạo Tạp chí Khoa học – Công nghệ Thủy sản số 01/2007 Trường Đại học Nha Trang 55 hàm bậc 2 chỉ nhận giá trị bằng 0 tại một điểm duy nhất tại 32 3/ aay −=∗ Trong một số nghiên cứu ứng dụng có thể rất có lợi chọn hàm cơ sở dưới dạng hàm (1) mở rộng, trong đó thay vì các giá trị nguyên các luỹ thừa có thể nhận các số thực dương bất kỳ, viết dưới dạng tổng quát: nkmyax nk k mk k ,...,4,3,2,1;0; 0 =>= ∑= = (11) hoặc chi tiết: (12) kk k k mmmm YaYaYaYaYaYaXX +++++++= −− 1144332210 ... Áp dụng chính các điều kiện biên đã xét ở trên theo (4), sau đó tiếp tục thực hiện các bước tính toán như đã trình bày, có thể dẫn đến đa thức luỹ thừa bậc 2m với m thực dương như dưới đây: mm YaYaXX 2210 ++= (13) Thừa số luỹ thừa m và các hệ số có mặt trong biểu thức được ai có thể xác định theo các biểu thức )(2 )4)((2)2(25,2)2(5,1 2 BA XtBABABABA m − +−−−−±−−= (14) [ ] m t mh XXAmma −+++= 01 )12()1( (15) m m t h haXXa 2 10 2 −−= (16) trong đó, ngoài các ký hiệu đã được chú thích ở trên các ký hiệu mới được dùng gồm: h hXA tt 0−= ω (17) và 2 2 0 2/ h hXm B oytt −= ω (18) Biểu thức (13) cùng với các biểu thức (14)÷(18) có thể sử dụng tiện lợi và hiệu quả hơn rất nhiều so với biểu thức (6), đặc biệt khi cần thiết giải ngược phương trình, tính Y theo X. Trong các trường hợp như vậy chỉ cần qua một vài phép biến đổi dẫn về dạng phương trình bậc 2 sử dụng các nghiệm giải sẵn quen thuộc. Vì cố gắng tìm kiếm lời giải trên cơ sở các nghiệm của phương trình bậc 2, hiển nhiên rằng biểu thức xấp xỉ (13) chỉ làm việc khi m có nghiệm thực, điều đó có nghĩa biểu thức dưới dấu căn, viết ở vế phải của biểu thức (14) không âm, thực chất được hiểu như bộ phận đặc biệt trong số những gì được gọi là điều kiện đủ để xấp xỉ toán học các đường cong thuộc lớp đang xét, được viết như sau: Tạp chí Khoa học – Công nghệ Thủy sản số 01/2007 Trường Đại học Nha Trang 56 (19) 0)4)((2)2(25,2 2 >=+−−−− tXBABABA Biểu thức (19) cho phép nhận đựơc các điều kiện đủ để xấp xỉ toán các đường cong như minh hoạ trên hình 1 bằng biểu thức dưới dạng đa thức luỹ thừa bậc 2m bao gồm: nếu: B > 2xt/ 3 (20) hoặc nếu: 5,0 64)2( ; 3 2 BxxBAXB ttt −−−−<< (20') và: 5,0 64)2( ; 3 2 BxxBAXB ttt −+−−>< (20'') Giả sử bây giờ nâng bậc đa thức luỹ thừa (13) lên bậc 3m bằng cách áp dụng thêm một điều kiện biên, chẳng hạn đó là hệ số góc tạo bởi tiếp tuyến với đường cong hàm hoá tại điểm cuối Y = Yt , Khi đó biểu thức xấp xỉ đối tượng tìm kiếm sẽ viết được dưới dạng: (21) mmm yayayaXX 33 2 210 +++= Trong đó thừa số luỹ thừa m có thể xác định như nghiệm của phương trình bậc 3 đủ: 0 )( )338( 1667,0 )( )4( )( )2(8333,1 0023 =− −+−−+− +−−+− −+ BA khxXBAm BA XXBAm BA BAm tt (22) Các hệ số ai có mặt trong biểu thức (21) được xác định như sau: [ ] [ ] m tt m tt hm XXBmmmXX m khmm hm XXAmmmXX m khmm a 32 00 32 00 3 2 )2()23)(22())(23( 2 )1()13)(12())(13( −+++++−++ = −+++++−++ = (23) [ ] [ ] m m t m m m t m m t hmm hammXXAmmm hmm hamm hmm XXBmmm h haXX m kh a 2 3 30 3 3 3 2 0 2 3 30 2 )13( )12(2)1()13)(12( )23( )22(2 )23( )2()23)(22(2 + ++−++++−=+ + ++ −++++−= −−+ = (24) và: m mm t h hahaXXa 3 3 2 20 1 −−−= (25) Hệ số góc tạo bởi tiếp tuyến tại điểm cuối (Xt,Yt) viết trong các biểu thức (22)÷(25) cũng mang ý nghĩa của các điều kiện “đủ” viết trong các biểu thức (20), (20') và (20'') áp dụng cho biểu thức (13). Tạp chí Khoa học – Công nghệ Thủy sản số 01/2007 Trường Đại học Nha Trang 57 3. THAY LỜI KẾT LUẬN - Các kết quả đạt được qua phân tích lý thuyết, đặc biệt qua chạy thử đoạn chương trình viết trên ngôn ngữ V.B cho phép khẳng định rằng khi các điều kiện biên được đảm bảo chính xác, các biểu thức xấp xỉ (13) và (21) cùng cho một kết quả. - Điều nhận xét trên đây khẳng định rằng hàm cơ sở mở rộng viết dưới dạng đa thức luỹ thừa bậc số thực bất kỳ (13) cùng với ý tưởng khai thác hợp lý các điều kiện biên, phân biệt gồm các điều kiện cần và các điều kiện “đủ” là có cơ sở lý thuyết đúng, có thể áp dụng rộng rãi và cho hiệu quả cao. - Các điều kiện được gọi là đủ (20), (20') và (20'') một mặt khẳng định tính không thể xấp xỉ toán học theo biểu thức (13) nếu đường cong được cho không thoả mãn chúng, mặt khác chính các điều kiện như vậy lại có thể đựơc lợi dụng, như cộng cụ chính, để đưa đường cong từ chỗ không đến có thể xấp xỉ được nhờ một vài phép biến đổi cần thiết. Chính vì vậy biểu thức (13) cuối cùng tỏ ra tiện lợi, vạn năng, đồng thời hiệu quả hơn trong xấp xỉ các đường cong so với biểu thức (21). Các đường cong cho trên hình 1 là sản phẩm trực tiếp của một đoạn chương trình máy tính viết trên cơ sở thuật toán đang trình bày có thể coi là một minh chứng sinh động. - Trong nhiều trường hợp các điều kiện (5) có thể và nên được coi như chìa khóa thiết kế, hoặc gọi cách khác như các yếu tố điều khiển đề cập ở trên, cho phép thiết kế trên cơ sở biểu thức (6) khi đường cong thiết kế có trong miền xác định một điểm uốn duy nhất, hoặc trên cơ sở các biểu thức (13), (21)-khi đường cong thiết kế có từ hai điểm uốn trở lên. Rất đáng chú ý rằng những kết quả thông báo trên đây đều nhận được từ các phép biến đổi toán học chính xác và trong điều kiện ứng dụng tin học sâu rộng, hiệu quả như hiện nay đảm bảo chính xác các tham số điều khiển đối với đường cong cho trước là hiện thực. Những nhận xét như vậy khiến ý nghĩa của phép xấp xỉ các đường cong, trên thực tế, có thể được thay thế bằng ý nghĩa của phép hàm hoá - mô tả toán học chính xác các đường cong đó. Tất cả những gì đã trình bày có thể đánh giá như cơ sở lý thuyết và thực tiễn vững chắc khẳng định triển vọng cuả một thuật toán lập trình thiết kế chính xác lớp các mặt cong kỹ thuật được đề cập trong bài viết. TÀI LIỆU THAM KHẢO 1. Phan Văn Hạp – Lê Đình Thịnh, Phương pháp tính và các thuật toán, Nhà xuất bản Giáo dục. 2. Nguyễn Quang Minh, Kết quả nghiên cứu hàm hoá bề mặt lý thuyết vỏ tàu thuỷ, Tuyển tập các công trình khoa học công nghệ, Trường Đại học Nha Trang, 1999 3. E.W. Cheney, Introduction to appoximation theory, University of Texas, 1966 4. Robert Sedgewick, Algorithms, Princeton University (USA), 2nd Edition. Addison-Wesley Publishing Co. Người dịch: Trần Đan Thư, Vũ Mạnh Tưởng, Dương Vũ Diệu Trà, Nguyễn Tiến Huy, NXB Khoa học và Kỹ thuật, 1994. 5. Zeldôvich Ya. B., Yaglom I.M., " Higher Math for beginner" Mir Publisher Moscow, 1987. ABSTRACT In the paper will be introduced the problem of researching an algorythm for designing the curve surfaces, that may be needed somewhere in the field of CNC application. The beginning results that will be represented are based on the reseaches of the ship theorical surfaces approximation, acheaved by the Author. The discussions clarify the aplyed abilities of the rised idea.