D
-
ˆ
O
`
HO
.
A M
´
AY T
´
INH I
Pha
.
m Tiˆe
´
n So
.
n
D
-
`a La
.
t, 2005
2
Mu
.
c lu
.
c
L`o

˙’
m gi˜u
.
a . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.3 Mˆo
.
t sˆo
´
vˆa
´
n d¯ˆe
`
liˆen quan d¯ˆe
´
n thuˆa
.
t to´an v˜e d¯oa
.
n thˇa
˙’
ng . . . . . . . . 18
1.1.4 C´ac thuˆo
.
c t´ınh cu
˙’
a d¯oa
.
n thˇa
˙’
ng . . . . . . . . . . . . . . . . . . . . . 21

.
`o
.
ng cong ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.3.1 Ellipse c´o da
.
ng ch´ınh tˇa
´
c . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.3.2 Ellipse trong tru
.
`o
.
ng ho
.
.
p tˆo
˙’
ng qu´at . . . . . . . . . . . . . . . . . . . 34
2 H`ınh ho
.
c cu
˙’
a c´ac d¯u
.
`o
.
ng cong v`a mˇa
.
t cong 47

a d¯u
.
`o
.
ng cong Bezier . . . . . . . . . . . . . . . . . . . . . . 55
2.3.1 D
-
iˆe
`
u khiˆe
˙’
n d¯i
.
a phu
.
o
.
ng . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.4 D
-
a th´u
.
c t`u
.
ng kh´uc v`a c´ac h`am spline . . . . . . . . . . . . . . . . . . . . . . 60
2.4.1 Su
.
˙’
du
.

.
˙’
du
.
ng c´ac knot bˆo
.
i . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
2.4.6 Vector knot chuˆa
˙’
n . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
2.5 C´ac t´ınh chˆa
´
t cu
˙’
a d¯u
.
`o
.
ng cong B-spline . . . . . . . . . . . . . . . . . . . . . 75
2.6 Nˆo
.
i suy c´ac d¯iˆe
˙’
m d¯iˆe
`
u khiˆe
˙’
n bˇa
`
ng d¯u

3.2 Giao cu
˙’
a hai d¯oa
.
n thˇa
˙’
ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.2.1 Phˆan t´ıch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4
3.2.2 Thuˆa
.
t to´an x´ac d¯i
.
nh giao hai d¯oa
.
n thˇa
˙’
ng . . . . . . . . . . . . . . . . 86
3.3 D
-
oa
.
n thˇa
˙’
ng v`a h`ınh ch˜u
.
nhˆa
.
t . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.3.1 T`ım giao bˇa

3.4.1 Vi
.
tr´ı tu
.
o
.
ng d¯ˆo
´
i cu
˙’
a mˆo
.
t d¯iˆe
˙’
m v´o
.
i d¯u
.
`o
.
ng thˇa
˙’
ng . . . . . . . . . . . . 100
3.4.2 Thuˆa
.
t to´an t`ım giao cu
˙’
a d¯oa
.
n thˇa

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
3.6.2 Giao cu
˙’
a tia s´ang v`a d¯u
.
`o
.
ng thˇa
˙’
ng . . . . . . . . . . . . . . . . . . . 117
3.6.3 Giao cu
˙’
a tia s´ang v´o
.
i d¯u
.
`o
.
ng tr`on . . . . . . . . . . . . . . . . . . . . 121
3.6.4 Xˆay du
.
.
ng v´ı du
.
ray tracing . . . . . . . . . . . . . . . . . . . . . . . 124
3.6.5 Buˆo
`
ng k´ın l`a ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
4 Tˆo m`au v`ung 127
4.1 C´ac d¯i

4.5 So s´anh c´ac thuˆa
.
t to´an . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
4.6 Tˆo m`au c´ac h`ınh ch˜u
.
nhˆa
.
t . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
4.7 Thuˆa
.
t to´an tˆo m`au d¯a gi´ac . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
4.7.1 C´ac d`ong qu´et ngang . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
4.7.2 C´ac ma
˙’
nh vu
.
n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
4.7.3 Liˆen kˆe
´
t ca
.
nh v`a thuˆa
.
t to´an tr`an . . . . . . . . . . . . . . . . . . . . 151
4.7.4 Tˆo m`au c´ac d¯a gi´ac chˆo
`
ng nhau . . . . . . . . . . . . . . . . . . . . . 158
4.8 Tˆo m`au theo mˆa
˜
u tˆo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

t l˜ınh vu
.
.
c hˆa
´
p dˆa
˜
n cu
˙’
a khoa ho
.
c m´ay t´ınh. Ch´ung ta su
.
˙’
du
.
ng d¯ˆo
`
ho
.
a
m´ay t´ınh nhu
.
mˆo
.
t cˆong cu
.
d¯ˆe
˙’
quan s´at thˆong tin trong nhiˆe

cho ph´ep ngu
.
`o
.
i su
.
˙’
du
.
ng l`am viˆe
.
c theo c´ach tu
.
.
nhiˆen nhˆa
´
t: ngu
.
`o
.
i su
.
˙’
du
.
ng cung cˆa
´
p thˆong
tin cho tr`ınh ´u
.

`
ho
.
a m´ay t´ınh d¯ang gi´up con ngu
.
`o
.
i thay d¯ˆo
˙’
i vˆe
`
quan niˆe
.
m v`a
c´ach th´u
.
c su
.
˙’
du
.
ng m´ay t´ınh.
Gi´ao tr`ınh D
-
ˆo
`
ho
.
a m´ay t´ınh I cung cˆa
´

`
n quan tro
.
ng khˆong thˆe
˙’
thiˆe
´
u d¯u
.
o
.
.
c s˜e d¯u
.
o
.
.
c
d¯ˆe
`
cˆa
.
p trong mˆo
.
t gi´ao tr`ınh kh´ac). D
-
ˆe
˙’
c´o mˆo
.

´
t kˆe
´
c´ac thuˆa
.
t to´an trong gi´ao tr`ınh cho ph´ep sinh viˆen c´o thˆe
˙’
viˆe
´
t
dˆe
˜
d`ang c´ac chu
.
o
.
ng tr`ınh minh ho
.
a. Gi´ao tr`ınh d¯u
.
o
.
.
c biˆen soa
.
n cho c´ac d¯ˆo
´
i tu
.
o

n c´o mˆo
.
t sˆo
´
kiˆe
´
n th´u
.
c vˆe
`
ngˆon ng˜u
.
C. Ngo`ai
ra, hˆa
`
u hˆe
´
t c´ac chu
.
o
.
ng tr`ınh thao t´ac trˆen cˆa
´
u tr´uc d˜u
.
liˆe
.
u nhu
.
danh s´ach liˆen kˆe

i ho
.
c: hiˆe
˙’
u biˆe
´
t vˆe
`
d¯a
.
i sˆo
´
tuyˆe
´
n t´ınh v`a h`ınh ho
.
c gia
˙’
i t´ıch, ph´ep t´ınh vi t´ıch phˆan.
Mu
.
c d¯´ıch cu
˙’
a gi´ao tr`ınh l`a, o
.
˙’
m´u
.
c d¯ˆo
.

