7-扫描线填充算法

1多边形区域扫描线填充算法内容大纲1扫描线填充思路2扫描线填充算法3图案填充简介求交：计算扫描线与多边形的交点。P0P1P2P3P4P5排序：将交点按x值排序。填充：每一对交点之间画线填充。1扫描线填充思路

123最简单解决办法：判断交点个数时将扫描线坐标加0.5特殊交点处理？

1个点

计算交点坐标时，再将扫描线还原1扫描线填充思路

1234

123

123确定多边形顶点坐标绘制多边形计算扫描线的范围ymin与ymaxfor（h=ymin;h<=ymax;h++)

//扫描线循环{k=0;

//交点数赋初值0for(i=0;i<n-1;i++)

//多边形边循环求交点交点排序每对交点填充}2扫描线填充算法x[0],y[0]x[3],y[3]x[4],y[4]x[5],y[5]x[6],y[6]x[1],y[1]x[2],y[2]n=72扫描线填充算法确定多边形顶点坐标绘制多边形计算扫描线的范围ymin与ymaxfor（h=ymin;h<=ymax;h++)

{k=0;

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

求交点交点排序每对交点填充}2扫描线填充算法确定多边形顶点坐标绘制多边形计算扫描线的范围ymin与ymaxfor（h=ymin;h<=ymax;h++)

{k=0;

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

求交点交点排序每对交点填充}pDC->MoveTo(x[0],y[0]);for(i=1;i<n;i++

)

pDC->LineTo(x[i],y[i]);2扫描线填充算法确定多边形顶点坐标绘制多边形计算扫描线的范围ymin与ymaxfor（h=ymin;h<=ymax;h++)

{k=0;

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

求交点交点排序每对交点填充}ymin=y[0];ymax=y[0];for(i=1;i<n-1;i++

)

{if(y[i]<ymin)ymin=y[i];

if(y[i]>ymax)ymax=y[i];}2扫描线填充算法确定多边形顶点坐标绘制多边形计算扫描线的范围ymin与ymaxfor（h=ymin;h<=ymax;h++)

{k=0;

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

求交点交点排序每对交点填充}

if(y[i+1]!=y[i]) //不包括水平线if((h+0.5-y[i])*(h+0.5-y[i+1])<0)

xd[k++]=

x[i]+(x[i+1]-x[i])*(h-y[i])/(y[i+1]-y[i]);

(xi,yi)(xi+1,yi+1)y=h(h-yi)(

h-yi+1)<02扫描线填充算法确定多边形顶点坐标绘制多边形计算扫描线的范围ymin与ymaxfor（h=ymin;h<=ymax;h++)

{k=0;

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

求交点

交点排序每对交点填充}for(i=0;i<k-1;i++)

for(j=0;j<k-1-i;j++)

if(xd[j]>xd[j+1])t=xd[i],xd[j]=xd[j+1],xd[j+1]=t;2扫描线填充算法确定多边形顶点坐标绘制多边形计算扫描线的范围ymin与ymaxfor（h=ymin;h<=ymax;h++)

{k=0;

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

求交点交点排序

每对交点填充}for(i=0;i<k;i=i+2)for(j=xd[i];j<=xd[i+1];j++)pDC->SetPixel(j,h,RGB(255,0,0));voidFull_XMX(CDC*pDC,intx[],inty[],intn,COLORREFInColor){inti,k,j,h,m,xd[10],t,ymin=y[0],ymax=y[0];for(i=1;i<n;i++){if(y[i]<ymin)ymin=y[i];if(y[i]>ymax)ymax=y[i];}//计算扫描线的范围for(h=ymin;h<=ymax;h++) //扫描线循环

{k=0;for(i=0;i<n;i++) //多边形边循环

if(y[i+1]!=y[i]) //不包括水平线

if((h+0.5-y[i])*(h+0.5-y[i+1])<0)xd[k++]=x[i]+(x[i+1]-x[i])*(h-y[i])/(y[i+1]-y[i]);//求交点

for(i=0;i<k-1;i++)for(j=0;j<k-1-i;j++) if(xd[j]>xd[j+1])t=xd[j],xd[j]=xd[j+1],xd[j+1]=t;//交点排序for(i=0;i<k;i=i+2)for(j=xd[i];j<=xd[i+1];j++)pDC->SetPixel(j,h,InColor);//每对交点填充}}2扫描线填充算法3图案填充简介①水平线填充确定多边形顶点坐标绘制多边形确定扫描线的范围ymin与ymaxfor（h=ymin;h<=ymax;h++)

{k=0;

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

求交点交点排序每对交点填充}h=h+d3图案填充简介②垂直线填充确定多边形顶点坐标绘制多边形计算垂直线的范围xmin与

xmax

for（h=xmin;h<=xmax;h=h+d)

{k=0;

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

求交点y值

交点按y排序垂直线填充}

3图案填充简介③斜平行线的填充3图案填充简介③斜平行线的填充多边形顶点坐标赋值x[i]，y[i](i=0，1,…,n)绘制多边形将多边形顶点坐标旋转

角，变换为a[i]，b[i](i=0,1,…,n)根据a[i]，b[i](i=0，1,…,n)计算扫描线的范围ymin与ymaxfor(h=ymin;h<=ymax;h=h+d) {k=0; for(i=0;i<=n-1;i++)

根据a[i]，b[i]求交点

交点按a排序

将交点坐标旋转-

角

每对交点间填充}3图案填充简介④图案填充3图案填充简介④图案填充3图案填充简介BYTEb[8]={252,102,99,99,99,102,252,0};for(inty=0;y<8;y++)for(intx=0;x<8;x++)if((b[y]&(BYTE)pow(2,7-x))==(BYTE)pow(2,7-x))pDC->SetPixel(x,y,color);确定多边形顶点坐标绘制多边形计算扫描线的范围ymin与ymaxfor（h=ymin;h<=ymax;h++)

{k=0;

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

求交点交点排序

每对交点填充}点阵字符显示④图案填充3图案填充简介确定多边形顶点坐标绘制多边形计算扫描线的范围ymin与ymaxfor（h=ymin;h<=ymax;h++)

{k=0;

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

求交点交点排序for(i=0;i<k;i=i+2)for(j=xd[i];j<=xd[i+1];j=j++){if((m[h%8]&(BYTE)pow(2,7-j%8))==(BYTE)pow(2,7-j%N)&&//获取字符点阵信息pDC->GetPixel(j,h)!=EdgeColor)