1
Area Filling
Area Filling
Tô màu đồ thị
Tô màu đồ thị
2
Vùng tô
Vùng tô
Vùng được xác định bởi điểm ảnh –
Vùng được xác định bởi điểm ảnh –
pixel-defined region
pixel-defined region
Vùng xác định bởi đa giác –
Vùng xác định bởi đa giác –
polygonal region
polygonal region
pixel-defined
pixel-defined
region
region
polygonal
polygonal
region
region
3
Pixel-defined region
Pixel-defined region
Vùng được định nghĩa bởi màu của pixel, chia làm 3 phần:
Vùng được định nghĩa bởi màu của pixel, chia làm 3 phần:
Vùng trong –
Vùng trong –

Interior defined
Tất cả các pixel trong vùng có cùng một màu, gọi là
Tất cả các pixel trong vùng có cùng một màu, gọi là
inside-color
inside-color
Các pixel trên biên không có màu này
Các pixel trên biên không có màu này
Có thể có lỗ trong vùng
Có thể có lỗ trong vùng
Boundary defined
Boundary defined
Các pixel thuộc biên có cùng màu –
Các pixel thuộc biên có cùng màu –
boundary-color
boundary-color
Các pixel trong vùng không có màu này
Các pixel trong vùng không có màu này
Nếu một số pixel trong vùng có màu boundary-color thì vùng sẽ chứa lỗ
Nếu một số pixel trong vùng có màu boundary-color thì vùng sẽ chứa lỗ
Interior-defined
Boundary-defined
inside
color
6
Polygonal Region
Polygonal Region
Định nghĩa bằng đa giác: xác định các định các đỉnh p
Định nghĩa bằng đa giác: xác định các định các đỉnh p
i
i

Recursive Flood-Fill Algorithm
(
(
interior-defined, 4-connected region
interior-defined, 4-connected region
)
)
Đổi màu của tất cả các interior-pixel thành màu tô –
Đổi màu của tất cả các interior-pixel thành màu tô –
fill color
fill color
.
.
Quá trình tô màu bắt đầu từ một điểm (
Quá trình tô màu bắt đầu từ một điểm (
seed pixel
seed pixel
) thuộc phía trong
) thuộc phía trong
vùng tô và lan truyền khắp vùng tô => Flood-Fill
vùng tô và lan truyền khắp vùng tô => Flood-Fill
Interior-defined
seed pixel
inside
color
Recursive Flood-Fill
fill
color
8
Recursive Flood-Fill Algorithm (cont)

(3,2) (1,2)(2,2)
(2,1)
(3,3)
9
Recursive Flood-Fill Program
Recursive Flood-Fill Program
void FloodFill(int x, int y, int inside_color, int
void FloodFill(int x, int y, int inside_color, int
fill_color)
fill_color)
{
{if (getpixel(x,y) == inside_color)
if (getpixel(x,y) == inside_color)
{
{
putpixel(x,y,fill_color);
putpixel(x,y,fill_color);
FloodFill(x-1,y, inside_color, fill_color);
FloodFill(x-1,y, inside_color, fill_color);
FloodFill(x+1,y, inside_color, fill_color);
FloodFill(x+1,y, inside_color, fill_color);
FloodFill(x,y+1, inside_color, fill_color);
FloodFill(x,y+1, inside_color, fill_color);
FloodFill(x,y-1, inside_color, fill_color);
FloodFill(x,y-1, inside_color, fill_color);
}
}

b
dc
e
12
Thuật toán cải tiến – Dùng stack
Thuật toán cải tiến – Dùng stack
Cho vào
Cho vào
stack
stack
run chứa
run chứa
seed pixel
seed pixel
while
while
stack
stack
not empty {
not empty {
begin
begin
= pop();
= pop();
Tô run bắt đầu từ
Tô run bắt đầu từ
begin
begin
Cho vào
Cho vào