Bài giảng Đồ họa máy tính - Bài: Các thuật toán mành hóa - Mai Thị Châu

2/17/17 Ma Thị Châu - Bộ môn KHMT1
Đồ họa máy tính
Các thuật toán mành hóa
2/17/17 Ma Thị Châu - Bộ môn KHMT2
Các thuật toán tô phủ
Bài toán tô phủ loang (Flood fill problem): 
Với hai màu khác nhau c và c’, một tập các điểm A có cùng màu c được 
bao quanh bởi các điểm có màu khác với c và c’, tìm thuật toán thay màu 
của tất cả các điểm thuộc A và chỉ các điểm này thành màu c’
2/17/17 Ma Thị Châu - Bộ môn KHMT3
Thuật toán tô phủ cơ bản
procedure BFA (integer x, y)
begin
if Inside (x,y) then
Begin
Set (x,y);
BFA (x,y - 1); BFA (x,y + 1);
BFA (x - 1,y); BFA (x + 1,y);
end
end;
2/17/17 Ma Thị Châu - Bộ môn KHMT4
Thuật toán tô phủ cơ bản
procedure BFA (integer x, y)
begin
if Inside (x,y) then
Begin
Set (x,y);
BFA (x,y - 1); BFA (x,y + 1);
BFA (x - 1,y); BFA (x + 1,y);
end
end;
2/17/17 Ma Thị Châu - Bộ môn KHMT5
Thuật toán tô phủ của Smith
Bắt đầu: (7,3). 
FillRight: đoạn (7,3) đến (8,3) được tô. 
FillLeft: (6,3) được tô. 
ScanHi: điểm (6,4) và (8,4) vào ngăn xếp. 
ScanLo:điểm (6,2) vào ngăn xếp. 
Lấy(6,2) ra, và coi đây là điểm bắt đầu. 
Lệnh FillRight và FillLeft: tô phủ đoạn từ 
(2,2) đến (8,2). 
ScanHi và ScanLo:cho (2,3) và (6,3) vào 
ngăn xếp. 
Lấy (6,3) ra. 
(6,3) đã được tô lấy ra (2,3) và cứ tiếp tục 
như thế cho đến khi ngăn xếp rỗng
6,2
6,4
8,4
2 3
6,3
2/17/17 Ma Thị Châu - Bộ môn KHMT6
Thuật toán tô phủ Smith
Các đoạn chứa (6,4), (8,4) và (6,2) được gọi là vùng bóng tối
2/17/17 Ma Thị Châu - Bộ môn KHMT7
Thuật toán tô phủ của Fishkin
Vùng bóng tối – shadow