Tài liệu Đồ á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 - Nguyễn Ngọc Hùng Cường: TRƯỜNG………………………
KHOA……………………
ĐỒ Á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ề ...
117 trang |
Chia sẻ: haohao | Lượt xem: 1590 | Lượt tải: 0
Bạn đang xem trước 20 trang mẫu tài liệu Đồ á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 - Nguyễn Ngọc Hùng Cường, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
TRƯỜNG………………………
KHOA……………………
ĐỒ Á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, tố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 tố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
hố 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 hố hoặc phát
triển của các sự vật sẽ được dự đốn trước chính xác hơn nhiều, ít ra là về mặt
nguyên tắc. Những bước phát triển ngoạn mục đầy lơi cuốn trong lĩnh vực kỹ
thuật máy tính và sự hứa hẹn cho việc điều khiển thơng tin nhiều hơn nữa của
nĩ đã làm gia tăng hy vọng của nhiều người về máy mĩc hiện cĩ và cả những
máy mĩc ở tương lai. Nhưng ngày nay người ta đã biết chính xác dựa trên cốt
lỗi của khoa học hiện đại là khả năng xem xét tính chính xác các phát triển ở
tương lai như thế sẽ khơng bao giờ đạt được. Một kết luận cĩ thể thu được từ
các lý thuyết mới cịn rất non trẻ đĩ là : giữa sự xác định cĩ tính nghiêm túc
với sự phát triển cĩ tính ngẫu nhiên khơng những khơng cĩ sự loại trừ lẫn nhau
mà chúng cịn cùng tồn tại như một quy luật trong tự nhiên. Hình học phân
hình và lý thuyết hỗn độn xác định kết luận này. Khi xét đến sự phát triển của
một tiến trình trong một khoảng thời gian, chúng ta sử dụng các thuật ngữ của
lý thuyết hỗn độn, cịn khi quan tâm nhiều hơn đến các dạng cĩ cấu trúc mà
một tiến trình hỗn độn để lại trên đường đi của nĩ, chúng ta dùng các thuật ngữ
của hình học phân hình là bộ mơn hình học cho phép “sắp xếp thứ tự” sự hỗn
độn. Trong ngữ cảnh nào đĩ hình học phân hình là ngơn ngữ đầu tiên để mơ tả,
mơ hình hố và phân tích các dạng phức tạp đã tìm thấy trong tự nhiên. Nhưng
trong khi các phần tử của ngơn ngữ truyền thống (Hình học Euclide) là các
dạng hiển thị cơ bản như đoạn thẳng, đường trịn và hình cầu thì trong hình học
phân hình đĩ là các thuật tốn chỉ cĩ thể biến đổi thành các dạng và cấu trúc
nhờ máy tính.
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:
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 2
Chương I: Trình bày các kiến thức tổng quan về lịch sử hình học phân
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 tố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 hồ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.
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 3
MỤC LỤC
Trang
LỜI NĨI ĐẦU. ..................................................................................................... 1
Chương I:SỰ RA ĐỜI VÀ CÁC KẾT QUẢ CỦA HÌNH HỌC PHÂN HÌNH. ..... 5
I.1 Sự ra đời của lý thuyết hình học phân hình .................................................. 5
Tính hỗn độn của các quá trình phát triển cĩ quy luật trong tự nhiên ............. 5
Sự mở rộng khái niệm số chiều và độ đo trong lý thuyết hình học Eulide
cổ điển .................................................................................................................. 8
I.2 Sự phát triển c ủa l ý thuyết hình học phân hình ......................................... 9
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
Biểu diễn tốn học của cây ......................................................................... 73
II.5 Phong cảnh Fractal ................................................................................... 77
II.6 Hệ thống hàm lặp (IFS) ............................................................................ 84
Các phép biến đổi Affine trong khơng gian R2 ............................................ 84
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 4
IFS của các pháp biến đổi Affine trong khơng gian R2 ................................ 85
Giải thuật lặp ngẫu nhiên ............................................................................ 86
II.7 Tập Mandelbrot ........................................................................................ 88
Đặt vấn đề .................................................................................................. 98
Cơng thức tốn học ...................................................................................... 88
Thuật tốn thể hiện tập Mandelbrot ............................................................. 89
II.8 Tập Julia ................................................................................................... 94
Đặt vấn đề .................................................................................................. 94
Cơng thức tốn học ..................................................................................... 94
Thuật tốn thể hiện tập Julia ........................................................................ 95
II.9 Họ các đường cong Phoenix...................................................................... 97
Chương III : GIỚI THIỆU VỀ NGƠN NGỮ CÀI ĐẶT VÀ KẾT QUẢ
CHƯƠNG TRÌNH. ........................................................................................... 100
III.1 Giới thiệu về ngơn ngữ cài đặt ............................................................... 100
III.2 Kết quả chương trình ............................................................................. 111
TÀI LIỆU THAM KHẢO ................................................................................. 116
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 5
CHƯƠNG I: SỰ RA ĐỜI VÀ CÁC KẾT QUẢ CỦA HÌNH HỌC
PHÂN HÌNH.
I.1 SỰ RA ĐỜI CỦA LÝ THUYẾT HÌNH HỌC PHÂN HÌNH:
Sự ra đời của lý thuyết hình học phân hình là kết quả của nhiều thập kỷ
nổ lực giải quyết các vấn đề nan giải trong nhiều ngành khoa học chính xác,
đặc biệt là vật lý và tốn học. Một cách cụ thể, lý thuyết hình học phân hình
được xây dựng dựa trên 2 vấn đề lớn được quan tâm ở những thập niên đầu thế
kỷ 20. Các vấn đề đĩ bao gồm:
Tính hỗn độn của các quá trình phát triển cĩ quy lực trong tự
nhiên.
Sự mở rộng khái niệm số chiều và độ đo trong lý thuyết hình
học Euclide cổ điển.
□ TÍNH HỖN ĐỘN CỦA CÁC QUÁ TRÌNH PHÁT TRIỂN CĨ QUY
LUẬT TRONG TỰ NHIÊN:
Các cơng thức lặp cĩ dạng:
Xn+1=f(Xn)
thường được sử dụng trong các ngành khoa học chính xác để mơ tả các quá
trình lặp đi lặp lại cĩ tính xác định. Các quá trình được xác định bởi cơng thức
trên, trong đĩ f thể hiện mối liên hệ phi tuyến giữa hai trạng thái nối tiếp nhau
Xn và Xn+1, đượ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ệ tố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ự đố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
tố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ự đốn ban đầu. Hơn nữa sai số tính tố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ự đố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 tố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.
- Po là lượng dân số khởi điểm (của một quốc gia, một thành
phố,…).
- Pn là lượng dân số cĩ được sau n năm phát triển.
Ta cĩ quan hệ sau:
Để ý là nếu dân số phát triển đều, tức là R khơng đổi từ năm này sang
năm khác, từ (1) ta sẽ cĩ:
Pn+1 = f(Pn) = (1+R)Pn
Do đĩ sau n năm, lượng dân số khảo sát sẽ là:
Pn = (1+R)n .Po
Cơng thức này chỉ ra sự gia tăng dân số theo hàm mũ là một điều khơng
thực tế. Vì vậy Verhulst đề nghị R thay đổi cùng với lượng dân số được khảo
sát. Một cách cụ thể, Verhust cho R tỉ lệ với tốc độ phát triển dân số theo mơi
trường (P-Pn) / 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:
Pn+1 - Pn
R = , n > 0 (1)
Pn
N - Pn
R = r (2)
N
Pn+1 - Pn N - Pn
= r
Pn N
Pn+1 - Pn
N Pn
= r
Pn N
N
Pk
Pk = ta cĩ:
N
Pn+1 - Pn
= r(1 - Pn)
Pn
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 7
Suy ra:
Pn+1 = Pn + rPn(1 – Pn)
Phương trình này được gọi là phương trình dân số Verhust. Rõ ràng
phương trình được xác định rất đơn giản. Do đĩ, kể từ khi được đưa ra người ta
áp dụng mà khơng nghi ngờ gì về tính ổn định của nĩ. Tuy nhiên khi May khảo
sát phương trình này thì với r thay đổi trong phạm vi khá lớn, ơng đã khám phá
ra sự bất ổn định về tỉ lệ phát triển dân số theo mơi trường Pk.
Các kết quả quan sát chi tiết cho thấy khi số lần lặp n trở nên khá lớn ta
cĩ các trường hợp sau:
- Với 0 < r < 2: Dãy (Pn) tiến đến 1, tức là sự phát triển dân số đạt
mức tối đa.
- Với 2 < r < 2,449: Dãy (Pn) dao động tuần hồ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à Po
Dân số:
Thời gian
Hình vẽ I.1 với r = 2.3 và P0 = 0.01
- Với 2,449 < r < 2,570: Dãy (Pn) 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.2 với r = 2.5
- Với r > 2.570: Dãy (Pn) khơng cịn tuần hồn nữa mà trở nên hỗn
độn, theo nghĩa các giá trị của dãy được chọn một cách hồn tồn
xác định nhưng khơng cĩ thể dự đốn chính xác. Hình vẽ (I.3)
minh hoạ trường hợp r = 3.0 và Po = 0.1
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 8
Dân số
Thời gian
Hình vẽ I.3 với r = 3.0 và Po = 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 hồn 3 thì cũng cĩ chu kỳ tuần hồ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 hồ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 rn 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 rn đĩ, chu kỳ 2n trở nên khơng ổn định nữa và chu kỳ 2n+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:
Sẽ tiến về giá trị = 4.669 khi n. Tính chất này cũng được tìm thấy
trong các tiến trình cĩ chu kỳ lần lượt được nhân đơi và khác với tiến trình
Verhulst. Do đĩ giá trị này ngày nay được gọi là hằng số phổ dụng
Feigenbaum (trong lý thuyết hỗn độn).
□ SỰ MỞ RỘNG KHÁI NIỆM SỐ CHIỀU VÀ ĐỘ ĐO TRONG LÝ
THUYẾT HÌNH HỌC EULIDE CỔ ĐIỂN:
Vào các năm 1890 & 1891, trong khi tìm kiếm các đặc trưng bất biến
của các đối tượng hình học qua các phép biến đổi đồng phơi trong lý thuyết
topo, các nhà tốn học Peano & Hilbert đã phát minh ra các đường cong cĩ
tính chất rất đặc biệt. Đĩ là các đường cong khơng tự cắt theo một quy luật
được chỉ ra bởi Peano và Hilbert, chúng lấp đầy mọi miền hữu hạn của mặt
phẳng. Hình học Euclide cổ điển quan niệm các đường cong như vậy vẫn chỉ là
rn - rn-1
n =
rn+1 - rn
ĐỒ Á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 tốn
số chiều hữu tỷ gây ra nhiều tranh luận tốn học trong các thập kỷ gần đây.
Tiếp sau đĩ, vào năm 1904 nhà tố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
trong tự nhiên” của Benoit B. Mandelbrot xuất bản năm 1982. Trong tác phẩm
của mình, Mandelbrot đã phân rã các dạng cấu trúc phức tạp của tự nhiên
thành các thành phần cơ bản gọi là fractal. Các fractal này chứa đựng các hình
dáng tự đồng dạng với nhiều kích thước khác nhau. Mandelbrot đã tạo nên
những bức tranh fractal trừu tượng đầu tiên và nhận thấy rằng đằng sau các đối
tượng tự nhiên như các đám mây, các dãy núi, các khu rừng, vv… là các cấu
trúc tốn học tương tự nhau. Chúng cĩ khuynh hướng hài hồ về màu sắc và
cân đối về hình thể. Ngồi ra Mandelbrot cũng thiết lập cách xác định số chiều
và độ dài của các dạng fractal cơ sở. Chính với định nghĩa về số chiều này, bài
tốn số chiều khơng nguyên mới được giải quyết một cách hồn chỉnh. Cĩ thể
nĩi cơng trình của Benoit B.Mandelbrot đã chính thức khai sinh lý thuyết hình
học phân hình sau hơn nửa thế kỷ nghiên cứu liên tục.
I.2 SỰ PHÁT TRIỂN CỦA LÝ THUYỂT HÌNH HỌC PHÂN HÌNH:
Kể từ khi ra đời một cách chính thức vào năm 1982 cho đến nay, lý
thuyết hình học phân hình học phân hình đã phát triển một cách nhanh chĩng.
Sau khi đặt nền mĩng cho lý thuyết phân hình, Mandelbrot cùng với các
nhà tốn học khác như A. Douady và J.Hubbard đã phát triển lý thuyết về các
mặt fractal. Các kết quả đạt được chủ yếu tập trung ở các tính chất của các cấu
trúc fractal cơ sở như tập Mandelbrot và tập Julia. Ngồi ra các nghiên cứu
cũng cố gắng tìm kiếm mối liên hệ giữa các cấu trúc này, ví dụ như mối liên hệ
giữa tập Mandelbrot và Julia.
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 10
Dựa trên các cơng trình của Mandelbrot (trong những năm 1976, 1979,
1982) và Hutchinson (1981), vào các năm 1986, 1988 Michael F.Barnsley và
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 tồ nhà,
một cổ máy nhưng lại hồn tồ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 tốn để vẽ nên các fractal của tự nhiên.
Ngồ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 tố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.
▪ Ứ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ẽ.
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 11
Ngồ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 hồ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 tố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.
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 12
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:
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 hố nhờ quá
trình fractal một ảnh số hố 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 tồ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ã hố dưới dạng các dữ
liệu fractal và chỉ chiếm xấp xỉ 600Mb trên một đĩa compact.
Ngồ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à tố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
tốn phi tuyến địi hỏi rất nhiều cơng sức trong việc tính tố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
Đề tài : Hình học Fractal Trang 13
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
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 hố 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.
I.4 CÁC KIẾN THỨC CƠ SỞ CỦA LÝ THUYẾT HÌNH HỌC PHÂN
HÌNH:
I.4.1 ĐỘ ĐO FRACTAL:
□ Số chiều Hausdorff của một tập hợp A Rn:
Cho trước các số thực dương s và . Gọi hs (A) là độ đo Hausdorff s-
chiều của tập A thì hs (A) được xác định bởi:
Hs (A) = lim hs (A)
0
với:
trong đĩ:
diam (Ui) = sup [ d(x,y) : x,y Ui ], với d là metric Euclide trong khơng
gian Rn, [U1, U2,… ] là một phủ mở của A và diam(Ui) < , i.
Hausdorff đã chứng minh được sự tồn tại của một số DH(A) sao cho:
0 khi s > DH(A)
hS(A) =
khi s < DH(A)
Giá trị DH(A) được gọi là số chiều Hausdorff của tập A.
Nĩi cách khác:
DH(A) thì hS(A) cĩ thể là một số thực dương 0 hay .
Định nghĩa này giữ vai trị quan trọng trong lý thuyết hình học phân
hình hiện đại nhưng khơng cĩ tính thực tiễn vì việc xác định số chiều theo định
nghĩa này rất phức tạp ngay cả với trường hợp tập A rất đơn giản. Do đĩ, xuất
phát từ định nghĩa này, Mandelbrot đã đưa ra khái niệm số chiều fractal tổng
quát dễ xác định hơn với ba dạng đặc biệt áp dụng cho từng loại đối tượng (tập
A) cụ thể. Sau đây chúng tơi sẽ trình bày các định nghĩa về các dạng đặc biệt
hs (A) = inf diam(Ui)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 DS là đại lượng xác
định bởi:
Khi đĩ DS được gọi là số chiều tự đồng dạng của cấu trúc đĩ.
Ví dụ:
◊ Xét một hình vuơng được chia thành 9 hình vuơng nhỏ với tỷ lệ đồng
dạng là 1/3. Khi đĩ số chiều tự đồng dạng của hình vuơng ban đầu
được xác định bởi:
◊ Xét một khối lập phương được chia thành 27 khối lập phương nhỏ
hơn với tỷ lệ đồng dạng 1/3. Ta cĩ số chiều của tự đồng dạng của
khối lập phương được xác định bởi:
Hai ví dụ trên cho thấy định nghĩa số chiều tự đồng dạng phù hợp với
định nghĩa thơng thường của hình học Euclide.
□ SỐ CHIỀU COMPA:
Số chiều được xác định theo định nghĩa này được áp dụng cho các
đường cong khơng phải là các đường cong tự đồng dạng hồn tồn (như các
đường bờ biển, các con sơng,…), nhưng cĩ thể sử dụng nhiều đơn vị khác nhau
để xác định độ dài của chúng.
Định nghĩa:
log N
DS =
log 1/r
D 23 log
23 log
3
1
1 log
9 log
s
D 33 log
33 log
3
1
1 log
27 log
s
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 15
Xét một đường cong khơng tự đồng dạng. Biểu diễn số đo của đường
cong trên hệ toạ độ log / log với:
- Trục hồnh: thể hiện logarit của độ chính xác trong phép đo chiều
dài đường cong. Độ chính xác được đặc tả bởi 1/s, với s là đơn vị
đo độ dài. Ở đây giá trị s càng nhỏ thì độ chính xác của phép đo
càng lớn.
- Trục tung: thể hiện logarit của độ dài u đo được ứng với một đơn
vị đo s.
- d: là hệ số gĩc của đường thẳng hồi qui dùng để xấp xỉ các giá trị
đo u đo được dựa trên phương pháp bình phương cực tiểu. Ta cĩ
quan hệ:
log u = d . log (1/s + b), b là hệ số tự do.
Khi đĩ số chiều compa DC được xác định bởi:
DC = 1 + d
Ví dụ:
Xét đường cong 3/2 được xây dựng theo kỹ thuật initiator / generator
chỉ ra bởi hình vẽ sau:
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 8k đoạn, mỗi
đoạn cĩ độ dài s = 1 / 4k nên độ dài của đường cong sẽ là 8k.1/4k = 2k.
Khi đĩ giá trị trên trục hồnh là log41 / 1 / 4k = k ứng với giá trị trên trục
tung là: log42k = k / 2. Do đĩ ta xác định được d = 0.5.
Vậy: DC = 1 + 0.5 = 1.5
generator
initiator
generator
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 16
□ SỐ CHIỀU BOX-COUNTING:
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 log2 (1/s).
- Trục tung biểu thị giá trị của đại lượng log2 N((s)).
- DB 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ĩ:
DB xác định như vậy được gọi là số chiều box-counting của cấu trúc
fractal đã cho.
□ SỐ CHIỀU BOX-COUNTING TRONG MỐI LIÊN HỆ VỚI SỐ
CHIỀU HAUSDORFF:
Định nghĩa:
Gọi N (A) là giá trị nhỏ nhất của các tập hợp cĩ khả năng phủ A và cĩ
đường kính tối đa là . Khi đĩ ta cĩ:
log2N(2 – (k+1)) – log2N(2 – k) N(2 – (k + 1))
DB = = log2
log22 k + 1 – log2 2 k N(2 – k)
sau nhưnR của A chặn bị
con tậpmột trên BD counting- boxchiều số của thức hìnhnghĩa định
một có Ta . s hạngsố các bởis)idiam(U hạngsố các thay cách bằng
này tác thao hóagiản đơn counting- boxchiều Số . s)idiam(U 1 i
hạn
vô tổng định xác việc là Hausdorff chiều số tính khiyếu chủ khănKhó
δ
Σ
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 17
Tuy nhiên 2 định nghĩa số chiều này khơng phảI luơn cho kết quả
giống nhau. Ví dụ xét tập các số hữu tỷ trong khoảng đĩng [0, 1]. Tập này cĩ
số chiều box-counting là 1 trong khi số chiều Hausdorff tương ứng bằng 0.
Kết quả này cịn cĩ thể mở rộng cho tập con trù mật A của Rn, vớI DB(A) = n
và DH(A) n.
I.4.2 CÁC HỆ HÀM LẶP IFS:
□ Khơng gian ảnh Hausdorff:
Giả sử (X, d) là một khơng gian mtric đầy đủ. Ở đây X được giới hạn
bằng R2 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,)idiam(U và A của hạn hữumột phủ là ...} ,2U,1U {
: đó trong
} s
1i
{ infs . (A)N
: vì hơngiản đơn (A)BD định xác nhiên Tuy
. (A)HD của nghĩa định với tự tương (A)BD của nghĩa định ràng rõVậy
} s . (A)N : s { sup } 0s . (A)N : s { inf (A)bD
: đó Do
(A)bD s khi
(A)bD s khi0s . (A)N
: rằng rachỉ trên nghĩa Định
1 log
(A)N log
0
lim(A)bD
δ
δΣδδ
δδδδ
δδ
δ
δ
δ
B y : y)d(x, min B)d(x,
A x : B)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
AnH(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 An
0
cũng thuộc H(X). A cĩ thể được đặc tả như sau:
A = [ x X : một dãy Cauchy [ xn An] hội tụ về x]
□ Ánh xạ co trên khơng gian Hausdorff:
Bổ đề 1:
Giả sử w: X X là một ánh xạ co liên tục trên khơng gian metric (X,
d). Khi đĩ w liên tục.
Chứng minh:
Cho s > 0. Gọi s là hệ số co của w. Khi đĩ:
d(w(x), w(y)) s.d(x,y) <
Khi và chỉ khi:
D(x,y) < = / s
Từ đĩ suy ra điều phải chứng minh.
Bổ đề 2:
Giả sử w: X X là một ánh xạ liên tục trên khơng gian metric(X,d).
Khi đĩ w ánh xạ khơng gian H(X) lên chính nĩ.
Chứng minh:
Giả sử S là một tập con compact khác rỗng của X. Khi đĩ ta cĩ:
w(S) = [w(x) : x S] là một tập khác rỗng. Ta chứng minh w(S)
compact. Xét [ yn = w(xn) ] là một dãy vơ hạn điểm của w(S).
Khi đĩ [xn] cũng là một dãy vơ hạn điểm trong S. Vì S compact
nên tồn tại một dãy con [xn ] 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 [ yNn = f (xNn ) ] là một dãy con
của [ yn ] 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).
Ta cĩ:
d( w(B), w(C)) = max [ min [ d(w(x), w(y)): y C ] : x B ]
max [ min [ s.d(x,y) : y C ]: x B ]
= s.d(B, C)
Một cách tương tự:
d( w(C), w(B)) s.d(C, B)
Do đĩ:
H(w(B), w(C)) = max [d(w(B), w(C), w(C), w(B)) ]
s.max [ d(B, C), d(C, B) ]
= s.h(B, C)
Từ đĩ suy ra điều phải chứng minh.
Bổ đề 4 sau đây cung cấp một cách thức cơ bản để nối kết các ánh xạ co
trên (H(X), h) thành các ánh xạ co mới trên (H(X), h):
Bổ đề 4:
Ký hiệu [wn ] là các ánh xạ co trên (H(X), h) với các hệ số co tương ứng
sn, n = 1, 2,…,N. Xác định W : H(X) H(X) bởi:
N
W(B) = wn (B)
n=1
với B H(X). Khi đĩ W là ánh xạ co với hệ số co s = max sn.
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,2s , C).h(B,1s { max
(C))}2w , (B)2 h(w, (C))1w , (B)1 h(w{ max
(C)) 2w (C)1w , (B) 2w (B)1 h(w W(C)), h(W(B)
ĐỒ Á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 nguyên 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 wn với hệ số co tương ứng sn, 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; wn, n = 1, 2,…, N]
và hệ số co s = max sn
1nN
Định lý sau tĩm tắt các kết quả chính của một IFS:
Định lý IFS:
Định nghĩa 2:
Điểm bất động A H(X) mơ tả trong định lý IFS được gọi là hấp tử của
IFS đĩ.
ns 1kn 1
max)1ks,Tmax(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)1kwT(B) W(B)
:viết thể có Vậy .ns kn 1
max Ts co số hệvới H(X) trên
co xạ ánhmột là T có ta nạp quithuyết giả do thì nw
k
1n
TĐặt
(B)1kw(B)nw
k
1n
(B)nw
1k
1n
W(B)
. H(X) B bất kỳvới (B)n W
n
lim A bởitrước cho được và
(A)nw
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)nw
N
1n
W(B)
: bởiđịnh xác H(X) H(X)
: Wđổi biến phépđó Khi . s co số hệvới N}, ... 1,2,n,nw{X; IFSmộ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
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 hồn tồ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:
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à tố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:
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 tồn bộ đường cong ở bước
thứ (k–1).
R
ND
1log
)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à:
Để viết một đoạn mã cho việc phát sinh ra đường hoa tuyết, chúng ta
cần phải trình bày về đồ hoạ con rùa (turtle graphic). Loại đồ hoạ này gồm một
số hàm thao tác chính sau:
Hàm Point (X1, Y1, X2, Y2):
Hàm này tính gĩc giữa con rùa và trục x (tức là tính gĩc giữa đoạn
thẳng cĩ hai đầu mút cĩ toạ độ (X1, Y1) và (X2, Y2) ) theo độ đo gĩc thơng
thường. Sau đây là đoạn mã mơ tả cách cài đặt hàm:
/* EDIT CODE */
#include”stdafx.h”
#include”math.h”
#define PI 3.141593
double Point(double X1, double Y1, double X2, double Y2)
double Theta,Temp=180/PI;
if((X2-X1)= = 0)
if(Y2 > Y1)
Theta= 90;
else
Theta = 270;
else
Theta= atan((Y2 -Y1) / (X2 -X1)) * Temp;
if (X1 > X2)
Theta += 180;
return Theta;
Hàm Turn (Angle, Turtle-Theta):
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
4log
1log
)log(
R
ND
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 23
Hàm này di chuyển con rùa đi một bước. Chiều dài của mỗi bước
là Turtle-R. Ở đây hàm sử dụng vị trí con rùa hiện tại cĩ toạ độ (Turtle-X,
Turtle-Y) và gĩc định hướng là Turle-Theta để xác định vị trí toạ độ mới sau
khi di chuyển một bước. Đoạn mã sau đây minh hoạ cho cách cài đặt:
void Step(double &Turtle_X, double &Turtle_Y,
double Turtle_R, double Turtle_Theta)
Double Temp=PI/180;
Turtle_X+=Turtle_R*cos(Turtle_Theta* Temp);
Turtle_Y+=Turtle_R*sin(Turtle_Theta* Temp);
Giả sử initiator gồm N điểm, mỗi điểm cĩ toạ độ là (x[i], y[i] ) và đường
hoa tuyết cĩ mức là Level (mức bắt đầu là 1), thì việc tạo ra đường hoa tuyết
như sau (các đường sau này được tạo ra cũng giống như vậy):
For(i= 0 ; i< N ;++i)
-Generator(x[i],y[i],x[i+1],y[i+1],Level);
Với hàm –Generator tương ứng với đoạn mã như sau:
//Phát sinh họ đường Vonkock:
void Generator(CDC *pDC,double X1, double Y1, double X2,
double Y2, int Level,int NumLines,double
LineLen,double Angles[])
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<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++)
X1=XPoints[ I ];
Y1=YPoints[ I ];
X2=XPoints[ I +1];
Y2=YPoints[ I +1];
Generator(pDC,X1,Y1,X2,Y2,Level,
NumLines,LineLen,Angles);
else
for (I= 0; I<NumLines; I++ )
pDC->MoveTo((int)XPoints[ I ], (int) YPoints [ I ]);
pDC->LineTo((int)XPoints[ I+1 ], (int) YPoints [ I+1 ]);
delete[]XPoints;
delete[]YPoints;
Hàm này cũng cĩ thể áp dụng cho việc phát sinh ra các đường khác
cùng họ. Chẳng hạn sau đây là một minh hoạ cho hình vẽ trình bày ở mức 3
của đường Von Kock-Snowflake.
Hình : Đường Von Kock-Snowflake mức 3.
Lưu đồ của đoạn mã ở trên như sau:
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 25
Level >0
Đ
S
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}.
Bắt đầu
Khởi động initiator,
Level, Generator
Thay Thế mỗi đoạn
thẳng bằng Generator
Kết Thúc
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 26
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ạ độ.
□ ĐƯỜ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
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
'119
944910
14
75
7
16
7
181
6
81
132
91
2
cos
cos2
7
1
72/3291
0
222222
222
222
R
R
R
RR
AEAB
EBAEAB
AEABABAEEB
R
RRRRR
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 27
Vì N = 3 nên số chiều fractal của đường Gosper là:
Hình sau là mức đầu tiên của đường Gosper.
Đ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 }
Ngồ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.
Hình sau là mức 3 của đường Gosper.
1291.1
7log
3log
D
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 28
Hình : Đường Gosper ở mức 3.
□ ĐƯỜ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:
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 29
Để 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
EB2 = EA2 + AB2 – 2EA.AB.cos
Vì N = 3 nên số chiều fractal là:
Hình sau là mức đầu tiên của đường cong Von Kock bậc hai 3-đoạn:
Đoạn mã đối với đường 3-đoạn giống như đoạn mã của đường hoa
tuyết.
Trong đĩ:
NumLines = 3
Mảng Angle cĩ giá trị sau: {26.56, -90.0 }
Ngồi ra, đường Von Kock 3-đoạn cĩ các mức khác nhau thì tương ứng
với các hình dạng khác nhau.
5
1
R
'5625
894427.0
5
52
5
14
5
131
4
31
1.2.2
14
2
cos
0
222222
R
R
R
RR
EAAB
EAABEA
3652.1
5log
3log
D
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 30
Hình sau là mức 4 của đường Von Kock 3-đoạn.
□ ĐƯỜ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ĩ:
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à:
Với 1/R là số chẵn
Với 1/R là số lẻ.
Do vậy R = 1/4 nên Nmax = 8. Số chiều fractal là:
2max 2
1
R
N
2
2
max 2
1
R
RN
5.1
4log
8log
D
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 31
Hình sau là mức đầu tiên của đường cong:
Đ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ồi ra, đường Von Kock 8-đoạn cĩ các mức khác nhau thì tương ứng
với các hình dạng khác nhau.
Hình sau là mức 5 của đường Von Kock 8-đoạn.
□ ĐƯỜ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:
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 32
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à:
Hình sau là mức đầu tiên của đường cong Vonkock bậc hai 18 đoạn:
Đ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ồi ra, đường Von Kock 18-đoạn cĩ các mức khác nhau thì tương
ứng với các hình dạng khác nhau.
6131.1
6log
18log
D
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 33
Hình sau là mức 5 của đường Von Kock 18-đoạn:
□ ĐƯỜ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:
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à:
6667.1
8log
32log
D
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 34
Hình sau là mức đầu tiên của đường cong:
Đ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:
Ngồi ra, đường Von Kock 32-đoạn cĩ các mức khác nhau thì tương
ứng với hình dạng khác nhau.
0,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,90,90
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 35
Hình sau là mức 4 của đường VonKock 32-đoạn:
□ ĐƯỜ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:
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à:
6990.1
10log
50log
D
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 36
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 ngồ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 ngồ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 để hồn tất quá trình.
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 37
Hình sau là mức đầu tiên của đường cong Von Kock bậc hai 50 đoạn:
Đ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 }
Ngồi ra, đường Von Kock 50-đoạn cĩ các mức khác nhau thì tương
ứng với các hình dạng khác nhau.
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 38
Hình sau là mức 3 của đường Von Kock 50-đoạn:
□ 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 để hồn tất generator.
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 39
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ĩ:
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à:
Thật vậy:
Ta cĩ:
CD2 = CB2 + DB2 – 2.CB.DB.cos600
Mà:
CB = 1/3
DB = 2/3
Do đĩ, chiều dài mỗi đoạn của generator nhỏ là:
Vậy chúng ta cĩ:
1. DMR
9
3
R
3
3
2
1
3
2
3
12
9
4
9
12
CD
CD
9
33/ CDR
238361.1
1
9
35
3
16
D
DD
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 40
Hình sau là mức đầu tiên của đường cong (ở đây initiator là một đoạn
thẳng).
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.
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:
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 41
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;
for (I=1 ; I<Split ;++I)
Step(Turtle_X, Turtle_Y, Turtle_R, Turtle_Theta);
XPoints[ I ]=Turtle_X;
YPoints[ I ]=Turtle_Y;
Turn(Angles[ I ]*Sign,Turtle_Theta);
for (I=NumLines -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);
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 42
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)
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 ];
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 43
ComplexVonKockGenerator(pDC,X1,Y1,X2,Y2,Level,Type,Sign,
NumLines,LineLen,Angles);
else
for (I= 0 ; I<NumLines ; I++ )
pDC->MoveTo((int)XPoints[ I ],(int) YPoints [ I ]);
pDC->LineTo((int)XPoints[ I+1 ],(int) YPoints [ I+1 ]);
delete[]XPoints;
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} và NumLines =
11
Hàm này cũng cĩ thể áp dụng cho việc phát sinh ra các đường khác, với
các mức khác nhau. Chẳng hạn sau đây là một minh hoạ cho hình vẽ trình bày
ở mức 5 của đường Complex_Von Kock_Generator.
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 44
Hình : Đường Complex-Von Kock-Generator ở mức 5.
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 hồn tồ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
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 45
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à:
Hình sau là mức thứ hai của đường cong:
Đ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:
□ ĐƯỜ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:
2
3log
9log
DD
0,90,90,90,90,90,90,90,0
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 46
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.
Hình sau là mức thứ hai của đường cong Peano cải tiến:
Để phát sinh ra đường này, chúng ta sử dụng hàm –Geneator như sau:
// 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];
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 47
--Level;
XPoints[0]= X1;
YPoints[0]= Y1;
Turtle_Theta = Point(X1,Y1,X2,Y2);
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;
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 48
YPoints[NumLines]= Y2;
for (I=1; I<NumLines; ++I)
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<NumLines ;++I)
pDC->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
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 49
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
đầ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à:
Giả sử đoạn thẳng ban đầu cĩ chiều dài là 1. Khi đĩ số chiều fractal là:
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 hồn tồ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
2
1R
2
2log
2log
DD
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 50
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;
Turtle_Y=Y1;
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 51
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<NumLines -1 ;++I )
X1 = XPoints [ I ];
Y1 = YPoints [ I ];
X2 = XPoints [ I+1 ];
Y2 = YPoints [ I+1 ];
CesaroTriangleGenerator(pDC, X1, Y1, X2,
Y2Level, NumLines, LineLen, Angles,
Sign );
else
for ( I= 0; I<NumLines;++I )
pDC->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ẽ.
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 52
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 hồn tồ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ĩ:
Mà
Ta cĩ:
cos2222 CEDEDECEc
0
2020
2
0
2
2
0
5sin.
)5(sin10cos1
2
10cos
22
2
2
10,2/
ac
aaaaac
aDECE
9128442.0
2
)5sin1(
2
)5sin1(2
2
0
0
aab
ab
acb
ABDBCDAC
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 53
Đ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 ];
ModifiedCesaroGenerator(pDC, X1, Y1, X2,
Y2,Level,NumLines, LineLen, Angles,Sign);
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 54
else
for (I= 0; I<NumLines -2; ++I)
pDC->MoveTo((int)XPoints[ I ],(int)YPoints[ I ]);
pDC->LineTo((int)XPoints[ I+3 ],(int)YPoints[ I+3 ]);
for (I= 1; I<NumLines -1; ++I)
pDC->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.
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 55
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);
Turtle_X=X1;
Turtle_Y=Y1;
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 56
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<NumLines -1; ++I)
X1 = XPoints [ I ];
Y1 = YPoints [ I ];
X2 = XPoints [ I+1 ];
Y2 = YPoints [ I+1 ];
OtherCesaroGenerator(pDC, X1, Y1, X2, Y2,
Level,NumLines,LineLen,
Angles,Sign );
else
for( I= 0; I<NumLines; ++I )
pDC->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
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:
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 57
Đ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 ];
PolyaGenerator(pDC, X1, Y1, X2, Y2, Level,
NumLines, LineLen, Angles, Sign );
Sign[Level]* = -1;
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 58
else
for (I= 0; I<NumLines; ++I)
pDC->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):
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 59
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
Vì generator cĩ số đoạn thẳng N = 7 nên số chiều fractal là:
Đường này cĩ tính chất 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:
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];
7
1
72/3291 222
D
RRRRR
2
7log
7log
DD
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 60
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);
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,Turtle_Theta);
if(Level)
for (I=0 ; I<NumLines ;++I)
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 61
switch(I)
case 0:
case 3:
case 4:
case 5:
Type = 0;
break;
case 2:
case 1:
case 6:
Type = 3;
break;
X1 = XPoints[ I ];
Y1 = YPoints[ I ];
X2 = XPoints[ I+1 ];
Y2 = YPoints[ I+1 ];
PeanoGosperGenerator(pDC,X1,Y1,X2,Y2,Level,
Type,NumLines,LineLen,Angles);
else
for (I= 0 ; I<NumLines ; I++ )
pDC->MoveTo((int)XPoints[ I ],(int) YPoints [ I ]);
pDC->LineTo((int)XPoints[ I+1 ],(int) YPoints [ I+1 ]);
delete[]XPoints;
delete[]YPoints;
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à:
0,0,120,60,120,60,1.19
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 62
□ ĐƯỜ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à:
(theo cách tính ở phần generator phức tạp).
Do đĩ:
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:
3
3
R
21
3
3
3
16
D
DD
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 63
Đ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 ;
--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)
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 64
Step(Turtle_X, Turtle_Y, Turtle_R, Turtle_Theta);
XPoints[ I ]=Turtle_X;
YPoints[ I ]=Turtle_Y;
Turn(Angles[ I ]*Sign,Turtle_Theta);
for (I=NumLines -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:
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
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 65
for (I= 0 ; I<NumLines ; I++ )
pDC->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à:
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:
60,0,60,60,60,0,60
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 66
□ ĐƯỜ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 tồ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:
Đ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;
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 67
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;
Turn(Angles[ 0 ]*Sign,Turtle_Theta);
for (I=1; I<Split; ++I)
Step(Turtle_X, Turtle_Y, Turtle_R, Turtle_Theta);
XPoints[ I ]=Turtle_X;
YPoints[ I ]=Turtle_Y;
Turn(Angles[ I ]*Sign,Turtle_Theta);
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 68
for (I=NumLines -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);
XPoints[ I ]=Turtle_X;
YPoints[ I ]=Turtle_Y;
Turn(Angles[ I ]*Sign,Turtle_Theta);
for (I=10; I>=9 ;--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 1:
case 2:
case 3:
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 69
case 4:
case 8:
case 9:
case 12:
Type =0;
break;
case 0:
case 5:
case 6:
case 7:
case 10:
case 11:
Type = 1;
break;
X1 = XPoints[ I ];
Y1 = YPoints[ I ];
X2 = XPoints[ I+1 ];
Y2 = YPoints[ I+1 ];
Peano13-DoanGenerator(pDC,X1,Y1,X2,Y2,Level,Type,Sign,
NumLines,LineLen,Angles);
else
for (I= 0; I<NumLines; I++ )
pDC->MoveTo((int)XPoints[ I ],(int) YPoints [ I ]);
pDC->LineTo((int)XPoints[ I+1 ],(int) YPoints [ I+1 ]);
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à:
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:
60,0,60,0,60,60,60,0,60,60,60,0,60
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 70
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 hồn
tồ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.
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.
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 71
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:
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];
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 72
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;
}
}
else
for(i=0;i<NumLines;i++)
{
pDC->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 ].
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 73
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 hồn tồ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 TỐ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
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ệ
210 DDD
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 74
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:
(a)
Ở đâ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:
(b)
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 tốn:
(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;
nBnB
1
21
nLnL
3
2
21
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 75
(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);
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à Color2.
+ Nếu Level >= 3 thì màu hiện thời là Color3.
If (Level < 3)
DrawLine (X, Y, X2, Y2, Width, Color2);
Else
DrawLine (X, Y, X2, Y2, Width, Color3);
iv) Nếu 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)
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 76
{
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.
ĐỒ ÁN TỐT NGHIỆP SVTH: Nguyễn Ngọc Hùng Cường
Đề tài : Hình học Fractal Trang 77
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
Các file đính kèm theo tài liệu này:
- ĐỒ Á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.pdf