˙’
c´ac chu
.
o
.
ng tr`ınh. Mˆo
.
t trong
nh˜u
.
ng mu
.
c d¯´ıch ch´ınh cu
˙’
a gi´ao tr`ınh l`a gi´up sinh viˆen nˇa
´
m v˜u
.
ng c´ac phu
.
o
.
ng ph´ap, tru
.
´o
.
c
hˆe
´
t to´an ho

n phu
.
lu
.
c v´o
.
i nh˜u
.
ng nˆo
.
i dung ch´ınh nhu
.
sau:
• Chu
.
o
.
ng th´u
.
nhˆa
´
t d¯ˆe
`
cˆa
.
p d¯ˆe
´
n c´ac phu
.
o

˙’
a Chu
.
o
.
ng 2. Hˆa
`
u hˆe
´
t c´ac
phˆa
`
n mˆe
`
m d¯ˆo
`
ho
.
a d¯ˆe
`
u c´o nh˜u
.
ng ch´u
.
c nˇang ta
.
o ra c´ac d¯u
.
`o
.

p cˆa
.
n
thu
.
.
c h`anh m`a c´ac tr`ınh ´u
.
ng du
.
ng d¯ˆo
`
ho
.
a ´ap du
.
ng.
• Chu
.
o
.
ng 3 gia
˙’
i quyˆe
´
t b`ai to´an x´ac d¯i
.
nh giao cu
˙’
a nh˜u

.
o
.
ng l`a mˆo
.
t v´ı du
.
cu
˙’
a k˜y thuˆa
.
t “ray tracing” hai chiˆe
`
u:
Chuyˆe
˙’
n d¯ˆo
.
ng cu
˙’
a tia s´ang trong buˆo
`
ng k´ın c´o ch´u
.
a c´ac “chu
.
´o
.
ng nga
.

i d¯u
.
`o
.
ng biˆen v`a v`ung l`a d¯a gi´ac.
• Phˆa
`
n phu
.
lu
.
c l`a thu
.
viˆe
.
n c´ac cˆa
´
u tr´uc d˜u
.
liˆe
.
u v`a c´ac h`am cˆa
`
n thiˆe
´
t v`a thu
.
`o
.
ng xuyˆen

´
m v˜u
.
ng kiˆe
´
n th´u
.
c d¯˜a ho
.
c. Ngo`ai ra, c´ac
lˆo
˜
i trong xuˆa
´
t ba
˙’
n lˆa
`
n tru
.
´o
.
c c˜ung d¯˜a d¯u
.
o
.
.
c chı
˙’
nh l´y; mˇa

.
.
c t`u
.
nhiˆe
`
u ngu
.
`o
.
i m`a khˆong thˆe
˙’
liˆe
.
t kˆe
hˆe
´
t, d¯ˇa
.
c biˆe
.
t l`a c´ac ba
.
n sinh viˆen, trong qu´a tr`ınh biˆen soa
.
n gi´ao tr`ınh n`ay.
D
-
`a La
.

ng n`ay tr`ınh b`ay c´ac thuˆa
.
t to´an v˜e d¯oa
.
n thˇa
˙’
ng, d¯u
.
`o
.
ng tr`on v`a ellipse trˆen lattice
nguyˆen Z
2
. C´ac thuˆa
.
t to´an chı
˙’
thao t´ac trˆen nh˜u
.
ng sˆo
´
nguyˆen v`a trong c´ac v`ong lˇa
.
p chı
˙’
su
.
˙’
du
.

a c´ac pixel nˇa
`
m trˆen hoˇa
.
c gˆa
`
n v´o
.
i d¯oa
.
n thˇa
˙’
ng
thu
.
.
c tˆe
´
nhˆa
´
t. Vˆe
`
nguyˆen tˇa
´
c, ch´ung ta muˆo
´
n cho
.
n d˜ay c´ac pixel gˆa
`

.
c xˆa
´
p xı
˙’
v´o
.
i mˆa
.
t d¯ˆo
.
mˆo
.
t pixel; ta cˆa
`
n c´o
nh˜u
.
ng t´ınh chˆa
´
t g`ı? V´o
.
i c´ac d¯oa
.
n thˇa
˙’
ng c´o hˆe
.
sˆo
´

n n`ay, c´o d¯´ung
mˆo
.
t pixel d¯u
.
o
.
.
c v˜e trˆen mˆo
˜
i h`ang. Tˆa
´
t ca
˙’
c´ac d¯oa
.
n thˇa
˙’
ng d¯u
.
o
.
.
c v˜e v´o
.
i c`ung mˆo
.
t d¯ˆo
.
s´ang,

n c´ac thuˆo
.
c t´ınh cu
˙’
a d¯oa
.
n thˇa
˙’
ng nhu
.
d¯ˆo
.
rˆo
.
ng, kiˆe
˙’
u v˜e Thˆa
.
m ch´ı
ch´ung ta muˆo
´
n cu
.
.
c tiˆe
˙’
u ho´a m´u
.
c d¯ˆo
.

`
ng c´ach ´ap du
.
ng kha
˙’
nˇang d¯ˇa
.
t cu
.
`o
.
ng
d¯ˆo
.
cu
˙’
a mˆo
˜
i pixel trˆen c´ac thiˆe
´
t bi
.
hiˆe
˙’
n thi
.
m`a mˆo
.
t pixel tu
.

.
t pixel v`a c´o d¯´ung mˆo
.
t
pixel trˆen mˆo
˜
i cˆo
.
t (hoˇa
.
c h`ang d¯ˆo
´
i v´o
.
i c´ac d¯oa
.
n thˇa
˙’
ng dˆo
´
c). Phˆa
`
n cuˆo
´
i chu
.
o
.
ng s˜e d¯ˆe
`

