Chương
Chương
2
2
C
C
á
á
c thu
c thu
ậ
ậ
t to
t to
á
á
n đ
n đ
ồ
ồ
ho
ho
ạ
ạ
c
c
ơ s
ơ s
ở
ở
Giảng viên: Ths.Vũ Minh Yến

ẳ
ng
ng
2.2. C
2.2. C
á
á
c thu
c thu
ậ
ậ
t to
t to
á
á
n v
n v
ẽ
ẽ
đư
đư
ờ
ờ
ng tròn
ng tròn
2.3. C
2.3. C
á
á
c thu

á
c thu
c thu
ậ
ậ
t to
t to
á
á
n tô m
n tô m
à
à
u
u
2.1. C
2.1. C
á
á
c thu
c thu
ậ
ậ
t to
t to
á
á
n v
n v
ẽ

Thu
ậ
ậ
t to
t to
á
á
n l
n l
à
à
m tròn s
m tròn s
ố
ố

Phương trình đường thẳng AB (x
A
≠ x
B
):

Đặt

Khi đó phương trình đường thẳng AB:
AA
AB
AB
yxx
xx

à
à
m tròn s
m tròn s
ố
ố
 Chia thành 4 trường hợp:

TH1: AB song song với Oy

TH2: AB song song với Ox

TH3: |m|≤1

TH4: |m|>1
m=1
m=
-
1
(1)
y
O
x
(4)
(3)
(3)
(2)
(4)
Thu
Thu

Bước 2: Vẽ điểm (x; y);

Bước 3: y=y+1;

Bước 4: Nếu y<=y
B
thì: Bước 2;

Bước 5: Kết thúc.
A
y
O
x
B
x
A
=x
B
y
A
y
B
Thu
Thu
ậ
ậ
t to
t to
á
á

Bước 3: x=x+1;

Bước 4: Nếu x<=xB thì: Bước 2;

Bước 5: Kết thúc.
A
y
O
B
x
A
y
A
=y
B
x
B
Thu
Thu
ậ
ậ
t to
t to
á
á
n l
n l
à
à
m tròn s

 Bước 5: Nếu x≤ x
B
thì: Bước 3;
 Bước 6: Kết thúc;
m=1
m=
-
1
y
O
x
A
B
x
A
x
B
Thu
Thu
ậ
ậ
t to
t to
á
á
n l
n l
à
à
m tròn s

);
 Bước 5: Nếu y≤ y
B
thì: Bước 2;
 Bước 6: Kết thúc;
m=1
m=
-
1
y
O
x
A
B
y
A
y
B
Thu
Thu
ậ
ậ
t to
t to
á
á
n Breseham
n Breseham

TH1 x

t to
á
á
n Breseham
n Breseham


TH3
TH3:
0 < m
0 < m
≤
≤≤
≤
≤
≤≤
≤
1
1
y
x
O(0,0)
d
1
d
2
y
i
y
y

á
n h
n h
ọ
ọ
c xây d
c xây d
ự
ự
ng thu
ng thu
ậ
ậ
t to
t to
á
á
n:
n:

Giả sử ta có điểm thứ i: (x
i
; y
i
)

Xác định điểm thứ i+1: (x
i+1
; y
i+1

= y
i
+1 nếu d1>d2
α
αα
α ≤
≤≤
≤ 45
0
Thu
Thu
ậ
ậ
t to
t to
á
á
n Breseham
n Breseham

Xét d1= y(x
i+1
) - y
i
⇔ d1=m(x
i+1
-x
A
)+y
A

)+y
A
A

Xét d2= y
i
+1 - y(x
i+1
)
= y
i
+1- m(x
i+1
-x
A
)-y
A
=
=
-
-
mx
mx
i
i
+y
+y
i
i
-

A
-1)
= 2dy.x
i
-2dx.y
i
+ 2dy(1-x
A
)+2dx.y
A
-dx
Thu
Thu
ậ
ậ
t to
t to
á
á
n Breseham
n Breseham

