1 //扫描线填充算法类 <BR> 显示代码打印001 class CPFill
002 {
003 public:
004 CPoint *Point;
005 //指向点坐标的指针
006 int Count;
007 //多边形点的个数
008 public:
009 CPFill(int,int[],int[]);//构造函数
010 bool FillPolygon(CDC*);//填充多边形
011 bool CrossJudge(CPoint,CPoint,CPoint,CPoint,CPoint&);//判断两条线段是否相交
012 int GetAi(int);//获取下一个点的索引号
013 int GetBi(int);//获取前一个点的索引号
014 bool Sort(int*,int);//冒泡排序
015 ~CPFill();//析构函数
016 };
017 //构造函数 （模块入口，koradji 注，合理的设计这个地方，就可以完全不用改动其他的地方就可以使用这个类）
018 CPFill::CPFill(){ }
019
020 //获取前一个点的索引号
021 int CPFill::GetBi(int i)
022 {
023 return (i==0)? Count-1:i-1;
024 }
025 //获取下一个点的索引号
026 int CPFill::GetAi(int i)
027 {
028 return (i==Count-1)?0:i+1;
029 }
030 //在指定的pDC设备中，填充多边形
031 bool CPFill::FillPolygon(CDC* pDC)
032 {
033 //获取多边形中所有坐标点的最大值和最小值，作为扫描线循环的范围
034 int minX=Point[0].x , minY=Point[0].y;
035 int maxX=Point[0].x , maxY=Point[0].y;
036 for(int i=1;i<Count;i++)
037 {
038 if(minX>Point[i].x) minX=Point[i].x;
039 if(minY>Point[i].y) minY=Point[i].y;
040 if(maxX<Point[i].x) maxX=Point[i].x;
041 if(maxY<Point[i].y) maxY=Point[i].y;
042 }
043 CUIntArray xArray;
044 int y;
045 for(y=minY;y<maxY;y++)
046 {
047 //扫描线从minY开始到maxY
048 for(i=0;i<Count;i++)
049 {
050 //对每条边进行循环
051 CPoint PointCross;
052 int Bi=GetBi(i),Ai=GetAi(i);
053 //判断是否跟线段相交
054 if(CrossJudge(Point[Bi],Point[i],CPoint(minX,y),CPoint(maxX,y),PointCross))
055 {
056 //若是存在交点，则进行相应的判断，即判断x的坐标取两次、一次还是不取
057 if(PointCross==Point[i])
058 {
059 if((Point[Bi].y>PointCross.y)&&(Point[Ai].y>PointCross.y))
060 {
061 //边顶点的y值大于交点的y值，x坐标取两次
062 xArray.Add(PointCross.x); xArray.Add(PointCross.x);
063 }
064 else
065 {
066 //边顶点的y值在交点的y值之间，即一个顶点的y值大于交点的y值，而另一个小于，相应的x坐标取一次
067 if((Point[Bi].y-PointCross.y)*(Point[Ai].y-PointCross.y)<0) xArray.Add(PointCross.x);
068 else if(PointCross.y==Point[Ai].y) xArray.Add(PointCross.x);
069 }
070 }
071 else
072 {
073 if(PointCross==Point[Bi]) continue;
074 else xArray.Add(PointCross.x);//当交点不在线段的顶点时，x坐标只取一次
075 }
076 }
077 }
078 int *scanLineX,num=xArray.GetSize();
079 scanLineX=new int[num];
080 for(i=0;i<num;i++) scanLineX[i]=xArray.GetAt(i);//获取扫描线x值，以构成填充区间
081 xArray.RemoveAll();
082 Sort(scanLineX,num);//对scanLine（扫描线x坐标进行排序）
083 for(i=0;i<num;i=i+2)
084 {
085 if(i+1>=num) break;
086 pDC->MoveTo(scanLineX[i],y);pDC->LineTo(scanLineX[i+1],y);//填充（Koradji改进）
087 }
088 Sleep(1);//CPU暂停1ms，以体现出多边形是以扫描线的方式，一条一条的填充的
089 delete scanLineX;
090 }
091 return true;
092 }
093
094 //判断两条线段是否相交
095 bool CPFill::CrossJudge(CPoint L1P1,CPoint L1P2,CPoint L2P1,CPoint L2P2,CPoint& coordinate)
096 {
097 //L1P1、L1P2是一条线段的顶点坐标，而L2P1、L2P2是另一条线段的顶点坐标
098 if(L1P1==L1P2) return false;//若L1P1、L1P2相等，则构不成线段，退出
099 if(L2P1==L2P2) return false;//若L2P1、L2P2等，则构不成线段，退出
100 if((L1P1.y-L1P2.y)*(L2P1.x-L2P2.x)==(L2P1.y-L2P2.y)*(L1P1.x-L1P2.x))//对斜率相等的情况下的处理
101 {
102 if((L1P1.y-L1P2.y)*(L2P1.x-L1P1.x)==(L1P1.x-L1P2.x)*(L2P1.y-L1P1.y))//判断两条线段是不是同一条线段
103 {
104 coordinate=L1P2;
105 return true;
106 }
107 else return false;
108 }
109 if(L1P1.x==L1P2.x)//当第一条线段斜率不存在时的
110 {
111 double x,y;
112 x=L1P1.x;
113 y=(L2P1.y-L2P2.y)*1.0/(L2P1.x-L2P2.x)*(L1P1.x-L2P1.x)+L2P1.y;
114 y=(float)((int)(y+0.5));
115 if(((L1P1.y-y)*(y-L1P2.y)>=0)&&((L1P1.x-x)*(x-L1P2.x)>=0))//判断交点是不是在该两条线段上
116 {
117 coordinate.x=L1P1.x;
118 coordinate.y=(int)(y+0.5);
119 return true;
120 }
121 return false;
122 }
123 else
124 {
125 if(L2P1.x==L2P2.x)//当第二条线段斜率不存在时
126 {
127 double x,y;
128 x=L2P1.x;
129 y=(L1P1.y-L1P2.y)*1.0/(L1P1.x-L1P2.x)*(L2P1.x-L1P1.x)+L1P1.y;
130 y=(float)((int)(y+0.5));
131 if(((L1P1.y-y)*(y-L1P2.y)>=0) && ((L1P1.x-x)*(x-L1P2.x)>=0))//判断交点是不是在该两条线段上
132 {
133 coordinate.x=L2P1.x;
134 coordinate.y=(int)(y+0.5);
135 return true;
136 }
137 return false;
138 }
139 else//两条线段斜率都存在时
140 {
141 double k1,k2;
142 k1=(L1P1.y-L1P2.y)*1.0/(L1P1.x-L1P2.x);
143 k2=(L2P1.y-L2P2.y)*1.0/(L2P1.x-L2P2.x);
144 //k1,k2为计算的两线段的斜率
145 double x,y;
146 x=(L2P1.y-L1P1.y-k2*L2P1.x+k1*L1P1.x)/(k1-k2);
147 y=(k1*k2*L2P1.x-k1*k2*L1P1.x+k2*L1P1.y-k1*L2P1.y)/(k2-k1);
148 x=(float)((int)(x+0.5));
149 y=(float)((int)(y+0.5));
150 if(((L1P1.y-y)*(y-L1P2.y)>=0)&&((L1P1.x-x)*(x-L1P2.x)>=0))//判断交点是不是在该两条线段上
151 {
152 coordinate.x=(int)(x+0.5);
153 coordinate.y=(int)(y+0.5);
154 return true;
155 }
156 return false;
157 }
158 }
159 return true;
160 }
161
162 //冒泡排序
163 bool CPFill::Sort(int* iArray,int iLength)
164 {
165 int i,j,iTemp;
166 bool bFlag;
167 for(i=0;i<iLength;i++)
168 {
169 bFlag=true;
170 for(j=0;j<iLength-i-1;j++)
171 {
172 if(iArray[j] > iArray[j+1])
173 {
174 iTemp=iArray[j];
175 iArray[j]=iArray[j+1];
176 iArray[j+1]=iTemp;
177 bFlag=false;
178 }
179 }
180 if(bFlag) break;
181 }
182 return true;
183 }
184 //析构函数,删除动态生成的Point指针
185 CPFill::~CPFill()
186 {
187 if(Point) delete [] Point;
188 }
下面说说怎么为我所用这个类。 在MFC中，若多边形控制定点的变量是：CPoint *P，记录下标的变量为int index。 则构造函数则变为
显示代码打印1 CPFill::CPFill(int index,CPoint *P)
2 {
3 Point=new CPoint[index-1];
4 Count=index-1;
5 for(int i=0;i<Count;i++)
6 {
7 Point[i]=P[i];
8 }
如果多边形控制定点的变量是：int px[MAX] int py[MAX]，记录下标的变量为int index。 则构造函数是：
显示代码打印01 CPFill::CPFill(int index,int px[],int py[])
02 {
03 Point=new CPoint[index-1];
04 Count=index-1;
05 for(int i=0;i<Count;i++)
06 {
07 Point[i].x=px[i];
08 Point[i].y=py[i];
09 }
10 }
