Đồ họa Raster - Các thuật toán vẽ đường thẳng (Phần 2)

ĐỒ HỌA RASTER
CÁC THUẬT TOÁN
VẼ ĐƯỜNG TRÒN
Giảng viên : Bùi Tiến Lên
Phân loại đường tròn
Đường tròn tâm O Đường tròn tâm bất kỳ
Trang 2
O O
Ứng dụng phép tịnh tiến
Nếu (x, y) thuộc đường tròn tâm O
Thì (x + xc, y + yc) thuộc đường tròn tâm (xc, yc)
(xc, yc)
Trang 3
O
(x, y)
(x+xc, y+yc)
Phương trình đường tròn
Trang 4
O
22
222
xry
ryx
−=
=+r
Tính đối xứng của đường tròn
Đường tròn có 4 trục đối xứng 
-Trục Ox
-Trục Oy
-Trục phân giác thứ nhất
-Trục phân giác thứ hai
x
y
Trang 5
O
Ứng dụng tính đối xứng
Nếu (x, y) thuộc đường tròn
Thì (-x, y), (x, -y), (-x, -y), (y, x), (-y, x), (y, -x) và (-y, -x) 
thuộc đường tròn
12 chọ
n
Trang 6
O
3
4
5 6
7
8
Vẽ cung một phần tám thứ nhất
Input
r bán kính
Output 
{(x1, y1), (x2, y2) … (xn, yn)} “thuộc” cung một phần 
tám thứ nhất
Trang 7
O
A
B
Khảo sát cung một phần tám thứ nhất
Mục tiêu khảo sát sự biến thiên của hoành độ và tung độ
22
22
xr
x
- y' 
]
2
r
 [0, x vớixr y Hàm
−
=
∈−=
Trang 8
2322
2
)xr(
r
- y" 
−
=
Khảo sát cung 1/8 thứ nhất
Bảng biến thiên
r
r
y
2
r
 0x
Đường cong 
giảm chậm
Trang 9
−−
−
"y
1
0
'y
2
Thuật toán trực tiếp
]
r
[ < x Lặp
lại còn điểm những định Xác 2 bước
r = y
0 = x
đầu điểm định Xác 1 bước
1
1
Trang 10
Round(y) = y
xr = y
1 + x = x
2
1+i
2
1i
2
i1+i
i
+−
Thuật toán MidPoint
Dự đoán điểm sáng thứ i+1
i A
Trang 11
B
Thuật toán MidPoint
- Khái niệm bên trong / bên 
ngoài đường tròn
- Hàm kiểm tra một điểm 
bên trong / bên ngoài 
đường tròn
F(x, y) = x2 + y2 – r2 bên trong
bên ngoài
Trang 12
- Cách kiểm tra
P(x, y) F(x, y)
bên trong < 0
nằm trên = 0
bên ngoài > 0
Thuật toán MidPoint
Xây dựng biến fi
Trung điểm M của AB 
M(xi + 1, yi – 1/2)
Biến fi
fi = F(M)
f = F(x + 1, y – 1/2)
i A
M
yi-1/2
yi
Trang 13
i i i
B
xi xi+1
yi-1
Thuật toán MidPoint
Công thức tính fi
4
1
r1yyx2xf 2i
2
ii
2
ii +−+−++=
Công thức tính fi nguyên
2
i
2
ii
2
ii r1yyx2xf −+−++=
Trang 14
Khi fi không nguyên !
Có hai cách giải quyết để fi thành nguyên
Cách 1
fi < 0 ⇔ kfi < 0
fi ≥ 0⇔ kfi ≥ 0
Với k > 0
Trang 15
Cách 2
fi < 0 ⇔ [fi] < 0
fi ≥ 0⇔ [fi] ≥ 0
Thuật toán MidPoint
Thuật toán
Bước 1 Xác định điểm đầu tiên
x1 = 0
y1 = r
Bước 2 Xác định những điểm tiếp theo
Lặp xi < yi
Trang 16
fi = …
fi < 0
xi+1 = xi + 1
yi+1 = yi
fi ≥ 0
xi+1 = xi + 1
yi+1 = yi – 1 
Thuật toán MidPoint
Cách tính fi cải tiến
f1 = 1 – r 
fi < 0
fi+1 = fi + 2xi + 3
fi ≥ 0 
f = f + 2x – 2y + 5
Trang 17
i+1 i i i