ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 16/22
• Chọn điểm bắt đầu để vẽ là điểm (0,R).
• Dựa vào hình vẽ, nếu
(
)
ii
y
x
,
là điểm nguyên đã tìm
được ở bước thứ i, thì điểm
(
)
11
,
++ ii
y
x
ở bước thứ
(i+1) là sự lựa chọn giữa S và P.
• Như vậy :
{ }



−∈
+=
+
+
1,

S
P
MidPoint
y
i
y
i
-1
x
i
x
i
+1
Q(x
i
+1, y)
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 17/22
• Xét
( )






−+==
2
1
,1MidPoint

y
y
.
• Mặt khác :






−+−






−+=−
+++
2
1
,1
2
1
,1
111 iiiiii
yxFyxFpp
( ) ( )



+++
2
2
2
2
2
1
2
11
2
1
1
2
1
1 RyxRyxpp
iiiiii
(
)
(
)
iiiiiii
yyyyxpp −−−++=−⇔
+++ 1
22
11
32
• Vậy :
♦
3
2

y
x
p
p
, nếu
0
≥
i
p
do ta chọn
1
1
−=
+ ii
y
y
.
•
0
p

ứng với điểm ban đầu
(
)
(
)
R
y
x
,

Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 18/22
Lưu đồ thuật toán MidPoint vẽ đường tròn
Begin
p=5/4-R;
x=0;
y=R;
Put8Pixel(x, y, c);
x<y
Yes
No
p<0
Yes
p=p+2*x+3;
No
p=p+2(x-y)+5;
y=y-1
x=x+1;
Put8Pixel(x,y,c);
End
ĐỒ HỌA MÁY TÍNH
Dương Anh Đức, Lê Đình Duy Các thuật toán vẽ đường 19/22
Cài đặt minh họa thuật toán MidPoint vẽ đường tròn
void CircleMidPoint (int R)
{
int x, y;
x = 0;
y = R;
Put8Pixel(x, y);
p = 1 - R; // 5/4-R
while (x < y)

D
e
e
l
l
t
t
a
a
1
1
D
D
e
e
l
l
t
t
a
a
2
2
0
0
0
0
1
1
5

5
-
-
1
1
1
1
-
-
1
1
4
4
+
+
2
2
*
*
(
(
0
0
)
)
+
+
3
3
5

*
(
(
1
1
)
)
+
+
3
3
7
7
-
-
2
2
1
1
3
3
3
3
1
1
5
5
1
1
-

4
1
1
4
4
-
-
1
1
8
8
1
1
+
+
2
2
*
*
(
(
3
3
-
-
1
1
5
5
)

1
8
8
+
+
2
2
*
*
(
(
4
4
)
)
+
+
3
3
1
1
3
3
-
-
1
1
3
3
6

1
5
5
-
-
1
1
1
1
7
7
7
7
1
1
3
3
-
-
5
5
6
6
+
+
2
2
(
(
6

1
2
2
-
-
5
5
+
+
2
2
(
(
7
7
)
)
+
+
3
3
1
1
9
9
-
-
5
5
9

+
5
5
2
2
1
1
-
-
1
1
1
1
0
0
1
1
0
0
1
1
1
1
6
6
7
7
+
+
2

1
1
1
0
0
9
9
6
6
+
+
2
2
(
(
1
1
0
0
-
-
1
1
1
1
)
)
+
+
5