´
m tr`on v´o
.
i tˆam ta
.
i vi
.
tr´ı (x, y) cu
˙’
a pixel trˆen lu
.
´o
.
i c´ac to
.
a d¯ˆo
.
nguyˆen Z
2
. Biˆe
˙’
u diˆe
˜
n n`ay l`a mˆo
.
t xˆa
´
p xı
˙’
th´ıch ho

a c´ac vˆe
´
t trˆen m`an h`ınh hiˆe
˙’
n thi
.
. Trong mˆo
.
t sˆo
´
hˆe
.
thˆo
´
ng, c´ac chˆa
´
m kˆe
`
nhau phu
˙’
lˆa
´
p mˆo
.
t phˆa
`
n lˆen nhau; v´o
.
i nh˜u
.

ho
.
n theo chiˆe
`
u d¯´u
.
ng. Mˆo
.
t kh´ac biˆe
.
t n˜u
.
a tu`y theo hˆe
.
thˆo
´
ng trong viˆe
.
c biˆe
˙’
u
diˆe
˜
n hˆe
.
to
.
a d¯ˆo
.
, chˇa

˙’
a lu
.
´o
.
i d¯iˆe
`
u khiˆe
˙’
n thay cho nˇa
`
m trˆen c´ac d¯u
.
`o
.
ng thˇa
˙’
ng cu
˙’
a
lu
.
´o
.
i. Theo c´ach n`ay, c´ac h`ınh ch˜u
.
nhˆa
.
t (x´ac d¯i
.

n (x, y) khˆong ch´u
.
a pixel n`ao, trong khi v´o
.
i nh˜u
.
ng hˆe
.
thˆo
´
ng kh´ac, c´o d¯´ung mˆo
.
t
pixel ta
.
i d¯iˆe
˙’
m n`ay. Du
.
´o
.
i d¯ˆay ch´ung ta s˜e biˆe
˙’
u diˆe
˜
n c´ac pixel nhu
.
c´ac h`ınh tr`on r`o
.
i nhau c´o

t pixel cu
˙’
a n´o.
C´ac pixel d¯u
.
o
.
.
c v˜e tu
.
o
.
ng ´u
.
ng c´ac h`ınh tr`on m`au d¯en v`a c´ac pixel khˆong d¯u
.
o
.
.
c v˜e tu
.
o
.
ng ´u
.
ng
h`ınh tr`on khˆong tˆo. Trˆen m`an h`ınh thu
.
.
c tˆe

˜
n bˇa
`
ng k´y hiˆe
.
u cu
˙’
a ch´ung ta l`a
mˆo
.
t ph´ong d¯a
.
i m´u
.
c d¯ˆo
.
r`o
.
i ra
.
c cu
˙’
a c´ac pixel.

.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
✐ ✐ ✐ ✐ ✐
✐ ✐ ✐ ✐ ✐
✐ ✐ ✐ ✐ ✐
✐ ✐ ✐ ✐ ✐
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
②

´
ng ch´ung ta x´ac d¯i
.
nh trˆen lu
.
´o
.
i d¯iˆe
`
u khiˆe
˙’
n nguyˆen nˆen
c´ac to
.
a d¯ˆo
.
d¯ˆa
`
u cuˆo
´
i cu
˙’
a d¯oa
.
n thˇa
˙’
ng l`a nguyˆen. Thˆa
.
t ra, nˆe
´

´
i cu
˙’
a d¯oa
.
n thˇa
˙’
ng c´o thˆe
˙’
khˆong nguyˆen. (Ch´ung ta s˜e tha
˙’
o luˆa
.
n c´ac giao d¯iˆe
˙’
m khˆong nguyˆen trong Phˆa
`
n 1.1.3). Gia
˙’
10
su
.
˙’
d¯oa
.
n thˇa
˙’
ng c´o hˆe
.
sˆo

`o
.
ng ho
.
.
p c´ac d¯oa
.
n thˇa
˙’
ng ngang, d¯´u
.
ng hoˇa
.
c c´o hˆe
.
sˆo
´
g´oc ±1 l`a tˆa
`
m thu
.
`o
.
ng v`ı ch´ung chı
˙’
d¯i qua c´ac pixel trˆen lu
.
´o
.
i.

.
ng thˇa
˙’
ng AB c´o da
.
ng y = mx +t, trong d¯´o hˆe
.
sˆo
´
g´oc m = dy/dx v`a t = y
A
−mx
A
.
C´ach d¯o
.
n gia
˙’
n nhˆa
´
t d¯ˆe
˙’
v˜e d¯oa
.
n thˇa
˙’
ng AB l`a:
1. T´ınh hˆe
.
sˆo

sau d¯´o v˜e pixel ta
.
i (x
i
, y
i
+ 0.5)
1
.
Theo c´ach n`ay ta cho
.
n pixel tˆo
´
t nhˆa
´
t, t´u
.
c l`a pixel m`a khoa
˙’
ng c´ach d¯ˆe
´
n d¯u
.
`o
.
ng thˇa
˙’
ng thu
.
.

t ph´ep cˆo
.
ng v`a mˆo
.
t ph´ep to´an l`am tr`on. Ta c´o thˆe
˙’
khu
.
˙’
ph´ep nhˆan bˇa
`
ng c´ach ch´u ´y rˇa
`
ng
y
i+1
= mx
i+1
+ t
= m(x
i
+ ∆x) + t
= y
i
+ m∆x,
v`a nˆe
´
u bu
.
´o

n
thˇa
˙’
ng ta biˆe
´
t rˇa
`
ng nˆe
´
u x
i+1
= x
i
+ 1 th`ı y
i+1
= y
i
+ m; t´u
.
c l`a, c´ac gi´a tri
.
x v`a y d¯u
.
o
.
.
c t´ınh
theo c´ac gi´a tri
.
tru

.
.
a trˆen bu
.
´o
.
c tru
.
´o
.
c.
Kho
.
˙’
i ta
.
o ta g´an (x
0
, y
0
) l`a to
.
a d¯ˆo
.
nguyˆen cu
˙’
a d¯iˆe
˙’
m xuˆa
´

. Do d¯´o
cˆa
`
n ho´an d¯ˆo
˙’
i vai tr`o cu
˙’
a x v`a y bˇa
`
ng c´ach g´an bu
.
´o
.
c tˇang mˆo
.
t d¯o
.
n vi
.
cho y v`a tˇang x mˆo
.
t
lu
.
o
.
.
ng ∆x =
∆y
m

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

, y
i
)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
D
-
u
.
`o
.
ng thˇa
˙’
ng
thu
.
.
c tˆe
´

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
✇
✇ ✇

