Giáo trình Đồ họa máy tính I (Phần 2) - Phạm Tiến Sơn
. .
Chuong 3
. .
´
˙’
Giao cua c´ac d¯ˆoi tuong
.
.
`
˙’
3.1 Mo d¯ˆau
.
. .
`
`
˙’
Mˆot trong nhu˜ng b`ai to´an quan trong cua d¯ˆo hoa m´ay t´ınh l`a x´ac d¯inh d¯uoc phˆan giao
.
.
.
.
.
.
. .
˙’
´
˙’
˙’
˙’
˙’
. .
(c`on goi l`a cˇat x´en) c´ac nguyˆen so: giao d¯iˆem cua hai d¯oan thˇang, giao cua d¯u`ong thˇang
.
.
.
. .
.
`
´
`
´
˙’
v´oi d¯u`ong tr`on hay d¯a d¯a gi´ac lˆoi... Vˆan d¯ˆe o d¯aˆy l`a x´ac d¯inh c´ac d¯oˆi tuong c´o giao nhau
.
.
´
˙’
khˆong? Nˆeu c´o th`ı t`ım giao cua chu´ng.
.
. .
.
. .
˙’
`
`
´
Nhu d¯˜a d¯ˆe cˆap trong Chuong 1, c´ac thuaˆt to´an cˆan thuc hiˆen nhanh nhˆat c´o thˆe d¯uoc
.
.
.
.
.
. .
.
.
˙’
˙’
´
´
˙’
. .
˙’
d¯ˆe cung cˆap ngu`oi su dung cˆap nhˆat nhanh c´ac kˆet qua thay d¯oˆi trong u´ng dung. Chu´ng
.
.
.
.
. .
˙’
´
˙’
˙’
ta s˜e ´ap dung c´ac phuong ph´ap giai t´ıch d¯ˆe giai quyˆet c´ac b`ai to´an trong chuong n`ay.
.
˙’
˙’
3.2 Giao cua hai d¯oan thˇang
.
-
˙’
`
˙’
Mˆot b`ai to´an thˆong dung trong d¯oˆ hoa m´ay t´ınh l`a x´ac d¯inh giao cua hai d¯oan thˇang. Dˆay
.
.
.
.
.
.
˙’
l`a mˆot phˆan quyˆet d¯inh cua nhu˜ng thuˆat to´an t`ım giao (chˇang han, giao hai d¯a gi´ac) v`a
`
´
˙’
.
.
.
.
˙’
xuˆat hiˆen trong nhiˆeu tiˆen tr`ınh kh´ac. Phˆan n`ay ´ap dung viˆec tham sˆo ho´a cua d¯oan thˇang
´
`
´
`
´
˙’
.
.
.
.
˙’
´
˙’
d¯ˆe giai quyˆet b`ai to´an sau
B`ai to´an
˙’
X´ac d¯inh giao d¯iˆem cua chu´ng nˆeu c´o.
˙’
˙’
´
˙’
Trong mˇat phˇang cho hai d¯oan thˇang
v`a
.
.
.
83
. .
.
.
˙’
H`ınh 3.1: C´ac tru`ong hop v´oi hai d¯oan thˇang.
.
.
3.2.1 Phˆan t´ıch
. .
.
.
.
˙’
˙’
`
˙’
C´o nhiˆeu tru`ong hop xay ra v´oi hai d¯oan thˇang nhu trong H`ınh 3.1: Chu´ng c´o thˆe khˆong
.
.
˙’
˙’
´
´
`
˙’
giao nhau, c´o thˆe cˇat nhau tai mˆot d¯iˆem hoˇac phu lˆap mˆot phˆan lˆen nhau.
.
.
.
.
. .
. .
.
˙’
´
X´et c´ac phuong tr`ınh tham sˆo tuong u´ng hai d¯oan thˇang
v`a
l`a
.
( ) := + ( − )
∈ [0 1]
v`a
( ) := + ( − )
∈ [0 1]
.
.
˙’ ˙’
˙’
˙’
˜
´
˙’
Viˆec su dung c´ac tham sˆo kh´ac nhau v´oi hai d¯oan thˇang d¯ˆe biˆeu diˆen c´ac d¯iˆem kh´ac nhau
.
.
.
trˆen hai d¯oan mˆot c´ach d¯oˆc lˆap.
.
.
.
.
. .
Ky´ hiˆeu v`a l`a c´ac d¯u`ong thˇang d¯i qua
. .
.
. .
.
˙’
˙’
v`a
tuong u´ng. Phuong ph´ap o
´
1
2
.
. .
. .
˙’
˙’
´
˙’
d¯ˆay tru´oc hˆet l`a t`ım giao d¯iˆem cua hai d¯u`ong thˇang v`a (nˆeu c´o) v`a sau d¯o´ x´ac d¯inh
1
2
.
. .
.
. .
˙’
`
˙’
˙’
giao d¯iˆem c´o nˇam trˆen hai d¯oan thˇang hay khˆong. Trong tru`ong hop hai d¯u`ong thˇang giao
.
.
-
`
`
´
˙’
nhau, ta cˆan x´ac d¯inh c´ac tham sˆo v`a
sao cho ( ) = ( ) Diˆeu kiˆen n`ay chı ra
0
0
0
0
0
.
.
+ (
+ (
−
−
)
)
=
=
+ (
+ (
−
−
)
(3.1)
(3.2)
0
0
)
0
Suy ra
0
×
=
0
84
trong d¯´o
v`a
−
−
−
−
:=
:=
−
−
−
−
0
. .
.
`
˙’
C´o hai tru`ong hop ch´ınh xay ra tuy` theo bˇang khˆong hay khˆong.
.
kh´ac khˆong
0
. .
.
`
´
´
´
Nˆeu khˆong thuoˆc d¯oan [0 1] th`ı
0
. .
Trong tru`ong hop n`ay, tˆon tai duy nhˆat tham sˆo
=
0
.
.
. .
.
˙’
kˆet luˆan hai d¯oan thˇang
´
´
v`a
khˆong giao nhau; nguoc lai x´ac d¯inh tham sˆo
tu`
0
.
.
.
.
.
. .
˙’
thuoˆc d¯oan [0 1] th`ı hai d¯oan thˇang giao nhau v`a
´
Phuong tr`ınh (3.1) hoˇac (3.2). Nˆeu
0
.
.
.
.
.
˙’
˙’
˙’
toa d¯oˆ d¯iˆem giao c´o thˆe x´ac d¯inh boi ( ) = ( )
0
0
.
.
.
`
bˇang khˆong
. .
Nˆeu = 0 th`ı hai d¯u`ong thˇang v`a song song hoˇac tru`ng nhau. C´ac d¯oan thˇang c´o thˆe
˙’
˙’
˙’
phu lˆap lˆen nhau nhung d¯iˆeu n`ay chı c´o thˆe xay ra khi hai d¯u`ong thˇang tru`ng nhau. Dˆe
. .
´
1
2
.
.
.
. .
-
˙’
˙’
˙’
˙’
´
`
˙’
˙’
˙’
˙’
˙’
`
˙’
`
`
˙’
kiˆem tra d¯iˆeu d¯´o, ta chı cˆan x´ac d¯inh d¯iˆem c´o nˇam trˆen d¯u`ong thˇang d¯i qua hai d¯iˆem
1
.
00
´
˙’
˙’
v`a khˆong. Ta c´o thuoˆc nˆeu toa d¯oˆ cua n´o thoa m˜an
(
) = 0 trong d¯o´
1
.
.
) :=
. .
.
−
−
−
00
(
−
. .
.
. .
˙’
Trong tru`ong hop nguoc lai, hai d¯u`ong thˇang v`a song song v`a khˆong tru`ng nhau; suy
1
2
.
.
.
˙’
˙’
˙’
´
´
ra hai d¯oan thˇang khˆong giao nhau. Do d¯´o tiˆen tr`ınh cuˆoi cu`ng l`a kiˆem tra hai d¯oan thˇang
.
.
´
˙’
c´o phu lˆap lˆen nhau khˆong.
.
.
-
˙’
`
`
´
Dˆe thuc hiˆen d¯iˆeu n`ay, ta cˆan x´ac d¯inh hai tham sˆo thuc
v`a
. .
sao cho = ( )
´
.
.
.
.
. .
˙’
`
˙’
v`a = ( ) V`ı hai d¯u`ong thˇang tru`ng nhau nˆen chı cˆan x´et phuong tr`ınh theo (nˆeu
1
.
. .
.
. .
˙’
˜
˙’
khˆong song song v´oi truc tung; nguoc lai su dung phuong tr`ınh theo ) Dˆe d`ang kiˆem tra
.
.
.
.
`
rˇang
−
=
=
−
v`a
−
−
85
. .
.
-
˙’
˙’
´
`
`
´
Doan thˇang
bˇat d¯aˆu v`a kˆet thu´c tuong u´ng tai = 0 v`a = 1 v`a bˇang c´ach kiˆem
.
.
.
.
. .
. .
˙’
´
´
´
˙’
tra thu´ tu cua bˆon tham sˆo 0 1
v`a
chu´ng ta c´o thˆe x´ac d¯inh d¯uoc vi tr´ı tuong d¯oˆi
.
.
.
.
.
.
˙’
`
.
`
´
˙’
˙’
cua hai d¯oan thˇang. Tˆon tai phˆan chung giu˜a hai d¯oan tru` khi ca hai tham sˆo
v`a
cu`ng
˙’
.
.
.
.
.
. .
.
˙’
˜
`
´
˙’
nho hon 0 hoˇac l´on hon 1. Trong tru`ong hop c´o d¯oan chung, c´ac d¯iˆem d¯ˆau cuˆoi c´o thˆe dˆe
.
.
.
.
d`ang x´ac d¯inh tu` c´ac gi´a tri
v`a
.
.
˙’
3.2.2 Thuˆat to´an x´ac d¯inh giao hai d¯oan thˇang
.
.
.
.
.
.
.
-
`
˙’
´
´
˙’ ˙’
˙’
Trˆen co so cua nhu˜ng thao luˆan trˆen ta c´o thˆe viˆet lai thuˆat to´an chi tiˆet nhu sau. Dˆau
.
.
.
˙’
v`ao gˆom bˆon d¯iˆem
˙’
v`a ; d¯aˆu ra gˆom giao d¯iˆem (nˆeu c´o) v`a biˆen
`
´
`
`
´
´
nhˆan mˆot
.
.
˙’
˙’
`
`
trong ba gi´a tri 0 1 hoˇac 2 tuy` theo khˆong tˆon tai d¯iˆem giao, tˆon tai mˆot d¯iˆem giao hoˇac
.
.
.
.
.
.
´
`
˙’
hai d¯oan phu lˆap lˆen nhau mˆot phˆan.
.
.
.
˙’
1. Khoi tao
= 0 T´ınh
.
.
.
˙’
2. Nˆeu = 0 (tu´c l`a c´ac d¯oan thˇang khˆong song song) thuc hiˆen
´
.
.
.
.
˙’
Nˆeu ∈ [0 1] th`ı du`ng, hai d¯oan thˇang khˆong giao nhau.
´
• T´ınh
• T´ınh
0
0
.
.
˙’
´
Nˆeu
∈ [0 1] th`ı du`ng, hai d¯oan thˇang khˆong giao nhau.
0
0
.
. .
˙’
´
• Nguoc lai, kˆet luˆan
= 1 v`a hai d¯oan thˇang giao nhau tai
.
.
.
.
.
=
+ ( − ) =
+
(
0
− )
0
. .
. .
˙’
˙’
`
˙’
´
3. Nguoc lai (c´ac d¯oan thˇang song song) v`a nˆeu d¯iˆem nˇam trˆen d¯u`ong thˇang
.
.
.
• X´ac d¯inh
v`a
.
.
.
.
˙’
cu`ng nho hon 0 hoˇac cu`ng l´on hon 1 th`ı hai d¯oan thˇang
´
˙’
˙’
• Nˆeu ca hai
v`a
.
.
. .
˙’
= 2; giao hai d¯oan thˇang l`a mˆot d¯oan
khˆong giao nhau. Nguoc lai, d¯ˇat
.
.
.
.
.
.
˙’
`
thˇang (t`ım hai d¯aˆu mu´t?).
.
˙’ ˙’
V´ı du 3.2.1 (a) Gia su (1 4) (7 6) (4 8) v`a (7 9) Ta c´o
.
−
−
−
−
6 2
3 1
=
=
= 0
. .
Suy ra hai d¯u`ong thˇang
-
˙’
´
song song hoˇac tru`ng nhau. Dˆe kˆet luˆan, thay toa d¯oˆ
. . . .
˙’
v`a
. .
00
. .
˙’
d¯iˆem v`ao phuong tr`ınh
(
) ta d¯uoc
.
−
−
−
−
3 4
6 2
00
(
) =
=
= −18 = 0
86
Vˆay
∩
= ∅
.
.
˙’ ˙’
(b) Gia su (1 3) (10 6) (4 7) v`a (13 1) Ta c´o
−
−
−
−
9
3
=
=
= −81 = 0
9 −6
. .
.
˙’
´
Suy ra hai d¯u`ong thˇang
v`a
cˇat nhau tai Tu`
.
−
−
−
−
3
4
0
=
˙’
=
= −54
9 −6
0
2
3
. .
. .
c´o
=
=
∈ [0 1] Giai
theo Phuong tr`ınh (3.1) ta d¯uoc
0
0
.
−3 + 923
(
−
) + (
−
)
1
3
0
=
=
=
∈ [0 1]
0
−
9
˙’
Vˆay hai d¯oan thˇang
v`a
=
giao nhau tai
.
.
.
2
+ ( − ) = (1 3) + (9 3) = (7 5)
0
3
.
-
˙’
3.3 Doan thˇang v`a h`ınh chu˜ nhˆat
.
.
˙’
Trong phˆan n`ay chu´ng ta t`ım hiˆeu mˆot sˆo thuˆat to´an x´ac d¯inh giao cua d¯oan thˇang v`a h`ınh
˙’
`
´
˙’
.
.
.
.
.
.
. .
.
´
˙’
chu˜ nhˆat ( ) (c´o c´ac canh song song v´oi c´ac truc toa d¯ˆo). H`ınh 3.2 chı ra bˆon tru`ong hop
.
.
.
.
.
.
˙’
c´o thˆe:
.
˙’
• Ca hai d¯iˆem d¯aˆu cuˆoi cua d¯oan thˇang, chaˇng han
˙’
˙’
`
`
´
˙’
˙’
nˇam ho`an to`an trong h`ınh chu˜
.
.
˙’
˙’
`
nhˆat. Hiˆen nhiˆen khi d¯o´ phˆan giao ch´ınh l`a d¯oan thˇang n`ay.
.
.
.
˙’
˙’
`
`
˙’
• Mˆot trong hai d¯ˆau mu´t cua d¯oan thˇang, chaˇng han
nˇam trong h`ınh chu˜ nhˆat.
.
.
.
.
.
.
˙’
• Ca hai d¯iˆem d¯aˆu cuˆoi cua d¯oan thˇang, chaˇng han
˙’
˙’
`
`
´
˙’
˙’
nˇam ngo`ai h`ınh chu˜ nhˆat nhung
.
.
.
.
.
´
c´o giao kh´ac trˆong v´oi h`ınh chu˜ nhˆat.
.
.
˙’
• Ca hai d¯iˆem d¯ˆau cuˆoi cua d¯oan thˇang (chˇang han
˙’
˙’
`
`
´
`
˙’
˙’
˙’
) nˇam ho`an to`an vˆe “nua mˇat
.
.
.
.
.
˙’
`
˙’
˙’
phˇang ngo`ai” x´ac d¯inh boi mˆot canh (bˆen tr´ai) cua h`ınh chu˜ nhˆat. Ta c´o phˆan giao
.
.
.
.
. .
.
`
´
´
˙’
˙’
˙’
bˇang trˆong. T`ınh huoˆng n`ay thu`ong xay ra khi h`ınh chu˜ nhˆat d¯u nho v`a do d¯´o c´o
.
.
`
`
nhiˆeu d¯oan nˇam ngo`ai h`ınh chu˜ nhˆat.
.
.
87
.
H`ınh chu˜ nhˆat ( )
.
.
˙’
H`ınh 3.2: C´ac d¯oan thˇang v`a h`ınh chu˜ nhˆat ( )
.
.
•
—
—
max
•
•
•
min
|
min
max
. .
.
˙’
´
˙’ ˙’
H`ınh 3.3: C´ac tru`ong hop chaˆp nhˆan hoˇac loai bo cua mˆot d¯oan thˇang.
.
.
.
.
.
.
. .
.
˙’
´
´
˙’
H˜ay quan s´at vi tr´ı tuong d¯oˆi cua d¯oan thˇang v`a h`ınh chu˜ nhˆat ( ) chu´ng ta s˜e thˆay
.
.
.
.
-
˙’
˙’
`
˙’
`
´
˙’
˙’ ˙’
c´o nhiˆeu t`ınh huoˆng c´o thˆe xay ra m`a thuaˆt to´an phai xu ly´. Doan thˇang c´o thˆe nˇam bˆen
.
.
. .
.
˙’
´
´
˙’
˙’
tr´ai, bˆen phai, ph´ıa du´oi hay ph´ıa trˆen cua h`ınh chu˜ nhˆat. Hoˇac n´o c´o thˆe cˇat bˆat ky` mˆot
.
.
.
.
˙’
´
´
`
´
`
˙’
(hay hai) canh h`ınh chu˜ nhˆat, v`a vˆan vˆan. T´om lai vˆan d¯ˆe c´o ve rˇac rˆoi v`ı c´o thˆe c´o nhiˆeu
.
.
.
.
˙’
˙’
`
´
˙’
˙’ ˙’
˙’
kha nˇang kh´ac nhau c´o thˆe xay ra. Do d¯o´ chu´ng ta cˆan mˆot c´ach tˆo chu´c v`a tiˆep cˆan hiˆeu
.
.
.
. .
.
.
˙’
˙’
´
`
´
qua giai quyˆet b`ai to´an trong tru`ong hop tˆong qu´at v`a t´ınh to´an c´ac d¯iˆem d¯ˆau cuˆoi m´oi
.
˙’
`
˙’
˙’
cua phˆan giao. T´ınh hiˆeu qua d¯ˇac biˆet quan trong do c´o thˆe c´o h`ang trˇam, thˆam ch´ı h`ang
.
.
.
.
.
.
˙’
˜
`
`
`
˙’
ng`an, d¯oan thˇang trong mˆot h`ınh v`a mˆoi d¯oan cˆan loai bo phˆan nˇam ngo`ai h`ınh chu˜ nhˆat.
.
.
.
.
.
.
˙’
`
´
˙’
Phˆan n`ay tr`ınh b`ay mˆot sˆo thuaˆt to´an t`ım giao cua d¯oan thˇang v`a h`ınh chu˜ nhˆat.
.
.
.
.
. .
. .
.
. .
˙’
`
´
`
˙’
Tru´oc hˆet nhˆan x´et rˇang c´o hai tru`ong hop tˆam thu`ong (xem H`ınh 3.3) c´o thˆe xay ra:
.
.
. .
.
. .
˙’
˙’
`
`
´
`
´
1. Tru`ong hop tˆam thu`ong d¯ˆau tiˆen, goi l`a chaˆp nhˆan, l`a hai d¯iˆem d¯aˆu cuˆoi d¯oan thˇang
.
.
.
.
88
.
.
chu´a trong h`ınh chu˜ nhˆat.
.
. .
.
. .
.
˙’
˙’
`
`
´
˙’ ˙’
˙’
2. Tru`ong hop tˆam thu`ong thu´ hai, goi l`a loai bo, ca hai d¯iˆem d¯aˆu cuˆoi cua d¯oan thˇang
.
.
.
.
.
.
.
`
˙’
`
˙’
˙’
˙’
nˇam ho`an to`an vˆe nua mˇat phˇang ngo`ai x´ac d¯inh boi mˆot canh cua h`ınh chu˜ nhˆat.
.
.
.
.
.
. .
3.3.1 T`ım giao bˇang c´ach giai hˆe c´ac phuong tr`ınh
`
˙’
.
. .
.
.
˙’
`
´
`
C´ach tiˆep cˆan ch´ınh trong tru`ong hop v`a khˆong d¯oˆng th`oi nˇam trong ( ) l`a kiˆem tra
.
.
.
.
˙’
´
˙’
d¯oan thˇang
.
c´o giao v´oi c´ac canh cua h`ınh chu˜ nhˆat khˆong; nˆeu c´o, x´ac d¯inh c´ac giao
.
.
.
.
˙’
˙’
`
`
˙’
d¯iˆem v`a suy ra phˆan giao. Do d¯´o d¯ua vˆe b`ai to´an x´ac d¯inh giao cua hai d¯oan thˇang v`a c´o
.
.
.
. .
˙’
´
`
`
˙’
thˆe ´ap dung nhu˜ng kˆet qua trong Phˆan 3.2. Theo phuong ph´ap n`ay, chu´ng ta cˆan t´ınh to´an
.
˙’
`
˙’
˙’
v`a kiˆem tra nhiˆeu kha nˇang; do d¯o´ khˆong hiˆeu qua.
.
3.3.2 Thuˆat to´an chia nhi phˆan
.
.
. .
.
. .
´
˙’
˙’
Y ch´ınh cua thuˆat to´an n`ay tuong tu thuˆat to´an t`ım nghiˆem cua phuong tr`ınh ( ) = 0
.
.
.
.
.
. .
`
trˆen d¯oan [ ] v´oi liˆen tuc v`a ( ) ( ) 0 bˇang phuong ph´ap chia nhi phˆan (bisection):
.
.
.
.
. .
˙’
˙’
`
´
˙’
X´ac d¯inh c´ac giao d¯iˆem (nˆeu c´o) cua d¯oan thˇang
v`a h`ınh chu˜ nhˆat bˇang phuong ph´ap
.
.
.
chia nhi phˆan.
.
. .
. .
.
˙’
´
´
´
˙’
˙’
Thuˆat to´an tru´oc hˆet kiˆem tra hai tru`ong hop chaˆp nhˆan v`a loai bo. Nˆeu khˆong xay
.
.
.
.
.
˙’
`
`
`
`
˙’
ra, n´o chia d¯oan thˇang th`anh hai phˆan bˇang nhau v`a loai bo nhu˜ng phˆan nˇam ngo`ai h`ınh
.
.
.
. .
.
. .
.
˙’
`
`
˙’
chu˜ nhˆat. Sau d¯o´ phˆan c`on lai d¯uoc xu ly´ lˇap lai bˇang c´ach kiˆem tra c´ac Tru`ong hop 1 v`a
.
.
.
.
.
.
.
`
´
´
`
´
`
2 v`a tiˆep tuc phˆan chia (nˆeu cˆan) cho d¯ˆen khi phˆan c`on lai ho`an to`an nˇam trong h`ınh chu˜
.
.
.
.
. .
`
˙’
˙’
˙’
˙’
nhˆat hoˇac nˇam trong nua mˇat phˇang ngo`ai x´ac d¯inh boi mˆot d¯u`ong thˇang bˆen tr´ai, bˆen
.
.
.
.
.
. .
˙’
phai, bˆen du´oi hoˇac bˆen trˆen n`ao d¯o´.
.
.
-
˙’
˙’
`
`
´
Dˆe x´ac d¯inh c´ac d¯iˆem d¯ˆau cuˆoi khi n`ao nˇam ngo`ai hay trong mˆot h`ınh chu˜ nhˆat, chu´ng
.
.
.
.
.
˙’
˙’
. .
˜
˜
˙’
˙’
ta d¯ˇat mˆot m˜a “nua mˇat phˇang” cho mˆoi d¯iˆem. Mˆoi canh cua h`ınh chu˜ nhˆat x´ac d¯inh mˆot
.
.
.
.
.
.
.
. .
.
˙’
˙’
˙’
˙’
˙’
d¯u`ong thˇang d¯i qua n´o; d¯u`ong thˇang n`ay chia mˇat phˇang th`anh nua mˇat phˇang trong v`a
.
.
.
.
.
. .
.
˙’
˙’
´
˙’
˙’
˙’
nua mˇat phˇang ngo`ai nhu trong H`ınh 3.4 d¯oˆi v´oi canh bˆen phai: Ta quy u´oc nua mˇat phˇang
.
.
.
. .
.
.
.
. .
.
˙’
˙’
trong tuong u´ng chu´a h`ınh chu˜ nhˆat; nguoc lai l`a nua mˇat phˇang ngo`ai.
.
.
.
.
.
˙’
˙’
˜
˙’
´
´
˙’
˙’
Do c´o bˆon canh, ta s˜e su dung chuoˆi bˆon bit d¯ˆe m˜a ho´a mˆot d¯iˆem trong mˇat phˇang.
.
.
.
.
.
. .
˜
`
˙’
Ky´ hiˆeu ( ) l`a m˜a cua d¯iˆem
Mˆoi bit trong tu` m˜a d¯uoc d¯aˇt bˇang 1 (TRUE) hoˇac 0
.
.
.
.
.
. .
.
´
`
(FALSE); bˆon bit trong tu` m˜a ( ) tuong u´ng c´ac d¯iˆeu kiˆen sau:
.
89
( )
.
˙’
Nua
˙’
mˇat phˇang
.
ngo`ai
.
˙’
Nua mˇat phˇang trong
˙’
.
max
.
. .
.
˙’
˙’
˙’
˙’
H`ınh 3.4: C´ac nua mˇat phˇang d¯uoc x´ac d¯inh boi canh bˆen phai.
.
.
.
.
.
.
.
˙’
`
˙’
´
´
˙’
˙’
• Bit thu´ nhˆat d¯ˇat bˇang 1 nˆeu d¯iˆem thuoˆc nua mˇat phˇang ngo`ai x´ac d¯inh boi canh
.
.
.
.
.
bˆen tr´ai;
.
.
.
˙’
`
˙’
thuˆoc nua mˇat phˇang ngo`ai x´ac d¯inh boi canh
´
˙’
˙’
• Bit thu´ hai d¯aˇt bˇang 1 nˆeu d¯iˆem
.
.
.
.
.
˙’
bˆen phai;
.
.
.
˙’
`
˙’
´
˙’
˙’
• Bit thu´ ba d¯aˇt bˇang 1 nˆeu d¯iˆem thuˆoc nua mˇat phˇang ngo`ai x´ac d¯inh boi canh bˆen
.
.
.
.
.
trˆen;
. .
.
.
˙’
`
˙’
´
˙’
˙’
• Bit thu´ tu d¯aˇt bˇang 1 nˆeu d¯iˆem thuoˆc nua mˇat phˇang ngo`ai x´ac d¯inh boi canh bˆen
.
.
.
.
.
. .
du´oi.
.
˙’
˙’
`
`
Do d¯´o c´ac d¯iˆem nˇam trong h`ınh chu˜ nhˆat c´o m˜a 0000; c´ac d¯iˆem thuoˆc vu`ng nˇam ph´ıa
.
.
.
. .
.
.
˙’
˙’
trˆen v`a bˆen tr´ai h`ınh chu˜ nhˆat d¯uoc g´an tu` m˜a l`a 1001. Viˆec xˆay dung m˜a cua mˆot d¯iˆem
.
.
.
.
.
.
. .
.
˙’
`
´
˙’
d¯on thuaˆn l`a bˆon ph´ep so s´anh: Ho`anh d¯ˆo cua d¯iˆem d¯uoc so s´anh v´oi canh bˆen tr´ai
;
min
.
.
.
. .
.
. .
. .
˙’
˙’
tung d¯oˆ d¯uoc so s´anh v´oi canh bˆen du´oi min; v.v. C´ac d¯u`ong thˇang d¯i qua c´ac canh cua
.
.
.
.
.
˙’
˙’
h`ınh chu˜ nhˆat chia mˇat phˇang th`anh ch´ın vu`ng. C´ac d¯iˆem trong mˆot vu`ng c´o cu`ng mˆot m˜a
.
.
.
.
.
.
˙’
´
˙’
˙’
nhu chı ra trong H`ınh 3.5. V`ı d¯on vi nho nhˆat c´o thˆe d¯oc, ghi trˆen m´ay t´ınh l`a byte, nˆen
.
.
.
. .
.
.
˙’
˙’
˙’
´
´
˙’
chu´ng ta su dung kiˆeu byte d¯ˆe m˜a ho´a mˆot d¯iˆem trong d¯´o bˆon bit thˆap tuong u´ng tu` m˜a
.
.
. .
.
`
´
´
˙’
˙’
cua n´o v`a bˆon bit cao d¯uoc d¯aˇt bˇang khˆong. Thu tuc Encode() thuc hiˆen tiˆen tr`ınh n`ay:
.
.
.
.
.
void Encode(Point2D P, float Left, float Right, float Bottom, float Top,
char *Code)
{
90
1001
1000
0001
0000
0101
0100
max
min
1010
0010
. .
0110
min
max
.
.
.
H`ınh 3.5: C´ac tu` m˜a tuong u´ng h`ınh chu˜ nhˆat ( )
.
*Code = 0;
if (P.x < Left) *Code |= 8;
if (P.x > Right) *Code |= 4;
if (P.y < Bottom) *Code |= 2;
if (P.y > Top) *Code |= 1;
}
. .
.
. .
˙’
˙’
C´ac d¯iˆem
d¯uoc m˜a ho´a th`anh c´ac tu` m˜a ( ) v`a ( ) Trˆen co so d¯´o chu´ng ta
.
.
.
˙’
˙’
`
˙’
nˇam ho`an to`an bˆen trong h`ınh chu˜ nhˆat hoˇac thuoˆc nua
c´o thˆe x´ac d¯inh d¯oan thˇang
.
.
.
.
.
˙’
mˇat phˇang ngo`ai n`ao d¯´o. Ta c´o
.
´
´
´
˙’
1. Chˆap nhˆan nˆeu v`a chı nˆeu ( ) = ( ) = 0
.
´
´
˙’
˙’
2. Loai bo nˆeu v`a chı nˆeu [ ( ) AND ( )] != 0.
.
. .
˙’ ˙’
.
.
˙’
Trˆen co so cua nhu˜ng phˆan t´ıch trˆen ta c´o thˆe viˆet lai thuˆat to´an chia nhi phˆan nhu
´
.
.
.
sau:
.
´
´
1. Nˆeu ( ) = 0 v`a ( ) = 0 kˆet luˆan
∩ ( ) =
; thuˆat to´an du`ng.
.
.
´
´
´
2. Nˆeu [ ( ) AND ( )] != 0 kˆet luˆan
∩ ( ) = ∅; kˆet thu´c thuaˆt to´an.
.
.
91
.
.
´
3. Nˆeu ( ) = 0 v`a ( ) = 0 (tu´c ∈ ( ) v`a ∈ ( )) thuc hiˆen
.
.
-
• Dˇat
=
=
.
.
.
. .
´
˙’
• Trong khi d¯ˆo d`ai k
k l´on hon (sˆo duong nho tu`y y´)
.
-
˙’
˙’
) = 0 th`ı cˆap nhˆat
Dˇat
l`a trung d¯iˆem cua d¯oan
.
.
. .
nguoc lai
´
Nˆeu
(
=
=
.
.
.
.
´
´
• Kˆet luˆan
∩ ( ) =
; kˆet thu´c thuˆat to´an.
.
.
.
˙’
´
˙’
4. Nˆeu ( ) = 0 v`a ( ) = 0 (tu´c ∈ ( ) v`a ∈ ( )) ho´an d¯oˆi vai tr`o cua v`a
;
. .
lˇap lai Bu´oc 3.
.
.
. .
.
5. Nguoc lai thuc hiˆen
.
.
.
.
-
• Dˇat
=
=
.
.
.
• Trong khi d¯ˆo d`ai k
k l´on hon
.
-
˙’
˙’
Dˇat
.
l`a trung d¯iˆem cua d¯oan
.
. .
´
Nˆeu
´
(
) = 0 ´ap dung Bu´oc 3 cho hai d¯oan
v`a
Kˆet luˆan
∩( ) =
.
.
.
´
; kˆet thu´c thuˆat to´an.
.
´
Nˆeu [ ( ) AND ( )] != 0 d¯aˇt
=
=
.
´
Nˆeu [ ( ) AND ( )] != 0 d¯ˇat
.
´
´
´
Nˆeu [ ( ) AND ( )] != 0 kˆet luˆan
∩ ( ) = ∅; kˆet thu´c thuˆat to´an.
.
.
—
•
max
1
3
•
2
•
•
•
—
min
|
|
min
max
˙’
H`ınh 3.6: Minh hoa cua thuaˆt to´an chia nhi phˆan.
.
.
.
.
˙’
V´ı du 3.3.1 X´et v´ı du t`ım giao cua h`ınh chu˜ nhˆat
.
.
.
2
:= {(
) ∈
| 3 ≤ ≤ 7 2 ≤ ≤ 5}
92
. .
v`a hai d¯iˆem (5 3) v`a (10 5) Ba bu´oc d¯ˆau tiˆen cua thuˆat to´an chia nhi phˆan cho trong
˙’
`
˙’
.
.
˙’
bang sau
( )
( ) E(M)
15
2
25
4
1
2
(5 3) (10 5)
15
(
(
4) 0000 0100 0100
7
(5 3)
(
4)
)
0000 0100 0000
0000 0100 0000
2
2
3 (245 27 ) (125 4) (585
)
15
4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. .
.
.
˙’
`
˙’
H`ınh 3.6 minh hoa ba bu´oc lˇap d¯ˆau tiˆen cua thuaˆt to´an chia nhi phˆan v´oi c´ac d¯iˆem giu˜a
.
.
.
.
. .
.
tuong u´ng l`a
v`a
1
2
3
. .
Nhˆan x´et rˇang phuong ph´ap chia nhi phˆan khˆong hiˆeu qua do t´ınh to´an nhiˆeu d¯ˆe x´ac
˙’
`
`
˙’
.
.
.
˙’
d¯inh c´ac giao d¯iˆem.
.
3.3.3 Thuˆat to´an Cohen-Sutherland
.
. .
. .
.
.
´
˙’
Thuˆat to´an Cohen-Sutherland thu`ong d¯uoc su dung trong c´ac u´ng dung cˇat x´en do t´ınh
.
.
.
.
˙’
˙’
´
´
´
´
˙’
˙’
hiˆeu qua v`a phˆo biˆen cua n´o. Thuˆat to´an cung cˆap mˆot c´ach tiˆep cˆan chia d¯ˆe tri rˆat hiˆeu
.
.
.
.
.
.
.
˙’
qua giai b`ai to´an x´ac d¯inh giao cua d¯oan thˇang v`a h`ınh chu˜ nhˆat.
˙’ ˙’
˙’
.
.
.
. .
.
. .
. .
˙’
´
Tuong tu phuong ph´ap chia nhi phˆan, thuaˆt to´an Cohen-Sutherland tru´oc hˆet kiˆem
.
.
.
. .
.
˙’
´
´
˙’
˙’
tra Tru`ong hop 1 (chaˆp nhˆan) v`a 2 (loai bo). Nˆeu khˆong xay ra, n´o chia d¯oan thˇang th`anh
.
.
.
.
.
. .
.
`
`
`
`
˙’
˙’
hai phˆan v`a loai bo phˆan nˇam ngo`ai h`ınh chu˜ nhˆat. Sau d¯o´ phˆan c`on lai d¯uoc xu ly´ lˇap
.
.
.
.
.
. .
.
˙’
`
´
´
`
´
lai bˇang c´ach kiˆem tra c´ac Tru`ong hop 1 v`a 2 v`a tiˆep tuc phˆan chia (nˆeu cˆan) cho d¯ˆen khi
.
.
.
.
.
`
`
˙’
`
˙’
phˆan c`on lai ho`an to`an nˇam trong h`ınh chu˜ nhˆat hoˇac nˇam trong nua mˇat phˇang ngo`ai x´ac
.
.
.
.
.
. .
. .
˙’
˙’
˙’
d¯inh boi mˆot d¯u`ong thˇang bˆen tr´ai, bˆen phai, bˆen du´oi hoˇac bˆen trˆen n`ao d¯´o.
.
.
.
. .
.
. .
.
˙’
Thuˆat to´an d¯ˇac biˆet hiˆeu qua trong hai tru`ong hop chung: Trong Tru`ong hop 1, h`ınh
.
.
.
.
.
.
.
.
.
.
˙’
´
`
´
`
´
˙’
chu˜ nhˆat chu´a tˆat ca hoˇac hˆau hˆet vu`ng hiˆen thi, v`a do d¯´o phˆan l´on c´ac nguyˆen so l`a chˆap
.
.
.
. .
.
. .
.
`
´
˙’
nhˆan. Tru`ong hop 2 nay sinh trong b`ai to´an chon c´ac d¯ˆoi tuong nˇam trong h`ınh chu˜ nhˆat
.
.
.
.
.
bao quanh con chay (xem [9]).
.
. .
.
˙’
´
`
˙’
Nˆeu khˆong xay ra hai Tru`ong hop 1 hoˇac 2 chu´ng ta cˆan phˆan chia d¯oan thˇang
.
.
.
. .
˙’
`
´
˙’
thˇang x´ac d¯inh boi canh cua h`ınh chu˜ nhˆat chia d¯oan thˇang
˙’
th`anh hai phˆan sao cho mˆot hoˇac ca hai d¯oan con c´o thˆe bi loai bo. Muˆon vˆay x´et d¯u`ong
.
.
.
.
.
.
.
.
˙’
˙’
`
`
˙’
˙’
˙’
th`anh hai phˆan: Phˆan
. .
˙’ ˙’
.
.
.
.
.
˙’
˙’
˙’
thuˆoc nua mˇat phˇang ngo`ai s˜e bi loai bo. C´o thˆe chon c´ac canh d¯ˆe kiˆem tra theo thu´ tu tuy`
.
.
.
.
.
.
.
.
.
.
.
.
`
´
˙’
˙’
y´, nhung cˆan nhˆat qu´an trong thuaˆt to´an. Chu´ng ta s˜e su dung thu´ tu tu` tr´ai sang phai
.
.
.
93
.
. .
.
.
. .
. .
.
`
`
v`a tu` du´oi lˆen trˆen trong tu` m˜a. Chu´ y´ rˇang, bit trong tu` m˜a d¯uoc d¯ˇat bˇang 1 tuong u´ng
.
.
.
˙’
˙’
`
´
˙’
˙’
canh cˆan x´et: Nˆeu, chˇang han, thuoˆc nua mˇat phˇang ngo`ai
v`a
khˆong thoa
min
.
.
.
.
. .
.
.
˙’
˙’
phai thuoˆc nua mˇat phˇang trong
˙’
˙’
˙’
Tru`ong hop 2 th`ı d¯iˆem
.
v`a d¯oan thˇang
min
.
.
.
. .
.
˙’
Do d¯o´ thuaˆt to´an luˆon luˆon chon mˆot d¯iˆem thuˆoc nua mˇat
´
˙’
˙’
˙’
phai cˇat d¯u`ong thˇang
.
=
min
.
.
.
.
.
.
. .
. .
. .
˙’
˙’
˙’
˙’
phˇang ngo`ai v`a su dung tu` m˜a cua n´o d¯ˆe x´ac d¯inh canh d¯uoc x´et; canh d¯uoc chon tuong
.
.
.
.
.
.
.
.
. .
. . .
.
. .
.
`
˙’
u´ng bit d¯uoc d¯ˇat bˇang 1 theo thu´ tu tu` tr´ai sang phai v`a tu` du´oi lˆen trˆen; tu´c l`a, n´o l`a bit
.
.
.
.
`
´
bˆen tr´ai nhˆat bˇang 1 trong tu` m˜a.
. .
.
`
Thuˆat to´an gˆom c´ac bu´oc nhu sau.
.
.
˙’
`
1. M˜a ho´a c´ac d¯iˆem
bˇang c´ac tu` m˜a ( ) v`a ( )
´
2. Nˆeu ( ) = ( ) = 0 th`ı
∩ ( ) =
´
3. Nˆeu [ ( ) AND ( )] != 0 th`ı
∩ ( ) = ∅
. .
.
.
˙’
˙’
`
˙’
4. Nguoc lai chon mˆot d¯iˆem nˇam ngo`ai v`a dua v`ao tu` m˜a cua n´o d¯ˆe x´ac d¯inh canh s˜e
.
.
.
.
.
.
.
˙’
˙’
´
`
`
˙’
cˇat. Sau d¯o´ x´ac d¯inh giao d¯iˆem, loai bo phˆan nˇam ngo`ai. Cˆap nhˆat d¯iˆem ngo`ai l`a giao
.
.
.
.
. .
d¯iˆem v`a m˜a ho´a n´o. Chuyˆen sang Bu´oc 2.
˙’
˙’
-
˙’
˙’
˙’
V´ı du 3.3.2 (a) Chˇang han, x´et d¯oan thˇang
trong H`ınh 3.7. Diˆem
. .
c´o m˜a 0000 v`a
.
.
.
.
-
˙’
d¯iˆem
˙’
˙’
c´o m˜a 0110. Doan thˇang
khˆong thoa m˜an c´ac Tru`ong hop 1 v`a 2. Do d¯´o
.
.
.
. .
˙’
chon d¯iˆem ngo`ai l`a
˙’
´
˙’
´
˙’
Tu` m˜a ( ) cho biˆet d¯oan thˇang
cˇat c´ac d¯u`ong thˇang bˆen phai
.
.
. .
.
.
.
˙’
˙’
˙’
˙’
=
v`a bˆen du´oi
=
Theo thu´ tu kiˆem tra, chu´ng ta su dung canh bˆen phai d¯ˆe
max
min
.
.
.
.
˙’
´
˙’
˙’
v`a cˆap nhˆat tu` m˜a cua
cˇat d¯oan thˇang
l`a
Thay d¯iˆem
l`a
l`a 0000. Trong
.
.
.
. .
. .
.
˙’
´ ´
´
´
˙’
bu´oc lˇap kˆe tiˆep, kiˆem tra ta thˆay
.
thoa m˜an Tru`ong hop 1, do d¯o´ kˆet thu´c thuaˆt to´an.
.
.
. .
.
-
˙’
M˜a cua c´ac d¯iˆem
˙’
˙’
(b) X´et d¯oan thˇang
v`a tuong u´ng l`a 1001 v`a 0010. Doan
.
.
. .
.
˙’
˙’
thˇang
˙’
˙’
. .
˙’
khˆong thoa m˜an c´ac Tru`ong hop 1 v`a 2. Chon d¯iˆem ngo`ai, chaˇng han
Do
.
.
.
.
.
. .
. .
`
´
˙’
bit kh´ac khˆong d¯aˆu tiˆen trong tu` m˜a cua
l`a bit thu´ nhˆat nˆen d¯u`ong thˇang d¯uoc chon
.
.
.
. .
.
.
˙’
˙’
l`a
=
Giao cua
v´oi d¯u`ong thˇang n`ay tai
Cˆap nhˆat
l`a tuong u´ng tu` m˜a
˙’
min
.
.
.
. .
. .
.
´ ´
˙’
0001. Bu´oc lˇap kˆe tiˆep,
khˆong thoa m˜an c´ac Tru`ong hop 1 v`a 2, nˆen chon d¯iˆem ngo`ai,
.
.
.
.
. .
˙’
chˇang han l`a
˙’
´
˙’
Chı c´o mˆot bit (thu´ ba) trong ( ) kh´ac khˆong, nˆen chon d¯u`ong thˇang cˇat
.
.
.
˙’
. .
l`a
=
Ta c´o
. .
=
∩
Do d¯o´ cˆap nhˆat l`a v`a cˆap nhˆat m˜a cua n´o l`a 0000.
max
max
.
.
.
.
.
. .
´
´
´
˙’
Lˇap lai mˆot bu´oc nu˜a, ta d¯uoc
.
˙’
ph´at tu` d¯iˆem
=
∩ ( ) Kˆet qua n`ay cu˜ng nhˆan d¯uoc nˆeu ta xuˆat
.
.
.
.
.
.
94
•
•
•
•
•
•
•
•
•
˙’
H`ınh 3.7: Minh hoa cua thuˆat to´an Cohen-Sutherland.
.
.
.
˙’
V´ı du 3.3.3 X´et v´ı du t`ım giao cua h`ınh chu˜ nhˆat
.
.
.
2
:= {(
) ∈
| 0 ≤ ≤ 8 0 ≤ ≤ 4}
. .
. .
˙’
˙’
v`a hai d¯iˆem (−1 −2) v`a (10 9) Phuong tr`ınh d¯u`ong thˇang
c´o dang
.
=
− 1;
. .
. .
hay tuong d¯uong
= + 1
. .
˙’ ˙’
´
˙’
˙’
C´ac bu´oc cua thuˆat to´an Cohen Sutherland c´o thˆe tˆong kˆet trong bang sau
.
. .
-
˙’
´
( )
( ) CodeOut Du`ong thˇang cˇat Toa d¯ˆo giao
.
.
1 (−1 −2) (10 9) 1010 0101
1010
0010
0101
0001
=
=
=
=
(0 −1)
(1 0)
(8 7)
(5 4)
min
min
max
max
2
3
4
5
(0 −1) (10 9) 0010 0101
(1 0)
(1 0)
(1 0)
(10 9) 0000 0101
(8 7) 0000 0001
(5 4) 0000 0000
.
˙’
˙’
˙’
´
˙’
Vˆay giao cua d¯oan thˇang
v`a h`ınh chu˜ nhˆat l`a d¯oan thˇang nˆoi hai d¯iˆem (1 0) v`a
.
.
.
.
(5 4)
.
. .
. .
.
. .
˙’
˙’
Nhu˜ng y´ tuong trˆen d¯uoc tˆap hop trong thu tuc Cohen Sutherland(). C´ac bu´oc lˇap
.
.
.
.
.
. .
.
˙’
. .
˙’
˜
´
`
`
´
˙’
kiˆem tra c´ac tru`ong hop chˆap nhˆan hay loai bo. Mˆoi lˆan trong v`ong lˇap hai d¯iˆem d¯ˆau cuˆoi
.
.
.
.
.
.
˙’
´
˙’
d¯uoc cˆap nhˆat cu`ng v´oi tu` m˜a cua chu´ng v`a sau d¯´o tiˆen h`anh kiˆem tra.
.
.
.
95
.
-
˙’
´
`
˙’
˙’
Dˆe thuˆat to´an hiˆeu qua hon, chu´ng ta nˆen t´ınh c´ac hˆe sˆo g´oc chı mˆot lˆan. Tuy nhiˆen,
.
.
.
.
.
. .
˙’
´
´
˙’
˙’
˙’
˙’
v´oi cai tiˆen n`ay, thuˆat to´an khˆong phai l`a hiˆeu qua nhˆat. Do viˆec kiˆem tra v`a loai bo d¯uoc
.
.
.
.
.
.
. .
.
´
´
˙’
thuc hiˆen theo mˆot thu´ tu nhˆat d¯inh, thuaˆt to´an d¯oˆi khi thuc hiˆen tiˆen tr`ınh loai bo khˆong
.
.
.
.
.
.
.
.
.
. .
.
.
˙’
˙’
˙’
`
´
˙’
˙’
cˆan thiˆet, chaˇng han trong tru`ong hop giao d¯iˆem cua d¯oan thˇang v´oi mˆot canh cua h`ınh
.
.
.
.
.
.
.
.
˙’
chu˜ nhˆat l`a “d¯iˆem giao ngo`ai”; tu´c l`a, khi n´o khˆong nˇam trˆen biˆen cua h`ınh chu˜ nhˆat (v´ı
`
˙’
trong H`ınh 3.7). Thuˆat to´an cua Nicholl v`a Lee tr´anh viˆec
.
.
˙’
du, d¯iˆem trˆen d¯oan thˇang
˙’
˙’
.
.
.
.
.
˙’
`
˙’
`
t´ınh to´an c´ac giao d¯iˆem ngo`ai bˇang c´ach phˆan chia mˇat phˇang th`anh nhiˆeu vu`ng hon (xem
.
[14]).
Boolean Cohen_Sutherland(Point2D *A, Point2D *B, float Left,
float Right, float Bottom, float Top)
{
char CodeA, CodeB, CodeOut;
float x, y;
Encode(*A, Left, Right, Bottom, Top, &CodeA);
Encode(*B, Left, Right, Bottom, Top, &CodeB);
while (1)
{
if ((CodeA == 0) && (CodeB == 0)) return True;
if ((CodeA & CodeB) != 0) return False;
if (CodeA != 0) CodeOut = CodeA;
else CodeOut = CodeB;
if ((CodeOut & 8) != 0) // Left
{
x = Left;
y = (*A).y + ((*B).y - (*A).y)*(x - (*A).x)/((*B).x - (*A).x);
}
else if ((CodeOut & 4) != 0) // Right
{
x = Right;
y = (*A).y + ((*B).y - (*A).y)*(x - (*A).x)/((*B).x - (*A).x);
}
else if ((CodeOut & 2) != 0) // Bottom
96
{
}
y = Bottom;
x = (*A).x + ((*B).x - (*A).x)*(y - (*A).y)/((*B).y - (*A).y);
else // if ((CodeOut & 1) != 0) // Top
{
y = Top;
x = (*A).x + ((*B).x - (*A).x)*(y - (*A).y)/((*B).y - (*A).y);
}
if (CodeOut == CodeA)
{
(*A).x = x;
(*A).y = y;
Encode(*A, Left, Right, Bottom, Top, &CodeA);
}
else
{
(*B).x = x;
(*B).y = y;
Encode(*B, Left, Right, Bottom, Top, &CodeB);
}
}
}
3.3.4 Thuˆat to´an Liang-Barsky
.
´
˙’
`
´
˙’
Sau khi thuˆat to´an cˇat d¯oan thˇang v`a d¯a gi´ac lˆoi cua Cyrus v`a Beck cˆong bˆo nˇam 1978
.
.
. .
.
.
`
´ ´
(d¯uoc tr`ınh b`ay trong phˆan kˆe tiˆep), nˇam 1984, Liang (d¯ˆoc lˆap v´oi Barsky) d¯a˜ xˆay dung
.
.
.
.
.
.
˙’
´
˙’
thuˆat to´an giao d¯oan thˇang v`a h`ınh chu˜ nhˆat rˆat hiˆeu qua theo c´ach ho`an to`an kh´ac v´oi
.
.
.
.
.
. .
.
˙’
´
˙’
nhu˜ng thuˆat to´an tr`ınh b`ay trˆen. Phuong ph´ap n`ay dua trˆen tham sˆo ho´a cua d¯oan thˇang
.
.
.
. .
˙’
´
´
´
˙’
v`a giai hˆe c´ac bˆat phuong tr`ınh tuyˆen t´ınh theo mˆot ˆan sˆo.
.
.
.
.
.
˙’
`
˙’
`
˙’
Nhˆan x´et rˇang h`ınh chu˜ nhˆat ( ) gˆom tˆap c´ac d¯iˆem trong mˇat phˇang gi´oi han boi c´ac
.
.
.
.
.
. .
.
˙’
˙’
d¯u`ong thˇang qua c´ac canh cua n´o; tu´c l`a
.
( ) = {(
) ∈ R2 |
≤
≤
≤
≤
}
min
max min
max
97
.
.
´
˙’
Tham sˆo ho´a ho´a d¯oan
boi ( ) := + ( − ) v´oi ∈ [0 1]
.
.
.
.
˙’
`
d¯ua vˆe x´ac
˙’
Nhu vˆay b`ai to´an x´ac d¯inh giao cua h`ınh chu˜ nhˆat ( ) v`a d¯oan thˇang
.
.
.
.
. .
´
´
˙’
d¯inh c´ac gi´a tri tham sˆo thoa hˆe c´ac bˆat phuong tr`ınh
.
.
.
0
≤
≤
≤
≤ 1
) ≤
+ (
+ (
−
−
min
min
max
max
)
≤
. .
. .
Hay tuong d¯uong
0
≤
≤
≤ 1
= 0 1 2 3
trong d¯´o
=
=
=
=
=
−
0
1
2
3
0
1
2
3
min
= −
=
−
max
−
−
min
= −
max
.
v´oi
:=
−
:=
−
. .
´
`
´
´
˙’
. .
Suy ra nˆeu tˆon tai chı sˆo ∈ {0 1 2 3} sao cho
= 0 v`a
0 th`ı hˆe bˆat phuong
.
.
.
.
.
˙’
`
giao v´oi h`ınh chu˜ nhˆat ( ) bˇang
.
tr`ınh vˆo nghiˆem; trong tru`ong hop n`ay, d¯oan thˇang
.
.
.
. .
´
trˆong. Nguoc lai d¯ˇat
.
.
.
:= max{0 max{
:= min{1 min{
|
0
= 0 1 2 3}}
= 0 1 2 3}}
0
1
|
0
. .
. .
. .
.
´
Khi d¯´o hˆe bˆat phuong tr`ınh tuong d¯uong v´oi
.
≤ ≤
0
1
.
.
-
`
˙’
`
´
´
˙’
˙’
. .
Diˆeu n`ay chı ra rˇang d¯oan thˇang
giao v´oi h`ınh chu˜ nhˆat ( ) kh´ac trˆong chı nˆeu
;
1
0
.
.
.
v`a trong tru`ong hop n`ay,
.
∩ ( ) = { ( ) | ∈ [
1]}
0
. .
˙’
.
´
Trˆen co so nhu˜ng phˆan t´ıch trˆen, ta c´o thuˆat to´an chi tiˆet sau:
.
.
1. T´ınh
.
v´oi = 0 1 2 3
˙’
2. Khoi tao = 0 v`a = 0 = 1
0
1
.
.
´
´
3. Nˆeu = 0 v`a
0 kˆet luˆan
∩ ( ) = ∅; thuaˆt to´an du`ng.
.
.
98
. .
} Chuyˆen sang Bu´oc 7.
˙’
´
4. Nˆeu
0 d¯ˇat = max{
0
0
.
. .
˙’
´
5. Nˆeu
0 d¯ˇat = min{
} Chuyˆen sang Bu´oc 7.
1
1
.
.
´
´
6. Nˆeu
kˆet luˆan
∩ ( ) = ∅; thuˆat to´an du`ng.
0
1
.
.
. .
. .
´
´
7. Nˆeu
3 thay = + 1 v`a lˇap lai Bu´oc 3; nguoc lai, kˆet luˆan
∩ ( ) =
trong
.
.
.
.
.
d¯o´
=
=
+ ( − )
0
+ ( − )
1
˙’
V´ı du 3.3.4 H`ınh 3.8 minh hoa mˆot v´ı du cua thuˆat to´an Lang-Barsky.
.
.
.
.
.
7
6
5
4
3
2
1
•
@ = 1
1
2
3
@ =
1
( )
1
5
@ =
0
•
@ = 0
0
1
2
3
4
5
6
7
8
9
˙’
H`ınh 3.8: Mˆot v´ı du cua thuˆat to´an Liang-Barsky.
.
.
.
.
V´ı du 3.3.5 X´et h`ınh chu˜ nhˆat
.
.
2
:= {(
) ∈
|0 ≤ ≤ 8 0 ≤ ≤ 4}
. .
˙’
˙’
´
v`a hai d¯iˆem (−1 −2) v`a (10 9) Phuong tr`ınh tham sˆo d¯oan thˇang
c´o dang
.
.
(1 − ) +
. .
`
´
˙’
Ta cˆan giai hˆe c´ac bˆat phuong tr`ınh
.
0 ≤
≤ 1
0 ≤ (1 − )(−1) + (10) ≤ 8
0 ≤ (1 − )(−2) + (9) ≤ 4
99
. .
. .
Hay tuong d¯uong
0 ≤
≤ 1
1 ≤ 11 ≤ 9
2 ≤ 11 ≤ 6
Vˆay
.
2
6
≤ ≤
11
11
.
˙’
˙’
˙’
´
˙’
Suy ra giao cua d¯oan thˇang
v`a h`ınh chu˜ nhˆat l`a d¯oan thˇang nˆoi hai d¯iˆem v`a trong
.
.
.
d¯´o
v`a
2
2
= (1 − ) +
11
9
11
2
=
(−1 −2) + (10 9) = (1 0)
11
11
6
6
= (1 − ) +
11
5
11
6
=
(−1 −2) + (10 9) = (5 4)
11
11
˙’
3.4 Giao cua d¯oan thˇang v`a d¯a gi´ac lˆoi
`
˙’
.
. .
.
. .
˙’
˙’
´
˙’
3.4.1 Vi tr´ı tuong d¯ˆoi cua mˆot d¯iˆem v´oi d¯u`ong thˇang
.
.
.
. .
.
.
˙’
`
˙’
˙’
Trong nhiˆeu u´ng dung ta thu`ong quan tˆam kh´ai niˆem nua mˇat phˇang trong v`a nua mˇat
.
.
.
.
.
. .
. .
˙’
˙’
˙’
˙’
phˇang ngo`ai x´ac d¯inh boi mˆot d¯u`ong thˇang (xem Chuong 1). Kh´ai niˆem n`ay liˆen quan mˆat
.
.
.
.
. .
˙’
´
´
thiˆet d¯ˆen ph´ap vector cua d¯u`ong thˇang.
. .
. .
˙’
´
˙’
˙’
Nhˇac lai l`a phuong tr`ınh tˆong qu´at cua d¯u`ong thˇang c´o dang
.
.
+
+ = 0
. .
. .
Hay tuong d¯uong
+
= −
N´oi c´ach kh´ac, = { ∈ R2 | h −→ i = } trong d¯´o = ( ) l`a ph´ap vector cua d¯u`ong
. .
˙’
˙’
thˇang v`a = − Ky´ hiˆeu
.
−→
+
( ) := { ∈ R2 | h
i
i
}
}
−→
−
( ) := { ∈ R2 | h
100
.
−
˙’
Nua mˇat phˇang ngo`ai ( )
•
˙’
.
.
+
˙’
Nua mˇat phˇang trong ( )
˙’
.
. .
.
. .
˙’
˙’
´
˙’
H`ınh 3.9: Vi tr´ı tuong d¯oˆi cua d¯iˆem v´oi d¯u`ong thˇang
.
.
.
.
˙’
˙’
˙’
˙’
˙’
l`a c´ac nua mˇat phˇang ngo`ai v`a nua mˇat phˇang trong x´ac d¯inh boi (xem H`ınh 3.9).
.
.
.
.
.
˙’
˙’
˙’
. .
´
`
˙’
Vˆan d¯ˆe d¯aˇt ra o d¯ˆay l`a v´oi mˆot d¯iˆem tu`y y´ trong mˇat phˇang, h˜ay x´ac d¯inh d¯iˆem
.
.
.
.
.
.
˙’
`
˙’
`
˙’
˙’
˙’ ˙’
nˇam trong nua mˇat phˇang n`ao? Gia su l`a d¯iˆem nˇam trˆen d¯u`ong thˇang Ky´ hiˆeu l`a
.
.
−→
.
.
0
.
˜
`
´
´
˙’
˙’
g´oc giu˜a vector v`a vector
˙’
Dˆe d`ang thˆay rˇang g´oc nho hon 90 nˆeu
thuoˆc nua
.
mˇat phˇang ngo`ai v`a do d¯´o h −→ i 0 Tuong tu, g´oc l´on hon 90 nˆeu thuˆoc nua mˇat
. .
.
.
.
0
.
´
˙’
.
˙’
.
.
. .
.
phˇang trong v`a do d¯o´ h −→ i 0 Cuˆoi cu`ng, g´oc bˇang 90 nˆeu thuˆoc d¯u`ong thˇang
0
`
˙’
´
´
.
v`a do d¯´o h −→ i = 0 Vˆay
.
∈ ( ) nˆeu h −→ i
0
0
+
´
1.
2.
3.
∈ ( ) nˆeu h −→ i
−
´
∈ nˆeu h −→ i = 0
´
`
Chu´ y´ rˇang
h
−→ i
−→ i
0
. .
. .
tuong d¯uong
h
.
.
˙’
˙’
˙’
˙’
˙’
´
˙’
Do d¯´o ta c´o thˆe viˆet lai tiˆeu chuaˆn kiˆem tra d¯iˆem thuˆoc nua mˇat phˇang n`ao nhu sau:
.
.
.
∈ ( ) nˆeu h −→ i
+
´
1.
2.
3.
∈ ( ) nˆeu h −→ i
−
´
∈ nˆeu h −→ i =
´
.
˙’
˙’
´
´
´
˙’
˙’
Chˇang han, gˆoc toa d¯oˆ (0 0) thuoˆc nua mˇat phˇang ngo`ai nˆeu v`a chı nˆeu
0
.
.
.
.
.
101
( )
˙’
`
˙’
H`ınh 3.10: Giao cua d¯oan thˇang v`a d¯a gi´ac lˆoi.
.
˙’
`
˙’
3.4.2 Thuˆat to´an t`ım giao cua d¯oan thˇang v`a d¯a gi´ac lˆoi
.
.
.
˙’
Nˇam 1978, Cyrus v`a Beck [5] d¯a˜ xˆay dung thuˆat to´an x´ac d¯inh giao cua d¯oan thˇang v`a d¯a
˙’
.
.
.
.
.
.
. .
.
˙’
˜
`
`
˙’
gi´ac lˆoi v`a c´o thˆe mo rˆong dˆe d`ang trong ba chiˆeu. H`ınh chu˜ nhˆat l`a mˆot tru`ong hop d¯aˇc
.
.
.
.
.
˙’
`
˙’
biˆet cua d¯a gi´ac lˆoi v`a do d¯o´ c´o thˆe ´ap dung thuaˆt to´an n`ay. Thuˆat to´an Liang-Barsky tr`ınh
.
.
.
.
. .
.
`
´
˙’
b`ay trong phˆan tru´oc dua trˆen c´ach tiˆep cˆan cua Cyrus v`a Beck. Thuaˆt to´an Cyrus-Beck
.
.
.
.
.
. .
.
˙’
˙’
`
´
˙’
˙’
˙’
dua trˆen tiˆeu chuaˆn loai bo d¯on gian bˇang c´ach x´et vi tr´ı tuong d¯ˆoi cua mˆot d¯iˆem v´oi mˆot
.
.
.
.
.
. .
˙’
d¯u`ong thˇang.
.
´
˙’
`
´
Nhˇac lai l`a trong thuˆat to´an Cohen-Sutherland, d¯ˆoi v´oi c´ac d¯oan thˇang khˆong nˇam
.
.
.
.
˙’
trong h`ınh chu˜ nhˆat hoˇac bi loai bo ho`an to`an, ta cˆan t´ınh toa d¯ˆo giao d¯iˆem (
`
˙’
˙’
) cua d¯oan
.
.
.
.
.
.
.
.
. .
˙’
`
´
´
thˇang v´oi mˆot canh n`ao d¯´o bˇang c´ach thˆe gi´a tri d¯˜a biˆet hoˇac v`ao phuong tr`ınh canh
.
.
.
.
.
.
. .
.
˙’
˙’
´
d¯u´ng hay ngang tuong u´ng. Tuy nhiˆen, trong thuaˆt to´an tham sˆo ho´a d¯oan thˇang, ta s˜e
.
.
. .
˙’
˙’
. .
˜
˙’
´
˙’
˙’
t`ım c´ac gi´a tri tham sˆo trong khoang biˆeu diˆen cua d¯oan thˇang cho d¯iˆem giao cua d¯u`ong
.
.
. .
.
˙’
˙’
´
´
˙’
thˇang v`a canh d¯uoc x´et. N´oi chung, v`ı tˆat ca c´ac canh s˜e giao v´oi d¯u`ong thˇang, nˆen bˆon
.
.
.
. .
.
.
`
´
´
˙’
trong bˆon gi´a tri n`ay tuong u´ng v´oi c´ac d¯iˆem giao thuc su. Sau d¯o´ c´ac toa d¯oˆ (
gi´a tri cˆan d¯uoc t´ınh. V´oi mˆot loat c´ac ph´ep so s´anh d¯on gian s˜e cho biˆet c´ac tham sˆo
.
.
.
.
. .
.
.
.
.
˙’
´
˙’
) cua
.
.
.
.
.
. .
.
˙’
´
´
mˆot hoˇac hai giao d¯iˆem d¯uoc x´ac d¯inh. N´oi chung c´ach tiˆep cˆan n`ay s˜e tiˆet kiˆem th`oi gian
.
.
.
.
.
.
.
˙’
´
´
`
´
`
hon thuˆat to´an cˇat x´en Cohen-Sutherland do n´o tr´anh v`ong lˇap cˆan thiˆet d¯ˆe cˇat nhiˆeu canh
.
.
.
.
.
.
.
.
´
˙’
˙’
cua h`ınh chu˜ nhˆat. Hon nu˜a, c´ac ph´ep t´ınh trong khˆong gian tham sˆo 1D d¯on gian hon
.
trong khˆong gian 2D.
.
. .
.
`
˙’ ˙’
˙’
Gia su d¯a gi´ac lˆoi ( ) d¯uoc d¯inh ngh˜ıa nhu mˆot d˜ay c´ac d¯ınh
= (
)
=
.
.
.
.
.
.
`
`
˙’
˙’
0 1
˙’
trong hˆe toa d¯oˆ thuc v´oi
. .
=
Muc d¯´ıch cua phˆan n`ay l`a loai bo nhu˜ng phˆan
0
.
.
.
.
.
˙’
˙’
cua d¯oan thˇang
`
˙’
khˆong nˇam trong “cua sˆo” ( ) (H`ınh 3.10).
.
102
Tải về để xem bản đầy đủ
91 trang
20160
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Đồ họa máy tính I (Phần 2) - Phạm Tiến Sơn", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_do_hoa_may_tinh_phan_2.pdf