Tương tự ta có
P
i+1
= 2dy.x
i+1
-2dx.y
i+1
+ 2dy(1-x

≥
d2 ⇔ y
i+1
=y
i
+1
⇒
∆
∆∆
∆
∆
∆∆
∆
P=2dy
P=2dy
-
-
2dx=const1
2dx=const1

Giả sử P
i
<0
⇔ d1-d2<0 ⇔ d1<d2 ⇔ y
i+1
=y
i
⇒
∆
∆∆

A
+2dy-2dy.x
A
+2dx.y
A
-dx
=
2dy
2dy
-
-
dx
dx=const
Thu
Thu
ậ
ậ
t to
t to
á
á
n Bresenham
n Bresenham


Thu
Thu
ậ
ậ
t to

Bước 4: x=x+1;

Bước 5: Nếu p>0 thì: y=y+1; p=p+const1;
còn lại: p=p+const2;

Bước 6: Nếu x ≤ x
B
thì: Bước 3;

Bước 7: Kết thúc
Thu
Thu
ậ
ậ
t to
t to
á
á
n Breseham
n Breseham


TH4:
TH4:
-
-
1
1
≤
≤≤



TH6: m <
TH6: m <
-
-
1
1
 Đổi vai trò x, y cho nhau
ta có TH4.
(5) (6)
y
O
x
2.2. C
2.2. C
á
á
c thu
c thu
ậ
ậ
t to
t to
á
á
n v
n v
ẽ
ẽ




=
=
α
α
sin
cos
ry
rx
[
]
π
α
2;0
∈
O x
y
x
y
M
α
r
OA



+=
+=

t to
t to
á
á
n v
n v
ẽ
ẽ
đ
đ
ư
ư
ờ
ờ
ng tròn
ng tròn
 Tính chất đối xứng:
Xét điểm M
1
(x,y)∈(O;r) , khi đó:
 M2(y,x)
 M3(y,-x)
 M4(x,-y)
 M5(-x,-y)
 M6(-y,-x)
 M7(-y,x)
 M8(-x,y)
M
1
M

ẽ
ẽ
đ
đ
ư
ư
ờ
ờ
ng tròn
ng tròn


B
B
à
à
i to
i to
á
á
n:
n:

Input: Cho tâm O(0,0), bán kính r

Output: Vẽ đường tròn tâm O, bán kính r.


Gi
Gi

n l
n l
à
à
m tròn s
m tròn s
ố
ố


Theo phương tr
Theo phương tr
ì
ì
nh đ
nh đ
ạ
ạ
i s
i s
ố
ố
:
:
 Cung AB:
 Xét trên cung AB: nếu ∆x=1 thì
|∆y|≤1 nên lấy cơ sở theo x


Thu

(-x;y)

Bước 3: x=x+1; y= round( )

Bước 4: Nếu x ≤ y thì: Bước 2;

Bước 5: Kết thúc.
B
O
y
x
A
[
]
2/;0,
22
rxxry ∈−=
22
xr −
Thu
Thu
ậ
ậ
t to
t to
á
á
n l
n l
à

x
y
M
α
r
Thu
Thu
ậ
ậ
t to
t to
á
á
n x
n x
ấ
ấ
p x
p x
ỉ
ỉ

Ta có phương trình (O;r):

Xét đạo hàm theo đối số α:



=
=

á
n x
n x
ấ
ấ
p x
p x
ỉ
ỉ

Xét đạo hàm tại điểm thứ i:
⇔

Xét đạo hàm tại điểm thứ i+1:
⇔


Thu
Thu
ậ
ậ
t to
t to
á
á
n:
n:

B
ướ

ế
t thúc;
1
1
1
1
0
'
1
lim
+
+
+
+
→
+
≈
−
≈
−
−
=
−
i
ii
ii
ii
step
i
x

+
+
+
→
+
α
αα
α
1
1
1
0
'
lim
α
stepyxx
iii
.
1
−
≈
+