3
7
∈ (0, 1).
´
Ap du
.
ng thuˆa
.
t to´an sˆo
´
gia ta d¯u
.
o
.
.
c d˜ay c´ac d¯iˆe
˙’
m v˜e tˆo
´
t nhˆa
´
t nhu
.
trong
ba
˙’
ng du
.
´o
.

18
7
3
7 9
21
7
3
Thu
˙’
tu
.
c Line() du
.
´o
.
i d¯ˆay minh ho
.
a thuˆa
.
t to´an v˜e d¯oa
.
n thˇa
˙’
ng t`u
.
(x
0
, y
0
) d¯ˆe

.
.
p
−1 ≤ m ≤ 1 v`ı c´ac tru
.
`o
.
ng ho
.
.
p kh´ac c´o thˆe
˙’
thu
.
.
c hiˆe
.
n do t´ınh d¯ˆo
´
i x´u
.
ng. Ho
.
n n˜u
.
a, ch´ung ta
c˜ung bo
˙’
qua viˆe
.

ng, trong ngˆon ng˜u
.
C, (int)y bˇa
`
ng y + 0.5.
void Line(int x_A, int y_A, int x_B, int y_B, int Value)
{
12
int x;
int dx, dy;
float y, m;
dx = x_B - x_A;
dy = y_B - y_A;
m = dy/(float)dx;
y = y0;
for (x = x_A; x <= x_B; x ++)
{
putpixel(x, (int)(y), Value);
y += m;
}
}
1.1.2 Thuˆa
.
t to´an d¯iˆe
˙’
m gi˜u
.
a
Thu
˙’

.
nh (x
i+1
, y
i+1
) theo sˆo
´
gia du
.
.
a trˆen nh˜u
.
ng gi´a tri
.
o
.
˙’
bu
.
´o
.
c tru
.
´o
.
c (x
i
, y
i
). Thuˆa

n n˜u
.
a, phu
.
o
.
ng
ph´ap cu
˙’
a Bresenham c´o thˆe
˙’
d¯u
.
o
.
.
c ´ap du
.
ng t´ınh to´an trˆen sˆo
´
nguyˆen v˜e d¯u
.
`o
.
ng tr`on mˇa
.
c d`u
n´o khˆong dˆe
˜
d`ang mo

o
.
.
c cˆong bˆo
´
lˆa
`
n d¯ˆa
`
u tiˆen bo
.
˙’
i Pitteway [16], [17] v`a d¯u
.
o
.
.
c
ca
˙’
i tiˆe
´
n bo
.
˙’
i Van Aken [26] v`a mˆo
.
t sˆo
´
t´ac gia

a suy ra cˆong th´u
.
c
cu
˙’
a Bresenham v`a do d¯´o sinh ra c`ung d˜ay c´ac pixel.
Khˆong mˆa
´
t t´ınh tˆo
˙’
ng qu´at, gia
˙’
su
.
˙’
hˆe
.
sˆo
´
g´oc m cu
˙’
a d¯u
.
`o
.
ng thˇa
˙’
ng thuˆo
.
c khoa

t c´ach th´ıch ho
.
.
p qua
c´ac tru
.
c to
.
a d¯ˆo
.
). Ta c˜ung k´y hiˆe
.
u d¯iˆe
˙’
m xuˆa
´
t ph´at l`a (x
A
, y
A
) v`a d¯iˆe
˙’
m kˆe
´
t th´uc l`a (x
B
, y
B
).
D

y =
dy
dx
x + t;
13
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

(l
−
)
(l
+
)

u c´ac nu
.
˙’
a mˇa
.
t phˇa
˙’
ng ngo`ai v`a nu
.
˙’
a mˇa
.
t
phˇa
˙’
ng trong x´ac d¯i
.
nh bo
.
˙’
i l tu
.
o
.
ng ´u
.
ng bo
.
˙’
i

˙’
m v˜e “tˆo
´
t nhˆa
´
t” (x
i
, y
i
)
bˇa
´
t d¯ˆa
`
u t`u
.
d¯iˆe
˙’
m (x
0
, y
0
) = (x
A
, y
A
). Kh´ai niˆe
.
m tˆo
´

˙’
ng thu
.
.
c tˆe
´
(da
.
ng liˆen tu
.
c) nhˆa
´
t. Theo gia
˙’
thiˆe
´
t, 0 < m < 1, nˆen khi
x tˇang mˆo
.
t lu
.
o
.
.
ng ∆x th`ı y tˇang khˆong qu´a ∆y = m∆x d¯o
.
n vi
.
.
V`ı vˆa

.
´o
.
c th´u
.
i + 1
ta s˜e cho
.
n d¯iˆe
˙’
m v˜e (x
i+1
, y
i+1
), trong d¯´o x
i+1
= x
i
+ 1 v`a y
i+1
= y
i
hoˇa
.
c y
i+1
= y
i
+ 1.
N´oi c´ach kh´ac, bu

ng thˇa
˙’
ng l v`a
x = x
i
+ 1. Theo Bresenham, dˆa
´
u cu
˙’
a biˆe
˙’
u th´u
.
c x´ac d¯i
.
nh bo
.
˙’
i hiˆe
.
u gi˜u
.
a hai khoa
˙’
ng c´ach t`u
.
R v`a D d¯ˆe
´
n Q cho ph´ep x´ac d¯i
.

.
t phˇa
˙’
ng x´ac d¯i
.
nh b o
.
˙’
i d¯u
.
`o
.
ng thˇa
˙’
ng l. Dˆe
˜
d`ang chı
˙’
ra rˇa
`
ng, nˆe
´
u M ∈ (l
+
) th`ı pixel D gˆa
`
n v´o
.
i d¯u
.

`
m vˆe
`
c`ung
mˆo
.
t nu
.
˙’
a mˇa
.
t phˇa
˙’
ng (l
+
) (hoˇa
.
c (l
−
)) nhu
.
ng trong bˆa
´
t c´u
.
tru
.
`o
.
ng ho

.
.
c cho
.
n v`a d¯u
.
`o
.
ng thˇa
˙’
ng
thu
.
.
c tˆe
´
l-luˆon luˆon nho
˙’
ho
.
n hoˇa
.
c bˇa
`
ng 1/2.
14
D
-
ˆe
˙’

