当前位置：编程学习 > C/C++ >>

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

寻求最正确的源代码，参数值阁下可任意输入，不过得标明...最好把每步的具体解释都写出来。
调试成功的答案，给分哦！
答案：
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);
  updateActiveList(scan,active);
 resortActiveList(active);
}
}
}
}
   }
}
//获取前一个点的索引号
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;
}
http://www.diybl.com/course/3_program/c++/cppsl/2008222/100446_2.html去这里找吧
//判断两条线段是否相交
bool CPFill::CrossJudge(CPoint L1P1,CPoint L1P2,CPoint L2P1,CPoint L2P2,CPoint& coordinate)
{
 //L1P1、L1P2是一条线段的顶点坐标，而L2P1、L2P2是另一条线段的顶点坐标
 if(L1P1==L1P2)  return false;//若L1P1、L1P2相等，则构不成线段，退出
 if(L2P1==L2P2) return false;//若L2P1、L2P2等，则构不成线段，退出
 if((L1P1.y-L1P2.y)*(L2P1.x-L2P2.x)==(L2P1.y-L2P2.y)*(L1P1.x-L1P2.x))//对斜率相等的情况下的处理
 {  
  if((L1P1.y-L1P2.y)*(L2P1.x-L1P1.x)==(L1P1.x-L1P2.x)*(L2P1.y-L1P1.y))//判断两条线段是不是同一条线段
  {   
   coordinate=L1P2;
   return true;
  }
  else return false;
 }
 if(L1P1.x==L1P2.x)//当第一条线段斜率不存在时的
 {  
  double x,y;
  x=L1P1.x;
  y=(L2P1.y-L2P2.y)*1.0/(L2P1.x-L2P2.x)*(L1P1.x-L2P1.x)+L2P1.y;
  y=(float)((int)(y+0.5));
  if(((L1P1.y-y)*(y-L1P2.y)>=0)&&((L1P1.x-x)*(x-L1P2.x)>=0))//判断交点是不是在该两条线段上
  {   
   coordinate.x=L1P1.x;
   coordinate.y=(int)(y+0.5);
   return true;
  }
  return false;
 }
 else
 {
  if(L2P1.x==L2P2.x)//当第二条线段斜率不存在时
  {   
   double x,y;
   x=L2P1.x;
   y=(L1P1.y-L1P2.y)*1.0/(L1P1.x-L1P2.x)*(L2P1.x-L1P1.x)+L1P1.y;
   y=(float)((int)(y+0.5));
   if(((L1P1.y-y)*(y-L1P2.y)>=0) && ((L1P1.x-x)*(x-L1P2.x)>=0))//判断交点是不是在该两条线段上
   {    
    coordinate.x=L2P1.x;
    coordinate.y=(int)(y+0.5);
    return true;
   }
   return false;
  }
  else//两条线段斜率都存在时
  {   
   double k1,k2;
   k1=(L1P1.y-L1P2.y)*1.0/(L1P1.x-L1P2.x);
   k2=(L2P1.y-L2P2.y)*1.0/(L2P1.x-L2P2.x);
   //k1,k2为计算的两线段的斜率
   double x,y;
   x=(L2P1.y-L1P1.y-k2*L2P1.x+k1*L1P1.x)/(k1-k2);
   y=(k1*k2*L2P1.x-k1*k2*L1P1.x+k2*L1P1.y-k1*L2P1.y)/(k2-k1);
   x=(float)((int)(x+0.5));  
   y=(float)((int)(y+0.5));
   if(((L1P1.y-y)*(y-L1P2.y)>=0)&&((L1P1.x-x)*(x-L1P2.x)>=0))//判
上一个：c ,c++,vc实现程序不在任务栏显示
下一个：请问在C＋＋中使用指针的好处有哪些？
更多图片编程知识:
更多C/C++疑问解答：
关于c++的cout输出的问题。
在学校里学过C和C++，不过学的很一般，现在自学C#，会不会很难？
全国计算机二级C语言笔试题
已知某树有2个2度结点，3个3度结点，4个4度结点，问有几个叶子结点？
c++数据结构内部排序问题，整数排序
2012九月计算机二级C语言全国题库，，急求急求
如果assert只有一个字符串作为参数，是什么意思呢?
C语言中，哪些运算符具有左结合性，哪些具有右结合性，帮忙总结下，谢谢了！
为什么用结构体编写的程序输入是，0输不出来啊~~~
将IEEE—754的十六进制转化为十进制浮点类型，用C或C++都行，多谢各位大侠啊，非常感谢！
为什么这个程序求不出公式？
这个链表倒置的算法请大家分析下
c语言函数库调用
C语言unsigned int纠错
C语言快排求解啊
asp
php
Delphi
Matlab
JSP
Foxpro
JS
C/C++
C#/ASP.NET
VC++
JAVA
VB
汇编语言
html/css
CGI
XML/UML
wap
网站相关
网页素材
python
微信小程序
thinkphp
如果你遇到编程学习难题：
访问www.zzzyk.com 试试
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络，