Đề tài Nghiên cứu về hình học fractal. viết chương trình cài đặt một số đường và mặt fractal

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI TRƯỜNG ĐẠI HỌC THUỶ SẢN NHA TRANG KHOA CÔNG NGHỆ THÔNG TIN LUẬN ÁN TỐT NGHIỆP ĐẠI HỌC Đề Tài: NGHIÊN CỨU VỀ HÌNH HỌC FRACTAL. VIẾT CHƯƠNG TRÌNH CÀI ĐẶT MỘT SỐ ĐƯỜNG VÀ MẶT FRACTAL. GV hướng dẫn: Tiến Sĩ. Huỳnh Quyết Thắng SV thực hiện: Nguyễn Ngọc Hùng Cường MSSV: 98S1013 NHIỆM VỤ ĐỀ TÀI LÝ DO CHỌN ĐỀ TÀI Có thể nói cùng với lý thuyết topo, hình học phân hình cung cấp cho nhà khoa học một một công cụ khảo sát tự nhiên vô cùng mạnh mẽ. Ngoài ra nó còn được áp dụng vào việc nghiên cứu lý thuyết từ tính, lý thuyết các phức chất trong hoá học, lý thuyết tái định chuẩn. Đồng thời nó còn có rất nhiều ứng dụng trong lĩnh vực giải trí, đồ hoạ và xử lý ảnh. NỘI DUNG NGHIÊN CỨU CỦA ĐỀ TÀI 1. Tìm hiểu tổng quan về lịch sử ra đời và các kết quả nghiên cứu của hình học phân hình. 2. Tìm hiểu các kỹ thuật hình học phân hình thông qua sự khảo sát các cấu trúc Fractal cơ sở và thuật toán chi tiết để tạo nên các cấu trúc này. 3. Lựa chọn một ngôn ngữ lập trình thích hợp để cài đặt cấu trúc Fractal vừa tìm hiểu. Nội Dung Trình Bày Phần I: Giới thiệu sơ lược hình học phân hình. Phần II: Một số kỹ thuật cài đặt hình học phân hình. Phần III: Một số kết quả cài đặt và hướng phát triển đề tài. PHẦN I I.1 Sự ra đời của lý thuyết hình học phân hình GIỚI THIỆU SƠ LƯỢC HÌNH HỌC PHÂN HÌNH I.2 Sự phát triển của lý thuyết hình học phân hình I.3 Các ứng dụng tổng quát của hình học phân hình I.1. Sự Ra Đời Của Lý Thuyết Hình Học Phân Hình  Tính hỗn độn của các quá trình phát triển có qui luật trong tự nhiên.  Sự mở rộng khái niệm số chiều và độ đo trong lý thuyết hình học Euclide cổ điển I.2 Sự Phát Triển Của Lý Thuyết Hình Học Phân Hình  Ứng dụng vấn đề tạo ảnh trên máy tính I.3. Các Ứng Dụng Tổng Quát Của Hình Học Phân Hình  Ứng dụng trong công nghệ nén ảnh  Ứng dụng trong khoa học cơ bản Một Số Kỹ Thuật Cài Đặt Hình Học Phân Hình II.1. Họ Đường Von Kock II.2. Họ Đường Peano II.3. Đường Sierpinski II.4. Cây Fractal II.5. Phong Cảnh Fractal II.6. Hệ Thống Hàm Lặp II.7. Tập Mandelbrot II.8. Tập Julia II.9. Đường Cong Phoenix PHẦN II PHẦN II II.1. Họ Đường Von Kock II.1.1. Đường Hoa Tuyết Von Kock II.1.2. Đường Gosper II.1.3. Đường Von Kock Bậc Hai 3 Đoạn II.1.4. Đường Von Kock Bậc Hai 8 Đoạn II.1.5. Đường Von Kock Bậc Hai 18 Đoạn II.1.6. Đường Von Kock Bậc Hai 32 Đoạn II.1.7. Đường Von Kock Bậc Hai 50 Đoạn II.1.8. Generator Phức Tạp II.1. Họ Đường Von Kock Được phát sinh bằng cách sử dụng kỹ thuật đệ qui initiator/generator với kết quả là các hình tự đồng dạng hoàn toàn. Số chiều fractal được tính theo công thức: Trong đó: N là số đoạn thẳng. R là chiều dài mỗi đoạn. II.1.1. Đường Hoa Tuyết Von Kock Mỗi đoạn thẳng được thay bằng generator như sau: Số chiều fractal là: Các hình minh họa của đường Mức 2 Mức 3 II.1.2. Đường Gosper Mỗi đoạn thẳng được thay bằng generator như sau: Số chiều fractal là: Các hình minh họa của đường Mức 1 Mức 2 II.1.3. Đường Von Kock Bậc Hai 3 Đoạn Mỗi đoạn thẳng được thay bằng generator như sau: Số chiều fractal là: Các hình minh họa của đường Mức 3 Mức 5 II.1.8. Generator Phức Tạp Mỗi đoạn thẳng được thay bằng generator như sau: Số chiều fractal là: Ta có: Các hình minh họa của đường Mức1 Mức 2 Vậy II.2. Họ Đường Peano II.2.1 Đường Peano Nguyên Thủy II.2.2 Đường Peano Cải Tiến II.2.3 Tam Giác Cesaro II.2.4 Tam Giác Cesaro Cải Tiến II.2.5 Một Dạng Khác Của Đường Cesaro II.2.6 Tam Giác Polya II.2.7 Đường Peano Gosper II.2.8 Đường Hoa Tuyết Peano 7 Đoạn II.2.9 Đường Hoa Tuyết Peano 13 Đoạn II.1. Họ Đường Peano Được phát sinh bằng cách sử dụng kỹ thuật đệ qui initiator/generator với kết qủa là các hình tự đồng dạng hoàn toàn. Các đường này có số chiều bằng 2, nên phải lấp đầy hoàn toàn mặt phẳng. II.2.1. Đường Peano Nguyên Thủy Mỗi đoạn thẳng được thay bằng generator như sau: Số chiều fractal là: Các hình minh họa của đường Mức 1 Mức 3 II.2.3. Tam Giác Cesaro Mỗi đoạn thẳng được thay bằng generator như sau: Số chiều fractal là: Generator chứa 2 cạnh của một tam giác cân. Do đó: Các hình minh họa của đường Mức 1 Mức 3 II.2.4. Tam Giác Cesaro cải tiến Generaor được thực hiện bằng cách thay thế góc từ 90 sang 85 độ như sau. Số chiều fractalø: gần giống như đường Cesaro nguyên thuỷ nhưng không hoàn toàn là 2, nhưng khi số lần đệ quy tiến ra vô cực thì số chiều fractal tiến về 2. Hình minh hoạ của đường Mức thứ 4 của tam giác Cesaro cải tiến. II.2.5. Một dạng khác của đường Cesaro Giả sử chúng ta bắt đầu với đường generator và hai mức đầu tiên như ở đường Cesaro, nhưng sử dụng sự sắp xếp khác đi khi đặt generator về phía trái và bên phải của đoạn thẳng gốc khi chúng ta ở mức cao hơn. Kết quả là nhiều đường khác nhau có thể được sinh ra từ cách sắp xếp này. Hình sau cho chúng ta các mức khác nhau của đường này. II.2.6. Tam giác Polya Giống như đường Cesaro, vị trí của generator đầu tiên thay đổi từ phải sang trái và được bắt đầu ở mức đầu tiên. Đối với đường này, vị trí của generator cũng thay đổi đường so với mỗi đoạn thẳng tương đương với các mức khác nhau. Hình sau cho ta thấy 2 mức đầu tiên và mức 4 của hình này. Mức 4 của tam giác Polya Mức 1 Mức 2 II.2.7. Đường Peano-Gosper Generator của đường này là một lưới gồm các tam giác đều liên kết với nó ( initiator là một đoạn thẳng nằm ngang) như sau. Vì generator có số đoạn thẳng N = 7 nên số chiều fractal là. Đường này có tính chất tự lấp đầy phần bên trong của đường Gosper. Hình sau cho ta thấy mức thứ 2 của đường này. II.2.8. Đường Hoa Tuyết Peano 7 Đoạn Mỗi đoạn thẳng được thay bằng generator như sau: Số chiều fractal là: Các hình minh họa của đường Mức 1 Mức 2 2 1 3 3 3 1 6 = Þ = ÷ ÷ ø ư ç ç è ỉ + ÷ ø ư ç è ỉ * D D D II.3. Đường Sierpinski Mỗi đoạn thẳng được thay bằng generator như sau: Các hình minh họa của đường Mức 1 Mức 2 Để phát sinh ra đường này người ta dùng các kỹ thuật giống như họ đường Von Kock và Peano. II.4. Cây Fractal Bắt đầu với một thân cây tại đầu mút của nó, tách thân cây thành hai hướng và vẽ hai nhánh. Chúng ta lặp lại qúa trình này tại đầu mút của mỗi nhánh. Kết qủa chúng ta sẽ được một cây. Hình minh họa cây fractal: II.5. Phong Cảnh Fractal Chúng ta bắt đầu bằng một tam giác và tiến hành thay thế trung điểm ứng với mỗi cạnh của tam giác này bằng một điểm trên đường trung trực của cạnh tương ứng. Khoảng cách giữa trung điểm cũ và điểm mới trong mỗi lần thay thế được xác định bởi việc nhân 1 hệ số ngẫu nhiên Gauss với độ dài đoạn thẳng. Kế tiếp chúng ta nối mỗi điểm vừa được tạo ra với hai đỉnh gần nhất của tam giác. Sau đó, từng cặp điểm mới tạo thành sẽ được nối lại với nhau. Cuối cùng chúng ta bỏ đi các cạnh của tam giác ban đầu. Hình minh họa thay thế trung điểm: Hình minh họa phong cảnh fractal: II.6. Hệ Thống Hàm Lặp (IFS) Một IFS là tập hợp các phép biến đổi affine co tức là: IFSIR2 ; wn : n=1,2,…,N với wn là phép biến đổi affine. Phép biến đổi affine có dạng: với a,b,c,d,e,f là các hệ số thực. Tương tự ,phép biến đổi affine trong không gian ba chiều có dạng: Hình minh họa áp dụng IFS: Lá dương xỉ 2 chiều Lá dương xỉ 3 chiều II.7. Tập Mandelbrot Sử dụng công thức toán học: Ký hiệu zn =( xn , yn), c=(p,q) , trong đó : xn = Re(zn), p = Re(c), yn =Im(zn), q = Im(c), n >= 0 Thì zn+1 = zn2 +c được viết lại như sau: xn+1 = xn2 - yn2 + p yn+1 = 2xnyn + q Hình minh họa tập Mandelbrot: II.8. Tập Julia Sử dụng công thức toán học: Ký hiệu zn =( xn , yn), c=(p,q) , trong đó : xn = Re(zn), p = Re(c), yn =Im(zn), q = Im(c), n >= 0 Thì zn+1 = zn2 +c được viết lại như sau: xn+1 = xn2 - yn2 + p yn+1 = 2xnyn + q Hướng khảo sát bằng cách cho c cố định và xem xét dãy (zn) ứng với mỗi giá trị khác của (zo ). Hình minh họa tập Julia: II.9. Đường Cong Phoenix Phương trình đường cong được xác định bởi: zn+1 = zn2 + p +qzn-1 với zi  C i  N. p = (p,0)  C. q = (q,0)  C. Phương trình được khai triển thành các phần thực và ảo của zn có dạng : xn+1 = xn2 - yn2 + p + qxn-1 yn+1 = 2xnyn + qyn-1 với : xn+1 = Re(zn+1) ; yn+1 = Im(zn+1 ) . Hình minh họa đường Phoenix: I. THÀNH QUẢ ĐẠT ĐƯỢC 1. CÁC ĐƯỜNG THUỘC HỌ ĐƯỜNG VON KOCK NHƯ: 1.1 Đường hoa tuyết Von Kock 1.2 Đường Gosper 1.3 Đường Von Kock bậc hai 3 đoạn 1.4 Đường Von Kock bậc hai 8 đoạn 1.5 Đường Von Kock bậc hai 18 đoạn 1.6 Đường Von Kock bậc hai 32 đoạn 1.7 Đường Von Kock bậc hai 50 đoạn 1.8 Đường Generator phức tạp PHẦN III PHẦN III 2.1 Đường Peano nguyên thủy 2.2 Đường Peano cải tiến 2.3 Tam giác Cesaro 2.4 Tam giác Cesaro cải tiến 2.5 Một dạng khác của đường Cesaro 2.6 Tam giác Polya 2.7 Đường Peano Gosper 2.8 Đường hoa tuyết Peano 7 đoạn 2.9 Đường hoa tuyết Peano 13 đoạn 2. CÁC ĐƯỜNG THUỘC HỌ ĐƯỜNG PEANO NHƯ: PHẦN III I. THÀNH QUẢ ĐẠT ĐƯỢC (TT) PHẦN III I. THÀNH QUẢ ĐẠT ĐƯỢC (TT) 3. ĐƯỜNG SIERPINSKI 4. CÂY FRACTAL 5. PHONG CẢNH FRACTAL 6. CÂY DƯƠNG XỈ 2 CHIỀU VÀ CÂY DƯƠNG XỈ 3 CHIỀU 7. MẶT MANDELBROT 8. MẶT JULIA 9. ĐƯỜNG CONG PHOENIX PHẦN III II. HẠN CHẾ CỦA ĐỀ TÀI 1. Chưa tìm hiểu được tất cả các cấu trúc Fractal cơ sở. 2. Chưa cài đặt được một số hiệu ứng chính như tạo các đám mây, lửa … 3. Tạo các dãy núi. 4. Một số đường chưa tìm hiểu và cài đặt kịp như đường Hilbert, đường tròn Apolo, đường cong Dragon … III. HƯỚNG PHÁT TRIỂN ĐỀ TÀI 1. Tạo đường Hilbert 2. Tạo đường tròn Apollo 3. Tạo họ đường cong Dragon 4. Tạo các hiệu ứng như: lửa, mây… 5. Tạo các dãy núi ……. PHẦN III