n quyˆe
´
t d¯i
.
nh
d
i
:= f(x
i
+ 1, y
i
+
1
2
)
= a(x
i
+ 1) + b(y
i
+
1
2
) + c.
Khi d¯´o
1. Nˆe
´
u d
i
> 0 cho
.

.
a d¯ˆo
.
d¯iˆe
˙’
m gi˜u
.
a M v`a do d¯´o biˆe
´
n quyˆe
´
t d¯i
.
nh d
i+1
o
.
˙’
bu
.
´o
.
c i + 1;
d˜ı nhiˆen d¯iˆe
`
u n`ay phu
.
thuˆo
.
c v`ao viˆe

i
+
1
2
) = a(x
i
+ 2) + b(y
i
+
1
2
) + c.
Nhu
.
ng
d
i
= a(x
i
+ 1) + b(y
i
+
1
2
) + c.
Suy ra d
i+1
= d
i
+ a.

.
˙’
bu
.
´o
.
c kˆe
´
tiˆe
´
p t`u
.
biˆe
´
n quyˆe
´
t d¯i
.
nh o
.
˙’
bu
.
´o
.
c hiˆe
.
n h`anh bˇa
`
ng

.
, nˆen
d
i+1
= f(x
i
+ 2, y
i
+
3
2
) = a(x
i
+ 2) + b(y
i
+
3
2
) + c.
V`a do d¯´o
d
i+1
= d
i
+ a + b.
K´y hiˆe
.
u sˆo
´
gia d¯u

, y
A
) nˆen c´o thˆe
˙’
t´ınh tru
.
.
c tiˆe
´
p gi´a tri
.
kho
.
˙’
i
ta
.
o d
0
. Thˆa
.
t vˆa
.
y, d¯iˆe
˙’
m gi˜u
.
a d¯ˆa
`
u tiˆen c´o to

+ c + a + b/2
= f(x
0
, y
0
) + a + b/2.
15
Nhu
.
ng (x
0
, y
0
) thuˆo
.
c d¯u
.
`o
.
ng thˇa
˙’
ng l nˆen f ( x
0
, y
0
) = 0; do d¯´o gi´a tri
.
kho
.
˙’

