Tại bài 8 chúng ta đã cùng đi tìm hiểu thuật toán tô màu Scanline, bài viết này chúng ta tiếp tục đi khám phá thêm 1 thuật toán tô màu nữa. Đó là thuật toán tô màu loang.

1. Giới thiệu

Thuật toán tô màu loang (hay còn gọi là tô màu theo đường biên, tô lân cận). Khác với thuật toán tô màu dựa theo dòng quét, đường biên của vùng tô màu ở thuật toán tô loang được xác định bởi tập các đỉnh của 1 đa giác, đường biên trong thuật toán được mô tả bằng một giá trị duy nhất, đó là màu của tất cả các điểm thuộc về đường biên (nói ngắn gọn là chúng ta sẽ tô đường biên một màu riêng).

Bắt đầu từ 1 điểm nằm bên trong vùng tô, ta sẽ kiểm tra các điểm lân cận của nó đã được tô màu hay có phải điểm biên hay không. Nếu không phải là điểm đã tô và không phải là điểm biên ta sẽ tô màu nó. Lặp lại cho tới khi nào không còn tô được điểm nào nữa thì dừng.

2. Giải thuật

*Nhận xét:

Thuật toán này có thể sẽ không hoạt động chính xác khi có 1 số điểm nằm trong vùng tô có màu là màu cần tô của vùng tô. Để khắc phục điều này, trước khi tô màu, cần phải đảm bảo rằng toàn bộ các điểm thuộc về vùng tô có màu khác màu tô.

Có hai quan điểm về cách tô này, đó là dùng 4 điểm lân cận hay 8 điểm lân cận đối với điểm đang xét được tô bằng màu trắng ( tại bài viết này, chúng ta sẽ đi xét 4 điểm lân cận nha).

Có hai hướng thực thi thuật toán: đó là sử dụng đệ quy và không đệ quy.

a) Thuật toán đệ quy:

-Bước 1: Kẻ vùng biên cần tô.

-Bước 2: Xác định một điểm (x,y) bên trong vùng cần tô.

-Bước 3: Tô điểm (x,y) sau đó tô loang những điểm lân cận.

Hàm đệ quy:

(coi như các bạn đã hiểu cách thực hiện của hàm đệ quy, mình không cần phải demo lại thứ tự thực thi của hàm đệ quy nữa nha. Còn nếu bạn nào chưa rõ thì comment nha)

void ToLoang(int x,int y,int Color) 
{  
     If((x,y)∈S)&&((x,y)chưa tô))  
     {   
         putpixel(x,y,Color);
         ToLoang(x+1,y,Color);
         ToLoang(x-1,y,Color);
         ToLoang(x,y+1,Color);
         ToLoang(x,y-1,Color);  
      }
}

=>Nhận xét về hàm đệ quy:

Ưu điểm:

+Có thể tô vùng có hình dạng bất kỳ.

+Cài đặt thuật toán dễ dàng.

Khuyết điểm:

+Không thể tô các vùng có kích thước lớn do tràn bộ nhớ khi sử dụng đệ quy.

+Việc gọi đệ quy, thuật toán cho 4 điểm lân cận của điểm hiện hành không quan tâm tới một trong bốn điểm đó đã được xét ở bước trước hay chưa (tức là sẽ có những điểm bị xét đi xét lại nhiều lần). Điều này khiến tốc độ chậm, không hiệu quả.

Chính vì đệ quy phức tạp như vậy nên hầu như ở các bài toán có tính đệ quy, chúng ta đều phải tìm cách khử đệ quy. Chúng ta sẽ tiến hành loang dần và lần lượt tô từng đoạn giao theo dòng quét ngang, thay vì tô theo 4 điểm lân cận.

b) Thuật toán khử đệ quy:

Áp dụng hàng đợi Queue, BFS

-Bước 1: Cất điểm hạt giống đầu tiên vào kho.

-Bước 2: Lặp nếu kho không rỗng

+Lấy điểm hạt giống.

+Tô điểm hạt giống, sau đó tô loang sang 2 bên.

+Bổ sung những điểm hạt giống mới vào kho từ dòng trên và dòng dưới.

Tiêu chuẩn để làm điểm hạt giống: điểm này chưa được tô màu và không phải điểm biên.

3. Code minh họa

3.1 Code đệ quy:

