Đ H A RASTERỒ Ọ
Đ H A RASTERỒ Ọ
CÁC THU T TOÁN TÔ MÀUẬ
CÁC THU T TOÁN TÔ MÀUẬ
Gi ng viên : Bùi Ti n Lênả ế
Trang
Trang 2
2
Bài toán tô màu
Bài toán tô màu
Tô màu là thao tác tìm các đi m sáng “ển m bên trongằ” m t vùng ộ
khép kín.
Input :
Vùng S
Output :
{(x1, y1), (x2, y2) … (xn, yn)}
Trang
Trang 3
3
Các h
Các hư
ưng ti p c nớ ế ậ
ng ti p c nớ ế ậ
Có hai phương pháp
- Tô màu theo lân c nậ
- Tô màu theo dòng quét
Tô màu theo lân c nậ
Tô màu theo lân c nậ
Trang
Trang 5
5
Lân c n là gì ?ậ
Lân c n là gì ?ậ
Có hai lo i lân c n : lân c n 4 và lân c n 8.ạ ậ ậ ậ
Lân c n 4ậ
N4(x, y) = {(x-1, y), (x, y+1), (x+1, y), (x, y-1)}
Lân c n 8ậ
N8(x, y) = {(x-1, y), (x-1, y+1), (x, y+1), (x+1, y+1), (x+1, y), (x+1, y-
1), (x, y-1), (x-1, y-1)}
(x,y) ph iảtrái
dưiớ
trên
x
y(x,y)
x
y
trái