ˆe
˙’
khu
.
˙’
mˆa
˜
u sˆo
´
trong d
0
ta d¯i
.
nh ngh˜ıa la
.
i h`am f bˇa
`
ng c´ach nhˆan n´o cho 2; t´u
.
c l`a
f(x, y) = 2(ax + by + c). N´oi c´ach kh´ac, nhˆan 2 cho c´ac hˇa
`
ng sˆo
´
a, b, c v`a biˆe
´
n quyˆe
´
t d¯i
.

.
a v˜e d¯oa
.
n thˇa
˙’
ng AB (trong tru
.
`o
.
ng ho
.
.
p x
A
< x
B
v`a 0 < m < 1) nhu
.
sau:
1. [Kho
.
˙’
i ta
.
o] D
-
ˇa
.
t dx = x
B

bu
.
´o
.
c th´u
.
i ta c´o d¯iˆe
˙’
m v˜e tˆo
´
t nhˆa
´
t (x
i
, y
i
) v`a biˆe
´
n quyˆe
´
t d¯i
.
nh d
i
.
3. [V˜e pixel hiˆe
.
n h`anh] D
-
ˇa

.
i, d¯ˇa
.
t
x
i+1
= x
i
+ 1;
y
i+1
=

y
i
nˆe
´
u d
i
≤ 0,
y
i
+ 1 nˆe
´
u ngu
.
o
.
.
c la

`
ng (i + 1) v`a lˇa
.
p la
.
i Bu
.
´o
.
c 3.
V´ı du
.
1.1.2 Gia
˙’
su
.
˙’
A(2, 0), B(9, 3). Khi d¯´o d¯u
.
`o
.
ng thˇa
˙’
ng qua hai d¯iˆe
˙’
m A v`a B c´o hˆe
.
sˆo
´
g´oc m =

Ap du
.
ng thuˆa
.
t to´an d¯iˆe
˙’
m gi˜u
.
a ta c´o d˜ay c´ac d¯iˆe
˙’
m v˜e tˆo
´
t nhˆa
´
t nhu
.
trong ba
˙’
ng du
.
´o
.
i:
i x
i
y
i
d
i
0 2 0 −1

ng ph´ap sˆo
´
gia trong
V´ı du
.
1.1.1.
Ch´u ´y rˇa
`
ng, ph´ep t´ınh cˆa
`
n thiˆe
´
t d¯ˆo
´
i v´o
.
i d
i+1
trong mˆo
˜
i bu
.
´o
.
c lˇa
.
p l`a ph´ep cˆo
.
ng v`a khˆong
c´o ph´ep nhˆan. Ho

for (x = x_A; x <= x_B; x++)
{
putpixel(x, y, Value);
if (d <= 0) d += DeltaR;
else
{
d += DeltaD;
17
y++;
}
}
}
1.1.3 Mˆo
.
t sˆo
´
vˆa
´
n d¯ˆe
`
liˆen quan d¯ˆe
´
n thuˆa
.
t to´an v˜e d¯oa
.
n thˇa
˙’
ng
Th´u

.
o
.
.
c v˜e t`u
.
A d¯ˆe
´
n B ch´u
.
a c`ung tˆa
.
p c´ac pixel nhu
.
d¯oa
.
n thˇa
˙’
ng d¯u
.
o
.
.
c v˜e t`u
.
B d¯ˆe
´
n A; n´oi
c´ach kh´ac, d¯oa
.

xa
˙’
y ra ta
.
i nh ˜u
.
ng d¯iˆe
˙’
m v˜e m`a d¯u
.
`o
.
ng thˇa
˙’
ng d¯i qua d¯iˆe
˙’
m gi ˜u
.
a v`a biˆe
´
n quyˆe
´
t d¯i
.
nh
bˇa
`
ng khˆong; trong tru
.
`o

.
.
a n`ay s˜e
sai lˆe
.
ch mˆo
.
t d¯o
.
n vi
.
theo th`anh phˆa
`
n y v´o
.
i pixel d¯u
.
o
.
.
c cho
.
n khi d¯i t`u
.
tr´ai sang pha
˙’
i. Do d¯´o
ch´ung ta cˆa
`
n cho

ng c´o hˆe
.
sˆo
´
g´oc bˆa
´
t k`y.
Phu
.
o
.
ng ph´ap ho´an d¯ˆo
˙’
i c´ac d¯iˆe
˙’
m d¯ˆa
`
u cuˆo
´
i cu
˙’
a d¯oa
.
n thˇa
˙’
ng d¯ˆe
˙’
thuˆa
.
t to´an xu

.
ng dˆa
´
u hiˆe
.
u ta
.
i d¯iˆe
˙’
m xuˆa
´
t ph´at, c´o thˆe
˙’
l`a d¯iˆe
˙’
m
du
.
´o
.
i bˆen tr´ai, khˆong phu
.
thuˆo
.
c v`ao hu
.
´o
.
ng di chuyˆe
˙’

.
.
d¯ˆo
.
ng d¯ˆo
˙’
i
th`anh d¯iˆe
˙’
m du
.
´o
.
i bˆen tr´ai. Ngo`ai ra, nˆe
´
u thuˆa
.
t to´an luˆon luˆon d¯ˇa
.
t la
.
i c´ac d¯iˆe
˙’
m d¯ˆa
`
u cuˆo
´
i
theo th´u
.

ng BA ; d¯iˆe
`
u n`ay ta
.
o ra su
.
.
gi´an d¯oa
.
n trong qu´a tr`ınh v˜e, chˇa
˙’
ng ha
.
n
d¯a gi´ac, ta
.
i nh˜u
.
ng d¯ı
˙’
nh chung.
D
-
iˆe
˙’
m xuˆa
´
t ph´at nˇa
`
m trˆen ca

.
.
c cˇa
´
t bo
.
˙’
i mˆo
.
t trong c´ac thuˆa
.
t to´an
trong Phˆa
`
n 3.3. H`ınh 1.4(a) minh ho
.
a d¯oa
.
n thˇa
˙’
ng d¯u
.
o
.
.
c cˇa
´
t bo
.
˙’

.
c. Pixel (x
min
, mx
min
+ t + 0.5) trˆen ca
.
nh x = x
min
ch´ınh l`a pixel
d¯u
.
o
.
.
c v˜e ta
.
i ho`anh d¯ˆo
.
x
min
cu
˙’
a d¯oa
.
n thˇa
˙’
ng tru
.
´o

i ta
.
o biˆe
´
n quyˆe
´
t d¯i
.
nh ta
.
i d¯iˆe
˙’
m gi˜u
.
a d¯oa
.
n
RD trong cˆo
.
t kˆe
´
bˆen. Cˆa
`
n ch´u ´y rˇa
`
ng, c´ach l`am n`ay ta
.
o ra d˜ay ch´ınh x´ac c´ac pixel, trong
2
Khi mx

18
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

min
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
(a)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.y = y
min
− 1


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

② ② ② ②② ② ② ②
✐ ✐ ✐ ✐ ② ② ② ② ✐ ✐ ✐
② ② ② ②

y = y
min
−
1
2
•
I
D C
(b)
H`ınh 1.4: D
-
iˆe
˙’
m xuˆa
´
t ph´at nˇa
`
m trˆen biˆen h`ınh ch˜u
.
nhˆa
.
t. (a) Giao v´o
.
i ca
.
nh d¯´u

˙’
ng d¯u
.
o
.
.
c cˇa
´
t t`u
.
(x
min
, mx
min
+ t + 0.5) d¯ˆe
´
n (x
B
, y
B
) theo thuˆa
.
t to´an d¯iˆe
˙’
m gi˜u
.
a s˜e cho d˜ay d¯iˆe
˙’
m v˜e khˆong
ch´ınh x´ac do d¯u

˙’
ng AB giao v´o
.
i d¯u
.
`o
.
ng thˇa
˙’
ng nˇa
`
m ngang nhu
.
trong H`ınh 1.4(b). Khi hˆe
.
sˆo
´
g´oc m rˆa
´
t nho
˙’
, c´o nhiˆe
`
u pixel nˇa
`
m trˆen d`ong qu´et y = y
min
tu
.
o

v`a sau d¯´o
l`am tr`on ho`anh d¯ˆo
.
x ta d¯u
.
o
.
.
c pixel C khˆong pha
˙’
i pixel bˆen tr´ai nhˆa
´
t D trˆen d`ong n`ay. Du
.
.
a
trˆen h`ınh v˜e, ta thˆa
´
y rˇa
`
ng pixel bˆen tr´ai nhˆa
´
t D l`a pixel trˆen bˆen pha
˙’
i giao d¯iˆe
˙’
m I cu
˙’
a d¯oa
.

i c`ung, thuˆa
.
t to´an d¯iˆe
˙’
m gi˜u
.
a c˜ung thu
.
.
c hiˆe
.
n tˆo
´
t trong tru
.
`o
.
ng ho
.
.
p c´ac d¯iˆe
˙’
m d¯ˆa
`
u
cuˆo
´
i c´o to
.
a d¯ˆo

n thˇa
˙’
ng theo hˆe
.
sˆo
´
g´oc. X´et hai d¯oa
.
n thˇa
˙’
ng trong
H`ınh 1.5. D
-
oa
.
n thˇa
˙’
ng l
2
c´o hˆe
.
sˆo
´
g´oc 1 v`a do d¯´o c´o d¯ˆo
.
d`ai bˇa
`
ng
√
2 lˆa

i pixel l`a I th`ı cu
.
`o
.
ng
d¯ˆo
.
trˆen mˆo
.
t d¯o
.
n vi
.
d¯ˆo
.
d`ai cu
˙’
a d¯oa
.
n thˇa
˙’
ng l
1
l`a I, trong khi cu
˙’
a l
2
l`a I/
√
2; su

´
ng n-bit trˆen pixel ch´ung ta c´o thˆe
˙’
ca
˙’
i thiˆe
.
n d¯u
.
o
.
.
c t`ınh tra
.
ng n`ay
bˇa
`
ng c´ach d¯ˇa
.
t cu
.
`o
.
ng d¯ˆo
.
l`a mˆo
.
t h`am cu
˙’
a hˆe

rˆo
.
ng he
.
p v`a t´ınh to´an th´ıch
ho
.
.
p c´ac cu
.
`o
.
ng d¯ˆo
.
v´o
.
i nhiˆe
`
u pixel trˆen mˆo
˜
i cˆo
.
t nˇa
`
m trong hoˇa
.
c gˆa
`
n h`ınh ch˜u
.

x´ac d¯i
.
nh bo
.
˙’
i c´ac d¯oa
.
n thˇa
˙’
ng. V´o
.
i c´ach v˜e c´ac d¯oa
.
n thˇa
˙’
ng,
ch´ung ta cˆa
`
n v˜e c´ac nguyˆen so
.
d¯u
.
o
.
.
c xˆay du
.
.
ng t`u
.

ng kˆe
`
nhau. C´ac h`ınh ch˜u
.
nhˆa
.
t v`a d¯a gi´ac l`a nh˜u
.
ng nguyˆen so
.
v`ung v`a c´o thˆe
˙’
v˜e c´ac ca
.
nh liˆen tiˆe
´
p nhu
.
ng d¯iˆe
`
u n`ay
dˆa
˜
n d¯ˆe
´
n mˆo
.
t sˆo
´
pixel nˇa

nh chung cu
˙’
a d¯u
.
`o
.
ng gˆa
´
p
kh´uc mˆo
.
t lˆa
`
n do viˆe
.
c v˜e hai lˆa
`
n c´o thˆe
˙’
l`am thay d¯ˆo
˙’
i m`au hoˇa
.
c d¯ˇa
.
t m`au nˆe
`
n khi viˆe
´
t trong

`
n nhau hoˇa
.
c cˇa
´
t nhau.
20

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
②
②
②
②
②
②
②
②
②
②
D
-
u

`o
.
ng thˇa
˙’
ng theo hˆe
.
sˆo
´
g´oc.
1.1.4 C´ac thuˆo
.
c t´ınh cu
˙’
a d¯oa
.
n thˇa
˙’
ng
Thuˆo
.
c t´ınh mˆa
˜
u tˆo d¯oa
.
n thˇa
˙’
ng c´o thˆe
˙’
a
˙’

˙’
m v˜e hay khˆong, chı
˙’
d¯ˇa
.
t khi d¯iˆe
`
u kiˆe
.
n
d¯´ung (gi´a tri
.
1). Ch´ung ta lu
.
u tr˜u
.
mˆa
˜
u v˜e nhu
.
mˆo
.
t chuˆo
˜
i d¯ˆo
.
d`ai Tile Size (thu
.
`o
.

.
n
putpixel() trong thuˆa
.
t to´an v˜e d¯oa
.
n thˇa
˙’
ng d¯ˆe
˙’
xu
.
˙’
l´y tru
.
`o
.
ng ho
.
.
p n`ay; chˇa
˙’
ng ha
.
n,
if bitstring[i % 16] putpixel(x, y, value);
trong d¯´o chı
˙’
sˆo
´

.
ng mˆo
.
t lˆa
`
n lˇa
.
p v`a khˆong
tu
.
o
.
ng ´u
.
ng d¯ˆo
.
d`ai d¯o
.
n vi
.
do
.
c theo d¯oa
.
n thˇa
˙’
ng nˆen d¯ˆo
.
d`ai cu
˙’

-
iˆe
`
u n`ay l`a khˆong chˆa
´
p nhˆa
.
n d¯u
.
o
.
.
c v´o
.
i nh˜u
.
ng ´u
.
ng du
.
ng mang t´ınh ch´ınh x´ac
cao, chˇa
˙’
ng ha
.
n trong thiˆe
´
t kˆe
´
cˆong nghiˆe

ng cu
˙’
a d¯oa
.
n thˇa
˙’
ng d¯u
.
o
.
.
c
xem nhu
.
mˆo
.
t d˜ay c´ac h`ınh ch˜u
.
nhˆa
.
t d¯ˇa
.
c v`a trong suˆo
´
t d¯u
.
o
.
.
c d¯ˇa

.
nhˆa
.
t mˆo
.
t; v´o
.
i c´ac d¯oa
.
n thˇa
˙’
ng ngang hoˇa
.
c d¯´u
.
ng, ta c´o thˆe
˙’
d`ung
lˆe
.
nh sao ch´ep c´ac h`ınh ch˜u
.
nhˆa
.
t.
Kiˆe
˙’
u d¯oa
.
n thˇa

˙’
ng thu
.
`o
.
ng d¯u
.
o
.
.
c su
.
˙’
du
.
ng d¯ˆe
˙’
x´ac d¯i
.
nh c´ac h`ınh ch˜u
.
nhˆa
.
t tu
.
o
.
ng ´u
.
ng c´ac n´et v˜e v`a mˆo

X´et d¯u
.
`o
.
ng tr`on f(x, y) := x
2
+ y
2
−R
2
= 0. C´o mˆo
.
t v`ai c´ach d¯o
.
n gia
˙’
n v˜e d¯u
.
`o
.
ng tr`on nhu
.
ng
khˆong hiˆe
.
u qua
˙’
.
D
-

´
i x´u
.
ng) ta c´o thˆe
˙’
tˇang x t`u
.
0 d¯ˆe
´
n R (mˆo
˜
i bu
.
´o
.
c mˆo
.
t d¯o
.
n
vi
.
) v`a gia
˙’
i y =
√
R
2
− x
2

i R v`ı tiˆe
´
p tuyˆe
´
n v´o
.
i d¯u
.
`o
.
ng tr`on
ta
.
i nh˜u
.
ng d¯iˆe
˙’
m tu
.
o
.
ng ´u
.
ng tiˆe
´
n d¯ˆe
´
n d¯u
.
`o

˙’
m (R cos θ, R sin θ)
v´o
.
i θ thay d¯ˆo
˙’
i t`u
.
0 d¯ˆe
´
n 90
0
.
1.2.1 D
-
ˆo
´
i x´u
.
ng t´am d¯iˆe
˙’
m
Ch´ung ta c´o thˆe
˙’
gia
˙’
m b´o
.
t qu´a tr`ınh t´ınh to´an du
.

.
c hiˆe
.
n ph´ep ti
.
nh
tiˆe
´
n t`u
.
tˆam vˆe
`
gˆo
´
c to
.
a d¯ˆo
.
. Nˆe
´
u d¯iˆe
˙’
m (x, y) nˇa
`
m trˆen d¯u
.
`o
.
ng tr`on th`ı ba
˙’

.
ng tr`on tˆam
ta
.
i gˆo
´
c, t´am d¯iˆe
˙’
m d¯ˆo
´
i x´u
.
ng c´o thˆe
˙’
d¯u
.
o
.
.
c hiˆe
˙’
n thi
.
bˇa
`
ng thu
˙’
tu
.
c sau (m`a dˆe

˙’
tu
.
c CirclePoints() khi x = y do c´o bˆo
´
n pixel d¯u
.
o
.
.
c
v˜e hai lˆa
`
n; ta chı
˙’
cˆa
`
n thay d¯ˆo
˙’
i d¯oa
.
n m˜a xu
.
˙’
l´y d¯iˆe
`
u kiˆe
.
n biˆen.
1.2.2 Thuˆa

˙’
trˆen. Ch´ung ta nˆeu thuˆa
.
t to´an tu
.
o
.
ng tu
.
.
, su
.
˙’
du
.
ng tiˆeu chuˆa
˙’
n d¯iˆe
˙’
m gi˜u
.
a, m`a trong tru
.
`o
.
ng
ho
.
.
p b´an k´ınh v`a c´ac to

.
`o
.
ng tr`on:
(C
1
) := {(x, y) ∈ R
2
| x
2
+ y
2
= R
2
, 0 ≤ y < x}
v`a su
.
˙’
du
.
ng thu
˙’
tu
.
c CirclePoints() d¯ˆe
˙’
hiˆe
˙’
n thi
.

≤ 0 v´o
.
i mo
.
i (x, y) ∈ (C
1
). Do d¯´o, khi y tˇang mˆo
.
t d¯o
.
n vi
.
th`ı x gia
˙’
m khˆong qu´a
mˆo
.
t d¯o
.
n vi
.
. V`ı vˆa
.
y, gia
˙’
su
.
˙’
o
.

´
tiˆe
´
p cˆa
`
n cho
.
n mˆo
.
t trong hai pixel T := (x
i
, y
i
+ 1) hoˇa
.
c D := (x
i
− 1, y
i
+ 1)
(xem H`ınh 1.6). Tu
.
o
.
ng tu
.
.
thuˆa
.
t to´an d¯iˆe

ta
.
i d¯iˆe
˙’
m gi ˜u
.
a M = (x
i
−
1
2
, y
i
+ 1) cu
˙’
a
hai d¯iˆe
˙’
m v˜e n`ay. Dˆe
˜
d`ang ch´u
.
ng minh rˇa
`
ng, nˆe
´
u d¯iˆe
˙’
m M nˇa
`

.
ng d¯u
.
o
.
ng
f(M) > 0) th`ı D gˆa
`
n d¯u
.
`o
.
ng tr`on ho
.
n. Tru
.
`o
.
ng ho
.
.
p M nˇa
`
m trˆen d¯u
.
`o
.
ng tr`on (t´u
.
c f(M) = 0)

+ (y
i
+ 1)
2
− R
2
.
Nˆe
´
u d
i
< 0 th`ı cho
.
n T v`a d¯iˆe
˙’
m gi˜u
.
a kˆe
´
tiˆe
´
p c´o tung d¯ˆo
.
tˇang mˆo
.
t d¯o
.
n vi
.
. Nˆen

.
´o
.
c tˇang ∆
T
:= 2y
i
+ 3.
23
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

D
✇
C
✇
T
✇
H`ınh 1.6: Lu
.
´o
.
i pixel trong thuˆa
.
t to´an d¯iˆe
˙’
m gi˜u
.
a v˜e d¯u
.
`o
.
ng tr`on.
Nˆe
´
u d
i
≥ 0 th`ı cho
.
n D v`a d¯iˆe
˙’
m gi˜u

2
, y
i
+ 2) = (x
i
−
3
2
)
2
+ (y
i
+ 2)
2
− R
2
.
Suy ra d
i+1
= d
i
+ 2y
i
− 2x
i
+ 5. Do d¯´o bu
.
´o
.
c tˇang ∆

D
l`a c´ac hˇa
`
ng sˆo
´
;
tuy nhiˆen, trong tru
.
`o
.
ng ho
.
.
p d¯u
.
`o
.
ng cong bˆa
.
c hai, ∆
T
v`a ∆
D
l`a c´ac h`am phu
.
thuˆo
.
c v`ao c´ac
to
.

p du
.
.
a v`ao c´ac gi´a tri
.
x v`a y cu
˙’
a pixel d¯u
.
o
.
.
c cho
.
n trong bu
.
´o
.
c lˇa
.
p tru
.
´o
.
c. T´ınh to´an nhu
.
vˆa
.
y khˆong hiˆe
.

`
u c´o to
.
a d¯ˆo
.
(R, 0) nˆen d¯iˆe
˙’
m gi˜u
.
a c´o to
.
a d¯ˆo
.
(R −
1
2
, 1) v`a do d¯´o d
0
= f(R −
1
2
, 1) =
(R −
1
2
)
2
+ 1 −R
2
=

-
ˇa
.
t x
0
= R , y
0
= 0, d
0
= 5/4 − R.
2. Gia
˙’
su
.
˙’
o
.
˙’
bu
.
´o
.
c th´u
.
i ta c´o d¯iˆe
˙’
m v˜e tˆo
´
t nhˆa
´

4. [Cˆa
.
p nhˆa
.
t] Nˆe
´
u x
i
= y
i
, thuˆa
.
t to´an d`u
.
ng; ngu
.
o
.
.
c la
.
i, d¯ˇa
.
t
x
i+1
=

x
i

+ 3 nˆe
´
u d
i
< 0,
d
i
+ 2(y
i
− x
i
) + 5 nˆe
´
u ngu
.
o
.
.
c la
.
i.
5. Thay i bˇa
`
ng (i + 1) v`a lˇa
.
p la
.
i Bu
.
´o

´
t d¯i
.
nh l`a sˆo
´
thu
.
.
c. Mˇa
.
c d`u c´o thˆe
˙’
dˆe
˜
d`ang ca
˙’
i tiˆe
´
n d¯ˆe
˙’
xu
.
˙’
l´y cho d¯u
.
`o
.
ng
tr`on c´o tˆam hoˇa
.

= d
i
−
1
4
v`a thay d
i
bo
.
˙’
i h
i
+
1
4
trong thuˆa
.
t to´an. Khi d¯´o ta
kho
.
˙’
i ta
.
o h
0
= 1 −R v`a so s´anh d
i
< 0 tu
.
o

`
n so s´anh h
i
< 0. Nhu
.
vˆa
.
y, ch´ung
ta c´o thuˆa
.
t to´an v˜e d¯u
.
`o
.
ng tr`on chı
˙’
su
.
˙’
du
.
ng c´ac sˆo
´
nguyˆen nhu
.
du
.
´o
.
i d¯ˆay; d¯ˆe