#include <conio.h>
#include <winbgim.h>
#include <iostream>
using namespace std;
struct ToaDo
{
	int x,y;
};
int MauNen;
void NhapDaGiac(int &n,int &x,int &y,ToaDo a[])
{
	cout<<"Nhap so dinh cua da giac n= "; cin>>n;
	for (int i=1;i<=n;i++)
	{
	cout<<"Toa do dinh P["<<i<<"].x= "; cin>>a[i].x;
	cout<<"Toa do dinh P["<<i<<"].y= "; cin>>a[i].y;
	}
	cout<<"Nhap diem (x,y) thuoc da giac:\n";
	cout<<"nhap x="; cin>>x;
	cout<<"nhap y="; cin>>y;
}
void VeDaGiac(int n,ToaDo a[],int color)
{
	setcolor(color);
	for (int i=1;i<=n;i++)
	{
	int j;
	if (i==n) j=1; else j=i+1;
	line(a[i].x,a[i].y,a[j].x,a[j].y);
	}
}
void ToLoang(int x,int y,int color)
{
	if (getpixel(x,y)==MauNen  && x<getmaxx() && y<getmaxy())
	{
	putpixel(x,y,color);
	ToLoang(x-1,y,color);
	ToLoang(x,y-1,color);
	ToLoang(x+1,y,color);
	ToLoang(x,y+1,color);
	}	
	delay(1);
}
int main()
{
	int x,y,n,Gd,Gm=VGAMAX;
	ToaDo a[10];
	NhapDaGiac(n,x,y,a);
	Gd=DETECT;
	initgraph(&Gd,&Gm,"");
	VeDaGiac(n,a,15);
	MauNen=getpixel(x,y);
	ToLoang(x,y,10);
	getch();
	closegraph();
}

3.2 Code khử đệ quy:

#include <conio.h>
#include <winbgim.h>
#include <iostream>
#include <queue>
using namespace std;
struct ToaDo
{
	int x,y;
};
int MauNen;
void NhapDaGiac(int &n,int &x,int &y,ToaDo a[])
{
	cout<<"Nhap so dinh cua da giac n= "; cin>>n;
	for (int i=1;i<=n;i++)
	{
	cout<<"Toa do dinh P["<<i<<"].x= "; cin>>a[i].x;
	cout<<"Toa do dinh P["<<i<<"].y= "; cin>>a[i].y;
	}
	cout<<"Nhap diem (x,y) thuoc da giac:\n";
	cout<<"nhap x="; cin>>x;
	cout<<"nhap y="; cin>>y;
}
void VeDaGiac(int n,ToaDo a[],int color)
{
	setcolor(color);
	for (int i=1;i<=n;i++)
	{
	int j;
	if (i==n) j=1; else j=i+1;
	line(a[i].x,a[i].y,a[j].x,a[j].y);
	}
}
void ToLoang(int x,int y,int color)
{
	//	Khai bao queue chua pixel chua duoc to mau
	queue<ToaDo> Q;
	ToaDo m, Tg;
	if (getpixel(x,y)==MauNen  && x<getmaxx() && y<getmaxy())
	{
    	m.x = x;
    	m.y = y;
    	putpixel(m.x, m.y, color);
    	Q.push(m);	//	Them 1 diem vao queue, queue size tang 1
		while(Q.empty() == false)	//Xet 4 diem xung quanh voi moi diem luu trong queue (neu queue con phan tu)
		{
			Q.pop();//	Xoa 1 diem phia dau queue, queue size giam 1
			//Xet cac diem lan can cua 1 diem
			if(getpixel(m.x+1, m.y) == MauNen)
			{
				putpixel(m.x+1, m.y, color );
				Tg.x = m.x+1;
				Tg.y = m.y; 
				Q.push(Tg);// Them 1 diem vao cuoi queue
			}  
			if(getpixel(m.x-1, m.y) == MauNen)
			{
				putpixel(m.x-1, m.y, color);
				Tg.x = m.x-1;
				Tg.y = m.y;
				Q.push(Tg);
			}
			if(getpixel(m.x, m.y+1) == MauNen)
			{
				putpixel(m.x, m.y+1, color);
				Tg.x = m.x;
				Tg.y = m.y+1;
				Q.push(Tg);
			}
			if(getpixel(m.x, m.y-1) == MauNen)
			{
				putpixel(m.x, m.y-1, color);
				Tg.x = m.x;
				Tg.y = m.y-1;
				Q.push(Tg);
			}
			m = Q.front();// Dua ve gia tri dau tien cho hang doi
		delay(1);
		}
	}
}
int main()
{
	int x,y,n,Gd,Gm=VGAMAX;
	ToaDo a[10];
	NhapDaGiac(n,x,y,a);
	Gd=DETECT;
	initgraph(&Gd,&Gm,"");
	VeDaGiac(n,a,15);
	MauNen=getpixel(x,y);
	ToLoang(x,y,10);
	getch();
	closegraph();
}

4. Hình ảnh minh họa

Tóm lại, có một điểm trừ cho thuật toán này (điểm mình không thích) là việc phải xác định 1 điểm bắt đầu phải nằm trong vùng tô. Nếu chọn ngu khiến điểm đó nằm ngoài vùng tô thì một là không tô được , hai là tô bên ngoài vùng muốn tô mãi mãi không dừng. Còn chọn chuẩn điểm nằm trong vùng tô thì sẽ tô ok. Và nếu chọn phải điểm nằm trên biên thì chỉ tô biên thôi. Dở hơi nhỉ (quan điểm cá nhân thui nha).

Cảm ơn các bạn đã đọc bài viết . Mong bài viết giúp ích cho việc học tập của các bạn !