intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Đồ họa máy tính - Chương 5 Tô màu, Font chữ - Bài 15

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST
Báo xấu
148
lượt xem 21
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tô màu, Font chữ $15. Các thuật toán về đa giác Trong kỹ thuật đồ hoạ có nhiều bài toán phức tạp đ-ợc chuyển về các bài toán về đa giác chính vì vậy trong phần này chúng ta sẽ khảo sát một số thuật toán liên quan đến đa giác

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đồ họa máy tính - Chương 5 Tô màu, Font chữ - Bài 15

  1. Kü thuËt §å ho¹ m¸y tÝnh Ch−¬ng 5 t« mμu, Font ch÷ $15. C¸c thuËt to¸n vÒ ®a gi¸c Trong kü thuËt ®å ho¹ cã nhiÒu bµi to¸n phøc t¹p ®−îc chuyÓn vÒ c¸c bµi to¸n vÒ ®a gi¸c chÝnh v× vËy trong phÇn nµy chóng ta sÏ kh¶o s¸t mét sè thuËt to¸n liªn quan ®Õn ®a gi¸c §Þnh nghÜa 1: Mét ®a gi¸c n ®Ønh gäi lµ ®a gi¸c låi nÕu ®o¹n th¼ng chøa hai ®iÓm bÊt kú cña ®a gi¸c n»m trong ®a gi¸c E Y X D A X Y B C §Þnh nghÜa 2: §a gi¸c th«ng th−êng lµ ®a gi¸c cã n ®Ønh, n c¹nh, mçi ®Ønh lµ ®iÓm ®Çu cña mét c¹nh vµ ®iÓm cuèi cña mét c¹nh kh¸c. Mçi ®Ønh kh«ng ph¶i lµ ®iÓm xuÊt ph¸t cña 2 c¹nh, c¸c c¹nh ®a gi¸c kh«ng c¾t nhau ë c¸c ®iÓm nµo kh¸c trªn ®Ønh cña nã 1. X¸c ®Þnh ®iÓm trong hay ngoµi ®a gi¸c Bµi to¸n : Cho mét ®a gi¸c th−êng vµ mét ®iÓm P h·y x¸c ®Þnh P lµ ®iÓm trong hay ®iÓm ngoµi cña ®a gi¸c ThuËt to¸n thø nhÊt: Gi¶ sö ®a gi¸c W cã c¸c ®Ønh P1,P2........Pn ®−îc ®¸nh sè theo chiÒu kim ®ång hå Nèi P víi tÊt c¶ c¸c ®Ønh P1,P2.....Pn cña ®a gi¸c W. Ta gäi αi lµ gãc t¹o bëi PPi vµ PPi+1 i=1,2......n+1 (Pn+1 =P1) 84
  2. Kü thuËt §å ho¹ m¸y tÝnh P5 α5 α4 P1 P4 α1 α3 P2 α2 P3 Gãc αi cã dÊu + nÕu PPi dÞch chuyÓn theo chiÒu kim ®ång hå tuú víi PPi+1, ng−îc l¹i αi cã dÊu - khi ®ã nÕu n n ∑ α i = 360 O th× P lµ ®iÓm trong cña ®a gi¸c nÕu ∑ α i = 0 th× P n»m ngoµi ®a i =1 i =1 gi¸c P5 P3 P4 P1 + P4 P2 P1 + P2 P3 P ThuËt to¸n 2: §Ó x¸c ®Þnh P lµ ®iÓm trong hoÆc ngoµi cña ®a gi¸c ta cã thÓ thùc hiÖn theo thuËt to¸n kh¸c Gi¶ sö cho ®a gi¸c W vµ P lµ ®iÓm bÊt kú ®Ó x¸c ®Þnh P lµ ®iÓm trong hay ngoµi ®a gi¸c ta thùc hiÖn c¸c b−íc sau: theo h−íng B−íc 1: Tõ P kÎ nöa ®−êng th¼ng s tuú ý kh«ng gi¶m tæng qu¸t cã thÓ chän h−íng // víi trôc OX vµ phÝa ph¶i B−íc 2: TÝnh sè giao ®iÓm cña N cña nöa ®−êng th¼ng l víi c¸c c¹nh cña ®a gi¸c B−íc 3: KiÓm tra nÕu N ch½n ⇒ P n»m ngoµi, nÕu N lÎ ⇒ P n»m trong VÝ dô: P6 l P P l 85
  3. Kü thuËt §å ho¹ m¸y tÝnh Chó ý: 1. §Ó tÝnh ®iÓm giao cña nöa ®−êng th¼ng l víi c¸c c¹nh cña ®a gi¸c ta kh«ng cÇn ph¶i t×m ®iÓm giao cña l víi tÊt c¶ c¸c c¹nh cña ®a gi¸c, cã thÓ c¶i tiÕn ®Ó thuËt to¸n lµm viÖc nhanh h¬n dùa vµo nhËn xÐt sau: Gi¶ sö P cã to¹ ®é (xo,yo) vµ Pi cã to¹ ®é (xi,yi), i = 1, n . C¹nh (Pi,Pi+1) kh«ng cÇn ph¶i tÝnh ®iÓm giao víi l nÕu max(xi,xi+1)xo vµ (yi-yo)(yi+1-yo)
  4. Kü thuËt §å ho¹ m¸y tÝnh 2. ThuËt to¸n ph©n chia ®a gi¸c a. H×nh thang c¬ b¶n H×nh thang c¬ b¶n lµ h×nh thang cã d¹ng sau H×nh thang c¬ b¶n lµ h×nh thang trong ®ã cã 2 cÆp ®Ønh cã cïng to¹ ®é y (x3,y3) (x4,y4) (x1,y1) (x2,y2) (x4,y4) (x3,y3) (x3,y3) (x4,y4) (x1,y1) (x2,y2) (x1,y1) (x2,y2) NÕu x3=x4 hoÆc x1=x2 th× h×nh thang c¬ b¶n biÕn d¹ng thµnh tam gi¸c do ®ã tam gi¸c lµ mét h×nh thang c¬ b¶n (x2,y2) (x3,y3) (x3,y3) (x1,y1) (x2,y2) (x1,y1) H×nh thang c¬ b¶n lµ mét ®a gi¸c ®¬n gi¶n nhÊt, viÖc t« mµu trªn nã ch¼ng h¹n lµ rÊt ®¬n gi¶n, v× vËy ta ph¶i cÇn ph©n chia mét ®a gi¸c thµnh tæng c¸c h×nh thang c¬ b¶n. b. Ph©n chia ®a gi¸c thµnh c¸c h×nh thang c¬ b¶n Bµi to¸n : Cho W lµ mét ®a gi¸c th−êng. H·y ph©n chia ®a gi¸c thµnh tæng c¸c h×nh thang S1, S2, ..., Sm sao cho : W = S1 ∪S 2 ∪...∪S m S i ∩S j = ∅ ∀ i, j = 1, m i ≠ j + ThuËt to¸n Brasel vµ Fagrat : 87
  5. Kü thuËt §å ho¹ m¸y tÝnh Gi¶ sö c¸c ®Ønh cña ®a gi¸c W lµ Wi=(xi,yi), i=1,2,..,n. C¸c ®Ønh cña ®a gi¸c ®−îc ®¸nh sè theo chiÒu ng−îc kim ®ång hå sao cho phÇn thuéc ®a gi¸c lu«n lu«n n»m vÒ phÝa cña canh WiWi+1. NÕu kh«ng chóng ta ®¸nh sè l¹i c¸c ®Ønh ®Ó ®¹t ®−îc ®iÒu nµy ®Ó ®¬n gi¶n cho viÖc tr×nh bµy thuËt to¸n ta gi¶ sö W kh«ng cã c¸c c¹nh // víi Ox W5 W4 W3 W1 W2 B−íc 1 : thùc hiÖn ph©n chia c¸c ®Ønh cña ®a gi¸c thµnh 3 lo¹i sau : + §Ønh Wk=(xk,yk) gäi lµ ®Ønh låi nÕu cã 2 ®Ønh Wk-1=(xk-1,yk-1), Wk+1=(xk+1,yk+1) tho¶ m·n ®iÒu kiÖn yk-1>yk; yk+1>yk. + §Ønh Wk=(xk,yk) gäi lµ ®Ønh lâm nÕu cã 2 ®Ønh Wk-1=(xk-1,yk-1), Wk+1=(xk+1,yk+1) tho¶ m·n ®iÒu kiÖn yk-1
  6. Kü thuËt §å ho¹ m¸y tÝnh C¸c h×nh thang c¬ b¶n sÏ lµ c¸c h×nh giíi h¹n bëi c¸c ®o¹n th¼ng (P1,P2), (P3,P4) ......(P2n-1, P2m) vµ c¸c ®o¹n th¼ng thuéc c¸c c¹nh cña ®a gi¸c VÝ dô: Bµi tËp: W1 W8 W1 W5 1 2 2 3 3 W6 W2 4 W2 5 7 6 5 8 W7 W4 9 6 W4 W5 W3 W3 H·y diÔn ®¹t chÝnh x¸c thuËt to¸n trªn vµ lËp ch−¬ng tr×nh ph©n chia ®a gi¸c thµnh c¸c h×nh thang c¬ b¶n $16. C¸c thuËt to¸n t« mμu 1. ThuËt to¸n t« mµu h×nh thang c¬ b¶n Gi¶ sö cho h×nh thang c¬ b¶n cã d¹ng: (x3y3) ( x4 y4 ) (x1y1) (x2y2) ThuËt to¸n nh− sau: 1. §Æt ymin=y1; ymax=y3; m=ymax-ymin+1 2. tÝnh hÖ sè gãc Cl=(x4-x1)/(y4-y1) Cr=(x3-x2)/(y3-y2) 2. §Æt yi=ymin+(i-1) i = 1,m tÝnh x li = x 1 + (y i − y 1 ).C l x ir = x 2 + (y i − y 2 ).C r 89
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2