Đồ án Tìm hiểu phương pháp sinh ảnh Fractal bằng hệ hàm lặp (IFS) và hệ thống L-SYSTEM

97 trang huongle 2840

Download

Bạn đang xem 20 trang mẫu của tài liệu "Đồ án Tìm hiểu phương pháp sinh ảnh Fractal bằng hệ hàm lặp (IFS) và hệ thống L-SYSTEM", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

do_an_tim_hieu_phuong_phap_sinh_anh_fractal_bang_he_ham_lap.pdf

Nội dung text: Đồ án Tìm hiểu phương pháp sinh ảnh Fractal bằng hệ hàm lặp (IFS) và hệ thống L-SYSTEM

Bé gi¸o dôc vµ ®µo t¹o Tr•êng ®¹i häc d©n lËp h¶i phßng o0o T×m hiÓu ph•¬ng ph¸p sinh ¶nh Fractal B»NG HÖ HµM LÆP (IFS) Vµ HÖ ThèNG L-SYSTEM ®å ¸n tèt nghiÖp ®¹i häc hÖ chÝnh quy Ngµnh: C«ng NghÖ Th«ng Tin Sinh viªn thùc hiÖn : NguyÔn Tam Hïng Gi¸o viªn h•íng dÉn : PGS.TS Ng« Quốc Tạo M· sè sinh viªn : 101430 H¶i Phßng - 2010
bé gi¸o dôc vµ ®µo t¹o céng hoµ x· héi chñ nghÜa viÖt nam tr•êng ®¹i häc d©n lËp h¶i phßng §éc lËp - Tù do - H¹nh phóc o0o nhiÖm vô thiÕt kÕ tèt nghiÖp Sinh viªn : NguyÔn Tam Hïng M· sè: 101430 Líp : CT1001 Ngµnh: C«ng nghÖ Th«ng tin Tªn ®Ò tµi: T×m hiÓu ph•¬ng ph¸p sinh ¶nh Fractal b»ng hÖ hµm lÆp (IFS) vµ hÖ thèng L-System 3
nhiÖm vô ®Ò tµi 1. Néi dung vµ c¸c yªu cÇu cÇn gi¶i quyÕt trong nhiÖm vô ®Ò tµi tèt nghiÖp a. Néi dung: b. C¸c yªu cÇu cÇn gi¶i quyÕt 2. C¸c sè liÖu cÇn thiÕt ®Ó thiÕt kÕ, tÝnh to¸n 3. §Þa ®iÓm thùc tËp 4
PhÇn nhËn xÐt ®¸nh gi¸ cña c¸n bé chÊm ph¶n biÖn ®Ò tµi tèt nghiÖp 1. §¸nh gi¸ chÊt l•îng ®Ò tµi tèt nghiÖp (vÒ c¸c mÆt nh• c¬ së lý luËn, thuyÕt minh ch•¬ng tr×nh, gi¸ trÞ thùc tÕ, ) 2. Cho ®iÓm cña c¸n bé ph¶n biÖn ( §iÓm ghi b»ng sè vµ ch÷ ) Ngµy th¸ng n¨m 2010 C¸n bé chÊm ph¶n biÖn ( Ký, ghi râ hä tªn ) 5
LỜI CẢM ƠN Trƣớc hết, em xin chân thành cảm ơn thầy giáo PGS.TS Ngô Quốc Tạo đã tận tình hƣớng dẫn, chỉ dạy giúp đỡ tận tình và tạo mọi điều thuận lợi để em hoàn thành báo cáo tốt nghiệp của mình. Em cũng xin chân thành cảm ơn trung tâm nghiên cứu và phát triển công nghệ phần mêm, nơi đã tạo điều kiện tốt trong suốt thời gian thực tập. Em cũng xin chân thành cảm ơn quý thầy cô khoa công nghệ thông tin trƣờng đại học dân lập Hải Phòng đã tận tình giảng dạy, trang bị cho chúng em những kiến thức cần thiết trong suốt quá trình học tập. Và em cũng xin gởi lòng biết ơn đến gia đình, cha, mẹ,bạn bè đã ủng hộ, giúp đỡ và động viên em trong những lúc khó khăn. Đề tài đƣợc thực hiện trong một thời gian tƣơng đối ngắn, nên dù đã hết sức cố gắng hoàn thành đề tài nhƣng chắc chắn sẽ không thể tránh khỏi những thiếu sót nhất định. Rất mong nhận đƣợc sự thông cảm và đóng góp những ý kiến vô cùng quý báu của các thầy cô, bạn bè, nhằm tạo tiền đề thuận lợi cho việc phát triển đề tài trong tƣơng lai. Hải Phòng, tháng 07 năm 2010 Sinh viên Nguyễn Tam Hùng 6
LỜI NÓI ĐẦU Tại sao môn hình học đƣợc xem là "khô cứng" và "lạnh lẽo"? Một trong lý do cơ bản nhất là vì nó không thể mô tả đƣợc thế giới tự nhiên xung quanh chúng ta. Những đám mây trôi lơ lững không phải là những quả cầu, những ngọn núi nhấp nhô không phải là những chóp nón, những bờ biển thơ mộng không phải là những đƣờng tròn. Từ cảm nhận trực quan này, năm 1982, nhà toán học thiên tài Mandelbrot nảy sinh ra ý tƣởng về sự tồn tại của một môn "Hình học của tự nhiên", Fractal Geometry. Từ đây, tôi và bạn có thể mô tả một đám mây một cách chính xác nhƣ một kiến trúc sƣ thiết kế căn nhà của họ. Trong những năm gần đây, toán học và khoa học tự nhiên đã bƣớc lên một bậc thềm mới, sự mở rộng và sáng tạo trong khoa học trở thà . Với một ngƣời quan sát tình cờ màu sắc của các cấu trúc Fractal cơ sở và vẽ đẹp của chúng tạo nên một sự lôi cuốn hình thức hơn nhiều lần so với các đối tƣợng toán học đã từng đƣợc biết đến. Những nguyên nhân của sự lôi cuốn do hình học Fractal tạo ra là nó đã chỉnh sửa đƣợc khái niệm lỗi thời về thế giới thực thông qua tập hợp các bức tranh mạnh mẽ và duy nhất của nó. Việc nghiên cứu ngôn ngữ hình học tự nhiên này mở ra nhiều hƣớng mới cho khoa học cơ bản và ứng dụng. Trong đề tài này chỉ mới thực hiện nghiên cứu một phần rất nhỏ về hình học phân hình và ứng dụng của nó. Nội dung của đề tài gồm có ba chƣơng đƣợc trình bày nhƣ sau: 7
6 CHƯƠNG I. TÌM HIỂU VỀ FRACTAL 9 9 1.2. Các ứng dụng tổng quát của hình học Fractal 10 1.3. Các kiến thức toán học cơ bản 14 1.4. Số chiều Fractal 19 CHƯƠNG II. PHƯƠNG PHÁP SINH ẢNH BẰNG FRACTAL 22 II.1. Họ đƣờng Vonkock 22 II.2. Họ đƣờng peano 38 II .3. Đƣờng sierpinski 64 II.4. Cây fractal 68 II.5. Phong cảnh fractal 71 II.6. Hệ thống hàm lặp (IFS) 78 II.7. Tập Mandelbrot 82 II.8. Tập Julia 88 II.9. Họ các đƣờng cong Phonenix 91 KẾT LUẬN CHƢƠNG 95 96 8
CHƯƠNG I TÌM HIỂU VỀ FRACTAL 1.1. VÀ PHÁT TRIỂN CỦA FRACTAL “Khoa học hiện đại” vốn đƣợc phát triển từ kỷ nguyên Khai sáng (Enlightenment) ở thế kỷ 17, khởi đầu bởi những phát minh của Kepler, Galilei và Newton về các định luật của vận động vật chất và bởi sự thúc đẩy mạnh mẽ của cuộc cách mạng công nghiệp. Với những phát minh đó, lần đầu tiên con ngƣời tìm đƣợc một cách nhận thức thế giới bằng “phƣơng pháp khoa học” mà không cần dựa vào một sức mạnh thần thánh nào hay phải viện đến những liên cảm huyền bí nào giữa trí tuệ con ngƣời với một tinh thần hay linh hồn của tự nhiên. Và cũng do đó, “khoa học” đã đƣợc phát triển trƣớc hết và mạnh mẽ ở các lĩnh vực nghiên cứu tự nhiên nhƣ cơ học, vật lý học, thiên văn học, v.v “tự nhiên không đến với ta sạch sẽ nhƣ ta nghĩ về nó”, và khoa học, trong tinh thần qui giản của cơ giới luận, với việc làm sạch tự nhiên đó đã “hất đổ cả đứa bé cùng với chậu nƣớc tắm” . Ta trở lại đối mặt với một tự nhiên và cuộc đời nhƣ nó vốn có, đầy cát bụi trần gian, lô nhô khúc khuỷu, gãy vỡ quanh co, chứ đâu có thẳng băng, tròn trịa nhƣ các hình vẽ của khoa học hình thức. Ta nhận ra điều đó cả từ trong chính bản thân phần cốt lõi tri thức của khoa học, cả từ những lĩnh vực ứng dụng khoa học đang có nhiều hứa hẹn thành công. Nền tảng đầu tiên của Fractal đã đƣợc nhà toán học và vật lí học Leibniz đƣa ra cùng khoảng thời gian đó là self-similarity (tính tự tƣơng tự) 9
mặc dù chƣa hoàn chỉnh nhƣng đã mở ra bƣớc tiến đầu tiên. Nhƣng nó chỉ đƣợc biết đến với cái tên hình học Fractal đầu tiên vào năm 1872 khi Karl Weierstrass đƣa ra một ví dụ với chức năng không trực quan của thuộc tính hiện thân khắp nơi liên tục mà không phụ thuộc vào không gian. Vào 1904, volt Helge Koch không hài lòng với kết luận của Weierstrass, đƣa ra một định nghĩa hình học cao hơn về chức năng tƣơng tự, mà bây giờ đƣợc gọi là đường cong Koch. Dựa trên thành quả đó , Waclaw Sierpinski đã xây dựng với tam giác vào năm 1915 mà sau nay gọi là tam giác Sierpinski. Ban đầu các Fractal hình học đã đƣợc mô tả nhƣ là những đƣờng cong hơn là hình 2D mà ta đƣợc biết đến nhƣ là trong các công trình hiện đại ngày nay. Vào 1918, Bertrand Russell đã đoán nhận về một " vẻ đẹp tối cao " bên trong nẩy sinh trong toán học Fractal.Ý tƣởng của các đƣờng đồng dạng đƣợc cầm xa hơn nữa bởi Pierre Lévy Paul, ngƣời mà, trong 1938 đã đƣa ra kiến giả về một đƣờng cong fractal mới, đường cong C Lévy. Georg Cantor cũng đã cung cấp các ví dụ về các tập con cảu thuộc tính bất thƣờng thực sự phù hợp – tập Cantor bây giờ cũng đƣợc công nhận là fractals. Những hàm lặp trong mặt phẳng phức đƣợc điều tra vào cuối thế kỉ 19 - đầu thế kỉ 20 bởi Henry Poincaré, Felix Klein, Pierre Fatou và Gaston Julian. Tuy nhiên, không có sự giúp đỡ của đồ họa máy tính hiện đại, họ thiếu những phƣơng tiện để làm cho trực quan vẻ đẹp của nhiều đối tƣợng mà họ khám phá. Vào những năm 1960, Benoit Mandelbrot bắt đầu điều tra self-similarity (tính tự tƣơng tự), mà trƣớc đó đƣợc xây dựng trên công việc của Lewis Fry Richardson. Cuối cùng, vào 1975 Mandelbrot đƣa ra từ "Fractal" để biểu thị một đối tƣợng mà có miền Hausdorff- Besicovitch là lớn hơn so với các miền trƣớc đây. Ông ta minh họa định nghĩa toán học này bởi máy tính những trực quan hóa. Những ảnh này bắt đầu trở lên nổi tiếng dựa vào phép đệ quy, dẫn tới hình thành thuật ngữ "Fractal" ngày nay. 1.2. CÁC ỨNG DỤNG TỔNG QUÁT CỦA HÌNH HỌC FRACTAL Hiện nay có 3 hƣớng ứng dụng lớn của lý thuyết hình học phân hình, bao gồm: ▪ Ứng dụng trong vấn đề tạo ảnh trên máy tính. ▪ Ứng dụng trong công nghệ nén ảnh. ▪ Ứng dụng trong nghiên cứu khoa học cơ bản. □ ỨNG DỤNG TRONG VẤN ĐỀ TẠO ẢNH TRÊN MÁY TÍNH: Cùng với sự phát triển vƣợt bậc của máy tính cá nhân trong những năm gần đây, công nghệ giải trí trên máy tính bao gồm các lĩnh vực nhƣ trò chơi, anmation video nhanh chóng đạt đỉnh cao của nó. Công nghệ này đòi hỏi sự mô tả các hình ảnh của máy PC với sự phong phú về chi tiết và màu sắc với sự tốn kém rất lớn về thời gian và công sức. Gánh nặng đó hiện nay đã đƣợc giảm nhẹ đáng kể nhờ các mô tả đơn giản nhƣng đầy đủ của lý thuyết fractal về các đối tƣợng tự nhiên. Với hình học phân hình khoa học máy tính có trong tay một công cụ mô tả tự nhiên vô cùng mạnh mẽ. 10
Ngoài các ứng dụng trong lĩnh vực giải trí, hình học phân hình còn có mặt trong các ứng dụng tạo ra các hệ đồ hoạ trên máy tính. Các hệ này cho phép ngƣời sử dụng tạo lập và chỉnh sửa hình ảnh, đồng thời cho phép tạo các hiệu ứng vẽ rất tự nhiên hết sức hoàn hảo và phong phú, ví dụ hệ phần mềm thƣơng mại Fractal Design Painter của công ty Fractal Design. Hệ này cho phép xem các hình ảnh dƣới dạng hình hoạ véctơ cũng nhƣ sử dụng các ảnh bitmap nhƣ các đối tƣợng. Nhƣ đã biết, các ảnh bitmap hiển thị hết sức nhanh chóng, thích hợp cho các ứng mang tính tốc độ, các ảnh véctơ mất nhiều thời gian hơn để trình bày trên màn hình (vì phải đƣợc tạo ra bằng cách vẽ lại) nhƣng đòi hỏi rất ít vùng nhớ làm việc. Do đó ý tƣởng kết hợp ƣu điểm của hai loại đối tƣợng này sẽ giúp tiết kiệm nhiều thời gian cho ngƣời sử dụng các hệ phần mềm này trong việc tạo và hiển thị các ảnh có độ phức tạp cao. □ ỨNG DỤNG TRONG CÔNG NGHỆ NÉN ẢNH: Một trong những mục tiêu quan trọng hàng đầu của công nghệ xử lý hình ảnh hiện nay là sự thể hiện hình ảnh thế giới thực với đầy đủ tính phong phú và sống động trên máy tính. Vấn đề nan giải trong lĩnh vực này chủ yếu do yêu cầu về không gian lƣu trữ thông tin vƣợt quá khả năng lƣu trữ của các thiết bị thông thƣờng. Có thể đơn cử một ví dụ đơn giản: 1 ảnh có chất lƣợng gần nhƣ chụp đòi hỏi vùng nhớ 24 bit cho 1 điểm ảnh, nên để hiện ảnh đó trên màn hình mày tính có độ phân giải tƣơng đối cao nhƣ 1024x768 cần xấp xỉ 2.25Mb. Với các ảnh “thực” 24 bit này, để thể hiện đƣợc một hoạt cảnh trong thời gian 10 giây đòi hỏi xấp xỉ 700Mb dữ liệu, tức là bằng sức chứa của một đĩa CD- ROM. Nhƣ vậy khó có thể đƣa công nghệ multimedia lên PC vì nó đòi hỏi một cơ sở dữ liệu ảnh và âm thanh khổng lồ. Đứng trƣớc bài toán này, khoa học máy tính đã giải quyết bằng những cải tiến vƣợt bậc cả về phần cứng lẫn phần mềm. Tất cả các cải tiến đó dựa trên ý tƣởng nén thông tin hình ảnh trùng lặp. Tuy nhiên cho đến gần đây, các phƣơng pháp nén thông tin hình ảnh đều có 1 trong 2 yếu điểm sau: ● Cho tỉ lệ nén không cao. Đây là trƣờng hợp của các phƣơng pháp nén không mất thông tin. ● Cho tỉ lệ nén tƣơng đối cao nhƣng chất lƣợng ảnh nén quá kém so với ảnh ban đầu. Đây là trƣờng hợp của các phƣơng pháp nén mất thông tin, ví dụ chuẩn nén JPEG. Các nghiên cứu lý thuyết cho thấy để đạt một tỷ lệ nén hiệu quả (kích thƣớc dữ liệu nén giảm so với ban đầu ít nhất hàng trăm lần), phƣơng pháp nén mất thông tin là bắt buộc. Tuy nhiên một vấn đề đặt ra là làm thế nào có đƣợc một phƣơng pháp nén kết hợp cả tính hiệu quả về tỷ lệ nén lẫn chất lƣợng ảnh so với ảnh ban đầu? Phƣơng pháp nén ảnh phân hình đƣợc áp dụng gần đây bởi Iterated System đáp ứng đƣợc yêu cầu này. Nhƣ đã biết, với một ánh xạ co trên một không gian metric đầy đủ, luôn tồn tại một điểm bất động xr sao cho: 11
Xr = f(xr) Micheal F.Barnsley đã mở rộng kết quả này cho một họ các ánh xạ co f.Barnsley đã chứng minh đƣợc với một họ ánh xạ nhƣ vậy vẫn tồn tại một “điểm” bất động xr Để ý rằng với một ánh xạ co, ta luôn tìm đƣợc điểm bất động của nó bằng cách lấy một giá trị khởi đầu rồi lặp lại nhiều lần ánh xạ đó trên các kết quả thu đƣợc ở mỗi lần lặp. Số lần lặp càng nhiều thì giá trị tìm đƣợc càng xấp xỉ chính xác giá trị của điểm bất động. Dựa vào nhận xét này, ngƣời ta đề nghị xem ảnh cần nén là “điểm bất động” của một họ ánh xạ co. Khi đó đối với mỗi ảnh chỉ cần lƣu thông tin về họ ánh xạ thích hợp, điều này làm giảm đi rất nhiều dung lƣợng cần có để lƣu trữ thông tin ảnh. Việc tìm ra các ảnh co thích hợp đã đƣợc thực hiện tự động hoá nhờ quá trình fractal một ảnh số hoá do công ty Iterated System đƣa ra với sự tối ƣu về thời gian thực hiện. Kết quả nén cho bởi quá trình này rất cao, có thể đạt tỷ lệ 10000: 1 hoặc cao hơn. Một ứng dụng thƣơng mại cụ thể của kỹ thuật nén phân hình là bộ bách khoa toàn thƣ multimedia với tên gọi “Microsoft Encarta” đƣợc đƣa ra vào tháng 12/1992. Bộ bách khoa này bao gồm hơn 7 giờ âm thanh, 100 hoạt cảnh, 800 bản đồ màu cùng với 7000 ảnh chụp cây cối, hoa quả, con ngƣời, phong cảnh, động vật, Tất cả đƣợc mã hoá dƣới dạng các dữ liệu fractal và chỉ chiếm xấp xỉ 600Mb trên một đĩa compact. Ngoài phƣơng pháp nén phân hình của Barnsley, còn có một phƣơng pháp khác cũng đang đƣợc phát triển. Phƣơng pháp đó do F.H.Preston, A.F.Lehar, R.J.Stevens đƣa ra dựa trên tính chất của đƣờng cong Hilbert. Ý tƣởng cơ sở của phƣơng pháp là sự biến đổi thông tin n chiều về thông tin một chiều với sai số cực tiểu. Ảnh cần nén có thể xem là một đối tƣợng 3 chiều, trong đó hai chiều dùng để thể hiện vị trí điểm ảnh, chiều thứ ba thể hiện màu sắc của nó. Ảnh đƣợc quét theo thứ tự hình thành nên đƣờng cong Hilbert chứ không theo hàng từ trái sang phải nhƣ thƣờng lệ để đảm bảo các dữ liệu nén kế tiếp nhau đại diện cho các khối ảnh kế cạnh nhau về vị trí trong ảnh gốc. Trong quá trình quét nhƣ vậy, thông tin về màu sắc của mỗi điểm ảnh đƣợc ghi nhận lại. Kết quả cần nén sẽ đƣợc chuyển thành một tập tin có kích thƣớc nhỏ hơn rất nhiều vì chỉ gồm các thông tin về màu sắc. Phƣơng pháp này thích hợp cho các ảnh có khối cùng tông màu lớn cũng nhƣ các ảnh dithering. □ ỨNG DỤNG TRONG KHOA HỌC CƠ BẢN: Có thể nói cùng với lý thuyết topo, hình học phân hình đã cung cấp cho khoa học một công cụ khảo sát tự nhiên vô cùng mạnh mẽ nhƣ đã trình bày trong phần I.1, vật lý học và toán học thế kỷ XX đối đầu với sự xuất hiện của tính hỗn độn trong nhiều quá trình có tính quy luật của tự nhiên. Từ sự đối đầu đó, trong những thập niên tiếp theo đã hình thành một lý thuyết mới chuyên nghiên cứu về các hệ phi tuyến, gọi là lý thuyết hỗn độn. Sự khảo sát các bài toán phi tuyến đòi hỏi rất nhiều công sức trong việc tính toán và thể hiện các quan sát một cách trực quan, do đó sự phát triển của lý thuyết này bị hạn chế rất nhiều. Chỉ gần đây với sự ra đời của lý thuyết fractal và sự hỗ trợ đắt lực của máy tình, các nghiên cứu chi tiết về sự hỗn độn mới đƣợc đẩy mạnh. Vai 12
trò của hình học phân hình trong lĩnh vực này thể hiện một cách trực quan các cƣ xử kỳ dị của các tiến trình đƣợc khảo sát, qua đó tìm ra đƣợc các đặc trƣng hoặc các cấu trúc tƣơng tự nhau trong các ngành khoa học khác nhau. Hình học phân hình đã đƣợc áp dụng vào 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 và phƣơng trình Yang & Lee của vật lý, các nghiệm của các hệ phƣơng trình phi tuyến đƣợc giải dựa trên phƣơng pháp xấp xỉ liên tiếp của Newton trong giải tích số, Các kết quả thu đƣợc giữ vai trò rất quan trọng trong các lĩnh vực tƣơng ứng. 13
1.3. CÁC KIẾN THỨC TOÁN HỌC CƠ BẢN 1.3.1. Không gian Metric : a) Không gian: 1: . 2: (không gian Metric) : :XxX , y X: * d (x, y) = d (y, x) x, y X * 0 0 sao cho: d1(x, y) 0, : d(xn, xm) N 2: xn n =1 >0, o cho: 14
d(xn, x) 0 sao cho: d(a, x)<R x S 3: S y1, y2, , yn S sao cho khi x d(x, yi) < y1, y2, , yn : . 15
4: S S >0 sao cho B(x, )= y X:d(x, y) S. 1.3.2. Không gian Hausdorff (H(X), h): . 1: (X . 2: , x : d(x, B)=Min d(x, y):y B . 3: , B : d(A, B)=Max d(x, B):x A . 4: A, B : h(A, B) = d(A, B) d(B, A) : (X). : +) h(A, B) = d(A, B) d(B, A) =d(B, A) d(A, B) = h(B, A) +) A B H(X) A, a B : d(a, B)>0 h(A, B) d(a, B)>0 +) h(A, A) = d(A, A) d(A, A) = d(A, A) = Max d(a, A):a A = 0 +) d(a, B) = min d(a, b) : b B , a A min d(a, c)+d(c, b):b B c C = d(a, C)+min d(c, b):b B c C d(a, C)+max min d(c, b):b B :c C d(a, C)+d(c, B) d(A, B)=max d(a, B):a A d(a, C)+d(C, B) d(A, C)+d(C, B) (B, A) d(B, C)+d(C, A) h(A, B) = d(A, B) d(B, A) 16
(d(A, C)+d(C, B)) (d(B, C)+d(C, A)) d(A, C) d(C, A)+d(C, B) d(B, C) h(A, C) + h(C, B) 5: S + = y X : d(x, y) S + . 1: Cho A, B , : h(A, B) A B+ A+ . ) , An : n = 1, 2, , trong (H(X), h), nj j =1 0<n1<n2<n3< xnj Anj ; j=1, 2, xn An ; n 1 sao cho ~ x nj = xnj j = 1, 2, 3, : ) An H(X) n =1 = limn An H(X). : A= x X : xn An : , xn X (limn d(x, xn : X n f(xn)=f(x). 1.3.3. Ánh xạ co 1: :X 0 s<1 sao cho: d(f(x), f(y)) s.d(x, y) x, y X. . ) f:X on f X, x f (x) : n=0, 1, 2, f : on limn f (x) = xf X . 1: 17
:X . 2: w:X (X). 3: w:X :H(X) H(X) nhƣ sau: w(B) = w(x): x B B H(X). . 4: h(B C, D E) h(B, D) h(C, E) B, C, D, E H(X) 5: , wn:n=1, 2, , N n n :H(X) H(X) đ : N W(B) = w1(B) w2 (B) wn (B) = Uwn (B) n 1 =Max sn:n=1, 2, , N . 1.3.4. Định lý cắt dán (COLLAGE) 1: 0:H(X) w0 H( 0 . 2: Cho X;wn, n=1, 2, , N 0 w0:H(X) X;wn, n=0, 1, 2, , N . : Cho X;wn, n=0, 1, 2, , N :H(X) : N W(B) Uwn (B) B H(X) n 0 : h(W(B), W(C)) s.h(B, C) B, C H(X) : 18
N on A = W(A) =  w n (A) =limn W (B) H(X). n=0 (collage) : IFS X;wn, n=1, 2, , N 0 s<1 sao cho N h L,  w n (L) n 1(n 0) h(L, A) - A=limn wn(L) A=L w(L) w2(L) =wn(L) : N 1 h(L, A) (1 s) h L,  w n (L) L H(X). n 1(n 0) 0 , A0 0, w1, , wn 2 : h(A, w(A0) w (A0) ) - A0 - . 1.4. SỐ CHIỀU FRACTAL - - - : D= log N/log (1/r) . 19
2.1 CÁC THUẬT TOÁN DỰA VÀO HỆ HÀM LẶP . IFS(Iterated Function Systems ). m . 2.1 (Deterministic Algorithm) X;wn, n = 1, 2, , N An , n=1, 2, 0 A1 =w1(A0) w2(A0) wn(A0) A2 =w1(A1) w2(A1) wn(A1) n on Ak = w1(Ak-1) w2(Ak-1) wn(Ak-1)= i =1wi(Ak-1) An=W (A) D An; n =1, 2, Hausdorff. 0n W =limn W . 2 R ; wn(n=1, 2, , N) A phin x1 a i b i x1 e1 w i (x) w i A i x t i x 2 c i d i x 2 f2 : 0.5 0 x1 0.5 0 x1 0.5 w1 w 1 ` 0 0.5 x 2 0 0.5 x 2 0 0.5 0 x 0.5 w 1 1 0 0.5 x 0 2 20
1 2 3 2.1 (Random Interation Algorithm): IFS{X;w1, w2, , wN}, wi i i N sè lÇn ¸p dông w i Pi Pi 1 sè lÇn ¸p dông tÊt c¶ c¸c ¸nh x¹ i 1 0 1, 2, N ) xn=wi(xn-1 xn: n=1, 2, 3, X s i(X)=Ai X +bi det(A ) P i i N det(A i ) j 1 {X;w1, w2, , wN i N pi 1 0 , i 1 xn {w1(xn-1), w2(xn-1), , wN(xn-1 xn=wi(xn-1 i {xn; n=0, 1, } . 21
CHƯƠNG II: MỘT SỐ KỸ THUẬT CÀI ĐẶT HÌNH HỌC PHÂN HÌNH. II.1 HỌ ĐƯỜNG VONKOCK: Trong phần này chúng ta sẽ cùng nhau thảo luận các fractal đƣợc phát sinh bằng cách sử dụng đệ qui initiator / generator với kết quả là các hình tự đồng dạng hoàn toàn. Các hình này có số chiều tự đồng dạng, số chiều fractal và số chiều Hausdorff-Besicovitch bằng nhau. Số chiều đƣợc tính theo công thức sau: log( N) D 1 log R Trong đó: N: Là số đoạn thẳng. R: Là số chiều dài của mỗi đoạn. Chúng ta bắt đầu bằng một initiator, nó có thể là một đoạn thẳng hay một đa giác. Mỗi cạnh của initiator đƣợc thay thế bởi một generator, mà là tập liên thông của các đoạn thẳng tạo nên bằng cách đi từ điểm bắt đầu đến điểm cuối của đƣờng thay thế (Thông thƣờng các điểm của generator là một lƣới vuông hay một lƣới tạo bởi các tam giác đều). Sau đó mỗi đoạn thẳng của hình mới đƣợc thay thế bởi phiên bản nhỏ hơn của generator. Quá trình này tiếp tục không xác định đƣợc. Sau đây là một số đƣờng Von Kock quan trọng: □ ĐƯỜNG HOA TUYẾT VON KOCK-NOWFLAKE: Đƣờng hoa tuyết đƣợc xây dựng bởi nhà toán học Helge Von Kock vào năm 1904. Ở đây chúng ta bắt đầu với initiator là một đoạn thẳng. Còn generator đƣợc phát sinh nhƣ sau: 22
Generator của đƣờng von kock Chúng ta chia đoạn thẳng thành ba phần bằng nhau. Sau đó thay thế một phần ba đoạn giữa bằng tam giác đều và bỏ đi cạnh đáy của nó. Sau đó chúng ta lặp lại quá trình này cho mỗi đoạn thẳng mới. Nghĩa là chia đoạn thẳng mới thành ba phần bằng nhau và lặp lai các bƣớc nhƣ trên. Ta thấy quá trình xây dựng là tự đồng dạng, nghĩa là mỗi phần trong 4 phần ở bƣớc thứ k là phiên bản nhỏ hơn 3 lần của toàn bộ đƣờng cong ở bƣớc thứ (k–1). Nhƣ vậy mỗi đoạn thẳng của generator có chiều dài R = 1/3 (giả sử chiều dài đoạn thẳng ban đầu là 1) và số đoạn thẳng của generator N = 4. Do vậy số chiều fractal của đƣờng hoa tuyết là: log( N) log 4 D 1,2618 1 log 3 log R Một số hình ảnh của đường (Bậc 2) (Bậc 3) Lưu đồ thuật toán 23
Mỗi lúc chúng ta thay thế đoạn thẳng bởi generator, chúng ta dùng 2 mảng XPoints, YPoints để tạo mảng các vị trí toạ độ và sau đó vẽ đoạn thẳng từ cặp tọa độ thứ nhất đến thứ hai, từ thứ hai đến thứ ba, v.v cho đến khi chúng ta cần vẽ hết số đoạn cần vẽ NumLines (trong trƣờng hợp đƣờng hoa tuyết thì NumLines = 4). Để phát sinh ra các cặp tọa độ chúng ta sử dụng các lệnh đồ họa con rùa nhƣ đã mô tả ở trên. Đầu tiên, hàm –Generator giảm Level đi một đơn vị. Sau đó chúng xác định các toạ độ của các điểm cần vẽ của generator bằng cách trƣớc tiên tính chiều dài của mỗi đoạn thẳng của generator cần thay thế (Line-Len chính là 1/R), sau đó lƣu trữ hai đầu mút của đoạn thẳng cần thay thế, rồi tính góc con rùa, sau đó di chuyển con rùa tới toạ độ đầu của đoạn thẳng này, và cuối cùng quay đi một góc thích hợp (có lúc góc quay là 00 ). Sau đó chúng ta lặp lại quá trình sau để xác định các toạ độ của các đoạn thẳng của generator: di chuyển con rùa đi một bƣớc, lƣu trữ vị trí mới của con rùa và quay đi một góc thích hợp. Ở đây góc quay đƣợc lƣu trữ trong mảng Angle. Đối với đƣờng hoa tuyết giá trị của mảng Angle là : {0, 60, -120, 0}. Kế tiếp hàm –Generator kiểm tra xem mức Level có lớn hơn 0 chƣa: Nếu có hàm bắt đầu lặp, xác định các toạ độ các đầu mút của đoạn thẳng mới trong các mảng toạ độ vừa mới tạo thành và sau đó gọi đệ quy hàm –Generator để thay thế mỗi đoạn bằng một generator. Nếu Level bằng 0, hàm sẽ vẽ các đoạn thẳng đƣợc lƣu trong các mảng toạ độ. Code void Generator(CDC *pDC,double X1, double Y1, double X2, double Y2, int Level,int NumLines,double LineLen,double Angles[]) 24
double *XPoints,*YPoints; int I; double Turtle_Theta,Turtle_X, Turtle_Y, Turtle_R; XPoints = new double[NumLines +1]; YPoints = new double[NumLines +1]; Level; Turtle_R=sqrt((X2-X1)* (X2-X1)+ (Y2-Y1)* (Y2-Y1))*LineLen; XPoints[0]=X1; YPoints[0]=Y1; XPoints[NumLines]=X2; YPoints[NumLines]=Y2; Turtle_Theta=Point(X1,Y1,X2,Y2); Turtle_X=X1; Turtle_Y=Y1; Turn(Angles[0],Turtle_Theta); for (I=1; I MoveTo((int)XPoints[ I ], (int) YPoints [ I ]); pDC->LineTo((int)XPoints[ I+1 ], (int) YPoints [ I+1 ]); delete[]XPoints; delete[]YPoints; } □ ĐƯỜNG VON KOCK-GOSPER: Một dạng khác của đƣờng Von Kock đƣợc phát hiện bởi W.Gosper. Trong đƣờng mới này, initiator là một lục giác đều và generator chứa ba đoạn 25
nằm trên một lƣới của các tam giác đều. Hình sau cho chúng ta thấy generator bố trí trên lƣới: Ta thấy đƣờng này có chút khác biệt so với đƣờng hoa tuyết ở chổ đoạn thẳng đƣợc thay thế không nằm trên bất kỳ các đƣờng nào của lƣới. Để tính số chiều fractal của đƣờng Gosper trƣớc hết ta tính chiều dài mỗi đoạn của generator. Giả sử chiều dài từ đầu mút của generator đến đầu mút khác là 1. Đặt: AC = R => AE = 3AC = 3R AB2 = AE2 + EB2 – 2AE.EB.Cos(600) Ta có: Mà AB = 1, AE = 3R, EB = AC = R 2 2 2 1 9R R 2 3R R / 2 7R 1 R 7 EB 2 AE 2 AB 2 2AEAB cos 1 1 8 AB 2 AE 2 EB 2 1 9R 2 R 2 1 8R 2 5 7 cos 7 2AEAB 2 3R 1 6R 1 14 6 7 0 94491 1901' Vì N = 3 nên số chiều fractal của đƣờng Gosper là: log 3 D 1.1291 log 7 Một số hình ảnh của đường 26
(Mức 1) (Mức 2) Code Đoạn mã đối với đƣờng Gosper giống nhƣ đoạn mã của đƣờng hoa tuyết, trong đó: NumLines = 3 Mảng Angle có giá trị sau: {19.1, -60.0 } Ngoài ra, đƣờng Gosper có các mức khác nhau thì tƣơng ứng với các hình dạng khác nhau. □ ĐƯỜNG VON KOCK BẬC HAI 3-ĐOẠN: Một vài đƣờng cong kế tiếp đƣợc gọi là bậc hai (quadric) vì initiator là một hình vuông (Tuy nhiên điều này không có gì bí mật về initiator là hình vuông, nó có thể là một đa giác). Hơn nữa chúng ta sẽ tạo ra các generator trên lƣới các hình vuông. Đối với đƣờng cong đầu tiên này, một generator của 3- đoạn sẽ đƣợc sử dụng. Hình sau sẽ cho chúng ta một generator: Để tính số chiều fractal của đƣờng này trƣớc hết ta tính số chiều của mỗi đoạn của generator. Giả sử chiều dài từ đầu mút của generator đến đầu mút khác là 1: Ta có: Đặt AC = R AB2 = AE2 + EB2 Mà AB = 1, AE = 2AC = 2R, EB = R => 1 = 4R2 + R2 1 R 5 EB2 = EA2 + AB2 – 2EA.AB.cos 1 2 2 2 2 2 2 1 3 EA AB EA 4R 1 R 1 3R 5 2 5 cos 0.894427 2EAAB 2.2R.1 4R 1 5 4 5 25056' 27
Vì N = 3 nên số chiều fractal là: log 3 D 1.3652 log 5 Một số hình ảnh của đường (Mức 1) (Mức 3) (Mức 5) Code Đoạn mã đối với đƣờng 3-đoạn giống nhƣ đoạn mã đƣờng hoa tuyết. NumLines = 3 Mảng Angle có giá trị sau: {26.56, -90.0 } □ ĐƯỜNG VON KOCK BẬC HAI 8-ĐOẠN: Một vài đƣờng cong kế tiếp sẽ giúp sử dụng một lƣới hình vuông và quay các góc đi 900. Chúng đều hơn một chút so với đƣờng cong trƣớc bởi vì đoạn thẳng đƣợc thay thế sẽ rơi vào đƣờng nằm ngang ở giữa lƣới. Hình sau cho chúng ta thấy generator của nó: 28
Giả sử chiều dài từ đầu nút của generator đến đầu mút khác là 1, thì chiều dài mỗi đoạn thẳng của generator R = 1/4. Bây giờ chúng ta có thể vẽ các generator khác nhau, giới hạn duy nhất là đƣờng cong không tự đè lên nhau và không tự giao nhau. Nếu chúng ta muốn đƣờng cong có số chiều lớn nhất có thể có, thì chúng ta cần tìm generator với N lớn nhất. Mandelbrot đã định giá trị N lớn nhất có thể có là: 1 Với 1/R là số chẵn N max 2R 2 2 1 R Với 1/R là số lẻ. N max 2R 2 Do vậy R = 1/4 nên Nmax = 8. Số chiều fractal là: log8 D 1.5 log4 Một số hình ảnh của đường (Mức 1) (Mức 5) Code Đoạn mã đối với đƣờng cong 8-đoạn giống nhƣ đoạn mã của đƣờng hoa tuyết, trong đó: NumLine = 8 Mảng Angle có giá trị sau: {0, 90, -90, -90, 0, 90, 90, 0 } □ ĐƯỜNG VON KOCK BẬC HAI 18-ĐOẠN: Hình sau là generator của đƣờng Von Kock bậc hai 18-đoạn: 29
Giả sử chiều dài từ đầu mút của generator đến đầu mút khác là 1, thì chiều dài mỗi đoạn thẳng của generator là R = 1/6. Khi đó Nmax = 18. Do đó số chiều fractal là: log18 D 1.6131 log 6 Một số hình ảnh của đường (Mức 1) (Mức 5) Code Đoạn mã đối với đƣờng 18-đoạn giống nhƣ đoạn mã của đƣờng hoa tuyết, trong đó: NumLine = 18 Mảng Angle có giá trị sau: {0, 90, 0, -90, 0, -90, -90, 90, 90, 0, -90, -90, 90, 90, 0, 90, 0, 0 } . □ ĐƯỜNG VON KOCK BẬC HAI 32-ĐOẠN: Hình sau là generator của đƣờng Von Kock bậc hai 32-đoạn: 30
Giả sử chiều dài từ đầu mút của generator đến đầu mút khác là 1, thì chiều dài mỗi đoạn thẳng của generator là R = 1/8. Khi đó Nmax = 32. Do đó số chiều fractal là: log 32 D 1.6667 log 8 Một số hình ảnh của đường (Mức 1) (Mức 4) Code Đoạn mã đối với đƣờng 32-đoạn giống nhƣ đoạn mã của đƣờng hoa tuyết, trong đó: NumLine = 32 Mảng Angle có giá trị sau: 90 , 90,90,90, 90, 90,0,90, 90, 90,0, 90,90,90,0, 90,0,90,0, 90, 90,90,0,90,90, 90,0,90,90, 90, 90,0 □ ĐƯỜNG VON KOCK BẬC HAI 50-ĐOẠN: Hình sau là generator của đƣờng Von Kock bậc hai 50-đoạn: 31
Giả sử chiều dài từ đầu mút của generator đến đầu mút khác là 1, thì chiều dài mỗi đoạn thẳng của generator là R = 1/10. Khi đó Nmax = 50. Do đó số chiều fractal là: log 50 D 1.6990 log10 Chúng ta thấy generator chứa nhiều đoạn thẳng hơn, do đó nó trở nên kém rõ ràng hơn trong cách thức chứa đƣờng. Quá trình đƣợc sắp xếp và sửa sai. Nếu chúng ta sử dụng generator để thay thế các đoạn thẳng cắt nhau theo một góc 900, thì chúng ta không thể có bất cứ phần nào của generator vƣợt ra ngoài biên của ô vuông đƣợc tạo ra bởi các đƣờng chấm chấm (Nhƣ ở hình vẽ trên). Điều này đủ để tránh tự đè lên nhau, nhƣng không ngăn cản việc tự giao nhau. Để đảm bảo ngăn chặn tự giao nhau, chúng ta nối một cách hình thức mỗi cặp cạnh song song của ô vuông. Nếu generator tiếp xúc với cạnh của ô vuông ở cùng một điểm về cùng một bên của một cặp, thì sự tự giao nhau sẽ xảy ra. Cuối cùng, cách dễ dàng để tạo ra generator là chia nó ra làm hai phần mà đối xứng với nhau, mỗi phần bắt đầu ở mút của đoạn đƣợc thay thế và kết thúc ở điểm giữa của điểm này. Do đó sự ràng buộc ở đây là: ◊ Tạo một nửa generaor từ một đầu mút của đoạn đƣợc thay thế và kết thúc ở điểm giữa của đoạn này, chứa Nmax/2 đoạn. ◊ Không đi ra ngoài ô vuông. ◊ Nếu generator giao với một điểm nằm trên một cặp cạnh song song với nhau của ô vuông, thì nó không thể giao nhau ở một điểm tƣơng ứng của cặp cạnh khác. Khi nửa generator đã tạo, chúng ta có thể lật ngƣợc lại đồ thị và vẽ generator giống nhƣ trên để hoàn tất quá trình. Một số hình ảnh của đường 32
(Mức 1) (Mức 3) Code Đoạn mã đối với đƣờng 50-đoạn giống nhƣ đoạn mã của đƣờng hoa tuyết, trong đó: NumLine = 50 Mảng Angle có giá trị sau: { 0, 90, -90, -90, 0, 0, 90, 0, 0, 0, 90, 90, 0, 0, 90, 0, -90, 0, 0, 0, -90, -90, 0, 0, 90, 0, -90, 0, 0, 90, 90, 90, 0, 0, 0, 90, 0, -90, 0, 0, -90, -90, 0, 90, 0, -90, 0, 0, 90, 90, 0 } □ GENERATOR PHỨC TẠP: Chúng ta hãy quan sát geneator phức tạp dƣới đây: Generator này đƣợc khám phá bởi Mandelbrot. Cơ sở của nó là một lƣới các tam giác đều. Nếu generator chứa các đoạn nối các điểm 0, 1, 2, 3, 4 và 11 thì nó sẽ trở nên đơn giản hơn. Tuy nhiên mô hình nhỏ hơn của generator đơn giản này đƣợc chèn vào giữa điểm 4 và 9, sau đó hai đoạn thẳng bằng nhau đƣợc thêm vào để hoàn tất generator. Do có hai độ dài khác nhau đƣợc sử dụng, chúng ta sử dụng biểu thức sau để xác định số chiều fractal: Ta có: R.M D 1 Trong đó: M: Là đoạn thẳng. R: Là chiều dài của mỗi đoạn thẳng. D: Là số chiều của mỗi fractal. Giả sử chiều dài từ đầu mút của generator đến đầu mút khác là 1, thì chiều dài của các đoạn đều bằng nhau là R = 1/3. Đối với các đoạn nhỏ hơn thì chiều dài là: 33
3 R 9 Thật vậy: Ta có: CD2 = CB2 + DB2 – 2.CB.DB.cos600 Mà: CB = 1/3 DB = 2/3 1 4 1 2 1 CD 2 2 9 9 3 3 2 3 CD 3 Do đó, chiều dài mỗi đoạn của generator nhỏ là: 3 R CD / 3 9 Vậy chúng ta có: D D 1 3 6 5 1 3 9 D 1.238361 Một số hình ảnh của đường (Mức 1) (Mức 3) (Mức 5) Code Việc tạo ra đƣờng này cũng nhƣ phần trên, nhƣng hàm –Generator thì khác. Hàm này phải đảm bảo rằng đƣờng không tự đè lên nhau và tự giao nhau. Có 4 sự thay đổi của generator ở các vị trí: Bên phải đoạn thẳng gốc. Bên trái đoạn thẳng gốc. 34
Bên phải đoạn thẳng gốc (nhƣng với generator đảo ngƣợc). Bên trái đoạn thẳng gốc (nhƣng với generator đảo ngƣợc). Đoạn mã của hàm –Generator này là: //Phát sinh họ đƣờng Von Kock Generator phức tạp: void ComplexVonKockGenerator( CDC *pDC,double X1,double Y1[],double X2,double Y2,int Level,int Type,int Sign,int NumLines,double LineLen,double Angles[]) double * XPoints ,*YPoints; int I; double Thurtle_Theta,Thurtle_X,Thurtle_Y,Thurtle_R; int Split=5; double AngleSplit=60; XPoints = new double[NumLines + 1]; YPoints = new double[NumLines + 1]; Switch(Type) case1: Sign*= -1; break; case2: Sign*= -1; Case3: Double Temp; Temp = X1; X1=X2; X2=Temp; Temp = Y1; Y1 = Y2; Y2=Temp; break ; Level; Turtle_R=sqrt((X2-X1)* (X2-X1)+ (Y2-Y1)* (Y2- Y1))*LineLen; XPoints[0]=X1; YPoints[0]=Y1; XPoints[NumLines]=X2; YPoints[NumLines]=Y2; 35
Turtle_Theta=Point(X1,Y1,X2,Y2); TurtleX=X1; TurtleY=Y1; for (I=1 ; I =NumLines -2; I) Step(Turtle_X, Turtle_Y, Turtle_R, Turtle_Theta); XPoints[ I ]=Turtle_X; YPoints[ I ]=Turtle_Y; Turn(Angles[ I ]*Sign,Turtle_Theta); Turtle_R=sqrt((XPoints[NumLines -2]- XPoints[Split -1])* (XPoints[NumLines -2]- XPoints[Split -1]) + (YPoints[NumLines -2]- YPoints[Split -1])* (YPoints[NumLines -2]- YPoints[Split -1]))*LineLen; Turtle_Theta= Point(XPoints[Split-1], YPoints[Split-1], XPoints[NumLines -2], YPoints[NumLines -2]); Turn(-AngleSplit*Sign,Turtle_Theta); Turtle_X=XPoints [Split-1]; Turtle_Y=YPoints [Split-1]; for (I=Split ; I<NumLines -2 ;++I) Step(Turtle_X, Turtle_Y, Turtle_R, Turtle_Theta); XPoints[ I ]=Turtle_X; YPoints[ I ]=Turtle_Y; Turn(Angles[ I ]*Sign,Turtle_Theta); if(Level) for (I=0 ; I<NumLines ;++I) switch(I) 36
case2: case8: case10: Type = 0; break ; case0: Type = 1; break ; case5: if (Level= = 1) Type = 1; else Type = 3; break ; case1: case3: case4: Type =2; break; case6: case7: case9: Type = 3; break; X1 = XPoints[ I ]; Y1 = YPoints[ I ]; X2 = XPoints[ I+1 ]; Y2 = YPoints[ I+1 ]; ComplexVonKockGenerator(pDC,X1,Y1,X2,Y2,Level,Type,Sign, NumLines,LineLen,Angles); else for (I= 0 ; I MoveTo((int)XPoints[ I ],(int) YPoints [ I ]); pDC->LineTo((int)XPoints[ I+1 ],(int) YPoints [ I+1 ]); delete[]XPoints; 37
delete[]YPoints; Hàm này có thêm hai tham số Sign và Type. Sygn dùng để nhân với mỗi góc khi quay. Nếu Type = 0 không có gì thay đổi, tham số Sign vẫn duy trì giá trị củ và generator đƣợc sinh ra cùng bên nhƣ generator trƣớc. Khi type = 1, Sign đƣợc nhân với -1 thì tất cả các góc quay theo chiều đảo ngƣợc sao cho generator xuất hiện ở bên đối diện với đoạn thẳng từ generator trƣớc. Khi Type = 2, chúng ta tạo đoạn thẳng mà toạ độ đầu là điểm cuối của đoạn thẳng khác và ngƣợc lại sao cho generator đƣợc vẽ theo chiều ngƣợc lại. Chúng ta cũng cần đảo tất cả các dấu của generator đảo ngƣợc này để generator xuất hiện cùng bên với generator trƣớc. Cuối cùng, khi Type = 3, chúng ta đảo ngƣợc các toạ độ sao cho generator vừa đảo ngƣợc vừa di chuyển sang phía đối diện. Hàm này làm việc nhƣ sau: Xác định Type thuộc loại nào? Xác định các toạ độ của generator lớn và nhỏ. Nếu Level = 0 thì hàm sẽ vẽ các đoạn thẳng. Nếu Level khác 0 thì hàm xác định loại cho tham số Type đối với mỗi đoạn thẳng, sau đó gọi đệ quy. Mảng Angle là:{60, 0, -60, -60, -60, 0, 60, 60, 0, 0, -60} NumLines = 11 II.2 HỌ ĐƯỜNG PEANO: Trong phần này, chúng ta xét các đƣờng có số chiều fractal bằng 2. Chúng đƣợc gọi là các đƣờng Peano vì đƣờng đầu tiên trong họ đƣờng này đƣợc khám phá bởi Guiseppe Peano vào năm 1900. Do đó chiều fractal là 2 nên các đƣờng này phải lấp đầy hoàn toàn mặt phẳng. Điều này dẫn đến sự tự giao nhau của chúng tại nhiều điểm trong mặt phẳng. □ ĐƯỜNG PEANO NGUYÊN THUỶ: Hình sau cho chúng ta thấy generator của đƣờng Peano nguyên thuỷ: Ở đây initiator rất đơn giản. Nó chỉ là một đoạn thẳng. Thật không may, tất cả đều tự cắt, nên hầu nhƣ không thể xác định cách thức mà theo đó đƣờng 38
Peano đƣợc vẽ, ngay cả các mũi tên đƣợc thêm vào trong hình vẽ. Nhìn vào hình vẽ này chúng ta thấy generator đƣợc hình thành nhƣ sau: Đầu tiên chúng ta dựng đoạn thẳng đứng về phía trên, rồi dựng đoạn thẳng ngang về bên trái, rồi dựng đoạn thẳng đứng về phía trên, rồi dựng dựng đoạn thẳng ngang về bên phải, rồi dựng đoạn thẳng đứng về phía dƣới, rồi dựng đoạn thẳng ngang về bên phải, rồi dựng đoạn thẳng đứng về phía trên, rồi dựng đoạn thẳng ngang về phía trái, và cuối cùng dựng đoạn thẳng đứng về phía trên. Nhƣ vậy generator chứa 9 đoạn thẳng (nghĩa là N = 9), chiều dài mỗi đoạn của generator là R = 1/3 (Giả sử chiều dài đoạn thẳng ban đầu là 1). Do đó số chiều fractal là: log 9 D D 2 log 3 Một số hình ảnh của đường (Mức 1) (Mức 3) Code Đoạn mã đối với đƣờng Peano giống đoạn mã của đƣờng hoa tuyết, trong đó: NumLines = 9 Mảng Angle có giá trị sau: 0,90, 90, 90, 90,90,90,90,0 □ ĐƯỜNG PEANO CẢI TIẾN: Nếu không có sự tự giao của generator đối với đƣờng Peano thì việc đi theo vết của nó và quan sát cách thức vẽ sẽ dễ dàng hơn. Vì thế, đƣờng Peano cải tiến đƣợc phát triển theo kiểu làm tròn các góc để tránh sự tự giao. Kết quả chúng ta đƣợc generator nhƣ hình sau: 39
Tuy nhiên, generator cập nhật này chỉ có thể sử dụng ở mức thấp nhất trƣớc khi thực vẽ đƣờng cong. Nếu sử dụng nó ở mức cao hơn, bằng kỹ thuật đệ quy chúng ta cố gắng thay thế generator đối với mỗi đƣờng chéo đƣợc làm tròn ở một góc, cũng nhƣ đối với các đoạn thẳng đều. Do đó generator cho đƣờng Peano nguyên thuỷ đƣợc sử dụng ở mức cao. Vì generator sử dụng lần đệ quy cuối cùng có độ dài ngắn hơn so với đƣờng Peano nguyên thuỷ, ta có số chiều fractal D nhỏ hơn 2. Khi số lần đệ quy tăng lên, số chiều fractal sẽ thay đổi và tiến về 2. Một số hình ảnh của đường (Mức 2) Code // Edit Code phát sinh của đƣờng cong Peano cải tiến: void ModifiedPeanoGenerator(CDC *pDC, double X1, double Y1, double X2, double Y2, int Level, int NumLines, double LineLen, double Angles[], double &XTemp, double &YTemp) double *XPoints, *YPoints,SplitLineLen=1.0/18.0; int I,Split = 9; double Turtle_Theta,Turtle_X, Turtle_Y, Turtle_R; XPoints = new double[NumLines + 1]; YPoints = new double[NumLines + 1]; Level; XPoints[0]= X1; YPoints[0]= Y1; Turtle_Theta = Point(X1,Y1,X2,Y2); 40
Turtle_X=X1; Turtle_Y=Y1; if (Level) Turtle_R=sqrt((X2-X1)* (X2-X1)+ (Y2-Y1)* (Y2-Y1))*LineLen; XPoints[Split]=X2; YPoints[Split]=Y2; for (I=1; I<Split; ++I) Step(Turtle_X, Turtle_Y, Turtle_R, Turtle_Theta); XPoints[ I ]=Turtle_X; YPoints[ I ]=Turtle_Y; if (I!=Split) Turn(Angles[ I ],Turtle_Theta); for (I=0 ; I<Split ;++I) X1 = XPoints [ I ]; Y1 = YPoints [ I ]; X2 = XPoints [ I+1 ]; Y1 = YPoints [ I+1 ]; ModifiedPeanoGenerator(pDC, X1, Y1, X2, Y2, Level, NumLines, LineLen, Angles, XTemp, YTemp); else Turtle_R=sqrt((X2-X1)* (X2-X1)+ (Y2-Y1)* (Y2- Y1))*SplitLineLen ; XPoints[0]= XTemp; YPoints[0]= YTemp; XPoints[NumLines]= X2; YPoints[NumLines]= Y2; for (I=1; I<NumLines; ++I) 41
Step(Turtle_X, Turtle_Y, Turtle_R, Turtle_Theta); XPoints[ I ]=Turtle_X; YPoints[ I ]=Turtle_Y; if ( I= = NumLines -1) break; if ( I%2) Step(Turtle_X, Turtle_Y, Turtle_R, Turtle_Theta); Step(Turtle_X, Turtle_Y, Turtle_R, Turtle_Theta); Step(Turtle_X, Turtle_Y, Turtle_R, Turtle_Theta); else Step(Turtle_X, Turtle_Y, Turtle_R, Turtle_Theta); Turn(Angles[ I/2 ],Turtle_Theta); XTemp = XPoints [NumLines -1]; YTemp = YPoints [NumLines -1]; for (I= 0 ; I MoveTo((int)XPoints[ I ],(int)YPoints[ I ]); pDC->LineTo((int)XPoints[ I+1 ],(int)YPoints[ I+1 ]); delete[]XPoints; delete[]YPoints; Đối với Level > 1 thì hàm này giống nhƣ hàm –Generator của đƣờng Peano gốc. Với Level = 1, thì hàm này có hơi khác một chút. Thay vì định nghĩa bƣớc con rùa (là biến Turtle_R) bằng 1/3 chiều dài đoạn thẳng ban đầu thì ta định nghĩa nó bằng 1/18 chiều dài đoạn thẳng ban đầu, về cơ bản generator đƣợc viết sao cho con rùa vẫn đi qua con đƣờng giống nhƣ generator của đƣờng Peano gốc, sử dụng các góc quay giống nhau, nhƣng dùng 6 bƣớc thay vì 1 bƣớc nhƣ generator của Peano gốc. Tuy nhiên, các điểm đƣợc lƣu trữ trong các mảng toạ độ có thay đổi. Sau khi lƣu trữ toạ độ thứ nhất, ta lƣu trữ vị trí sau bƣớc 5, vị trí kế tiếp đƣợc lƣu trữ ở cuối bƣớc 1 sau khi quay đi một góc 42
đầu tiên. Các vị trí còn lại đƣợc lƣu trữ sau bƣớc 5 và sau bƣớc đầu tiên của đoạn thẳng kế, ngoại trừ bƣớc 5 của đoạn thẳng cuối cùng sẽ không đƣợc lƣu trữ lại. Kết quả là khi các đoạn thẳng đƣợc vẽ, chúng sẽ tạo nên một đƣờng xiên nối các điểm 1/6 khoảng cách trên mỗi đoạn thẳng gặp nhau ở góc. (Ở đây NumLines = 19). □ TAM GIÁC CESARO: Hình sau cho chúng ta xem một generator rất đơn giản (initiator là đoạn thẳng nằm ngang): Generator chứa hai cạnh của một tam giác cân. Do đó, số đoạn thẳng là N=2 và chiều dài của mỗi đoạn là: 1 R 2 Giả sử đoạn thẳng ban đầu có chiều dài là 1. Khi đó số chiều fractal là: log 2 D D 2 log 2 Phụ thuộc vào các điều kiện cụ thể, generator này sẽ đƣợc đặt bên trái hoặc bên phải của mỗi đoạn thẳng mà nó thay thế. Nhiều đƣờng cong khác nhau hoàn toàn có thể đƣợc sinh ra từ generator này. Các đƣờng này đƣợc khám phá bởi Ernest Cesaro vào năm 1905. Các hình sau là các mức khác nhau của tam giác Cesaro: Mức thứ nhất 43
Mức thứ năm Ở bất kỳ mức nào trong việc xây dựng đƣờng này, generator luôn đƣợc đặt ở bên phải của mỗi đoạn thẳng ở mức đầu tiên, bên trái của mỗi đoạn thẳng ở mức thấp hơn kế tiếp, bên phải của mỗi đoạn thẳng ở mức thấp hơn kế tiếp nữa v.v Nhƣ vậy đoạn mã của hàm Generator có thêm mảng Sign để lúc quay theo các góc khác nhau, chúng ta nhân tƣơng ứng với phần tử của mảng Sign đƣợc khởi động nhƣ sau: for (I = Level; I >=0; I ) { Sign [ I ] = Sign1; Sign1 = -1; } Với Sign1 có thể khởi động lúc đầu là 1 hoặc -1. // Sau đây là Edit Code của đƣờng cong Tam Giác Cesaro. void CesaroTriangleGenerator(CDC *pDC,double X1, double Y1, double X2, double Y2, int Level,int NumLines, double LineLen, double Angles[],int Sign[]) double *XPoints ,*YPoints; int I; double Turtle_Theta,Turtle_X, Turtle_Y, Turtle_R; XPoints = new double [NumLines + 1]; YPoints = new double [NumLines + 1]; Level; Turtle_R=sqrt((X2-X1)* (X2-X1)+ (Y2-Y1)* (Y2- Y1))*LineLen; XPoints[0]= X1; YPoints[0]= Y1; XPoints[NumLinesv -1]= X2; YPoints[NumLines -1]= Y2; Turtle_Theta = Point(X1,Y1,X2,Y2); Turtle_X=X1; 44
Turtle_Y=Y1; for (I=NumLines ; I>=1 ;I-=2) Step(Turtle_X, Turtle_Y, Turtle_R, Turtle_Theta); XPoints[ I ]=Turtle_X; YPoints[ I ]=Turtle_Y; Turn(Angles[ I ]*Sign[Level],Turtle_Theta); if (Level) for ( I=0 ; I MoveTo((int)XPoints[ I ],(int)YPoints[ I ]); pDC->LineTo((int)XPoints[ I+1 ],(int)YPoints[ I+1 ]); delete[]XPoints; delete[]YPoints; □ TAM GIÁC CESARO CẢI TIẾN: Tam giác mô tả ở trên hơi khó để lần theo dấu vết vì đƣờng rẽ theo góc 900 từ tâm của đoạn thẳng gốc thật sự đi lại theo vết của nó nhƣng không thể quan sát đƣợc khi vẽ. Việc cập nhật đƣờng cesaro có thể thực hiện bằng cách thay đổi góc generator từ 900 sang 850 đối với mức thấp nhất trƣớc khi thực hiện quá trình vẽ. 45
Hình sau minh hoạ một generator (initiator là đoạn thẳng nằm ngang ). Giống nhƣ đƣờng Peano cải tiến, kết quả thu đƣợc là một đƣờng cong mà số chiều fractal 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 sau cho chúng ta thấy mức thứ tƣ của tam giác Cesaro cải tiến: Ta tính chiều dài mỗi đoạn của generator. Giả sử chiều dài đoạn thẳng gốc là a Ta có: AE = a / 2 Đặt: AC = b CD = c Ta có: c2 CE 2 DE 2 2CEDE cos Mà CE DE a / 2, 100 a 2 a a a 2 c 2 2 cos100 1 cos100 a 2 (sin50 ) 2 2 2 2 2 c a.sin50 Ta có: AC CD DB AB 2b c a 2b a(1 sin50 ) a a b (1 sin50 ) 0.9128442 2 2 46
Đoạn mã của hàm –Generator nhƣ sau: void ModifiedCesaroGenerator(CDC *pDC,double X1, double Y1, double X2, double Y2, int Level,int NumLines, double LineLen, double Angles[],int Sign[]) double *XPoints , *YPoints ; int I; double Turtle_Theta,Turtle_X, Turtle_Y, Turtle_R,Turtle_R1; XPoints = new double [NumLines + 1]; YPoints = new double [NumLines + 1]; Level; Turtle_R1=sqrt((X2-X1)* (X2-X1)+ (Y2-Y1)* (Y2- Y1))*LineLen; Turtle_R=Turtle_R1* 0.9128442; XPoints [0]= X1; YPoints [0]= Y1; XPoints[NumLines -2]= X2 ; YPoints[NumLines -2]= Y2 ; Turtle_Theta = Point(X1,Y1,X2,Y2); Turtle_X=X1; Turtle_Y=Y1; for (I=NumLines -1; I >=1; I-=2) Step(Turtle_X, Turtle_Y, Turtle_R, Turtle_Theta); XPoints[ I ]=Turtle_X; YPoints[ I ]=Turtle_Y; Turn(Angles[ I ]* Sign[Level],Turtle_Theta); if (I= =NumLines - 1) Turtle_R=Turtle_R1; Step(Turtle_X, Turtle_Y, Turtle_R, Turtle_Theta); XPoints[NumLines ]=Turtle_X; YPoints[NumLines ]=Turtle_Y; Turn(Angles[NumLines ]* Sign[Level],Turtle_Theta); if (Level) for (I= 0; I<NumLines - 2; ++I) X1 = XPoints [ I ]; Y1 = YPoints [ I ]; X2 = XPoints [ I+1 ]; Y2 = YPoints [ I+1 ]; 47
ModifiedCesaroGenerator(pDC, X1, Y1, X2, Y2,Level,NumLines, LineLen, Angles,Sign); else for (I= 0; I MoveTo((int)XPoints[ I ],(int)YPoints[ I ]); pDC->LineTo((int)XPoints[ I+3 ],(int)YPoints[ I+3 ]); for (I= 1; I MoveTo((int)XPoints[ I ],(int)YPoints[ I ]); pDC->LineTo((int)XPoints[ I+2 ],(int)YPoints[ I+2 ]); delete[]XPoints; delete[]YPoints; Hàm này giống với hàm trong đƣờng Cesaro gốc nhƣng lúc này mảng Angle là {0, -170, 0, 85, 0 } và NumLines = 4, đồng thời chiều dài các đoạn của generator có khác nhau. Chúng chia làm hai loại: Loại chiều dài thứ nhất: Bằng nửa chiều dài của đoạn thẳng ban đầu. Loại chiều dài thứ hai: Bằng nửa chiều dài của đoạn ban đầu nhân với 0.9128442. □ 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 bên trái và 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. 48
Hình sau cho chúng ta mức khác nhau của hình Cesaro này: Đoạn mã của hàm –Generator nhƣ sau: void OtherCesaroGenerator(CDC *pDC,double X1, double Y1, double X2, double Y2, int Level,int NumLines, double LineLen, double Angles[],int Sign) double *XPoints ,*YPoints; int I; double Turtle_Theta,Turtle_X, Turtle_Y, Turtle_R; XPoints = new double [NumLines + 1]; YPoints = new double [NumLines + 1]; Level; Turtle_R=sqrt((X2-X1)* (X2-X1)+ (Y2-Y1)* (Y2-Y1))*LineLen; XPoints[0]= X1; YPoints[0]= Y1; XPoints[NumLinesv -1]= X2; YPoints[NumLines -1]= Y2; Turtle_Theta = Point(X1,Y1,X2,Y2); 49
Turtle_X=X1; Turtle_Y=Y1; for (I=NumLines; I>=1; I-=2) Step(Turtle_X, Turtle_Y, Turtle_R, Turtle_Theta); XPoints[ I ]=Turtle_X; YPoints[ I ]=Turtle_Y; Turn(Angles[ I ]*Sign,Turtle_Theta); Sign= -1; if (Level) for(I=0; I MoveTo((int)XPoints[ I ],(int)YPoints[ I ]); pDC->LineTo((int)XPoints[ I+1 ],(int)YPoints[ I+1 ]); delete[]XPoints; delete[]YPoints; } □ TAM GIÁC POLYA: Đƣờng này đƣợc khám phá bởi George Polya. Initiator và generator thì giống nhƣ đƣờng Cesaro, nhƣng vị trí đặt chúng có thay đổi. Hình sau cho chúng ta thấy hai mức đầu tiên của 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 50
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: Đoạn mã của hàm Polya-Generator nhƣ sau: void PolyaGenerator(CDC *pDC,double X1, double Y1, double X2, double Y2, int Level,int NumLines, double LineLen, double Angles[],int Sign[]) double *XPoints ,*YPoints; int I; double Turtle_Theta,Turtle_X, Turtle_Y, Turtle_R; XPoints = new double [NumLines + 1]; YPoints = new double [NumLines + 1]; Turtle_R=sqrt((X2-X1)* (X2-X1)+ (Y2-Y1)* (Y2- Y1))*LineLen; XPoints[0]= X1; YPoints[0]= Y1; XPoints[NumLinesv -1]= X2; YPoints[NumLines -1]= Y2 ; Turtle_Theta = Point(X1,Y1,X2,Y2); Turtle_X=X1; Turtle_Y=Y1; Turn(Angles[ 0 ]*Sign[Level],Turtle_Theta); for (I=1 ; I<NumLines ;++I) Step(Turtle_X, Turtle_Y, Turtle_R, Turtle_Theta); XPoints[ I ]=Turtle_X; YPoints[ I ]=Turtle_Y; Turn(Angles[ I ]*Sign[Level],Turtle_Theta); Level; if (Level) for (I=0; I<NumLines; ++I) X1 = XPoints[ I ]; Y1 = YPoints[ I ]; X2 = XPoints[ I+1 ]; Y2 = YPoints[ I+1 ]; 51
PolyaGenerator(pDC, X1, Y1, X2, Y2, Level, NumLines, LineLen, Angles, Sign ); Sign[Level]* = -1; else for (I= 0; I MoveTo((int)XPoints[ I ],(int)YPoints[ I ]); pDC->LineTo((int)XPoints[ I+1 ],(int)YPoints[ I+1 ]); delete[]XPoints ; delete[]YPoints ; Chúng ta sử dụng cùng một kỹ thuật đã đƣợc sử dụng đối với đƣờng Cesaro tức là cũng dùng mảng Sign sau khi chúng ta gọi đệ quy hàm – Generator. Mảng Angles có giá trị là {45, 0 } và NumLines = 2. Tuỳ vào mức khác nhau thì tƣơng ứng với hình vẽ khác nhau. Sau đây là hình minh hoạ của đƣờng Polya có mức là 4: □ ĐƯỜNG PEANO_GOSPER: Hình sau là generator của đƣờng Peano_Gosper và 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): 52
Giả sử chiều dài từ đầu mút của generator đến đầu mút khác là 1, chúng ta tính chiều dài mỗi đoạn của generator nhƣ sau: Đặt: AD = R Ta có: AB2 = AC2 + BC2 – 2.AC.BC.cos600 Mà: AC = 3AD = 3R BC = AD = R AB = 1 1 9 R 2 R 2 2 3R R / 2 7R 2 1 D 7 Vì generator có số đoạn thẳng N = 7 nên số chiều fractal là: log 7 D D 2 log 7 Đƣờng này có tính chất là nó lấp đầy phần bên trong của đƣờng Gosper. Hình sau cho chúng ta thấy mức thứ hai của đƣờng này: Đoạn mã của hàm Peano-Gosper-Generator: 53
void PeanoGosperGenerator(CDC *pDC, double X1, double Y1, double X2, double Y2, int Level, int Type, int NumLines, double LineLen, double Angles[ ]) double * XPoints ,*YPoints; int I; int Sign =1; double Thurtle_Theta,Thurtle_X,Thurtle_Y,Thurtle_R; XPoints = new double[NumLines + 1]; YPoints = new double[NumLines + 1]; Switch(Type) case 0: break; case 1: Sign*= -1; break; case 2: Sign*= -1; Case 3: Double Temp; Temp = X1; X1=X2; X2=Temp; Temp = Y1 ; Y1 = Y2 ; Y2=Temp; break ; Level; Turtle_R=sqrt((X2-X1)* (X2-X1)+ (Y2-Y1)* (Y2- Y1))*LineLen; XPoints[0]=X1; YPoints[0]=Y1; XPoints[NumLines]=X2; YPoints[NumLines]=Y2; Turtle_Theta=Point(X1,Y1,X2,Y2); TurtleX=X1; TurtleY=Y1; Turn(Angles[ 0 ]*Sign,Turtle_Theta); 54
for (I=1; I MoveTo((int)XPoints[ I ],(int) YPoints [ I ]); pDC->LineTo((int)XPoints[ I+1 ],(int) YPoints [ I+1 ]); delete[]XPoints; delete[]YPoints; 55
Hàm này cũng giống nhƣ hàm –Generator của đƣờng Gosper, chỉ khác là nó thêm hai tham số Sign và Type nhƣ trong họ các Generator phức tạp đƣợc trình bày trong phần Complex Von Kock Generator trƣớc. Ở đây NumLines = 7 và mảng Angles là: 19.1,60,120, 60, 120,0,0 □ ĐƯỜNG HOA TUYẾT PEANO 7-ĐOẠN: Hình sau là generator của đƣờng hoa tuyết Peano 7-đoạn (initiator là một đoạn nằm ngang): Đƣờng này đƣợc khám phá bởi Mandelbrot. Chú ý rằng tƣơng tự nhƣ generator sử dụng trong mục “Generator phức tạp” của họ đƣờng Von Kock đã trình bày ở phần II.1. Điểm khác nhau duy nhất là generator này không chứa các mô hình nhỏ hơn. Giả sử chiều dài từ đầu mút của generator đến đầu mút khác là 1, chúng ta tính chiều dài mỗi đoạn của generator. Ta thấy, generator có 7 đoạn, trong đó có 6 đoạn có chiều dài bằng nhau là R = 1/3, còn chiều dài của đoạn còn lại là: 3 R 3 (theo cách tính ở phần generator phức tạp). Do đó: D D 1 3 6 1 D 2 3 3 Hình sau cho chúng ta thấy mức thứ hai của đƣờng hoa tuyết Peano 7-đoạn này: 56
Đoạn mã của đƣờng hoa tuyết Peano 7-đoạn: void Peano7-DoanGenerator(CDC *pDC,double X1, double Y1•, double X2, double Y2, int Level, int Type, int Sign, int NumLines, double LineLen, double Angles[]) double * XPoints ,*YPoints; int I; double Thurtle_Theta,Thurtle_X,Thurtle_Y,Thurtle_R; XPoints = new double[NumLines + 1]; YPoints = new double[NumLines + 1]; Switch(Type) Case 0: break; case 1: Sign*= -1; break; case 2: Sign*= -1; Case 3: Double Temp; Temp = X1; X1=X2; X2=Temp; Temp = Y1 ; Y1 = Y2 ; Y2=Temp; break ; 57
Level; Turtle_R=sqrt((X2-X1)* (X2-X1)+ (Y2-Y1)* (Y2- Y1))*LineLen; XPoints[0]=X1; YPoints[0]=Y1; XPoints[NumLines]=X2; YPoints[NumLines]=Y2; Turtle_Theta=Point(X1,Y1,X2,Y2); Turtle_X=X1; Turtle_Y=Y1; Turn(Angles[ 0 ]*Sign,Turtle_Theta); for (I=1; I =NumLines -2; I) Step(Turtle_X, Turtle_Y, Turtle_R, Turtle_Theta); XPoints[ I ]=Turtle_X; YPoints[ I ]=Turtle_Y; Turn(Angles[ I ]*Sign,Turtle_Theta); if(Level) for (I=0; I<NumLines; ++I) switch(I) case 0: case 5: Type =1; break; case 1: case 2: case 3: case 6: 58
Type = 2; break; case 4: Type = 3; break; X1 = XPoints[ I ]; Y1 = YPoints[ I ]; X2 = XPoints[ I+1 ]; Y2 = YPoints[ I+1 ]; Peano7-DoanGenerator(pDC,X1,Y1,X2,Y2,Level,Type, Sign,NumLines,LineLen,Angles); else for (I= 0 ; I MoveTo((int)XPoints[ I ],(int) YPoints [ I ]); pDC->LineTo((int)XPoints[ I+1 ],(int) YPoints [ I+1 ]); delete[]XPoints; delete[]YPoints; Giống nhƣ trƣờng hợp generator phức tạp, có 4 khả năng lựa chọn cho các vị trí của generator và phải chọn một cách cẩn thận ở mỗi mức, mỗi đoạn thẳng để đảm bảo rằng đƣờng cong đƣợc tạo thành không tự giao nhau hay tự chồng lên nhau. Ở đây NumLines = 7 và mảng Angles là: 60,0, 60, 60, 60,0, 60 Tuỳ vào mức khác nhau thì tƣơng ứng với hình vẽ khác nhau. Sau đây là hình minh hoạ của đƣờng Peano 7-đoạn có mức là 4: 59
□ ĐƯỜNG HOA TUYẾT PEANO 13-ĐOẠN: Hình sau thể hiện generator của đƣờng hoa tuyết Peano 13-đoạn (initiator là một đoạn nằm ngang): Đƣờng này cũng đƣợc khám phá bởi Mandelbrot. Generator này thu đƣợc bằng cách thay thế đoạn thứ 5 của generator đƣờng hoa tuyết 7-đoạn với mô hình nhỏ hơn của toàn bộ generator đƣờng hoa tuyết 7 đoạn. Để tính số chiều fractal của đƣờng này, chúng ta sử dụng công thức ở mục về đƣờng hoa tuyết 7-đoạn. Do đó số chiều fractal của đƣờng này vẫn là 2. Hình sau cho chúng thấy mức thứ ba của đƣờng hoa tuyết Peano 13- đoạn này: 60
Đoạn mã của đƣờng hoa tuyết Peano 13-đoạn nhƣ sau: void Peano13-DoanGenerator(CDC *pDC, double X1, double Y1, double X2, double Y2, int Level, int Type, int Sign, int NumLines, double LineLen, double Angles[]) double * XPoints ,*YPoints; int I; int Split =5; double AngleSplit= 60; double Thurtle_Theta,Thurtle_X,Thurtle_Y,Thurtle_R; XPoints = new double[NumLines + 1]; YPoints = new double[NumLines + 1]; Switch(Type) Case 0: break; case 1: Sign*= -1; break; case 2: Sign*= -1; Case 3: Double Temp; Temp = X1; X1=X2; X2=Temp; Temp = Y1 ; Y1 = Y2 ; Y2=Temp; break ; Level; Turtle_R=sqrt((X2-X1)* (X2-X1)+ (Y2-Y1)* (Y2-Y1))*LineLen; XPoints[0]=X1; YPoints[0]=Y1; XPoints[NumLines]=X2; YPoints[NumLines]=Y2; Turtle_Theta=Point(X1,Y1,X2,Y2); Turtle_X=X1; Turtle_Y=Y1; 61
Turn(Angles[ 0 ]*Sign,Turtle_Theta); for (I=1; I =NumLines -2; I) Step(Turtle_X, Turtle_Y, Turtle_R, Turtle_Theta); XPoints[ I ]=Turtle_X; YPoints[ I ]=Turtle_Y; Turn(Angles[ I ]*Sign,Turtle_Theta); Turtle_R=sqrt((XPoints[NumLines -2] - XPoints[Split - 1]) * (XPoints[NumLines -2]- XPoints[Split -1]) + (YPoints[NumLines -2]- YPoints[Split -1])* (YPoints[NumLines -2]- YPoints[Split - 1]))*LineLen; Turtle_Theta= Point(XPoints[Split-1], YPoints[Split- 1], XPoints[NumLines -2], YPoints[NumLines -2]); Turtle_X=XPoints [Split-1]; Turtle_Y=YPoints [Split-1]; Turn(-AngleSplit*Sign,Turtle_Theta); for (I=Split ; I =9 ; I) Step(Turtle_X, Turtle_Y, Turtle_R, Turtle_Theta); 62
XPoints[ I ]=Turtle_X; YPoints[ I ]=Turtle_Y; Turn(Angles[ I ]*Sign,Turtle_Theta); if(Level) for (I=0; I MoveTo((int)XPoints[ I ],(int) YPoints [ I ]); pDC->LineTo((int)XPoints[ I+1 ],(int) YPoints [ I+1 ]); 63
delete[]XPoints; delete[]YPoints; Đối với đƣờng này cũng có 4 khả năng lựa chọn cho vị trí của generator và phải chọn một cách cẩn thận đối với mỗi mức, mỗi đoạn thẳng để đảm bảo rằng đƣờng cong tạo thành không tự giao nhau hay tự chồng lên nhau. Ở đây NumLines = 13 và mảng Angle là: 60,0, 60, 60, 60,0,60,60,60,0,60,0, 60 Tuỳ vào mức khác nhau thì tƣơng ứng với hình vẽ khác nhau. Sau đây là hình minh hoạ của đƣờng Peano 13-đoạn có mức là 5: II.3 ĐƯỜNG SIERPINSKI: Đƣờng Sierpinski đƣợc trình bày sau đây là một đƣờng cong rất đặc biệt, bởi vì có rất nhiều cách phát sinh ra nó với các khởi động ban đầu hoàn toàn khác nhau nhƣng lại kết thúc ở việc sinh ra một loại đƣờng cong duy nhất. Chúng ta đã quen với phƣơng pháp đầu tiên để phát sinh ra tam giác Sierpinski bằng cách sử dụng kỹ thuật initiator / generator đƣợc mô tả ở các phần trƣớc. Đối với đƣờng này, initiator là một đoạn thẳng. 64
Generator đối với đƣờng cong này và các đƣờng đƣợc sinh ra ở mức 1, 2 và 3 đƣợc minh hoạ nhƣ sau: Hình : Generator của tam giác Sierpinski m ức 2. Generator của tam giác Sierpinski Mức 1 Mức 3 Và đây là đƣờng Sierpinski ở mức 4 và 8: Mức 4 Mức 8 Để phát sinh ra đƣờng này ta dùng kỹ thuật giống nhƣ các đƣờng họ Von Kock và Peano. Đoạn mã của hàm Generator nhƣ sau: 65
void Generator_SierpinskiCurve(CDC *pDC, double X1, double Y1, double X2, double Y2, int Level, int Sign, int NumLines, doubleLinelen, double Angles[], COLORREF color) { CPen pen; pen.CreatePen(PS_SOLID,1,color); CPen* pOldPen=pDC->SelectObject(&pen); double *XPoints,*YPoints; int i; int Init_Sign; double Turtle_Theta,TurtleX,TurtleY,TurtleR; XPoints=new double[NumLines+1]; YPoints=new double[NumLines+1]; TurtleR=sqrt((X2-X1)*(X2-X1)+(Y2-Y1)*(Y2-Y1))*Linelen; XPoints[0]=X1; YPoints[0]=Y1; XPoints[NumLines]=X2; YPoints[NumLines]=Y2; Turtle_Theta=Point(X1,Y1,X2,Y2); TurtleX=X1; TurtleY=Y1; Turn(Angles[0]*Sign,Turtle_Theta); for(i=1;i<NumLines;i++) { Step(TurtleX,TurtleY,TurtleR,Turtle_Theta); XPoints[i]=TurtleX; YPoints[i]=TurtleY; Turn(Angles[i]*Sign,Turtle_Theta); } Level; Sign*=-1; if(Level) { Init_Sign=Sign; for(i=0; i<NumLines; i++) { X1=XPoints[i]; Y1=YPoints[i]; X2=XPoints[i+1]; Y2=YPoints[i+1]; Generator_SierpinskiCurve(pDC, X1, Y1, X2, Y2, Level, Init_Sign, NumLines, Linelen, Angles, color); Init_Sign*=-1; } } 66
else for(i=0;i MoveTo((int)XPoints[i],(int)YPoints[i]); pDC->LineTo((int)XPoints[i+1],(int)YPoints[i+1]); } pDC->SelectObject(pOldPen); delete []XPoints; delete []YPoints; } Với Num-line = 3 và mảng Angle là [60, -60, 0 ]. II.4 CÂY FRACTAL: Trong các phần trƣớc, chúng ta đã tạo ra các đƣờng fractal bằng cách thay thế một cách lặp lại của các đoạn thẳng với các mẫu thu nhỏ của một generator mẫu, kết quả là các đƣờng có tính tự đồng dạng. Bây giờ, chúng ta sẽ tạo ra đƣờng cong theo một hƣớng khác. Chúng ta sẽ bắt đầu với một thân cây tại đầu mút của nó chúng ta tách thân cây thành hai hƣớng và vẽ hai nhánh. Chúng ta sẽ lặp lại quá trình này tại các đầu mút của mỗi nhánh. Kết quả chúng ta sẽ đƣợc một cây. Trƣớc khi chúng ta biểu diễn các cây tự nhiên, đầu tiên chúng ta thảo luận vài điều về các cây thực tế. □ CÁC CÂY THỰC TẾ: Chúng ta phác thảo quá trình tạo cây đƣợc cho ở trên. Tại mỗi nút trong quá trình tạo cây, chúng ta tách làm hai hƣớng. Kết quả ta đƣợc một cây hai chiều. Chúng ta hy vọng nó có một số quan hệ với cây thực tế 3 chiều. Trƣớc khi đi xa hơn, chúng ta quan sát một vài cây tự nhiên. Đầu tiên, có hai lớp cây là lớp cây rụng lá (deciduous) mỗi năm và lớp cây tùng bách (conifers). Hai lớp cây này hoàn toàn khác nhau. Cây tùng bách có khuynh hƣớng có các vòng của các nhánh ở tại các độ cao khác nhau vòng quanh trung tâm của thân cây. Điều này dƣờng nhƣ không thích hợp với tất cả các quá trình rẽ nhánh nhị phân và chúng ta sẽ thấy các cây sau đây do chúng phát sinh không bao giờ giống với cây tùng bách thật sự. Thứ hai, đối với cây rụng lá mặc dù sự xuất hiện của chúng rất gần với mô hình của chúng ta, thế nhƣng vẫn còn rất nhiều phức tạp trong cấu trúc của chúng. Trong khi đó, việc rẽ nhánh nhị phân thƣờng có qui luật và đơn giản hơn nhiều, chỉ ngoại trừ một vài thân cây có khả năng tách ra nhiều hơn hai nhánh. □ BIỂN DIỄN TOÁN HỌC CỦA CÂY: Theo Leonardo da Vinci quan sát, kết quả đó là do tổng số các vùng cắt ngang của các nhánh cây ở một độ cao cho trƣớc là hằng số. Điều này không 67
gây ngạc nhiên vì cây đòi hỏi chuyển dinh dƣỡng từ gốc đến lá và cho trƣớc một lƣợng dinh dƣỡng, một ngƣời nghĩ rằng thiết diện cần thiết cho sự vận chuyển sẽ không đổi bất kể chiều cao hay số ống dẫn. Khi chúng ta chuyển sự quan sát này vào các đƣờng kính (hay các chiều rộng khi chúng ta vẽ thành cây hai chiều ) thì chúng ta có đƣợc biểu thức sau: Ở đây D0, D1, D2 là đƣờng kính của hai nhánh chia cây làm đôi, = 2 theo da Vinci. Do đó các dạng các dạng cấu trúc giống cây, mô hình đơn giản đƣợc cho ở trên có khả năng áp dụng cho các hệ thống sông tốt hơn các cây, vì thƣờng có nhiều hơn hai con sông nhánh của một hệ thống sông sẽ nối với nhau ở cùng một nơi. Các cây khác đƣợc tìm thấy trong cơ thể con ngƣời là hệ thống động mạch và cuống phổi dùng để vận chuyển máu và oxy, trong đó đối với hệ thống cuống phổi là 3 và đối với động mạch là 2.7. Khi chúng ta xây dựng cây chúng ta sẽ sử dụng biểu thức: 1 B 2 B (a) n 1 n Ở đây Bn là đƣờng kính của nhánh ở mức thấp hơn. Bn+1 biểu diễn đƣờng kính mỗi nhánh con khi Bn tách thành hai nhánh. Chúng ta cũng cần xem xét chiều dài mỗi nhánh. McMahon nghiên cứu các loại cây kiểu mẫu khác nhau và đƣa ra công thức nhƣ sau cho chiều dài: 2 (b) L 23 L n 1 n Với Ln là chiều dài của nhánh trƣớc đó và Ln+1 chiều dài của mỗi nhánh trong hai nhánh kế sau khi nhánh trƣớc đó đƣợc tách ra làm hai. Để tạo thành một cây, ở đây chúng ta sử dụng đồ hoạ con rùa. Gọi: (X,Y) là toạ độ của gốc cây. Height, Width là chiều cao và chiều rộng của cây. Letf_Alpha, Right_Alpha là góc Alpha bên trái và góc Alpha bên phải. Left_Angle, Right_Angle là góc rẽ bên trái và góc rẽ bên phải của nhánh. Level là mức của cây. Color1 là màu của thân cây. Color2 là màu của tƣớc cây. Color3 là màu của lá cây. Thuật toán: 68
(i) Tính các hệ số: + Chiều rộng trái và phải theo công thức (a). Left_Width_Factor = pow (2, -1.0 / Left_Alpha ); Right_Width_Factor = pow (2, -1.0 / Right_Anpha ); + Chiều cao trái và phải theo công thức (b) Left_Height_Factor = pow (2, -2.0 / (3 * Left_Alpha)); Right_Height_Factor = pow (2, -2.0 / (3 * Right_Alpha)); (ii) Xác định toạ độ ngọn của thân cây: X1 = X; Y1 = Y + Height; (iii) Vẽ thân cây từ (X, Y) đến (X1, Y1) với màu Color1 và chiều rộng là Width. DrawLine (X, Y, X1,Y1, Color1, Width); (iv) Phát sinh nhánh bên trái: a) Xác định gốc giữa thân cây và trục x (tức là góc của con rùa) Turtle_Theta = Point (X, Y, X1, Y1); b) Quay con rùa về phía bên trái một góc Left Turn (Left_Angle, &Turtle_Theta); c) Sau đó gọi hàm Generator để phát sinh ra nhánh bên trái. Generator (X1, Y1,Left_Width_Factor * Width, Left_Height_Factor * Height, Level); v) Phát sinh bên nhánh bên phải: a) Xác định gốc giữa thân cây và trục x (tức là góc của con rùa) Turtle_Theta = Point (X, Y, X1, Y1); b) Quay con rùa về phía phải một góc Right_Angle Turn (-Right_Angle, &Turtle_Theta); c) Sau đó gọi hàm Generator để phát sinh ra nhánh bên phải Generator (X1, Y1, Right_Width_Factor * Width, Right_Height_Factor * Height, Level); Hàm Generator có đoạn mã nhƣ sau: Generator (float X, float Y,float Width, float Height, unsigned char Level) { (i) Xác định vị trí con rùa hiện tại và chiều dài một bƣớc của con rùa Turtle_X = X; Turtle_Y = Y; Turtle_R = Height; (ii) Xác định ngọng của tƣớc mới phát sinh và giảm mức đi một đơn vị. Step (&Turtle_X, &Turtle_Y, Turtle_R, Turtle_Theta); 69
X2 = Turtle_X; Y2 = Turtle_Y; Level ; (iii) Vẽ đoạn thẳng từ (X, Y) đến (X2, Y2) với độ rộng là Width và màu đƣợc xác định nhƣ sau: + Nếu Level = 3 thì màu hiện thời là Color3. If (Level 0 thì chúng ta tiếp tục phân làm hai nhánh trái và phải. if (Level > 0) { Turtle_Theta = Point(X, Y, X2, Y2); Turtle (Left_Angle, &Turtle_Theta); Generator (Turtle_X, Turtle_Y, Left_Width_Factor * Width, Left_Height_Factor * Height, Level ) Turntle_Theta = Point (X, Y, X2, Y2); Turn (- Right_Angle, &Turtle_Theta); Generator (X2, Y2, Right_Width_Factor * Width, Right_Height_Factor * Height, Level); } } Sau đây là hình minh hoạ một cây fractal với Level = 14, Height = 80, Width = 20, Left_Alpha = 2.0, Right_Alpha = 2.2, Left_Angle = 20, Right_Angle = 28. 70
II.5 PHONG CẢNH FRACTAL: Trong phần này chúng ta sẽ tạo ra phong cảnh fractal bằng cách sử dụng thay thế trung điểm. Các hình vẽ sau cho chúng ta thấy những bƣớc đầu tiên trong quá trình thay thế trung điểm: Hình (a) Hình (b) Hình (c) 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à trung đ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. Kết quả của quá trình này là sự thay thế tam giác ban đầu bằng 4 tam giác mới. Sau đó, chúng ta lại áp dụng quá trình xử lý trên mỗi một trong 4 tam giác mới này, lúc đó ta sẽ thu đƣợc từ 4 tam giác con 18 tam giác nhƣ hình vẽ (c). Điều gì sẽ xảy ra khi chúng ta có hai tam giác có chung một cạnh, ngay cả khi bắt đầu với tam giác đơn, trạng thái này vẫn xuất hiện sau bƣớc đầu tiên. Lúc đó chúng ta có cách giải quyết nhƣ sau: Sự thay thế của cạnh chung đối với tam giác đầu tiên đƣợc hƣớng về phía bên trong tam giác này, còn sự thay thế của cạnh chung đối với tam giác thứ hai đƣợc hƣớng về phía bên trong trong tam giác đó. Nếu chúng ta giả sử đây là mức thấp nhất và lấp đầy các tam giác kết quả với một màu nào đó, thì 71
hiển nhiên mhận thấy rằng có một lổ hở không đƣợc lấp đầy. Có hai cách để giải quyết vấn đề này nhƣ sau: 72
Cách thứ nhất: Cách này do Michael Batty đƣa ra. Ở mỗi mức của quá trình đệ qui, ngoại trừ mức thấp nhất ông ta đã tạo ra một tam giác nhỏ hơn tam giác ban đầu và tô nó bằng một màu. Hy vọng rằng tam giác này đủ nhỏ sao cho nó không che các mặt không đều theo ý muốn đƣợc tạo bởi quá trình thay thế trung điểm nhƣng nó đủ lớn sao cho nó tô đƣợc miền mà lổ hỏng sẽ phải xảy ra ở mức kế tiếp trở xuống của quá trình. Cách thứ hai: Sử dụng các toạ độ của trung điểm không đƣợc thay thế của đƣờng để tạo ra một số duy nhất. Số này đƣợc sử dụng nhƣ hạt giống cho bộ phát sinh số ngẫu nhiên của máy tính để từ đó phát sinh ra các số ngẫu nhiên cho sự thay thế dọc theo trung trực của đoạn thẳng tƣơng ứng. Khi đƣờng trung trực này xuất hiện trong tam giác khác, vì trung điểm không đƣợc thay thế vẫn có cùng toạ độ hạt giống cho bộ phát sinh số ngẫu nhiên sẽ giống nhau và sự thay thế sẽ giống nhau, vì thế không có khả năng xảy ra lổ hỏng. Chƣơng trình sau tạo ra phong cảnh cây xƣơng rồng trong hẻm núi đá gần Sedona, Arizona. Để tạo đƣợc cảnh nhƣ thế, chúng ta dựa vào hình sau: Khuôn cảnh trên để tạo nên hẻm núi đá ở Sedona, Arizano Gọi toạ độ cửa sổ thực XWMin, YWMin, XWMax, YWMax Sau đây là đoạn mã tạo ra phong cảnh này: Y_Max = 280; double Level[22]=( 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4); double X1[22]={-330, -90, -90, 120, 120, 120, -160, -120, -120, -80, -80, -50, -50,-50 , 80, 104, 104, 128, 128, 152, 152, 200}; 73
double Y1[22]={-110, -110, -110, -110, -110, -110, -10, -10, -10, -10, -10, -10, -10,-10 , 50, 50, 50, 50, 50, 50, 50, 50}; double X2[22]={-160, -160, 0, 0, 80, 200, -160, -160, -120, -120, -80, -80, -50, 0,100, 100, 104, 104, 128, 128, 152, 152}; double Y2[22]={0, 0, 0, 0, 50, 50, 220, 220, 190, 190, 230, 230,100, 180, 180,180,200, 205,215, 215, 160, 160 }; double X3[22]={-90, 0, 120, 80, 200, 340, -120, -120, -80, -80, -50, -50, 0, 0, 104,104, 128, 128, 152, 152, 200, 200}; double Y3[22]={-110, 0, -110, 50, 50, -110, -10, 220, -10, 200, -10, 235, 180, -10, 50, 200, 50, 210, 50, 220, 50, 140}; for(I=0 ; I<22 ; ++I) Generate(X1[ I ],Y1[ I ], X2[ I ],Y2[ I ], X3[ I ],Y3[ I ],Level[ I ],4,12); Y_Max= -100; Gen_Quad(-330, -260, -330, -100, 330, -100, 330, -260, 4, 6,14); Cactus(-110, -130, 3, 4, 2, 10); Cactus(-200, -120, 2, 4, 2, 10); Cactus(0, -160, 4, 4, 2, 10); Cactus(210, -200, 6, 4,2,10); Trong đó các hàm có đoạn mã sau: void Node(double X1, double Y1, double X2, double Y2, double X3, double Y3, double X4, double Y4, double X5, double Y5, double X6, double Y6, unsigned char Level, int Color1, int Color2) { if(!Level) return; Generate(X1,Y1, X4,Y4, X6,Y6,Level-1,Color1,Color2); Generate(X6,Y6, X5,Y5, X3,Y3,Level-1,Color1,Color2); Generate(X4,Y4, X2,Y2, X5,Y5,Level-1,Color1,Color2); Generate(X4,Y4, X5,Y5, X6,Y6,Level-1,Color1,Color2); } void Generate(double X1, double Y1, double X2, double Y2, double X3, double Y3, unsigned char Level, int Color1, int Color2) { double X4,Y4,X5,Y5,X6,Y6,Ax,Ay,Bx,By,Cx,Cy; X=X2-X1; Y=Y2-Y1; MidPoint(); X4=X1+Xz-Xp; 74
Y4=Y1+Yz-Yp; Ax=-Xp; Ay=-Yp; X=X3-X1; Y=Y3-Y1; MidPoint(); X6=X1+Xz; Y6=Y1+Yz; Cx=Xp; Cy=Yp; X=X3-X2; Y=Y3-Y2; MidPoint(); X5=X2+Xz; Y5=Y2+Yz; Bx=-Xp; By=-Yp; if(Level) { PlotTriange(X1,Y1,X4+Ax,Y4+Ay,X6+Cx,Y6+Cy,Color1,Color2); PlotTriange(X6+Cx,Y6+Cy,X5+Bx,Y5+By,X3,Y3,Color1,Color2); PlotTriange(X4+Ax,Y4+Ay,X5+Bx,Y5+By,X6+Cx,Y6+Cy,Color1, Color2); PlotTriange(X4+Ax,Y4+Ay,X2,Y2,X5+Bx,Y5+By,Color1,Color2); Node(X1,Y1,X2,Y2,X3,Y3,X4,Y4,X5,Y5,X6,Y6,Level, Color1, Color2); } else { PlotTriange(X1,Y1,X4,Y4,X6,Y6,Color1,Color2); PlotTriange(X6,Y6,X5,Y5,X3,Y3,Color1,Color2); PlotTriange(X4,Y4,X5,Y5,X6,Y6,Color1,Color2); PlotTriange(X4,Y4,X2,Y2,X5,Y5,Color1,Color2); } } void PlotTriange(double X1, double Y1, double X2, double Y2, double X3, double Y3, int Color1, int Color2) { int Color; double C1=0.35; double C2=0.92; double Ytt,Zt; 75
Ytt=(Y1>Y2)?Y1:Y2; if(Ytt (C2*(Y_Max+YWMax))) Color=Color2; FillTriange(X1,Y1, X2,Y2, X3,Y3,Color); //Lấp đầy tam giác với màu Color } void MidPoint() { double R,W,C=1.0/2; double Lstart1=0,Lend1=1.0/6; double Lstart2=0.03,Lend2=0.07; R=C+Random_No(LStart1,LEnd1); W=Random_No(LStart2,LEnd2); Xz=R*X-W*Y; Yz=R*Y-W*X; C=0.05; Xp=C*Y; Yp=-C*X; } double Random_No(double LimitStart,double LimitEnd) { int Half=MAXINT/2; LimitEnd-=LimitStart; LimitEnd=Half/LimitEnd; Double Result=(rand() - half)/LimitEnd; if(Result >= 0) Result+=LimitStart; else Result-=LimitStart; Return Result; } void Gen_Quad(double X1, double Y1, double X2, double Y2, double X3, double Y3, double X4, double Y4, unsigned char Level, int Color1, int Color2) 76
{ Generate(X1,Y1, X2,Y2, X3,Y3,Level,Color1,Color2); Generate(X1,Y1, X4,Y4, X3,Y3,Level,Color1,Color2); } void Cactus(double X1, double Y1, int Scale, unsigned char Level, int Color1, int Color2) { Gen_Quad(X1, Y1, X1, Y1+21*Scale, X1+1.6*Scale, Y1+22*Scale, X1+1.6*Scale,Y1,Level,Color1,Color2); Gen_Quad(X1+1.4*Scale, Y1, X1+1.4*Scale, Y1+22*Scale, X1+3*Scale, Y1+21*Scale,X1+3*Scale, Y1,Level,Color1,Color2); Gen_Quad(X1, Y1+9*Scale, X1+7*Scale, Y1+9*Scale, X1+7*Scale,Y1+12*Scale,X1, Y1+12*Scale, 0, Color1,Color2); Gen_Quad(X1, Y1+9*Scale, X1+6*Scale, Y1+9*Scale, X1+7*Scale,Y1+12*Scale,X1, Y1+12*Scale, Level,Color1,Color2); Gen_Quad(X1+7*Scale, Y1+9*Scale, X1+7*Scale, Y1+16*Scale, X1+8.5*Scale, Y1+17*Scale, X1+8.5*Scale, Y1+9*Scale, Level, Color1, Color2); Gen_Quad(X1+8.4*Scale, Y1+9*Scale, X1+8.4*Scale, Y1+16*Scale,X1+10*Scale, Y1+17*Scale, X1+10*Scale,Y1+10*Scale, Level, Color1,Color2); Gen_Quad(X1, Y1+7*Scale, X1-6*Scale, Y1+7*Scale, X1 - 6*Scale, Y1+10*Scale, X1, Y1+10*Scale,0, Color1,Color2); Gen_Quad(X1, Y1+7*Scale, X1-6*Scale, Y1+7*Scale, X1 -6*Scale,Y1+10*Scale, X1,Y1+10*Scale, Level,Color1,Color2); Gen_Quad(X1-7*Scale, Y1+8*Scale, X1-7*Scale, Y1+12*Scale, X1+5.4*Scale, Y1+13*Scale, X1+5.4*Scale, Y1+7*Scale, Level,Color1,Color2); Gen_Quad(X1-5.6*Scale, Y1+7*Scale, X1-5.6*Scale, Y1+13*Scale, X1-4*Scale, Y1+12*Scale, X1- 4*Scale, Y+7*Scale, Level,Color1,Color2); } Để vẽ phong cảnh này, chúng ta sử dụng kỹ thuật lấp đầy tam giác đƣợc chia nhỏ của Michael Batty ở các giai đoạn trung gian nhằm tránh các lổ hỏng. Đầu tiên, chúng ta xem qua hàm Generator. Hàm này xác định chiều dài theo hƣớng x và y cho mỗi đoạn của tam giác có toạ độ (X1, Y1), (X2, Y2), 77
(X3,Y3), sau đó gọi hàm MidPoint để xác định các phép thay thế trung điểm theo hƣớng x và y. Toạ độ của trung điểm thay thế đƣợc lƣu trữ và các phép thay thế cần xác định một tam giác đƣợc chia nhỏ và lấp đầy ở mức trên mức thấp nhất, các đỉnh của tam giác này đƣợc lƣu trữ trong các vị trí Ax, Ay, Bx, By, Cx, Cy. Nếu chúng ta ở mức thấp nhất (mức 0), hàm này gọi hàm PlotTriange để xác định màu lấp đầy và thực hiện việc lấp đầy 1 trong 4 tam giác mới, nếu mức thấp nhất chƣa đạt đến, nó sẽ gọi hàm PlotTriange để lấp đầy 1 trong 4 tam giác đƣợc chia nhỏ và sau đó gọi hàm Node, hàm này gọi đệ quy hàm Generator để phát sinh ra 4 tam giác mới từ 1 trong 4 tam giác vừa đƣợc tạo ra. Đối với hàm Node, nếu Level = 0 thì thoát, còn đối với các trƣờng hợp khác thì nó gọi hàm Generator cho lần lƣợt từng tam giác trong 4 tam giác vừa đƣợc tạo thành. Hàm Gen_Quad chỉ chạy Generator đối với hai tam giác tạo thành một hình thang. Hàm Random_No đƣợc sử dụng trong việc xác định thay thế ngẫu nhiên, hàm có 2 tham số giới hạn trên và dƣới (Cả 2 giá trị này đều là số dƣơng) của số ngẫu nhiên đƣợc phát sinh. Số ngẫu nhiên trả về sẽ là số âm nằm giữa hai giá trị âm của hai số giới hạn hoặc dƣơng nằm giữa hai giá trị dƣơng của hai số giới hạn. Còn hàm MidPoint ban đầu lấy số ngẫu nhiên và đƣợc chọn biểu diễn cho việc thay thế trung điểm dọc theo đƣờng trung trực với khoảng cách theo chiều x đƣợc lƣu trữ trong giá trị X và khoảng cách theo chiều y đƣợc lƣu trữ trong giá trị Y. Khoảng cách này bằng nửa độ dài cạnh ứng với trung trực cộng hay trừ với một giá trị ngẫu nhiên giữa 0 và 1/6 lần chiều dài cạnh đó. Kế đến chúng ta tính độ dịch chuyển vuông góc với cạnh này. Nó bằng độ dài cạnh đang xét nhân với một số ngẫu nhiên giữa 0.03 và 0.07 hay giữa -0.07 và 0.03. Hàm PlotTriange có các tham số là 3 đỉnh của tam giác và hai giá trị màu, nó dùng biến Y_Max là giá trị độ cao điều khiển việc chọn lựa màu. Đầu tiên hàm này chọn giá trị y của đỉnh cao nhất trong tam giác. Sau đó nó tạo biến Zt theo công thức: 2 Ytt YWMax Zt (Y _ Max YWMax) 1 Y _ Max YWMax Với Y_Max là độ cao điều khiển và Ytt là độ cao của đỉnh cao nhất của tam giác. Khi giá trị Zt đã đƣợc xác định, hàm PlotTriange sẽ chọn một số ngẫu nhiên giữa 0 và Y_Max rồi so sánh giá trị này với Zt. Nếu giá trị này nhỏ hơn 78
hay bằng Zt, màu thứ nhất sẽ đƣợc chọn, ngƣợc lại màu thứ hai đƣợc chọn. Cuối cùng nếu độ cao Ytt dƣới giới hạn đƣợc chọn thì màu đƣợc chọn là màu thứ nhất, ngƣợc lại chọn màu thứ hai. Sau đó hàm này gọi hàm FillTriange để lấp đầy tam giác với màu đƣợc chọn. Hàm Cactus có các tham số là các toạ độ, hệ số vị tự, mức và hai màu. Nhiệm vụ của nó là phát sinh ra các cây xƣơng rồng. Đoạn mã chạy phong cảnh ở trên bắt đầu là chạy vòng for để gọi hàm Generator 22 lần để tạo ra vách đá màu đỏ. Sau đó gọi hàm Gen_Quad để vẽ nền sa mạc màu vàng và màu nâu, cuối cùng nó gọi hàm Cactus bốn lần để tạo 4 cây xƣơng rồng với các vị trí và kích thƣớc khác nhau. Bức tranh hẻm núi đá đƣợc thực hiện bằng kỹ thuật tạo phong cảnh fractal. II.6 HỆ THỐNG HÀM LẶP (IFS) □ CÁC PHÉP BIẾN ĐỔI AFFINE TRONG KHÔNG GIAN R2 Cho phép biến đổi w: IR2 IR2 có dạng: w (x, y) = (ax + by + e, cx + dy + f) Ở đây a, b, c, d, e, f là các hệ số thực, đƣợc gọi là phép biến đổi affine (hai chiều). Phép biến đổi có thể viết dƣới dạng: x a b x e w AX T y c d y f Với: a b x e A , X ,T c d y f 79
Bằng cách biểu diễn phép biến đổi trên dƣới dạng tách các phép quay và vị tự ma trận A có thể viết dƣới dạng: r cos ssin A r sin scos Với: r: hệ số vị tự trên trục x. s: hệ số vị tự trên trục y. : góc quay trên trục x. : góc quay trên trục y. e: hệ số tịnh tiến trên trục x. f: hệ số tịnh tiến trên trục y. □ IFS CỦA CÁC PHÉP BIẾN ĐỔI AFFINE TRONG KHÔNG GIAN R2: Một IFS là tập hợp các phép biến đổi affine co tức là: 2 IFS { IR ; wn : n = 1, 2, , N } với wn là phép biến đổi affine. Ví dụ: 2 Một IFS của ba phép biến đổi w1, w2, w3 là IFS { IR ; w1, w2, w3 } với w1, w2, w3 xác định bởi: x 0.5 0 x 0 w 1 y 0 0.5 y 0 x 0.5 0 x 1 w 2 y 0 0.5 y 0 x 0.5 0 x 0.25 w 3 y 0 0.5 y 0.25 Trong đó mỗi phép biến đổi affine liên kết với một xác xuất Pn quyết định độ quan trọng của nó so với phép biến đổi khác. Để ý rằng: N Pn 1, Pn 0(n 1, , N) n 1 Ví dụ: Mã IFS đối với tam giác Sierpinski 80
w a b c d e f p 1 0.5 0 0 0.5 0 0 0.33 2 0.5 0 0 0.5 1 0 0.33 3 0.5 0 0 0.5 0.5 0.5 0.34 □ GIẢI THUẬT LẶP NGẪU NHIÊN: 2 Cho IFS [IR ; wn : n = 1, 2, , N ] , mỗi wn liên kết với xác xuất Pn. Trƣớc khi trình bày thuật toán, chúng ta tìm cách chọn các xác xuất Pn thích hợp. Khi chúng ta xác định các phép biến đổi, chúng ta cần chọn các xác xuất cho chúng. Việc chọn các xác xuất khác nhau sẽ không dẫn đến các hấp tử khác nhau, nhƣng chúng ảnh hƣởng đến tốc độ ở các miền khác nhau hay thuộc tính của hấp tử đƣợc làm đầy. Mỗi phép biến đổi affine wn tƣơng ứng với hấp tử J là: x an bn x en wn ,n 1,2, ,N y cn dn y fn Số lần mà điểm nhảy một cách ngẫu nhiên dùng trong hấp tử con wn xấp xỉ với: s wn s j Với S(A): Diện tích của A Nếu detAn 0 thì việc chọn xác xuất Pn nhƣ sau: det A a d b c P n n n n n n N N det A a d b c i 1 i i 1 i i i i Nếu detAn = 0 thì Pn đƣợc gán cho một số nhỏ nhất và khá gần 0, ví dụ nhƣ 0.001. Sau đây là các bảng mã IFS: 81
Mã IFS cho lá dƣơng xỉ: W A b C d E f p 1 0 0 0 0.16 0 0 0.01 2 0.2 -0.26 0.23 0.22 0 1.6 0.07 3 -0.15 0.28 0.26 0.24 0 0.44 0.07 4 0.85 0.04 -0.04 0.85 0 1.6 0.85 Thuật toán lặp ngẫu nhiên: (i) Khởi động các giá trị x = 0; y = 0; (ii) for (i = 1; i < number_iterates; ++i) { + Chọn k là một trong số 1, 2, , N + Áp dụng phép biến đổi wk cho điểm (x, y) ta thu đƣợc diểm (x~,y~). + Đặt (x, y) bằng điểm mới x = x~; y = y~; + putpixel(x, y, color); } Tƣơng tự chúng ta áp dụng thuật toán này đối với IFS của phép biến đổi affine trong không gian ba chiều có dạng: x a b c x n ax by cz n w y d e f y q dx ey fz q z g h m z r gx hy mz r Mã IFS cho lá dƣơng xỉ ba chiều: w A B c D E f G h m n q r P 1 0 0 0 0 0.18 0 0 0 0 0 0 0 0.001 2 0.83 0 0 0 0.86 0. 0 -0.12 0.84 0 1.62 0 0.901 1 3 0.22 -0.23 0 0.2 0.22 0 0 0 0.32 0 0.82 0 0.049 4 4 0.22 0.23 0 0.2 0.22 0 0 0 0.32 0 0.82 0 0.049 4 82
Sau đây là các hình vẽ minh hoạ giải thuật lặp ngẫu nhiên tƣơng ứng với bảng mã IFS đƣợc trình bày ở phần trƣớc: Lá dƣơng xỉ 2 chiều Lá dƣơng xỉ 3 chiều II.7 TẬP MANDELBROT □ Đặt vấn đề: Trong nhiều thập niên của thế kỷ XX, các nhà toán học đã để tâm nghiên cứu đến một loại biểu thức phức tạp xác định bởi: 2 zn+1 = zn + c, trong đó zi C, i N & c C (1) Để đơn giản hoá vấn đề, trƣớc hết ta xét trƣờng hợp c = 0 và z0 R. Khi đó có 3 trƣờng hợp sau: + z0 = 1 : khi đó zn = 1, n 1. + z0 1 : khi đó zn khi n . Ở đây tốc độ tiến đến 0 hay tiến đến của dãy (zn) đƣợc quyết định bởi giá trị ban đầu z0 của dãy. Trong trƣờng hợp z0 1, giá trị z0 càng lớn thì dãy (zn) càng tiến nhanh ra . Trong trƣờng hợp tổng quát, dãy (zn) đƣợc xác định bởi công thức (1) ở trên rất khó khảo sát về mặt lý thuyết. Chỉ đến năm 1979, Mandelbrot mới thành công trong việc quan sát dãy này với sự hỗ trợ của máy tính điện tử. Kết quả đƣợc Mandelbrot quan sát thấy là một trong những cấu trúc fractal phức tạp và đẹp. Nó đã đƣợc đặt tên Mandelbrot để ghi nhớ công lao của tác giả, ngƣời đã khai sinh ra lý thuyết hình học phân hình. □ CÔNG THỨC TOÁN HỌC: Ký hiệu zn = ( xn , yn), c = (p,q), trong đó: 83
xn = Re(zn), p = Re(c), yn = Im(zn), q = Im(c), n 0 thì hệ thức truy hồi xác định ở (1) có thể đƣợc viết lại theo dạng đơn giản hơn nhƣ sau: 2 2 xn+1 = xn – yn + p yn+1 = 2xn .yn + q (2) Ngoài ra khi khảo sát dãy (zn) ta tìm đƣợc tính chất sau: Tính chất về sự hội tụ của dãy (zn): - Nếu tồn tại k N sao cho | zk | > 2 thì dãy (zn) hội tụ đến vô cực. - Nếu tồn tại k N sao cho | zt | 2 ở một ngƣỡng k hữu hạn nào đó. Vấn đề đặt ra ở đây là cần quan sát tính hỗn độn của dãy (zn). Do đó chúng ta tập trung các quan sát vào các giá trị c thuộc lớp 2. Muốn nhƣ vậy các 84
giá trị này phải đƣợc thực hiện một cách nổi bật trên màn hình máy tính bởi các màu khác nhau. Chúng ta sẽ tô màu mặt phẳng phức màn hình theo qui tắc sau: + Các giá trị c thuộc lớp 1 đƣợc tô màu đen vì không có tính chất gì đáng chú ý. + Các giá trị c thuộc lớp 2 đƣợc tô bằng các màu khác nhau ứng với các ngƣỡng tiến ra vô hạn k khác nhau. Do số lƣợng màu có thể hiển thị trên một màn hình đồ hoạ là hữu hạn, việc tô màu các giá trị này sẽ đƣợc thực hiện theo kỹ thuật tô màu xoay vòng đƣợc chỉ ra ở các phần tiếp sau đây. 2. Thuật toán tổng quát để thể hiện tập Mandelbrot: Thuật toán gồm các bƣớc sau: - Bƣớc 1: Xuất phát với một giá trị khởi đầu c = (p,q). - Bƣớc 2: Kiểm tra c thuộc lớp 1 hay lớp 2. - Bƣớc 3: Nếu c thuộc lớp 1 thì tô điểm ảnh tƣơng ứng với c trên màn hình bằng màu đen, ngƣợc lại tô điểm ảnh này bởi màu tƣơng ứng xác định từ kỹ thuật tô xoay vòng. - Bƣớc 4: Chọn một giá trị c mới và trở lại bƣớc 1 cho đến khi quét hết toàn bộ giá trị c cần khảo sát (đôi khi chúng ta không cần khảo sát toàn bộ mà chỉ khảo sát một miền con đƣợc yêu cầu của mặt phẳng phức). Khi đó thuật toán kết thúc. Bây giờ ta ký hiệu: + Max_Iterations là số lần lặp tối đa cần có để kiểm tra giá trị c thuộc lớp 1 hay lớp 2 (chính là giá trị 1 đƣợc đề cập trong định nghĩa của lớp 1). + Count là số lần lặp đã thực hiện (giá trị này tƣơng ứng với một ngƣỡng tiến ra vô hạn k đƣợc nêu ra trong định nghĩa lớp 2). + Miền con của mặt phẳng phức cần khảo sát là một cửa sổ hình chữ nhật đƣợc mô tả bởi toạ độ góc trái bên dƣới (Xmin , Ymin) và toạ độ góc phải trên (Xmax , Ymax) (theo hệ trục toạ độ thông thƣờng). Khi đó mối liên hệ giữa hệ trục toạ độ phức thực tế với hệ toạ độ nguyên trên màn hình máy tính đƣợc x thể hiện bởi hình 11.1 dƣới đây: 85
q (Xmax, Ymax) (0,0) Col Thể hiện trên (Xmin, Ymin) màn hình (Max_Col,Max_Row) p Row Vùng khảo sát là 1 miền con của Hệ toạ độ nguyên trên máy mặt phẳng phức biểu biễn giá trị c tính với chiều dƣơng ngƣợc chiều thực tế. Hình 11.1 Theo hình này, điểm bắt đầu (0, 0) trên màn hình máy tính sẽ tƣơng ứng với giá trị c = (Xmin , Ymax), điểm kết thúc (Max_Col, Max_Row), trong đó Max_Col x Max_Row thể hiện độ phân giải của mode đồ hoạ hiện thời của màn hình (ví dụ với mode VGA 16 màu ta có Max_Col = 604, Max_Row = 480), sẽ tƣơng ứng với điểm c = (Xmax , Ymax). Do đó nếu ký hiệu: p là lƣợng gia tăng theo theo trục thực của giá trị p ứng với mỗi cột trên màn hình. q là lƣợng gia tăng theo trục ảo của giá trị q ứng với mỗi hàng trên màn hình thì: X X p max min Max _ Col Ymax Ymin q Max_ Row Khi đó một số phức c = (p, q) ứng với một điểm ảnh có toạ độ màn hình là (Col, Row) sẽ đƣợc xác định bởi: p = Xmin + Col. p q = Ymax – Row. q Có thể kiểm tra là khi Col, Row biến thiên theo chiều tăng đến các giá trị tƣơng ứng Max_Col, Max_Row, chúng ta cũng có p biến thiên từ Xmin đến Xmax và q biến thiên từ Ymax xuống Ymin , đúng nhƣ yêu cầu về quan hệ giữa hệ 86
toạ độ phức sử dụng trong toán học với hệ toạ độ hiển thị của màn hình đã đƣợc nêu trong Hình 11.1. Việc kiểm tra c thuộc lớp 1 hay 2 đƣợc viết dƣới dạng: if (Count > Max_Iterations) & (Modul (Zcount) 2 )) c thuộc lớp 2 Đồng thời màu tô cho một điểm c = (p, q) thuộc lớp 2 đƣợc tính toán theo công thức: Màu tô (p, q) = Count(p, q) mod Max_Colors Với: Màu tô (p, q): số hiệu màu gán cho điểm ảnh tƣơng ứng với giá trị (p, q) Count(p, q): ngƣỡng tiến ra vô hạn của dãy (zn) tƣơng ứng với (p, q). Max_Colors: số lƣợng màu tối đa có trong palette màu đang đƣợc sử dụng. Trong thuật toán này, để thể hiện một cách chi tiết, chúng ta quét các giá trị c trong cửa sổ giới hạn bởi (Xmin , Ymin) và (Xmax , Ymax) theo thứ tự từ trên xuống dƣới và từ trái sang phải, tức là ứng với mỗi cột Col, ta kiểm tra và tô màu tất cả các điểm ảnh trên cột này theo các giá trị phức tƣơng ứng, sau đó mới chuyển sang cột mới kế tiếp đó. Nhƣ vậy chúng ta có đƣợc thuật toán chi tiết sau: for(Col = 0; Col < Max_Col; ++Col) { for(Row = 0; Row <= Max_Row; ++Row) { X = Y = xn = yn = 0; (vì ứng với mỗi giá trị c = (p, q) tƣơng ứng với điểm ảnh (Col, Row), dãy (zn) đƣợc khảo sát với z0 = 0) Count = 1; While (Count < Max_Iterations) & ( X + Y < 2) { 2 X = xn ; 2 Y = yn ; yn = 2xnyn + q; xn = X – Y + p; Count = Count + 1; } Tô màu điểm ảnh (Col, Row) bởi màu có số hiệu Count mod Max_Colors ; q = q + q ; } 87
p = p + p ; } Chúng ta có nhận xét đầu tiên là trong thuật toán trên, giá trị q đƣợc tính tất cả Max_Col x Max_Row lần, nhƣ vậy với màn hình có độ phân giải 640 x 480, q đƣợc tính 307200 lần, nhƣng thực chất chỉ có 480 giá trị q ứng với 480 hàng đƣợc sử dụng. Do đó để tăng tốc độ làm việc của thuật toán, các giá trị q có thể đƣợc tính trƣớc khi vào vòng lặp và đƣợc lƣu lại trong 1 mảng 1 chiều Q có Max_Row phần tử nhƣ sau: Q[0] = Ymax ; for(i = 0; i < Max_Row; ++i) Q[i] = Q[i - 1] - q; Ở đây q đƣợc tính trƣớc theo công thức đã nêu. 2 2 Một nhận xét thứ hai là việc tính | zn | = X + Y = xn + yn để so sánh với 2 chiếm rất nhiều thời gian. 2 2 2 2 Do đó chúng ta thay việc so sánh xn +yn < 2 bởi xn + yn < 4 vì hai bất đẳng thức này tƣơng đƣơng. Việc làm này sẽ làm giảm đáng kể thời gian thực hiện thuật toán. Thuật toán đƣợc viết lại dƣới dạng: for(Col= 0; Col<Max_Col; ++Col) { for(Row= 0; Row<= Max_Row; ++Row) { X = Y = xn = yn = 0; Count =1; While(Count<Max_Iterations) & (X+Y < 4) { 2 X = xn ; 2 Y = yn ; yn = 2xnyn + Q[Row]; xn = X – Y + p ; Count = Count +1; } Tô màu điểm ảnh (Col, Row) bởi màu có số hiệu Count mod Max_Colors ; } p = p + Δp; } 88
Hình 11.2 thể hiện tập Mandelbrot cổ điển với các giá trị khảo sát nằm trong vùng giới hạn bởi Xmin = -2.0, Ymin = -1.2, Xmax = 1.2, Ymax = 1.2 và Max_Iterations = 512, Max_Colors = 1.6. Hình 11.2 II.8 TẬP JULIA: □ Đặt vấn đề: 2 Đối với biểu thức zn+1 = zn + c, ngoài hƣớng đã khảo sát nhƣ đã trình bày trong phần tập Mandelbrot, còn có hƣớng khảo sát khác 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 z0. Theo hƣớng này chúng ta sẽ thu đƣợc 1 lớp các đối tƣợng fractal mới đƣợc gọi là tập Julia. Tập Julia và tập Mandelbrot là hai lớp các đối tƣợng fractal có mối liên hệ rất chặt chẽ với nhau. Một tính chất đáng chú ý là tập Mandelbrot có thể xem nhƣ một loại “bản đồ” Mandelbrot có thể cho ra các dạng tập Julia đầy sức lôi cuốn. Các vị trí nhƣ vậy đƣợc quan sát thấy ở gần biên của tập Mandelbrot. Nhất là gần các chỏm nhọn. Ngoài ra khi phóng to một phần của tập Mandelbrot, ta sẽ thu đƣợc một hình rất giống với tập Julia đƣợc tạo bởi giá trị của tâm phần đƣợc phóng to. □ Công thức toán học: Để thể hiện tập Julia trên màn hình máy tính, ta vẫn sử dụng các công thức nhƣ trong phần tập Mandelbrot, nhƣ là: 2 2 xn+1 = xn – yn + p yn+1 = 2xnyn + q Ngoài ra các tính chất đã nêu về giới hạn của dãy (z0) vẫn đƣợc sử dụng cho tập Julia. 89
□ Thuật toán thể hiện tập Julia: Điểm khác biệt so với tập Mandelbrot ở đây là giá trị p và q đƣợc giữ cố định, mặt phẳng màn hình biến đổi thành mặt phẳng phức thu hẹp biểu diễn các giá trị của x0 với: - Trục x biểu diễn phần thực của số phức z0. - Trục y biểu diễn phần ảo của số phức z0. Ngoài ra còn có sự phân lớp các giá trị của z0 nhƣ sau: Lớp 1: Bao gồm các giá trị (z0) có | zk | 2, với n k, k Z , tức là gồm các giá trị làm cho dãy (zn) tiến ra vô cực. Ngƣợc lại với tập Mandelbrot, khi thể hiện tập Julia trên màn hình, chúng ta quan tâm đến các giá trị z0 làm cho dãy (zn) không hội tụ đến vô cực. Do đó kỹ thuật tô màu của tập Julia vẫn là kỹ thuật xoay vòng nhƣng hoàn toàn ngƣợc lại với kỹ thuật tô màu tập Mandelbrot. Trong kỹ thuật tô màu này: - Các điểm ảnh tƣơng ứng với các giá trị z0 thuộc lớp 1, sẽ đƣợc gán màu tùy thuộc độ lớn của | zl| với l là ngƣỡng quyết định hội tụ của dãy (zn) đã nêu trong định nghĩa về lớp 1. - Các điểm ảnh tƣơng ứng với giá trị z0 thuộc lớp 2 sẽ đƣợc gán màu trùng với màu nền của bảng màu đang sử dụng. Với các thay đổi nhƣ vậy, tập Julia sẽ đƣợc thể hiện bằng thuật toán trình bày nhƣ sau: Thuật toán tổng quát để thể hiện tập Julia: Gồm các bƣớc sau: Bƣớc 1: Xuất phát với 1 giá trị khởi đầu z0 = (x0, y0) và giá trị cố định c = (p, q). Bƣớc 2: Kiểm tra z0 thuộc lớp 1 hay 2. Bƣớc 3: 90
Tô màu điểm ảnh tƣơng ứng với z0 theo kỹ thuật tô màu đƣợc nêu ở trên. Bƣớc 4: Chọn giá trị z0 mới và lặp lại bƣớc 1 cho đến khi đã quét hết tất cả các giá trị z0 cần khảo sát. Sử dụng ký hiệu đã đƣợc xác định khi trình bày thuật toán Mandelbrot chúng ta có thuật toán tạo tập Julia một cách chi tiết đƣợc viết dƣới dạng sau: for(Col = 0; Col Max_Iterations) Tô màu điểm ảnh (Col, Row) bởi màu có số hiệu (X + Y) (Max_Color – 1) mod (Max_Color +1) ; else Tô màu điểm ảnh (Col, Row) bởi màu nền của bảng màu hiện tại; } Sự khác biệt chủ yếu giữa thuật toán này với thuật toán Mandelbrot là sự thay đổi vai trò của z0 và c. Giá trị c = (p,q) đƣợc giữ cố định trong khi z0 thay đổi. Các đại lƣợng x0, y0, x0, y0 đƣợc xác định theo cách hoàn toàn giống với các đại lƣợng p, q, p, q trong thuật toán tạo tập Mandelbrot tức là: xmax x x min Max _Col ymax y y min Max _ Row 91
x0 = xmin + Col * x0; y0 = ymax – Row * y0; Còn có một điểm cần chú ý là các giá trị x0, y0 vừa đại diện cho z0 ban đầu và cũng đại diện cho dãy (zn) trong vòng lặp kiểm tra z0 thuộc lớp 1 hay 2. Hình minh hoạ tập Julia nhƣ sau: II.9 HỌ CÁC ĐƯỜNG CONG PHOENIX Họ các đƣờng cong Phoenix do Shigehiro Ushiki ở trƣờng đại học Kyoto tìm ra. Phƣơng trình của đƣờng cong đƣợc xác định bởi: 2 Zn+1 = zn + p + q.zn-1 Trong đó: 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: 2 2 xn+1 = xn – yn + p + q.xn-1 yn+1 = 2xn.yn + q.yn-1 với: xn+1 = Re(zn+1); yn+1 = Im(zn+1). 92
Khi đó việc thể hiện đƣờng cong này lên màn hình gần giống với việc thể hiện tập Julia. Tuy nhiên có hai điểm thay đổi quan trọng: Thay đổi 1: - Trục x của màn hình biểu thị phần ảo của số phức z0. - Trục y của màn hình biểu thị phần thực của số phức z0. Ở đây chúng ta đảo ngƣợc các trục thực và ảo của mặt phẳng phức thông thƣờng là để thể hiện hình ảnh theo chiều đứng chứ không phải chiều ngang. Hình 14.1 trình bày 1 loại đƣờng cong loại này với yêu cầu rõ ràng là phải đổi vai trò của trục x và y để hình ảnh có thể đƣợc thể hiện tốt trên màn hình. Do đó tƣơng ứng với một điểm ảnh (Col, Row) trên màn hình sẽ là số phức z = (x, y) có dạng: x = ymax – Row * x; y = ymin – Col * y; Với: ymax y x min Max _ Row xmax x y min Thay đổi 2: Max _Col Thay đổi về thuật toán tô màu. Ở đây với các điểm thuộc lớp 1 (theo định nghĩa đã nêu ở phần về tập Julia) chúng ta sẽ sử dụng 3 loại màu tuỳ theo ngƣỡng hội tụ: Màu 1: đƣợc sử dụng để tô các điểm z0 cho ra giá trị | zk | < 2 với tối đa k = 32 lần lặp. Màu 2: đƣợc sử dụng để tô các điểm z0 cho ra giá trị | zk | < 2 với số lần lặp từ 33 đến 64. Màu 3: đƣợc sử dụng để tô các điểm z0 cho ra giá trị | zk | < 2 với số lần lặp vƣợt quá 64 lần. Còn đối với các điểm thuộc lớp 2, chúng ta sẽ tô chúng bằng một màu khác với màu nền hiện tại. Với các thay đổi nhƣ vậy, đoạn mã dùng xác định giá trị z0 thuộc lớp 1 hay 2, cùng với kỹ thuật tô màu điểm ảnh sẽ đƣợc viết dƣới dạng: for(Col = 0; Col<Max_Col; ++Col) { for(Row=0; Row<= Max_Row; ++Row) { xn = ymax - Row* Δx; yn = xmin + Col* Δy; X =Y= 0; Count = 0; 93
While((Count Max_Iterations) Tô màu điểm ảnh (Col, Row) bằng màu dành cho các điểm loại 2; else if (Count >= 64) Tô màu điểm (Col, Row) bằng màu 3; else if (Color >= 32) Tô điểm ảnh (Col, Row) bằng màu 2; else Tô điểm ảnh (Col, Row) bằng màu 1; } } Đây là ảnh của đƣờng cong Phoenix Hình 14.1: Đƣờng cong Phoenix 94
N Tam g 0. . . , khôn 3) 2 1/K , N=k N=k3 ơng. =kd =kd => d= logN/logk log8/log4=1,5 (k=2) 95
KẾT LUẬN CHƯƠNG , . Hiện nay trên thế giới Fractal rất phát triển. Thị trƣờng tranh fractal và phần mềm sáng tác fractal cũng không hề nhỏ, nó có giá trị gần 1 tỉ USD trong năm 2004. Tìm hiểu sâu hơn về fractal hãy truy cập những địa chỉ sau: www.les.stclair.btinternet.co.uk www.biofractalevolution.com www.fractalism.com . Còn muốn tạo ra những hình họa fractal nhanh chóng và dễ dàng nhất, hãy sử dụng các phần mềm miễn phí: - Aros Fractals: Dung lƣợng chỉ 165 KB, tƣơng thích với mọi môi trƣờng Windows hiện hành, giải nén vào một thƣ mục rồi sử dụng ngay mà không cần cài đặt. Tải về từ địa chỉ www.arosmagic.com. - Double Fractal: Của tác giả Joao Paulo Schwarz Schuler. Dung lƣợng 676 KB, không cần cài đặt, tải về từ địa chỉ www.schulers.com/fractal. 96
[1] Michale Barnsly. " Fractal Everywhere ", University of Wisconsin- Madison, 1998. [2] John C.Hart “Fractal Image Compression and the Inverse Problem of Recurrent Iterated Function Systems”. School of EECS, 1995 [3] , " 97-12, 1997. [4] [5] 97