Bài giảng Xén hình

CH
NG III XÉN HÌNH 3.1. T VN  Cho m
t min D ⊂ Rn và F là m
t hình trong Rn (F ⊂ Rn). Ta gi F ∩ D là hình có c t F bng cách xén vào trong D và ký hi u là ClipD(F). Bài toán  t ra là xác nh ClipD(F). 3.2. XÉN ON THNG VÀO VÙNG HÌNH CH NH T CA R2 3.2.1. Cnh c a hình ch nht song song vi các trc ta  Lúc này: D =
     ≤≤ ≤≤ ∈ maxmin maxmin |),( 2 YyY XxX Ryx và F là on th ng ni 2 im (x1,y1), (x2,y2) nên phng trình ca F là: x x x x t y y y y t = + − = + −    1 2 1 1 2 1 ( ). ( ). t ∈ [0,1] Do ó, F có th c vit di dng: F = {(x,y) ∈ R2 | x = x1 + (x2 -x1).t; y = y1 + (y2 -y1).t; 0 ≤ t ≤ 1} Khi ó, giao im ca F và D chính là nghi m ca h bt phng trình (theo t): Xmin x1+ (x2 - x1). t Xmax Ymin 1+ (y2 - y1). t max 0 t 1 ≤ ≤ ≤ ≤ ≤ ≤      y Y Gi N là tp nghi m ca h phng trình trên. Nu N = ∅ thì ClipD(F) = ∅ Nu N ≠ ∅ thì N = [t1, t2] (t1 ≤ t2) Gi P, Q là 2 giao im xác nh bi: xMin xMax X y yMax yMin A B P Q Hình 3.1 Ch
ng III. Xén hình 33 Px x x x t Py y y y t = + − = + −    1 2 1 1 1 2 1 1 ( ). ( ). Qx x x x t Qy y y y t = + − = + −    1 2 1 2 1 2 1 2 ( ). ( ). thì: ClipD(F) = PQ (Hình 3.1) 3.2.1.1. Thut toán Cohen - Sutherland • Chia m t ph ng ra làm 9 vùng, mi vùng ánh m
t mã nh phân 4 bit (hình 3.2). Bit 1: Qui nh vùng nm bên trái ca s Bit 2: Qui nh vùng nm bên phi ca s Bit 3: Qui nh vùng nm bên di ca s Bit 4: Qui nh vùng nm bên trên ca s • Xét im P ∈ R2 : Pleft =    < laûi Ngæåüc0 minP nãúu x X1 PRight =    > laûi Ngæåüc0 maxP nãúu x X1 PBelow =    < laûi Ngæåüc0 minP nãúu y Y1 PAbove =    > laûi Ngæåüc0 maxP nãúu y Y1 • Xét on th ng AB, ta có các trng hp sau: i/ Nu Mã(A) = Mã(B) = 0000 thì AB ∈ D  ClipD(F) = AB ii/ Nu Mã(A) AND Mã(B) ≠ 0000 thì on AB nm hoàn toàn bên ngoài hình ch nht  ClipD(F) = ∅ Chú ý: Phép toán AND là phép toán Logic gia các bit. iii/ Nu (Mã(A) AND Mã(B) = 0000) và (Mã(A) ≠ 0000 ho c Mã(B) ≠ 0000) thì: Gi s Mã(A) ≠ 0000 ⇔ A nm ngoài hình ch nht. ♦ Nu Aleft = 1 : thay A bi im nm trên on AB và ct cnh trái (ni dài) ca hình ch nht. 100 0 000 0 101 0 001 0 011 0 010 0 010 1 000 1 100 1 Hình 3.2 Ch
ng III. Xén hình 34 ♦ Nu Aright = 1: thay A bi im nm trên on AB ct cnh phi (ni dài) ca hình ch nht. ♦ Nu ABelow = 1: thay A bi im nm trên on AB và ct cnh di (ni dài) ca hình ch nht. ♦ Nu AAbove = 1: thay A bi im nm trên on AB và ct cnh trên (ni dài) ca hình ch nht. Chú ý: Quá trình này c l p li: Sau mi ln l p, ta phi tính li mã ca A. Nu cn, phi i vai trò ca A và B  m bo A luôn luôn nm bên ngoài hình ch nht. Quá trình s dng khi x y ra m
t trong 2 trng hp: i/ ho c ii/ 3.2.1.2. Thut toán chia nh phân • Ý tng ca thut toán này tng t! nh thut toán tìm nghi m bng phng pháp chia nh phân. • M
nh : Cho M: trung im ca on AB, Mã(A) ≠ 0000, Mã(B) ≠ 0000, Mã(M) ≠ 0000 thì ta có: [Mã(A) AND Mã(M)] ≠ 0000 hoc [Mã(M) AND Mã(B)] ≠ 0000. Ý ngha hình hc c a mnh : Nu c ba im A, B, M  u  ngoài hình ch nh t thì có ít nht mt on hoàn toàn nm ngoài hình ch nh t. • Ta phát tho thut toán nh sau: i/ Nu Mã(A) = 0000 và Mã(B) = 0000 thì ClipD(F) = AB ii/ Nu Mã(A) AND Mã(B) ≠ 0000 thì ClipD(F) = ∅ iii/ Nu Mã(A) = 0000 và Mã(B) ≠ 0000 thì: P:=A; Q:=B; Trong khi |xP -xQ| + |yP - yQ| ≥ 2 thì: ♦ Ly trung im M ca PQ; ♦ Nu Mã(M) ≠ 0000 thì Q:= M. Ch
ng III. Xén hình 35 Ngc li: P:= M.  ClipD(F) = AP iv/ Nu Mã(A) ≠ 0000 và Mã(B) = 0000 thì: "i vai trò ca A, B và áp d#ng ii/ v/ Nu Mã(A) ≠ 0000 ≠ Mã(B) và [Mã(A) AND Mã(B)]= 0000 thì: P:=A; Q:=B; Ly M: trung im PQ; Trong khi Mã(M) ≠ 0000 và |xP - xQ| + |yP - yQ| ≥ 2 thì: ♦ Nu Mã(M) AND Mã(Q) ≠ 0000 thì Q:=M. Ngc li P:=M. ♦ Ly M: trung im PQ. Nu Mã(M) ≠ 0000 thì ClipD(F) = ∅ . Ngc li, áp d#ng ii/ ta có: ClipD(MA) = MA1 ClipD(MB) = MB1 Suy ra: Clip D (F) = A 1 B 1 3.2.1.3. Thut toán Liang - Barsky " t ∆x = x2 - x1 ∆y = y2 - y1 p1 = - ∆x q1 = x1 - xMin p2 = ∆x q2 = xMax - x1 p3 = - ∆y q3 = y1 - yMin p4 = ∆y q4 = yMax - y1 thì h bt phng trình giao im ca F và D có th vit li:    ≤≤ =≤ 1..4k ,Q.tP kk 10 t Xét các trng hp sau: i/ ∃k: Pk = 0 và Qk < 0: ( "ng th ng song song vi các biên và nm ngoài vùng hình ch nht ) Ch
ng III. Xén hình 36  ClipD(F) = ∅ ii/ ∀k ∈ {1,2,3,4}: Pk ≠ 0 ho c Qk ≥ 0: " t K1 = {k | Pk > 0 } K2 = {k | Pk < 0 } u1 = Max({ k k P Q | k ∈ K2} ∪ {0}) u2 = Min({ k k P Q | k ∈ K1} ∪ {1}) Nu u1 > u2 thì ClipD(F) = ∅ Ngc li: Gi P, Q là 2 im th$a    ∆+= ∆+= 1 1 1 1 uyyPy uxxPx . . và    ∆+= ∆+= 2 2 1 1 uyyQy uxxQx . . thì ClipD(F) = PQ 3.2.2. Khi cnh c a vùng hình ch nht to vi trc hoành mt góc α∈(0,Π/2) Ta dùng phép quay tr#c ta 
 a bài toán v trng hp các cnh ca hình ch nht song song vi các tr#c ta 
(hình 3.3). Gi R là ma trn quay ca phép i tr#c, ta có: X Y min min  = R. X Y min min  X Y max max  = R. X Y max max  vi R = cos( ) sin( ) sin( ) cos( ) α α α α−  α x O y Hình 3.3 Ch
ng III. Xén hình 37 3.3. XÉN ON THNG VÀO HÌNH TRÒN Gi s ta có ng tròn tâm O(xc,yc) bán kính R và on th ng cn xén là AB vi A(x1,y1), B(x2,y2) (Hình 3.4). * Thut toán: • Tính d(O,AB) • Xét các trng hp: i/ Nu d > R thì ClipD(F) = ∅ ii/ Nu d = R thì ClipD(F) = A0 vi A0 là chân ng vuông góc h t O xung AB. iii/ Nu d < R thì xét các trng hp sau: ♦ (OA < R) AND (OB < R) thì ClipD(F) = AB ♦ Nu m
t im nm trong và im kia nm ngoài hình tròn, ch%ng hn OAR thì ClipD(F) = AI vi I là giao im duy nht gia AB và ng tròn. ♦ (OA > R) AND (OB > R) thì ClipD(F) = IJ vi I, J là hai giao im ca AB vi ng tròn. Sau ây là phng pháp tìm giao im gia on th ng và ng tròn:  Phng trình ng tròn: (x - xc)2 + (y - yc)2 = R2 (1)  Phng trình on AB:      ≤≤ −+= −+= 10 ).12(1 ).12(1 λ λ λ yyyy xxxx (2)  Thay (2) vào (1) ta suy ra: λ = b bcaa −±− 2 Trong ó: a = ∆x.(x1 - xc) + ∆y.(y1 - yc) b = (∆x)2 + (∆y)2 c = (x1 - xc) 2 + (y1 - yc)2 - R2 A B Hình 3.4 Ch
ng III. Xén hình 38 ∆x = x2 - x1 ∆y = y2 - y1  D!a vào iu ki n 0 ≤ λ ≤ 1  chn giao im. 3.4. XÉN 
NG TRÒN VÀO HÌNH CH NH T CÓ CÁC CNH SONG SONG VI TRC TA  Lúc này: D = {(x,y)| xMin ≤ x ≤ xMax ; yMin ≤ y ≤ yMax } F = { (x,y)| (x - xC) 2 + (y - yC) 2 = R2} *Trc ht, ta kim tra các trng hp  c bi t sau: i/ Nu xMin ≤ xC -R; xC +R ≤ xMax; yMin ≤ yC -R; yC +R ≤ yMax; thì ClipD(F) = F (Hình 3.5) ii/ Nu xC +R < xMin ho c xC -R > xMax ho c yC +R < yMin ho c yC - R > yMax thì ClipD(F) = ∅ (Hình 3.6) *Xét trng hp còn li: Tìm các giao im ca F và D. Sp xp các giao im ó theo chiu ngc kim &ng h&. • Các cung tròn c to bi 2 giao im liên tip s hoàn toàn nm trong D ho c hoàn toàn nm bên ngoài D. • " xác nh các cung này nm trong hay ngoài D, ta ch' cn ly trung im M ca cung ó. Nu M ∈ D thì cung ó nm trong D, ngc li thì nó nm ngoài D. Hình 3.5 Hình 3.6 Ch
ng III. Xén hình 39 3.5. XÉN A GIÁC VÀO HÌNH CH NH T Hình 3.7. Xén a giác vào hình ch nh t Thut toán SutherLand - Hodgman i/ Nu tt c các 'nh ca a giác u nm trong hình ch nht thì hình cn xén chính là a giác và bài toán coi nh ã c gii quyt. Hình 3.8. Các tr
ng hp cn xét ii/ Trng hp ngc li: - Xut phát t m
t 'nh nm ngoài hình ch nht, ta chy theo dc biên ca a giác. Vi mi cnh ca a giác, ta có các trng hp sau:
Nu c hai 'nh u nm ngoài hình ch nht thì: Nu Ma(Ai) and Ma(Ai+1) ≠ 0000 thì không lu 'nh Ngc li thì lu hai giao im.
Ai ngoài, Ai+1 trong: lu giao im P và Ai+1.
C hai 'nh u nm trong hình ch nht: lu Ai và Ai+1.
Ai trong, Ai+1 ngoài: lu Ai và giao im P. Ai Ai + Ai + Ai Ai Ai + Ai + Ai Ai Ai + Ch
ng III. Xén hình 40 - Sau khi duy t qua tt c các cnh ca a giác thì ta có c m
t dãy các 'nh mi phát sinh: B1, B2, ..., Bn Nu trong dãy các 'nh mi này có hai 'nh liên tip không nm trên cùng m
t cnh ca hình ch nht , gi s hai 'nh ó là Bi và Bi+1 thì ta i dc các cnh ca hình ch nht t Bi n Bi+1  tìm tt c các 'nh ca hình ch nht nm trong a giác r&i b sung chúng vào gia Bi và Bj. Tp 'nh mi tìm c chính là a giác xén c. - Nu tp 'nh mi này là rng: Nu có m
t 'nh ca hình ch nht nm trong a giác thì hình xén c chính là toàn b
hình ch nht. Ngc li, hình xén c là rng. BÀI T P 1. Vit hàm MA(P:ToaDo):Byte;  ánh mã cho im P. 2. Cài  t thut toán xén m
t on th ng vào m
t hình ch nht theo các thut toán: Liang-Barsky, Cohen-Sutherland, chia nh phân. 3. Cài  t thut toán xén m
t on th ng vào m
t hình tròn. 4.Cài  t thut toán xén m
t a giác vào m
t vùng hình ch nht.