Question

求助：谁有C++的多边形扫描线填充算法的源代码！

寻求最正确的源代码，参数值阁下可任意输入，不过得标明...最好把每步的具体解释都写出来。
调试成功的答案，给分哦！

Answer 1

typedef struct tEdge
{ int yUpper;
float xIntersect,dxPerScan;
struct tEdge *next;
}Edge;
void insertEdge(Edge *list Edge *edge)//将结点插入边表
{
Edge *p,*q=list;
p=q->next;
while (p!=NULL)
{ if (edge->xIntersect<p->xIntersect) p=NULL;
else { q=p; p=p->next;}
}
edge->next=q->next;
q->next=edge;
}

int yNext(int k,int cnt, dcPt *pts)//求奇异点
{
int j;
if ((k+1)>(cnt-1)) j=0;
else j=k+1;
while (pts[k].y==pts[j].y)
if((j+1)>(cnt-1)) j=0;
else j++;
return (pts[j].y);
}

void makeEdgeRec(dcPt lower,dcPt upper,int yComp, Edge *edge, Edge *edges[]) //生成边表结点，并插入到边表中
{
edge->dxPerScan=(float)(upper.x-lower.x)/(upper.y-lower.y);
edge->xIntersect=lower.x;
if (upper.y<yComp)
edge->yUpper=upper.y-1;
else
edge->yUpper=upper.y;
insertEdge(edges[lower.y],edge);
}

void buildEdgeList(int cnt,dcPt *pts, Edge *edges[])//创建边表的主体函数
{
Edge *edge;
dcPt v1,v2;
int i,yPrev=pts[cnt-2].y;
v1.x=pts[cnt-1].x; v1.y=pts[cnt-1].y;
for (i=0;i<cnt;i++)
{ v2=pts[i];
if (v1.y!=v2.y)
{ edge=(Edge *)malloc(sizeof(Edge));
if (v1.y<v2.y)
makeEdgeRec(v1,v2,yNext(i,cnt,pts),edge,edges);
else makeEdgeRec(v2,v1,yPrev,edge,edges);
}
yPrev=v1.y;
v1=v2;
}
}

void buildActiveList(int scan,Edge * active,Edge *edges[])//建立活动边表的主题函数
{ Edge *p,*q;
p=edges[scan]->next;
while (p)
{ q=p->next;
insertEdge(active,p);
p=q;
}
}

void fillScan(int scan,Edge *active)//填充一对交点
{
Edge *p1,*p2;
int i
p1=active->next;
while(p1)
{
p2=p1->next;
for (i=p1->xIntersect;i<p2->xIntersect;i++)
setPixel((int)i,scan);
p1=p2->next;
}
}

void delectAfter(Edge *q)//删除链表中结点
{
Edge *p=q->next;
q->next=p->next;
free(p);
}

void updateActiveList(int scan,Edge *active)//填充完后，更新活动边表
{
Edge *q=active,*p=active->next;
while (p)
if (scan>=p->yUpper)
{
p=p->next;
deleteAfter(q);
}
else
{ p->xIntersect=p->xIntersect+p->dxPerScan;
q=p;
p=p->next;
}
}

void resortActiveList(Edge *active)//对活动边表结点重新排序
{
Edge *q,*p=active->next;
active->next=NULL;
while(p)
{ q=p->next;
insertEdge(active,p);
p=q;
}
}

void scanFill(int cnt,dcPt *pts)//多边形填充主体程序
{
Edge *edge[WINDOW_HEIGHT],*active;
int i,scan;
for (i=0;i<WINDOW_HEIGHT;i++)
{
edges[i]=(Edge *)malloc(sizeof(Edge));
edges[i]->next=NULL;
}
buildEdgeList(cnt,pts,edges);
active=(Edge *)malloc (sizeof(Edge));
active->next=NULL;
for(scan=0;scan<WINDOW_HEIGHT;scan++)
{
buildActiveList(scan,active,edges);
if (active->next)
{fillScan(sacn,active);<br/> updateActiveList(scan,active);<br/> resortActiveList(active);<br/>}
}
}
}
}
}

Answer 2

//获取前一个点的索引号
int CPFill::GetBi(int i)
{
return (i==0)? Count-1:i-1;
}
//获取下一个点的索引号
int CPFill::GetAi(int i)
{
return (i==Count-1)?0:i+1;
}
//在指定的pDC设备中，填充多边形
bool CPFill::FillPolygon(CDC* pDC)
{
//获取多边形中所有坐标点的最大值和最小值，作为扫描线循环的范围
int minX=Point[0].x , minY=Point[0].y;
int maxX=Point[0].x , maxY=Point[0].y;

for(int i=1;i<Count;i++)
{
if(minX>Point[i].x) minX=Point[i].x;
if(minY>Point[i].y) minY=Point[i].y;
if(maxX<Point[i].x) maxX=Point[i].x;
if(maxY<Point[i].y) maxY=Point[i].y;
}
CUIntArray xArray;
int y;
for(y=minY;y<maxY;y++)
{
//扫描线从minY开始到maxY
for(i=0;i<Count;i++)
{
//对每条边进行循环
CPoint PointCross;
int Bi=GetBi(i),Ai=GetAi(i);
//判断是否跟线段相交
if(CrossJudge(Point[Bi],Point[i],CPoint(minX,y),CPoint(maxX,y),PointCross))
{
//若是存在交点，则进行相应的判断，即判断x的坐标取两次、一次还是不取
if(PointCross==Point[i])
{
if((Point[Bi].y>PointCross.y)&&(Point[Ai].y>PointCross.y))
{
//边顶点的y值大于交点的y值，x坐标取两次
xArray.Add(PointCross.x); xArray.Add(PointCross.x);
}
else
{
//边顶点的y值在交点的y值之间，即一个顶点的y值大于交点的y值，而另一个小于，相应的x坐标取一次
if((Point[Bi].y-PointCross.y)*(Point[Ai].y-PointCross.y)<0) xArray.Add(PointCross.x);
else if(PointCross.y==Point[Ai].y) xArray.Add(PointCross.x);
}
}
else
{
if(PointCross==Point[Bi]) continue;
else xArray.Add(PointCross.x);//当交点不在线段的顶点时，x坐标只取一次
}
}
}
int *scanLineX,num=xArray.GetSize();
scanLineX=new int[num];
for(i=0;i<num;i++) scanLineX[i]=xArray.GetAt(i);//获取扫描线x值，以构成填充区间
xArray.RemoveAll();
Sort(scanLineX,num);//对scanLine（扫描线x坐标进行排序）
for(i=0;i<num;i=i+2)
{
if(i+1>=num) break;
pDC->MoveTo(scanLineX[i],y);pDC->LineTo(scanLineX[i+1],y);//填充（Koradji改进）
}
Sleep(1);//CPU暂停1ms，以体现出多边形是以扫描线的方式，一条一条的填充的
delete scanLineX;
}
return true;
}

Answer 3

建议用绘图标准函数来搞定。

Answer 4

自己看书都有的啊