Thuật toán tô màu theo dòng quét (Scanline) được mô tả tóm tắt như sau:

Đặt x₀ = Min(x_i), iÎ[1,n].

Bước 1: Kẻ Dy//0y đi qua x₀ (Hình 2.10).

Bước 2: Xác định các giao điểm M_i­(x,y) của Dy với các cạnh C_i.

Nếu có cạnh C_i = P_iP_i+1 song song và trùng với Dy thì xem như Dy cắt C_i tại 2 điểm P_i và P_i+1.

Hình 2.10. Minh họa thuật toán Scanline.

Bước 3: Sắp xếp lại các điểm M_i theo thứ tự tăng dần đối với y_i (điểm đầu tiên có thứ tự là 1).

Bước 4: Những điểm nằm trên Dy ở giữa giao điểm lẻ và giao điểm chẵn liên tiếp là những điểm nằm trong đa giác và những điểm này sẽ được tô.

Bước 5: Tăng x₀ lên một Pixel. Nếu x₀ £Max(x_i) thì quay lại bước 1.

Sau đây là chương trình cài đặt thuật toán Scanline:

#include

#include

#include

struct ToaDo2D

{

int x,y;

};

void Nhap(int &n,ToaDo2D a[])

{

cout<<"\nNhap so dinh cho da giac:"; cin>>n;

for(int i=1;i<=n;i++)

{

cout<<"\n a["<>a[i].x;

cout<<"\n a["<>a[i].y;

}

}

void VeDaGiac(int n,ToaDo2D a[])

{

int i,j;

for (i=1;i<=n;i++)

{

if (i==n) j=1; else j=i+1;

line(a[i].x,a[i].y,a[j].x,a[j].y);

}

}

int min(int a,int b)

{

return (a<>

}

int max(int a,int b)

{

return (a>b)?a:b;

}

void Scanline(int n,ToaDo2D a[])

{

//Tim minx, maxx

int x,minx,maxx;

minx=a[1].x;

maxx=a[1].x;

for (int i=2;i<=n;i++)

{

if (a[i].x

if (a[i].x>maxx) maxx=a[i].x;

}

//Quet tu minx --> maxx

for (x=minx+1;x<=maxx-1;x++)

{

int m=0,z[50]; //so giao diem

//Duyet qua cac canh

for (int i=1;i<=n;i++)

{

int t=i+1; if (i==n) t=1;

int s=i-1; if (i==1) s=n;

if (x==a[i].x)

{

if((x>min(a[s].x,a[t].x))&&(x<>

{

m++; z[m]=a[i].y;

}

else

{

m++; z[m]=a[i].y;

m++; z[m]=a[i].y;

}

}

else

if((x>min(a[i].x,a[t].x))&&(x<>

{

++m;

float r;

r = (a[t].y-a[i].y)/(a[t].x-a[i].x);

z[m]=(int)(r*(x-a[i].x))+a[i].y;

}

}

//Sap xep cac giao diem theo thu tu tang dan

for (i=1;i<>

for (int k=i+1;k<=m;k++)

if (z[i]>z[k])

{

int tg=z[i];

z[i]=z[k];

z[k]=tg;

}

//To mau tu giao diem le dem giao diem chan

for (k=1;k<=m-1;k++)

if (k%2!=0) line(x,z[k],x,z[k+1]);

}

}

void main()

{

int n,gd=0,gm;

ToaDo2D a[100];

Nhap(n,a);

initgraph(&gd,&gm,"d:\\tc\\bgi");

VeDaGiac(n,a);

Scanline(n,a);

getch();

closegraph();

}