扫描线填充算法.doc

任意封闭多边形的扫描线填充算法类收藏
这个代码不是我写的,但是我肯定这代码是一个牛人写的,放在这里供大家学习和使用啦!感谢原作者!
我在这里做了些改进:
1 去除了绘制多边形的函数,使其成为了一个纯的填充算法模块
2 改进了其成员变量,使其更容易让大多数人所使用
3 改进了填充,使其“看”(代码上)起来更像用扫描线在填充
改进后的扫描线算法类如下:
//扫描线填充算法类
class CPFill
{
public:
CPoint *Point;
//指向点坐标的指针
int Count;
//多边形点的个数
public:
CPFill(int,int[],int[]);//构造函数
bool FillPolygon(CDC*);//填充多边形
bool CrossJudge(CPoint,CPoint,CPoint,CPoint,CPoint&);//判断两条线段是否相交
int GetAi(int);//获取下一个点的索引号
int GetBi(int);//获取前一个点的索引号
bool Sort(int*,int);//冒泡排序
~CPFill();//析构函数
};
//构造函数(模块入口,koradji 注,合理的设计这个地方,就可以完全不用改动其他的地方就可以使用这个类)
CPFill::CPFill(){ }
//获取前一个点的索引号
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>)&&(Point[Ai].y>))
{
//边顶点的y值大于交点的y值,x坐标取两次
(); ();
}
else
{
//边顶点的y值在交点的y值之间,即一个顶点的y值大于交点的y值,而另一个小于,相应的x坐标取一次
if((Point[Bi].y-)*(Point[Ai].y-)<0) ();
else if(==Point[Ai].y) ();
}
}
else
{
if(PointCross==Point[Bi]) continue;
else ();//当交点不在线段的顶点时,x坐标只取一次
}
}
}
int *scanLineX,num=();
sc