ĐỒ ÁN TỐT NGHIỆP: Nghiên cứu về
hình học practal. Viết chương trình cài đặt
một số đường và mặt practal
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 1
LỜI NÓI ĐẦU
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ành một cuộc
thử nghiệm liên ngành. Cho đến nay nó đã đưa khoa học tiến những bước rất
dài. Hình học phân hình đã được đông đảo mọi người chú ý và thích thú nghiên
cứu. Với một người quan sát tình cờ màu sắc của các cấu trúc phân hình 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. Hình học phân hình đã cung cấp
cho các nhà khoa học một môi trường phong phú cho sự thám hiểm và mô hình
hoá tính phức tạp của tự nhiên. Những nguyên nhân của sự lôi cuốn do hình
học phân hình 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ó.
Những thành công to lớn trong các lĩnh vực của khoa học tự nhiên và kỹ
thuật dẫn đến sự ảo tưởng về một thế giới hoạt động như một cơ chế đồng hồ
vĩ đại, trong đó các quy luật của nó chỉ còn phải chờ đợi để giải mã từng bước
một. Một khi các quy luật đã được biết, người ta tin rằng sự tiến hoá hoặc phát
triển của các sự vật sẽ được dự đoán trước chính xác hơn nhiều, ít ra là về mặt
hình, về các kết quả của cơ sở lý thuyết.
Chương II: Trình bày các kỹ thuật hình học phân hình thông qua sự
khảo sát các cấu trúc Fractal cơ sở và thuật toán chi tiết để tạo nên các cấu trúc
này.
Chương III: Kết quả cài đặt chương trình vẽ một số đường mặt fractal
và các hiệu ứng.
Nhân đây, em xin chân thành cảm ơn thầy T.S Huỳnh Quyết Thắng đã
tận tình hướng dẫn, chỉ dạy giúp đỡ em trong suốt thời gian thực hiện đề tài
nghiên cứu này.
Em cũng xin chân thành cảm ơn quý thầy cô khoa công nghệ thông tin
đã 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ẹ,
và 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.
Sinh viên thực hiện
Nguyễn Ngọc Hùng Cường.
I.3 Các ứng dụng tổng quát của hình học phân hình 10
Ứng dụng trong vấn đề tạo ảnh trên máy tính 11
Ứng dụng trong công nghệ nén ảnh 11
Ứng dụng trong khoa học cơ bản 13
I.4 Các kiến thức cơ sở của hình học phân hình 13
I.4.1 Độ đo Fractal 13
I.4.2 Các hệ hàm lặp IFS 17
Chương II : MỘT SỐ KỸ THUẬT CÀI ĐẶT HÌNH HỌC PHÂN HÌNH. 21
II.1 Họ đường Von Kock 21
Đường hoa tuyết Von Kock-Nowflake 21
Đường Von Kock-Gosper 26
Đường Von Kock bậc hai 3-đoạn 28
Đường Von Kock bậc hai 8-đoạn 30
Đường Von Kock bậc hai 18-đoạn 32
Đường Von Kock bậc hai 32-đoạn 33
Đường Von Kock bậc hai 50-đoạn 35
Generator phức tạp 38
II.2 Họ đường Peano 44
Đường Peano nguyên thuỷ 44
Đường Peano cải tiến 45
Tam giác Cesaro 49
Tam giác Cesaro cải tiến 51
Một dạng khác của đường Cesaro 54
Tam giác Polya 56
Đường Peano-Gosper 58
Đường hoa tuyết Peano 7-đoạn 62
Đường hoa tuyết Peano 13-đoạn 66
II.3 Đường Sierpinski 70
II.4 Cây Fractal 73
Các cây thực tế 73
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 5
, được quan tâm đặc biệt. Các khảo sát trong những thập niên gần
đây đã phát hiện ra các cư xử kỳ dị của các tiến trình lặp như vậy.
Khảo sát chi tiết đầu tiên được nhà khí tượng học Edward N. Lorenz
tiến hành vào năm 1961 khi nghiên cứu hệ toán học mô phỏng dự báo thời tiết.
Về mặt lý thuyết, hệ này cho ra các kết quả dự đoán chính xác về thời tiết trong
một khoảng thời gian dài. Tuy nhiên, theo Lorenz quan sát, khi bắt đầu tính
toán lại dựa vào dữ liệu cho bởi hệ tại một thời điểm tiếp sau đó không giống
với các kết quả dự đoán ban đầu. Hơn nữa sai số tính toán sẽ tăng lên nhanh
chóng theo thời gian. Điều này dẫn đến kết luận là nếu tiến trình dự đoán lại từ
một thời điểm nào đó trong tiến trình dự báo, khoảng thời gian để các kết quả
dự báo tiếp theo vẫn còn chính xác sẽ bị thu hẹp lại tức là không thể dự báo
chính xác về thời tiết trong một khoảng thời gian khá lớn. Vấn đề được Lorenz
tìm thấy ở đây ngày nay được gọi là sự hiện diện của tính chất hỗn độn trong
các tiến trình lặp xác định.
Tiếp theo sau phát hiện của Lorenz, vào năm 1976 Robert May trong
bài viết với tựa đề “Các mô hình toán học đơn giản với các hệ động lực phức
tạp” đã đề cập đến một vấn đề tương tự. Đó là sự hỗn độn của quá trình phát
triển dân số trong tự nhiên, vốn được xem là đã được xác định rất rõ ràng và
chi tiết nhờ mô hình dân số Verhulst xây dựng dưới đây.
Nếu ký hiệu: ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 6
- R là tốc độ gia tăng dân số mỗi năm.
- P
o
trường (P-P
n
) / N. Trong đó N là lượng dân số tối đa có thể có ứng với điều
kiện môi trường cho trước. Như vậy có thể biểu diễn R dưới dạng: Với r là hệ số tỷ lệ gọi là tham số phát triển theo môi trường.
Từ (1) và (2) suy ra:
Do đó:
Đặt:
-
P
n
N P
n
= r
P
n
N
N
P
k
P
k
= ta có:
N
P
n+1
- P
n
= r(1 - P
n
)
mức tối đa.
- Với 2 < r < 2,449: Dãy (P
n
) dao động tuần hoàn giữa hai giá trị,
tức là sự phát triển dân số biến động giữa hai mức xác định. Hình
vẽ (I.1) minh hoạ cho trường hợp r = 2.3 và P
o
Dân số: Thời gian
Hình vẽ I.1 với r = 2.3 và P
0
= 0.01
- Với 2,449 < r < 2,570: Dãy (P
n
) dao động ổn định với các giá trị
được lặp lại theo chu kỳ lần lượt được nhân đôi khi giá trị r chạy
từ 2,449 đến 2,570. Hình vẽ (I.2) minh hoạ trường hợp r = 2,5 và
sự dao động ở đây có chu kỳ 4.
Dân số:
Thời gian
Hình vẽ I.3 với r = 3.0 và P
o
= 0.1
Một kết quả lý thuyết cũng đã được chứng minh bởi Jame York và Tiên
Yien Li trong bài viết ”Các chu kỳ 3 chứa đựng sự hỗn độn” vào tháng
12/1975. York và Li đã chỉ ra rằng mọi hàm số được xác định tương tự như
phương trình dân số có một chu kỳ tuần hoàn 3 thì cũng có chu kỳ tuần hoàn n,
với n là số tự nhiên khác 0 và 1. Điều này dẫn đến sự kiện là vô số các tập giá
trị tuần hoàn khác nhau được sản sinh bởi loại phương trình này.
Vào năm 1976, Mitchell Feigenbaum đã nghiên cứu phương trình này
một cách độc lập với May và York. Feigenbaum xét phương trình dân số ở
dạng đơn giản:
y = x(1- x)
và thể hiện nó trên sơ đồ phân nhánh. Nếu gọi r
n
là giá trị tham số phát
triển theo môi trường của mô hình Verhulst tại lần rẻ nhánh thứ n (là lúc ứng
với r
n
đó, chu kỳ 2
n
trở nên không ổn định nữa và chu kỳ 2
n+1
đạt được sự ổn
định), thì tỷ số của các khoảng liên tiếp
n
xác định bởi:
r
n+1
- r
n
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 9
các đối tượng một chiều như các đường thẳng. Tuy nhiên trực quan cho thấy
cách nhìn như vậy về số chiều là rất gò bó. Do đó người ta bắt đầu nghĩ đến
một sự phân lớp mới, trong đó các đường có số chiều bằng 1 được đại diện bởi
đường thẳng, các đối tượng hai chiều được đại diện bởi mặt phẳng, còn các
đường cong lấp đầy mặt phẳng đại diện cho các đối tượng có số chiều giữa 1
và 2. Ý tưởng cách mạng này đã dẫn đến việc hình thành và giải quyết bài toán
số chiều hữu tỷ gây ra nhiều tranh luận toán học trong các thập kỷ gần đây.
Tiếp sau đó, vào năm 1904 nhà toán học Thụy Điển Helge Koch đã đưa
ra một loại đường cong khác với những đường cong của Peano và Hilbert. Các
đường cong Von Koch không lấp đầy mặt phẳng nhưng lại có độ dài thay đổi
một cách vô hạn mặc dù chúng được chứa trong một miền hữu hạn. Những
đường cong như vậy có rất nhiều trong tự nhiên, ví dụ như các đường bờ biển,
đường biên của một bông hoa tuyết, các đám mây, vv… Tất vả các đường cong
này đều một tính chất đặc trưng là đồng dạng. Nó được biểu hiện bởi sự giống
nhau giữa một phần rất nhỏ của đường cong được phóng lớn với một phần
khác lớn hơn của cùng một đường cong đó. Tính chất này giữ một vị trí quan
trọng trong việc hình thành nên các dạng cấu trúc vô cùng phức tạp của tự
nhiên, nhưng vào thời Von Koch lại được hiểu biết rất sơ lược.
Chỉ với sự giúp đỡ của máy tính điện tử, bản chất của tính đồng dạng
mới được nghiên cứu đầy đủ và chi tiết trong tác phẩm “Hình học phân hình
M.Begger đã phát triển lý thuyết biểu diễn các đối tượng tự nhiên dựa trên cơ
sở lý thuyết về các hệ hàm lặp IFS. Các hệ hàm lặp này bao gồm một bộ hữu
hạn các phép biến đổi affine cho phép với sự giúp đỡ của máy tính tạo nên hình
ảnh các đối tượng trong tự nhiên. Theo lý thuyết này hình học Euclide cổ điển
rất có hiệu lực trong việc biểu diễn các đối tượng nhân tạo như một toà nhà,
một cổ máy nhưng lại hoàn toàn không thích hợp cho việc biểu diễn các đối
tượng của thế giới thực vì đòi hỏi một lượng quá lớn các đặc tả cần có. Nếu
như trong hình học Euclide các yếu tố cơ sở là đường thẳng, đường tròn, hình
vuông,… thì lý thuyết IFS mở rộng hình học cổ điển với các yếu tố cơ sở mới
là vô số thuật toán để vẽ nên các fractal của tự nhiên.
Ngoài ra các công trình có tính chất lý thuyết, hình học phân hình còn
được bổ sung bởi nhiều nghiên cứu ứng dụng lý thuyết vào khoa học máy tính
và các khoa học chính xác khác, ví dụ dựa trên lý thuyết IFS, Barnsley đã phát
triển lý thuyết biến đổi phân hình áp dụng vào công nghệ nén ảnh tự động trên
máy tính, là một lĩnh vực đòi hỏi những kỹ thuật tiên tiến nhất của tin học hiện
đại.
Hiện nay nhiều vấn đề, về lý thuyết phân hình vẫn đang được tiếp tục
nghiên cứu. Một trong những vấn đề lớn đang được quan tâm là bài toán về các
độ đo đa phân hình (multifractal measurement) có liên quan đến sự mở rộng
các khái niệm số chiều fractal với đối tượng fractal trong tự nhiên, đồng thời
cũng liên quan đến việc áp dụng các độ đo fractal trong các ngành khoa học tự
nhiên.
I.3 CÁC ỨNG DỤNG TỔNG QUÁT CỦA HÌNH HỌC PHÂN HÌNH:
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:
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
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ế
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
(A)
0
với:
trong đó:
diam (U
i
) = sup [ d(x,y) : x,y U
i
], với d là metric Euclide trong không
gian R
n
, [U
1
, U
2
,… ] là một phủ mở của A và diam(U
i
) < , i.
Hausdorff đã chứng minh được sự tồn tại của một số D
H
(A) sao cho:
0 khi s > D
i
)
s
i=1 ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 14
đó, đồng thời chỉ ra mối liên hệ giữa chúng với định nghĩa số chiều của
Hausdorff.
□ SỐ CHIỀU TỰ ĐỒNG DẠNG: (SỐ CHIỀU HAUSDORFF-
BESCOVITCH ):
Định nghĩa:
Cho trước một cấu trúc tự đồng dạng được chia thành N phần, hệ số thu
nhỏ của mỗi phần so với cấu trúc ban đầu là r. Ký hiệu D
S
là đại lượng xác
định bởi:
Khi đó D
S
được gọi là số chiều tự đồng dạng của cấu trúc đó.
D
S
=
log 1/r D 2
3 log
2
3 log
3
1
1
log
9 log
s
D 3
3 log
3
3 log
3
1
1
log
27 log
s
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Biểu diễn các đại lượng có liên quan trên hệ toạ độ log/log đã được trình
bày ở trên với chú ý sau bước tạo sinh thứ k, đường cong gồm 8
k
đoạn, mỗi
đoạn có độ dài s = 1 / 4
k
nên độ dài của đường cong sẽ là 8
k
.1/4
k
= 2
k
.
Khi đó giá trị trên trục hoành là log
4
Số chiều xác định theo định nghĩa này được áp dụng cho các đường
cong fractal khơng thể xác định số chiều theo 2 cách vừa trình bày. Cách tính
số chiều này có thể áp dụng cho mọi cấu trúc trong mặt phẳng và mở rộng cho
cấu trúc trong khơng gian.
Định nghĩa:
Xét một cấu trúc fractal bất kỳ. Lần lượt đặt cấu trúc này lên một dãy
các lưới có kích thước ơ lưới s giảm liên tiếp theo tỉ lệ ½. Gọi N(s) là các ơ
lưới có kích thước s có chứa một phần cấu trúc. Ta xây dựng hệ toạ độ log/log
như sau:
- Trục hồnh biểu thị giá trị của đại lượng log
2
(1/s).
- Trục tung biểu thị giá trị của đại lượng log
2
N((s)).
- D
B
là hệ số góc của đường thẳng hồi qui đối với tập hữu hạn các
điểm (s, N(s)) của hệ toạ độ.
Khi đó ta có:
D
B
(k+1)
) – log
2
N(2
–
k
) N(2
–
(k + 1)
)
D
B
= = log
2
log
2
2
k + 1
– log
2
2
k
N(2
– k
)
sau như
là
Hausdorff
chiều
số
tính
khi
yếu
chủ
khăn
Khó
δ
Σ
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 17
2
và d là metric Euclide. Ký hiệu H(X) là khơng gian các tập con
compact khác rỗng của X. Ta có các định nghĩa sau:
Định nghĩa 1:
Khoảng cách từ một điểm x X đến một tập B H(X) được xác định
bởi:
Định nghĩa 2:
Khoảng cách từ một tập A H(X) đến một tập B H(B) được xác định
bởi:
Định nghĩa 3:
i,)
i
diam(U và A của hạn hữumột phủ là } ,
2
U,
1
U {
: đó trong
}
s
1i
{ inf
s
. (A)N
: vì hơngiản đơn (A)
0
lim(A)
b
D
δ
δΣδ
δ
δ
δ
δ
δ
δ
δ
δ
δ
d(x,max
B)
d(x,
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 18
Khoảng cách Hausdorff giữa hai điểm A và B H(H) được xác định
bởi:
Với các định nghĩa trên ta có định lý:
Định lý về sự tồn tại của các IFS Fractal:
Ta có (H(X), h) là một không gian metric đầy đủ. Hơn nữa nếu
A
n
H(X) với n = 1,2,… lập thành một dãy Cauchy thì tập hợp A xác định bởi:
A = lim A
n
0
cũng thuộc H(X). A có thể được đặc tả như sau:
A = [ x X : một dãy Cauchy [ x
n
A
n
] hội tụ về một điểm x’ S, nhưng do
tính liên tục của w suy ra được [ y
Nn
= f (x
Nn
) ] là một dãy con
của [ y
n
] hội tụ về y’ w(S). Vậy w(S) compact.
Bổ đề được chứng minh.
Bổ đề 3 sau đây chỉ ra cách tạo một ánh xạ co trên không gian metric
(H(X), h) dựa trên một ánh xạ co trên (X,d).
Bổ đề 3:
Giả sử w: X X là một ánh xạ có không gian metric (X,d) với hệ số co
s. Khi đó ánh xạ w: H(X) H(X) được xác định bởi:
Ad(B,B),d(A, max B)h(A,
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 19
W(B) = [w(x): x B], với B thuộc H(X) cũng là một ánh xạ co trên
(H(X), h(d)) với hệ số co s.
Chứng minh:
Từ bổ đề 1 suy ra w: X X liên tục. Do đó theo bổ đề 2, ánh xạ H(X)
lên chính nó. Bây giờ xét B, C thuộc H(X).
.
1nN
Chứng minh:
Kết quả trên được chứng minh bằng qui nạp.
Với N = 2: Xét B, C H(X).
Ta có:
Vậy W là ánh xạ co với N = 2.
Giả sử khẳng định đúng với N = k. Ta chứng minh khẳng định đúng
với N = k + 1. Thật vậy, ta có:
C)s.h(B,
C)}.h(B,
2
s , C).h(B,
1
s { max
(C))}
2
w , (B)
2
h(w, (C))
1
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 20
Vậy W là ánh xạ co với N = k +1.
Do đó theo ngun lý qui nạp bổ đề 4 được chứng minh xong.
□ CÁC HỆ HÀM LẶP IFS (ITERATED FUNCTION SYSTEM ):
Định nghĩa 1:
Một hệ hàm lặp gồm một khơng gian metric đầy đủ (X, d) và một bộ
hữu hạn các ánh xạ co w
n
với hệ số co tương ứng s
n
, n = 1, 2,…, N. Ta ký hiệu
IFS thay cho cụm từ hàm lặp. Một IFS được ký hiệu bởi [X; w
n
1
k
n
1
max)
1k
s,
T
max(ss co số hệvới H(X) trên
co xạ ánh là Wcó cũng ta , 2 N với nạp quithuyết giả do nhưng
(B)
1k
wT(B) W(B)
:viết thể có Vậy .
n
s
kn 1
max
T
s co số hệvới H(X) trên
co xạ ánhmột là T có ta nạp quithuyết giả do thì
n
w
k
1n
TĐặt
(B)
1k
w(B)
. H(X) B bất kỳvới (B)
n
W
n
lim A bởitrước cho được và
(A)
n
w
N
1n
W(A)A
: với H(X) A động điểm bấtmột nhất duy có này xạ Ánh
H(X) CB, , C)B, s.h( W(C)), h(W(B)
: là tức , s co số hệvới h(d)), (H(X)
đủ đầy metric gian khôngtrên co xạ ánhmột là H(X) B đó trong
(B)
n
w
N
1n
,
n
w
{X;
IFS
một
Xét
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 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
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).
R
N
D
1
log
)
log(
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 22
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à:
Hàm này cộng thêm vào Turtle-Theta một góc Angle (tức là quay con
rùa đi một góc theo chiều ngược chiều kim đồng hồ nếu Angle > 0, còn nếu
Angle < 0 thì quay cùng chiều kim đồng hồ). Đoạn mã sau đây minh hoạ cách
cài đặt:
void Turn(double Angle, double &Turtle_Theta)
Turtle_Theta+=Angle; Hàm Step (Turtle-X, Turtle-Y, Turtle-R, Turtle-Theta):
2618,1
3log
4
log
1
log
)
log(
R
N
D
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<NumLines; ++I)
Step(Turtle_X, Turtle_Y, Turtle_R, Turtle_Theta);
XPoints[ I ]=Turtle_X;
YPoints[ I ]=Turtle_Y;
Turn(Angles[ I ],Turtle_Theta);
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 24
if (Level)
for (I=0; I<NumLines; I++)
Hình : Đường Von Kock-Snowflake mức 3.
Lưu đồ của đoạn mã ở trên như sau:
Copyright: Tài liệu đại học ©