Luận án Chương trình nghiên cứu về hình học fractal. Viết chương trình cài đặt một số đường và mặt fractal

TRÖÔØNG Ñ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 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. 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. PHAÀN I I.1 Söï ra ñôøi cuûa lyù thuyeát hình hoïc phaân hình GIÔÙI THIEÄU SÔ LÖÔÏC 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 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 I.2 Söï Phaùt Trieån Cuûa Lyù Thuyeát Hình Hoïc Phaân Hình  ÖÙng duïng vaán ñeà taïo aûnh treân maùy tính I.3. Caùc ÖÙng Duïng Toång Quaùt Cuûa Hình Hoïc Phaân Hình  ÖÙng duïng trong coâng ngheä neùn aûnh  ÖÙng duïng trong khoa hoïc cô baûn 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 PHAÀN II PHAÀN II 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 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: Trong ñoù: N laø soá ñoaïn thaúng. R laø chieàu daøi moãi ñoaïn. II.1.1. Ñöôøng Hoa Tuyeát Von Kock Moãi ñoaïn thaúng ñöôïc thay baèng generator nhö sau: Soá chieàu fractal laø: Caùc hình minh hoïa cuûa ñöôøng Möùc 2 Möùc 3 II.1.2. Ñöôøng Gosper Moãi ñoaïn thaúng ñöôïc thay baèng generator nhö sau: Soá chieàu fractal laø: Caùc hình minh hoïa cuûa ñöôøng Möùc 1 Möùc 2 II.1.3. Ñöôøng Von Kock Baäc Hai 3 Ñoaïn Moãi ñoaïn thaúng ñöôïc thay baèng generator nhö sau: Soá chieàu fractal laø: Caùc hình minh hoïa cuûa ñöôøng Möùc 3 Möùc 5 II.1.8. Generator Phöùc Taïp Moãi ñoaïn thaúng ñöôïc thay baèng generator nhö sau: Soá chieàu fractal laø: Ta coù: Caùc hình minh hoïa cuûa ñöôøng Möùc1 Möùc 2 Vaäy 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 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. II.2.1. Ñöôøng Peano Nguyeân Thuûy Moãi ñoaïn thaúng ñöôïc thay baèng generator nhö sau: Soá chieàu fractal laø: Caùc hình minh hoïa cuûa ñöôøng Möùc 1 Möùc 3 II.2.3. Tam Giaùc Cesaro Moãi ñoaïn thaúng ñöôïc thay baèng generator nhö sau: Soá chieàu fractal laø: Generator chöùa 2 caïnh cuûa moät tam giaùc caân. Do ñoù: Caùc hình minh hoïa cuûa ñöôøng Möùc 1 Möùc 3 II.2.4. Tam Giaùc Cesaro caûi tieán Generaor ñöôïc thöïc hieän baèng caùch thay theá goùc töø 90 sang 85 ñoä nhö sau. Soá chieàu fractalø: gaàn gioáng nhö ñöôøng Cesaro nguyeân thuyû 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. Hình minh hoaï cuûa ñöôøng Möùc thöù 4 cuûa tam giaùc Cesaro caûi tieán. II.2.5. Moät daïng khaùc cuûa ñöôøng Cesaro 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. II.2.6. Tam giaùc Polya 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. 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 4 cuûa tam giaùc Polya Möùc 1 Möùc 2 II.2.7. Ñöôøng Peano-Gosper Generator cuûa ñöôøng naøy laø moät löôùi goàm caùc tam giaùc ñeàu lieân keát vôùi noù ( initiator laø moät ñoaïn thaúng naèm ngang) nhö sau. Vì generator coù soá ñoaïn thaúng N = 7 neân soá chieàu fractal laø. Ñöôøng naøy coù tính chaát töï laáp ñaày phaàn beân trong cuûa ñöôøng Gosper. Hình sau cho ta thaáy möùc thöù 2 cuûa ñöôøng naøy. II.2.8. Ñöôøng Hoa Tuyeát Peano 7 Ñoaïn Moãi ñoaïn thaúng ñöôïc thay baèng generator nhö sau: Soá chieàu fractal laø: Caùc hình minh hoïa cuûa ñöôøng Möùc 1 Möùc 2 2 1 3 3 3 1 6 = Þ = ÷ ÷ ø ö ç ç è æ + ÷ ø ö ç è æ * D D D II.3. Ñöôøng Sierpinski Moãi ñoaïn thaúng ñöôïc thay baèng generator nhö sau: Caùc hình minh hoïa cuûa ñöôøng Möùc 1 Möùc 2 Ñ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. 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: II.5. Phong Caûnh Fractal Chuùng ta baét ñaàu baèng moät tam giaùc vaø tieán haønh thay theá trung ñ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 vieäc nhaân 1 heä soá ngaãu nhieân 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. Hình minh hoïa thay theá trung ñieåm: Hình minh hoïa phong caûnh fractal: II.6. Heä Thoáng Haøm Laëp (IFS) Moät IFS laø taäp hôïp caùc pheùp bieán ñoåi affine co töùc laø: IFSIR2 ; 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á thöïc. Töông töï ,pheùp bieán ñoåi affine trong khoâng gian ba chieàu coù daïng: Hình minh hoïa aùp duïng IFS: Laù döông xæ 2 chieàu Laù döông xæ 3 chieàu II.7. Taäp Mandelbrot Söû duïng coâng thöùc toaùn hoïc: 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 Thì zn+1 = zn2 +c ñöôïc vieát laïi nhö sau: xn+1 = xn2 - yn2 + p yn+1 = 2xnyn + q Hình minh hoïa taäp Mandelbrot: II.8. Taäp Julia Söû duïng coâng thöùc toaùn hoïc: 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 Thì zn+1 = zn2 +c ñöôïc vieát laïi nhö sau: xn+1 = xn2 - yn2 + 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 ). Hình minh hoïa taäp Julia: II.9. Ñöôøng Cong Phoenix Phöông trình ñöôøng cong ñöôïc xaùc ñònh bôûi: zn+1 = zn2 + p +qzn-1 vôùi zi  C i  N. p = (p,0)  C. q = (q,0)  C. Phöông trình ñöôïc khai trieån thaønh caùc phaàn thöïc vaø aûo cuûa zn coù daïng : xn+1 = xn2 - yn2 + p + qxn-1 yn+1 = 2xnyn + qyn-1 vôùi : xn+1 = Re(zn+1) ; yn+1 = Im(zn+1 ) . Hình minh hoïa ñöôøng Phoenix: 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 PHAÀN III PHAÀN III 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 2. CAÙC ÑÖÔØNG THUOÄC HOÏ ÑÖÔØNG PEANO NHÖ: PHAÀN III I. THAØNH QUAÛ ÑAÏT ÑÖÔÏC (TT) 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 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 … 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 ……. PHAÀN III