Báo cáo 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 - Nguyễn Ngọc Hùng Cường

Nội dung text: Báo cáo 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 - Nguyễn Ngọc Hùng Cường

1. TRÖÔØNG ÑAÏI HOÏC BAÙCH KHOA HAØ NOÄI TRÖÔØNG ÑAÏI HOÏC THUYÛ SAÛN NHA TRANG KHOA COÂNG NGHEÄ THOÂNG TIN LUAÄN AÙN TOÁT NGHIEÄP ÑAÏI HOÏC Ñeà Taøi: NGHIEÂN CÖÙU VEÀ HÌNH HOÏC FRACTAL. VIEÁT CHÖÔNG TRÌNH CAØI ÑAËT MOÄT SOÁ ÑÖÔØNG VAØ MAËT FRACTAL. GV höôùng daãn: Tieán Só. Huyønh Quyeát Thaéng SV thöïc hieän: Nguyeãn Ngoïc Huøng Cöôøng MSSV: 98S1013
2. NHIEÄM VUÏ ÑEÀ TAØI LYÙ DO CHOÏN ÑEÀ TAØI Coù theå noùi cuøng vôùi lyù thuyeát topo, hình hoïc phaân hình cung caáp cho nhaø khoa hoïc moät moät coâng cuï khaûo saùt töï nhieân voâ cuøng maïnh meõ. Ngoaøi ra noù coøn ñöôïc aùp duïng vaøo vieäc nghieân cöùu lyù thuyeát töø tính, lyù thuyeát caùc phöùc chaát trong hoaù hoïc, lyù thuyeát taùi ñònh chuaån. Ñoàng thôøi noù coøn coù raát nhieàu öùng duïng trong lónh vöïc giaûi trí, ñoà hoaï vaø xöû lyù aûnh. NOÄI DUNG NGHIEÂN CÖÙU CUÛA ÑEÀ TAØI 1. Tìm hieåu toång quan veà lòch söû ra ñôøi vaø caùc keát quaû nghieân cöùu cuûa hình hoïc phaân hình. 2. Tìm hieåu caùc kyõ thuaät hình hoïc phaân hình thoâng qua söï khaûo saùt caùc caáu truùc Fractal cô sôû vaø thuaät toaùn chi tieát ñeå taïo neân caùc caáu truùc naøy. 3. Löïa choïn moät ngoân ngöõ laäp trình thích hôïp ñeå caøi ñaët caáu truùc Fractal vöøa tìm hieåu.
3. Noäi Dung Trình Baøy Phaàn I: Giôùi thieäu sô löôïc hình hoïc phaân hình. Phaàn II: Moät soá kyõ thuaät caøi ñaët hình hoïc phaân hình. Phaàn III: Moät soá keát quaû caøi ñaët vaø höôùng phaùt trieån ñeà taøi.
4. PHAÀN I GIÔÙIGIÔÙI THIEÄUTHIEÄU SÔSÔ LÖÔÏCLÖÔÏC HÌNHHÌNH HOÏCHOÏC PHAÂNPHAÂN HÌNHHÌNH I.1 Söï ra ñôøi cuûa lyù thuyeát hình hoïc phaân hình I.2 Söï phaùt trieån cuûa lyù thuyeát hình hoïc phaân hình I.3 Caùc öùng duïng toång quaùt cuûa hình hoïc phaân hình
5. I.1. Söï Ra Ñôøi Cuûa Lyù Thuyeát Hình Hoïc Phaân Hình  Tính hoãn ñoän cuûa caùc quaù trình phaùt trieån coù qui luaät trong töï nhieân.  Söï môû roäng khaùi nieäm soá chieàu vaø ñoä ño trong lyù thuyeát hình hoïc Euclide coå ñieån
6. I.2 Söï Phaùt Trieån Cuûa Lyù Thuyeát Hình Hoïc Phaân Hình
7. I.3. Caùc ÖÙng Duïng Toång Quaùt Cuûa Hình Hoïc Phaân Hình  ÖÙng duïng vaán ñeà taïo aûnh treân maùy tính  ÖÙng duïng trong coâng ngheä neùn aûnh  ÖÙng duïng trong khoa hoïc cô baûn
8. PHAÀNPHAÀN IIII Moät Soá Kyõ Thuaät Caøi Ñaët Hình Hoïc Phaân Hình II.1. Hoï Ñöôøng Von Kock II.2. Hoï Ñöôøng Peano II.3. Ñöôøng Sierpinski II.4. Caây Fractal II.5. Phong Caûnh Fractal II.6. Heä Thoáng Haøm Laëp II.7. Taäp Mandelbrot II.8. Taäp Julia II.9. Ñöôøng Cong Phoenix
9. II.1. Hoï Ñöôøng Von Kock II.1.1. Ñöôøng Hoa Tuyeát Von Kock II.1.2. Ñöôøng Gosper II.1.3. Ñöôøng Von Kock Baäc Hai 3 Ñoaïn II.1.4. Ñöôøng Von Kock Baäc Hai 8 Ñoaïn II.1.5. Ñöôøng Von Kock Baäc Hai 18 Ñoaïn II.1.6. Ñöôøng Von Kock Baäc Hai 32 Ñoaïn II.1.7. Ñöôøng Von Kock Baäc Hai 50 Ñoaïn II.1.8. Generator Phöùc Taïp
10. II.1. Hoï Ñöôøng Von Kock Ñöôïc phaùt sinh baèng caùch söû duïng kyõ thuaät ñeä qui initiator/generator vôùi keát quaû laø caùc hình töï ñoàng daïng hoaøn toaøn. Soá chieàu fractal ñöôïc tính theo coâng thöùc: log( N ) D = æ 1 ö log ç ÷ è R ø Trong ñoù: N laø soá ñoaïn thaúng. R laø chieàu daøi moãi ñoaïn.
11. II.1.1. Ñöôøng Hoa Tuyeát Von Kock b Moãi ñoaïn thaúng ñöôïc thay b Caùc hình minh hoïa cuûa ñöôøng baèng generator nhö sau: b Soá chieàu fractal laø: Möùc 2 Möùc 3
12. II.1.2. Ñöôøng Gosper b Moãi ñoaïn thaúng ñöôïc thay b Caùc hình minh hoïa cuûa ñöôøng baèng generator nhö sau: Möùc 1 b Soá chieàu fractal laø: log3 D = »1.1291 log 7 Möùc 2
13. II.1.3. Ñöôøng Von Kock Baäc Hai 3 Ñoaïn b Moãi ñoaïn thaúng ñöôïc thay b Caùc hình minh hoïa cuûa ñöôøng baèng generator nhö sau: Möùc 3 b Soá chieàu fractal laø: log3 D = »1.3652 log 5 Möùc 5
14. II.1.8. Generator Phöùc Taïp b Moãi ñoaïn thaúng ñöôïc thay b Caùc hình minh hoïa cuûa ñöôøng baèng generator nhö sau: b Soá chieàu fractal laø: Möùc1 Ta coù: å R . M D =1 Vaäy D æ öD æ 1 ö ç 3 ÷ 6ç ÷ + 5ç ÷ =1 è 3ø è 9 ø Þ D »1.238361 Möùc 2
15. II.2. Hoï Ñöôøng Peano II.2.1 Ñöôøng Peano Nguyeân Thuûy II.2.2 Ñöôøng Peano Caûi Tieán II.2.3 Tam Giaùc Cesaro II.2.4 Tam Giaùc Cesaro Caûi Tieán II.2.5 Moät Daïng Khaùc Cuûa Ñöôøng Cesaro II.2.6 Tam Giaùc Polya II.2.7 Ñöôøng Peano Gosper II.2.8 Ñöôøng Hoa Tuyeát Peano 7 Ñoaïn II.2.9 Ñöôøng Hoa Tuyeát Peano 13 Ñoaïn
16. II.1. Hoï Ñöôøng Peano Ñöôïc phaùt sinh baèng caùch söû duïng kyõ thuaät ñeä qui initiator/generator vôùi keát quûa laø caùc hình töï ñoàng daïng hoaøn toaøn. Caùc ñöôøng naøy coù soá chieàu baèng 2, neân phaûi laáp ñaày hoaøn toaøn maët phaúng.
17. II.2.1. Ñöôøng Peano Nguyeân Thuûy b Moãi ñoaïn thaúng ñöôïc thay b Caùc hình minh hoïa cuûa ñöôøng baèng generator nhö sau: Möùc 1 b Soá chieàu fractal laø: log9 D = Þ D = 2 log3 Möùc 3
18. II.2.3. Tam Giaùc Cesaro b Moãi ñoaïn thaúng ñöôïc thay b Caùc hình minh hoïa cuûa ñöôøng baèng generator nhö sau: b Soá chieàu fractal laø: Möùc 1 Generator chöùa 2 caïnh cuûa moät tam giaùc caân. Do ñoù: log2 D = Þ D = 2 log 2 Möùc 3
19. II.2.4. Tam Giaùc Cesaro caûi tieán Generaor ñöôïc thöïc hieän baèng Hình minh hoaï cuûa ñöôøng caùch thay theá goùc töø 90 sang 85 ñoä nhö sau. Soá chieàu fractalø: gaàn gioáng Möùc thöù 4 cuûa tam giaùc Cesaro nhö ñöôøng Cesaro nguyeân thuyû caûi tieán. nhöng khoâng hoaøn toaøn laø 2, nhöng khi soá laàn ñeä quy tieán ra voâ cöïc thì soá chieàu fractal tieán veà 2.
20. II.2.5. Moät daïng khaùc cuûa ñöôøng Cesaro b Giaû söû chuùng ta baét ñaàu vôùi ñöôøng generator vaø hai möùc ñaàu tieân nhö ôû ñöôøng Cesaro, nhöng söû duïng söï saép xeáp khaùc ñi khi ñaët generator veà phía traùi vaø beân phaûi cuûa ñoaïn thaúng goác khi chuùng ta ôû möùc cao hôn. Keát quaû laø nhieàu ñöôøng khaùc nhau coù theå ñöôïc sinh ra töø caùch saép xeáp naøy. Hình sau cho chuùng ta caùc möùc khaùc nhau cuûa ñöôøng naøy.
21. II.2.6. Tam giaùc Polya b Gioáng nhö ñöôøng Cesaro, vò trí cuûa generator ñaàu tieân thay ñoåi töø phaûi sang traùi vaø ñöôïc baét ñaàu ôû möùc ñaàu tieân. Ñoái vôùi ñöôøng naøy, vò trí cuûa generator cuõng thay ñoåi ñöôøng so vôùi moãi ñoaïn thaúng töông ñöông vôùi caùc möùc khaùc nhau. b Hình sau cho ta thaáy 2 möùc ñaàu tieân vaø möùc 4 cuûa hình naøy. Möùc 1 Möùc 2 Möùc 4 cuûa tam giaùc Polya
22. II.2.7. Ñöôøng Peano-Gosper b Generator cuûa ñöôøng naøy laø Ñöôøng naøy coù tính chaát töï laáp moät löôùi goàm caùc tam giaùc ñeàu ñaày phaàn beân trong cuûa ñöôøng lieân keát vôùi noù ( initiator laø moät Gosper. Hình sau cho ta thaáy ñoaïn thaúng naèm ngang) nhö möùc thöù 2 cuûa ñöôøng naøy. sau. Vì generator coù soá ñoaïn thaúng N = 7 neân soá chieàu fractal laø. log7 D = Þ D = 2 log 7
23. II.2.8. Ñöôøng Hoa Tuyeát Peano 7 Ñoaïn b Moãi ñoaïn thaúng ñöôïc thay b Caùc hình minh hoïa cuûa ñöôøng baèng generator nhö sau: Möùc 1 b Soá chieàu fractal laø: D æ ö D æ 1 ö ç 3 ÷ 6 * ç ÷ + ç ÷ = 1 Þ D = 2 è 3 ø è 3 ø Möùc 2
24. II.3. Ñöôøng Sierpinski b Moãi ñoaïn thaúng ñöôïc thay b Caùc hình minh hoïa cuûa ñöôøng baèng generator nhö sau: Möùc 1 Ñeå phaùt sinh ra ñöôøng naøy ngöôøi ta duøng caùc kyõ thuaät gioáng nhö hoï ñöôøng Von Kock vaø Peano. Möùc 2
25. II.4. Cây Fractal Baét ñaàu vôùi moät thaân caây taïi ñaàu muùt cuûa noù, taùch thaân caây thaønh hai höôùng vaø veõ hai nhaùnh. Chuùng ta laëp laïi quùa trình naøy taïi ñaàu muùt cuûa moãi nhaùnh. Keát quûa chuùng ta seõ ñöôïc moät caây. Hình minh hoïa caây fractal:
26. II.5. Phong Caûnh Fractal b Chuùng ta baét ñaàu baèng moät tam Hình minh hoïa thay theá trung giaùc vaø tieán haønh thay theá trung ñieåm: ñieåm öùng vôùi moãi caïnh cuûa tam giaùc naøy baèng moät ñieåm treân ñöôøng trung tröïc cuûa caïnh töông öùng. Khoaûng caùch giöõa trung ñieåm cuõ vaø ñieåm môùi trong moãi laàn thay theá ñöôïc xaùc ñònh bôûi • Hình minh hoïa phong caûnh vieäc nhaân 1 heä soá ngaãu nhieân fractal: Gauss vôùi ñoä daøi ñoaïn thaúng. Keá tieáp chuùng ta noái moãi ñieåm vöøa ñöôïc taïo ra vôùi hai ñænh gaàn nhaát cuûa tam giaùc. Sau ñoù, töøng caëp ñieåm môùi taïo thaønh seõ ñöôïc noái laïi vôùi nhau. Cuoái cuøng chuùng ta boû ñi caùc caïnh cuûa tam giaùc ban ñaàu.
27. II.6. Heä Thoáng Haøm Laëp (IFS) b Moät IFS laø taäp hôïp caùc pheùp bieán 2 Hình minh hoïa aùp duïng IFS: ñoåi affine co töùc laø: IFS IR ; wn : n=1,2, ,N vôùi wn laø pheùp bieán ñoåi affine. Pheùp bieán ñoåi affine coù daïng: vôùi a,b,c,d,e,f laø caùc heä soá Laù döông xæ 2 chieàu thöïc. b Töông töï ,,pheùp bieán ñoåi affineaffine trong khoâng gian ba chieàu coù daïng: Laù döông xæ 3 chieàu
28. II.7. Taäp Mandelbrot b Söû duïng coâng thöùc toaùn hoïc: Hình minh hoïa taäp Mandelbrot: Kyù hieäu zn =( xn , yn), c=(p,q) , trong ñoù : xn = Re(zn), p = Re(c), yn =Im(zn), q = Im(c), n >= 0 2 Thì zn+1 = zn +c ñöôïc vieát laïi nhö sau: 2 2 xn+1 = xn - yn + p yn+1 = 2xnyn + q
29. II.8. Taäp Julia b Söû duïng coâng thöùc toaùn hoïc: Hình minh hoïa taäp Julia: Kyù hieäu zn =( xn , yn), c=(p,q) , trong ñoù : xn = Re(zn), p = Re(c), yn =Im(zn), q = Im(c), n >= 0 2 Thì zn+1 = zn +c ñöôïc vieát laïi nhö sau: 2 2 xn+1 = xn - yn + p yn+1 = 2xnyn + q Höôùng khaûo saùt baèng caùch cho c coá ñònh vaø xem xeùt daõy (zn) öùng vôùi moãi giaù trò khaùc cuûa (zo ).
30. II.9. Ñöôøng Cong Phoenix b Phöông trình ñöôøng congcong ñöôïc xaùc Hình minh hoïa ñöôøng Phoenix: ñònh bôûi: 2 zn+1 = zn + p +qzn-1 vôùi zi C i N. p = (p,0) C. • q = (q,0) C. • Phöông trình ñöôïc khai trieån thaønh caùc phaàn thöïc vaø aûo cuûa zn coù daïng : 2 2 xn+1 = xn - yn + p + qxn-1 yn+1 = 2xnyn + qyn-1 vôùi : xn+1 = Re(zn+1) ; yn+1 = Im(zn+1 ) .
31. PHAÀN III I. THAØNH QUAÛ ÑAÏT ÑÖÔÏC 1. CAÙC ÑÖÔØNG THUOÄC HOÏ ÑÖÔØNG VON KOCK NHÖ: 1.1 Ñöôøng hoa tuyeát Von Kock 1.2 Ñöôøng Gosper 1.3 Ñöôøng Von Kock baäc hai 3 ñoaïn 1.4 Ñöôøng Von Kock baäc hai 8 ñoaïn 1.5 Ñöôøng Von Kock baäc hai 18 ñoaïn 1.6 Ñöôøng Von Kock baäc hai 32 ñoaïn 1.7 Ñöôøng Von Kock baäc hai 50 ñoaïn 1.8 Ñöôøng Generator phöùc taïp
32. PHAÀN III I. THAØNH QUAÛ ÑAÏT ÑÖÔÏC (TT) 2. CAÙC ÑÖÔØNG THUOÄC HOÏ ÑÖÔØNG PEANO NHÖ: 2.1 Ñöôøng Peano nguyeân thuûy 2.2 Ñöôøng Peano caûi tieán 2.3 Tam giaùc Cesaro 2.4 Tam giaùc Cesaro caûi tieán 2.5 Moät daïng khaùc cuûa ñöôøng Cesaro 2.6 Tam giaùc Polya 2.7 Ñöôøng Peano Gosper 2.8 Ñöôøng hoa tuyeát Peano 7 ñoaïn 2.9 Ñöôøng hoa tuyeát Peano 13 ñoaïn
33. PHAÀN III I. THAØNH QUAÛ ÑAÏT ÑÖÔÏC (TT) 3. ÑÖÔØNG SIERPINSKI 4. CAÂY FRACTAL 5. PHONG CAÛNH FRACTAL 6. CAÂY DÖÔNG XÆ 2 CHIEÀU VAØ CAÂY DÖÔNG XÆ 3 CHIEÀU 7. MAËT MANDELBROT 8. MAËT JULIA 9. ÑÖÔØNG CONG PHOENIX
34. PHAÀN III II. HAÏN CHEÁ CUÛA ÑEÀ TAØI 1. Chöa tìm hieåu ñöôïc taát caû caùc caáu truùc Fractal cô sôû. 2. Chöa caøi ñaët ñöôïc moät soá hieäu öùng chính nhö taïo caùc ñaùm maây, löûa 3. Taïo caùc daõy nuùi. 4. Moät soá ñöôøng chöa tìm hieåu vaø caøi ñaët kòp nhö ñöôøng Hilbert, ñöôøng troøn Apolo, ñöôøng cong Dragon
35. PHAÀN III III. HÖÔÙNG PHAÙT TRIEÅN ÑEÀ TAØI 1. Taïo ñöôøng Hilbert 2. Taïo ñöôøng troøn Apollo 3. Taïo hoï ñöôøng cong Dragon 4. Taïo caùc hieäu öùng nhö: löûa, maây 5. Taïo caùc daõy nuùi .