二维区域扫描线填充算法的实现
这个程序从一放暑假就开始做，直做到今天，花了1个星期的时间，真是不应该啊，唉，谁让咱编程技术不太好呢，得，闲话少说。
关于区域填充，我们常用的算法有扫描线填充算法以及种子填充算法，我现在只完成了前一种，后一种等过两天实现之，扫描算法的理解不难，可是实现起来有许多细节问题还是有点烦琐，下面这个是非常粗糙的一个版本，只能说是实现了所需，代码一点也不好，到处充斥着各种命名模糊的变量，又不很多注释，谁要是想看，那肯定费很大劲，不过整体结构是正确的。我本来想把整个算法详细地一步一步列出来，可是要讲解算法的话，还要画很多图，还要贴上来，就此做罢，如果谁也在做这个程序，就在下面留下评论即可，我一定在最短时间内给你回复。下面是我的代码，直接CTRL+V到VC6中就可以看到效果了：
(通过这个程序我还发现，当代码一上500行，变量就开始混淆了，尤其是用来控制循环的那些小变量，还有就是在这个程序中我初步使用了VC6的调试功能 ，确实非常方便，但还有些功能不清楚，唉，慢慢来吧)
下面是一个简单的填充效果：
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include<windows.h>
#include<math.h>
#define FILLING 1
#define RESET 2
typedef struct
{
int xStart,yStart;
int xEnd,yEnd;
}LINE,*PLINE;
LINE lines[100];
LINE line;
static int j=0;
POINT draw_refresh[1000];
static int l=0;
LRESULT CALLBACK WndProc(HWND,UINT,WPARAM,LPARAM);
int WINAPI WinMain(HINSTANCE hInstance,HINSTANCE prevInstance,PSTR szCmdLine,int iCmdShow)
{
static TCHAR szAppName[]="2D Region Filling";
HWND hwnd;
MSG msg;
WNDCLASS wndclass;
for(int i=0;i<100;i++)
{
lines[i].xStart=0;
lines[i].yStart=0;
lines[i].xEnd=0;
lines[i].yEnd=0;
}
wndclass.style=CS_HREDRAW | CS_VREDRAW |CS_DBLCLKS;
wndclass.lpfnWndProc=WndProc;
wndclass.cbClsExtra=0;
wndclass.cbWndExtra=0;
wndclass.hInstance=hInstance;
wndclass.hIcon=LoadIcon(NULL,IDI_APPLICATION);
wndclass.hCursor=LoadCursor(NULL,IDC_CROSS);
wndclass.hbrBackground=(HBRUSH)GetStockObject(WHITE_BRUSH);
wndclass.lpszMenuName=NULL;
wndclass.lpszClassName=szAppName;
if(!RegisterClass(&wndclass))
{
MessageBox(NULL,"Regist window class failed!","Error",MB_OK);
}
hwnd=CreateWindow(szAppName,"2D Region Filling",WS_OVERLAPPED | WS_CAPTION | WS_MINIMIZEBOX | WS_SYSMENU,CW_USEDEFAULT,CW_USEDEFAULT,CW_USEDEFAULT,CW_USEDEFAULT,NULL,NULL,hInstance,NULL);
ShowWindow(hwnd,iCmdShow);
UpdateWindow(hwnd);
while(GetMessage(&msg,NULL,0,0))
{
TranslateMessage(&msg);
DispatchMessage(&msg);
}
return msg.wParam;
}
LRESULT CALLBACK WndProc(HWND hwnd,UINT message,WPARAM wParam,LPARAM lParam)
{
HWND hButtonFilling;
HWND hButtonReset;
int cxChar=0;
int cyChar=0;
static PLINE head=lines;
int i=0;
HDC hdc;
PAINTSTRUCT ps;
RECT clientrect;
POINT need_draw={0,0};
POINT draw[100];
int b=0;
static int filled=0;
for(int e=0;e<100;e++)
{
draw[e].x=0;
draw[e].y=0;
}
int k=0;
int smallest_y=0;
int lardgest_y=0;
int m=0;
int n=0;
int h=0;
int x=0;
int x1=0;
int x2=0;
int y1=0;
int y2=0;
int a=0;
int c=0;
int flag=0;
switch(message)
{
case WM_CREATE:
cxChar=LOWORD(GetDialogBaseUnits());
cyChar=HIWORD(GetDialogBaseUnits());
hButtonFilling=CreateWindow(TEXT("BUTTON"),"Filling", WS_CHILD | WS_VISIBLE | BS_DEFPUSHBUTTON,40*cxChar,28*cyChar,20*cxChar,7*cyChar/4,hwnd,(HMENU)FILLING, ((LPCREATESTRUCT)lParam)->hInstance,NULL);
hButtonReset =CreateWindow(TEXT("BUTTON"),"Reset", WS_CHILD | WS_VISIBLE | BS_DEFPUSHBUTTON,70*cxChar,28*cyChar,20*cxChar,7*cyChar/4,hwnd,(HMENU)RESET, ((LPCREATESTRUCT)lParam)->hInstance,NULL);
return 0;
case WM_LBUTTONDOWN:
// SetCapture(hwnd);
line.xStart=(int)LOWORD(lParam);
line.yStart=(int)HIWORD(lParam);
for(i=0;j>=1 && i<=j-1;i++)
{
if((line.xStart>lines[i].xStart-30) && (line.xStart<lines[i].xStart+30) && (line.yStart>lines[i].yStart-30) && (line.yStart<lines[i].yStart+30))
{
line.xStart=lines[i].xStart;
line.yStart=lines[i].yStart;
}
else if((line.xStart>lines[i].xEnd-30) && (line.xStart<lines[i].xEnd+30) &&(line.yStart>lines[i].yEnd-30) && (line.yStart<lines[i].yEnd+30))
{
line.xStart=lines[i].xEnd;
line.yStart=lines[i].yEnd;
}
}
return 0;
case WM_MOUSEMOVE:
if(wParam & MK_LBUTTON)
{
hdc=GetDC(hwnd);
SelectObject(hdc,GetStockObject(WHITE_PEN));
if(line.xEnd!=0 && line.yEnd!=0)
{
MoveToEx(hdc,line.xStart,line.yStart,NULL);
LineTo(hdc,line.xEnd,line.yEnd);
}
line.xEnd=(int)LOWORD(lParam);
line.yEnd=(int)HIWORD(lParam);
SelectObject(hdc,GetStockObject(BLACK_PEN));
MoveToEx(hdc,line.xStart,line.yStart,NULL);
LineTo(hdc,line.xEnd,line.yEnd);
InvalidateRect(hwnd,NULL,FALSE);
ReleaseDC(hwnd,hdc);
}
return 0;
case WM_LBUTTONUP:
line.xEnd=LOWORD(lParam);
line.yEnd=HIWORD(lParam);
for(i=0;j>=1 && i<=j-1;i++)
{
if((line.xEnd>lines[i].xStart-30) && (line.xEnd<lines[i].xStart+30) && (line.yEnd>lines[i].yStart-30) && (line.yEnd<lines[i].yStart+30))
{
hdc=GetDC(hwnd);
SelectObject(hdc,GetStockObject(WHITE_PEN));//clear the last black line if find a adjacent vetex
MoveToEx(hdc,line.xStart,line.yStart,NULL);
LineTo(hdc,line.xEnd,line.yEnd);
line.xEnd=lines[i].xStart;
line.yEnd=lines[i].yStart;
SelectObject(hdc,GetStockObject(BLACK_PEN));
MoveToEx(hdc,line.xStart,line.yStart,NULL);
LineTo(hdc,line.xEnd,line.yEnd);
ReleaseDC(hwnd,hdc);
}
else if((line.xEnd>lines[i].xEnd-30) && (line.xEnd<lines[i].xEnd+30) &&(line.yEnd>lines[i].yEnd-30) && (line.yEnd<lines[i].yEnd+30))
{
hdc=GetDC(hwnd);
SelectObject(hdc,GetStockObject(WHITE_PEN));//clear the last black line if find a adjacent vetex
MoveToEx(hdc,line.xStart,line.yStart,NULL);
LineTo(hdc,line.xEnd,line.yEnd);
line.xEnd=lines[i].xEnd;
line.yEnd=lines[i].yEnd;
SelectObject(hdc,GetStockObject(BLACK_PEN));
MoveToEx(hdc,line.xStart,line.yStart,NULL);
LineTo(hdc,line.xEnd,line.yEnd);
ReleaseDC(hwnd,hdc);
}
}
lines[j].xStart=line.xStart;
lines[j].yStart=line.yStart;
lines[j].xEnd=line.xEnd;
lines[j].yEnd=line.yEnd;
j++;
line.xStart=0;
line.yStart=0;
line.xEnd=0;
line.yEnd=0;
// ReleaseCapture();
return 0;
case WM_COMMAND:
switch(LOWORD(wParam))
{
case FILLING:
smallest_y=lines[0].yStart;
lardgest_y=lines[0].yStart;
for(h=0;h<=100;h++)
{
draw[h].x=0;
draw[h].y=0;
}
filled=1;
for(h=0;h<j;h++)//find the smallest y coordinate of the edges
{
if(lines[h].yStart<smallest_y)
{
smallest_y=lines[h].yStart;
}
if(lines[h].yEnd<smallest_y)
{
smallest_y=lines[h].yEnd;
}
}
for(h=0;h<j;h++)//find the lardgest y coordinate of the edges
{
if(lines[h].yStart>lardgest_y)
{
lardgest_y=lines[h].yStart;
}
if(lines[h].yEnd>lardgest_y)
{
lardgest_y=lines[h].yEnd;
}
}
for(k=smallest_y;k<=lardgest_y;k++)
{//check every scan line to filling the region
for(m=0;m<j;m++)
{
a=lines[m].yStart>lines[m].yEnd ? lines[m].yStart:lines[m].yEnd ;
c=lines[m].yStart<lines[m].yEnd ? lines[m].yStart:lines[m].yEnd ;
if(k>a)
{
continue;
}
else if(k<c)
{
continue;
}
else if(lines[m].yStart==lines[m].yEnd && k==lines[m].yStart)
{
continue;
}
else
{
x=0;
if(lines[m].yStart==k)
{
for(n=0;n<j;n++)
{
if((n!=m) && (lines[m].yStart==lines[n].yStart))
{
if((lines[m].yEnd>lines[m].yStart && lines[n].yEnd>lines[m].yStart) || (lines[m].yEnd<lines[m].yStart && lines[n].yEnd<lines[m].yStart))
{
x=lines[m].xStart;
draw[b].x=x;
draw[b].y=k;
b++;
draw[b].x=x;
draw[b].y=k;
b++;
}
else
{
// MessageBox(hwnd,"error2","error2",MB_OK);
x=lines[m].xStart;
flag=0;
for(h=0;h<b;h++)
{
if(x==draw[h].x && k==draw[h].y)
{
flag=1;
break;
}
}
if(flag!=1)
{
draw[b].x=x;
draw[b].y=k;
b++;
}
}
}
else if((n!=m) && (lines[m].yStart==lines[n].yEnd))
{
if((lines[m].yEnd>lines[m].yStart && lines[n].yStart>lines[m].yStart) || (lines[m].yEnd<lines[m].yStart && lines[n].yStart<lines[m].yStart))
{
// MessageBox(hwnd,"error3","error3",MB_OK);
x=lines[m].xStart;
draw[b].x=x;
draw[b].y=k;
b++;
draw[b].x=x;
draw[b].y=k;
b++;
}
else
{
// MessageBox(hwnd,"error4","error4",MB_OK);
x=lines[m].xStart;
flag=0;
for(h=0;h<b;h++)
{
if(x==draw[h].x && k==draw[h].y)
{
flag=1;
break;
}
}
if(flag!=1)
{
draw[b].x=x;
draw[b].y=k;
b++;
}
}
}
}
}
else if(lines[m].yEnd==k)
{
for(n=0;n<j;n++)
{
if(m!=n && k==lines[n].yStart )
{
if((lines[m].yStart>lines[m].yEnd && lines[n].yEnd>lines[m].yEnd) || (lines[m].yStart<lines[m].yEnd && lines[n].yEnd<lines[m].yEnd))
{
// MessageBox(hwnd,"error","error",MB_OK);
x=lines[m].xEnd;
draw[b].x=x;
draw[b].y=k;
b++;
draw[b].x=x;
draw[b].y=k;
b++;
}
else
{
x=lines[m].xEnd;
flag=0;
for(h=0;h<b;h++)
{
if(x==draw[h].x && k==draw[h].y)
{
flag=1;
break;
}
}
if(flag!=1)
{
draw[b].x=x;
draw[b].y=k;
b++;
}
}
}
else if(m!=n && k==lines[n].yEnd)
{
if((lines[m].yStart>lines[m].yEnd && lines[n].yStart>lines[m].yEnd) || (lines[m].yStart<lines[m].yEnd && lines[n].yStart<lines[m].yEnd))
{
x=lines[m].xEnd;
draw[b].x=x;
draw[b].y=k;
b++;
draw[b].x=x;
draw[b].y=k;
b++;
}
else
{
x=lines[m].xEnd;
flag=0;
for(h=0;h<b;h++)
{
if(x==draw[h].x && k==draw[h].y)
{
flag=1;
break;
}
}
if(flag!=1)
{
draw[b].x=x;
draw[b].y=k;
b++;
}
}
}
}
}
else
{
if(lines[m].yStart>lines[m].yEnd)
{
x1=lines[m].xEnd;
y1=lines[m].yEnd;
x2=lines[m].xStart;
y2=lines[m].yStart;
}
else if(lines[m].yStart<lines[m].yEnd)
{
x1=lines[m].xStart;
y1=lines[m].yStart;
x2=lines[m].xEnd;
y2=lines[m].yEnd;
}
x=x2+(x1-x2)*(y2-k)/(y2-y1);
draw[b].x=x;
draw[b].y=k;
b++;
}
}
}
//check complete,then draw them
//sorting first!
for(h=0;h<b;h++)
{
for(m=h+1;m<b;m++)
{
if(draw[h].x>draw[m].x)
{
x=draw[h].x;
draw[h].x=draw[m].x;
draw[m].x=x;
x=draw[h].y;
draw[h].y=draw[m].y;
draw[m].y=x;
}
}
}
hdc=GetDC(hwnd); //real filling
for(h=0;h<b;h+=2)
{
MoveToEx(hdc,draw[h].x,draw[h].y,NULL);
LineTo(hdc,draw[h+1].x,draw[h+1].y);
}
ReleaseDC(hwnd,hdc);
for(h=0;h<b;h++)
{
draw_refresh[l].x=draw[h].x;
draw_refresh[l].y=draw[h].y;
l++;
}
b=0;
}
break;
case RESET:
filled=0;
j=0;
head=lines;
for(int i=0;i<100;i++)
{
lines[i].xStart=0;
lines[i].yStart=0;
lines[i].xEnd=0;
lines[i].yEnd=0;
}
for(h=0;h<l;h++)
{
draw_refresh[h].x=0;
draw_refresh[h].y=0;
}
hdc=GetDC(hwnd);
GetClientRect(hwnd,&clientrect);
Rectangle(hdc,clientrect.left-5,clientrect.top-5,clientrect.right+5,clientrect.bottom+5);
ReleaseDC(hwnd,hdc);
InvalidateRect(hwnd,NULL,FALSE);
break;
}
return 0;
case WM_PAINT:
hdc=BeginPaint(hwnd,&ps);
for(head=lines;head->xStart!=0 && head->yStart!=0 && head->xEnd!=0 && head->yEnd!=0;head++)
{
MoveToEx(hdc,head->xStart,head->yStart,NULL);
LineTo(hdc,head->xEnd,head->yEnd);
}
head=lines;
if(filled==1)
{
// MessageBox(hwnd,"filled","filled",MB_OK);
for(h=0;h<l;h+=2)
{
MoveToEx(hdc,draw_refresh[h].x,draw_refresh[h].y,NULL);
LineTo(hdc,draw_refresh[h+1].x,draw_refresh[h+1].y);
}
}
EndPaint(hwnd,&ps);
return 0;
case WM_DESTROY:
PostQuitMessage(0);
return 0;
}
return DefWindowProc(hwnd,message,wParam,lParam);
}
///////////////////////////////END/////////////////////////////////////////////////
如果你真要运行下的话，请务必在粘进VC的时候把行隔开，因为我暂时还不知道怎么能以好的格式把代码贴进CSDN的BLOG中。我自己做的测试中尚未发现错误，如果你发现了，麻烦好心和你告诉我，谢谢你