【MFC】多边形的扫描转换算法

发表于   |   更新于 | 分类于 | 阅读次数
字数统计: 1.8k | 阅读时长 ≈ 9

前言：本程序在VS2015环境下面MFC工程-单文档-VS样式 建立

测试输出样本变量：

int temp = 0;
CStrrng str;
str.Format(_T(“a = %d”),temp);
MessageBox(str);

1. 目的：输入多边形顶点，对多边形进行填充，使用多边形扫描转换算法； 2. 实现：

 const int POINTNUM=6;      //多边形点数.

/**定义结构体用于活性边表AET和新边表NET*/
typedef struct XET
{
float x;
float dx,ymax;
struct XET next;
}AET,NET;
/**定义点结构体point**/
struct point
{
float x;
float y;
}polypoint[POINTNUM]={370,10,560,100,560,200,430,130,340,170,340,80};//多边形顶点
//mypoint[POINTNUM]={100,100,200,100,200,200,100,200};//正方形
// 250,50,550,150,550,400,250,250,100,350,100,100
//{500,100,650,150,650,300,500,250,350,350,350,100};//多边形顶点
/**计算最高点的y坐标(扫描到此结束)**/
int MaxY=0;
int MinY = 2000;
int i;
for( i = 0;i < POINTNUM; i++ )
{
if( polypoint[i].y > MaxY )
{
MaxY = polypoint[i].y;
}
if( polypoint[i].y < MinY )
{
MinY = polypoint[i].y;
}
}
/**初始化AET表，即初始化活跃边表*/
AET pAET = new AET;
pAET->next = NULL;
/**初始化NET表，即初始化边表**/
NET pNET[1024];
for( i = MinY;i <= MaxY; i++ )
{
pNET[i] = new NET;
pNET[i]->next = NULL;
}
/**扫描并建立NET表，即建立边表*/
for( i = MinY; i <= MaxY; i++ )
{
for( int j = 0;j < POINTNUM; j++ )
{
if( polypoint[j].y == i)
{
if( polypoint[ (j-1+POINTNUM) % POINTNUM ].y > polypoint[j].y )
{
NET p=new NET;
p->x = polypoint[j].x;
p->ymax = polypoint[ (j-1+POINTNUM) % POINTNUM ].y;
p->dx = ( polypoint[ (j-1+POINTNUM)%POINTNUM ].x-polypoint[j].x ) / ( polypoint[ (j-1+POINTNUM) % POINTNUM ].y - polypoint[j].y );
p->next = pNET[i]->next;
pNET[i]->next = p;
}
if( polypoint[ (j+1+POINTNUM ) % POINTNUM].y > polypoint[j].y )
{
NET p = new NET;
p->x = polypoint[j].x;
p->ymax = polypoint[ (j+1+POINTNUM) % POINTNUM ].y;
p->dx = ( polypoint[ (j+1+POINTNUM) % POINTNUM ].x-polypoint[j].x ) / ( polypoint[ (j+1+POINTNUM) % POINTNUM ].y- polypoint[j].y );
p->next = pNET[i]->next;
pNET[i]->next = p;
}
}
}
}
/
AET ptest1 = pNET[10]->next;
AET ptest11 = pNET[10]->next->next;
AET ptest111 = pNET[10]->next->next->next;
AET ptest2 = pNET[80]->next;
AET ptest22 = pNET[80]->next->next;
AET ptest3 = pNET[100]->next;
AET ptest33 = pNET[100]->next->next;
AET ptest4 = pNET[130]->next;
AET ptest44 = pNET[130]->next->next;
AET ptest444 = pNET[130]->next->next->next;
AET ptest5 = pNET[170]->next;
AET ptest6 = pNET[200]->next; /
/**建立并更新活性边表AET*/
for( i = MinY; i <= MaxY; i++ ) // for循环中按下面的流程而不是《计算机图形学》徐长青第二版P38中Polygonfill算法中的while循环中的流程，
{ // 这样可以处理书中的边界问题，无需开始时进行边缩短
//计算新的交点x,更新AET**/
NET p = pAET->next;
while( p != NULL )
{
p->x = p->x + p->dx;
p = p->next;
}
//更新后新AET先排序**/
//断表排序,不再开辟空间
AET tq = pAET;
p = pAET->next;
tq->next = NULL;
while( p != NULL )
{
while( tq->next != NULL && p->x >= tq->next->x )
{
tq = tq->next;
}
NET s = p->next;
p->next = tq->next;
tq->next = p;
p = s;
tq = pAET;
}
//(改进算法)先从AET表中删除ymax==i的结点**/
AET q = pAET;
p = q->next;
while( p != NULL )
{
if( p->ymax == i)
{
q->next = p->next;
delete p;
p = q->next;
}
else
{
q = q->next;
p = q->next;
}
}
//将NET中的新点加入AET,并用插入法按X值递增排序**/
p = pNET[i]->next;
q = pAET;
while( p != NULL )
{
while( q->next != NULL && p->x >= q->next->x)
{
q = q->next;
}
NET s = p->next;
p->next = q->next;
q->next = p;
p = s;
q = pAET;
}
/**配对填充颜色*/
p = pAET->next;
while( p != NULL && p->next != NULL )
{
for(float j = p->x;j <= p->next->x; j++)
{
pDC.SetPixel( static_cast(j), i, RGB(255,0,0) );
} // pDC.MoveTo( static_cast(p->x), i ); 用画直线来替换上面的设置像素点颜色，速度更快
// pDC.LineTo( static_cast(p->next->x), i );
p = p->next->next;//考虑端点情况
}
}
NET phead = NULL;
NET pnext = NULL;
//释放边表
/
for( i = MinY;i <= MaxY;i++ ) //下面代码释放内存有点错误
{
phead = pNET[i];
while( phead != NULL )
{
pnext = phead->next;
delete phead;
phead = pnext;
}
pNET[i] = NULL;
} /
//释放活跃边表
phead = pAET;
while( phead != NULL )
{
pnext = phead->next;
delete phead;
phead = pnext;
}

上面建立的边表如下： 可以按照上面算法流程运行一次，可以发现算法可以正确运行 MFC实现：http://download.csdn.net/download/winernathan/4022374 若上面的for循环替换为《计算机图形学》徐长青第二版P38中Polygonfill算法中的while循环中的流程，如下所示：

/**建立并更新活性边表AET*/
for( i = MinY; i <= MaxY; i++ ) // for循环中按下面的流程而不是《计算机图形学》徐长青第二版P38中Polygonfill算法中的while循环中的流程，
{ // 这样可以处理书中的边界问题，无需开始时进行边缩短
NET p=pAET->next;
AET q=pAET;
//将NET中的新点加入AET,并用插入法按X值递增排序**/
p=pNET[i]->next;
q=pAET;
while(p)
{
while(q->next && p->x >= q->next->x)
q=q->next;
NET s=p->next;
p->next=q->next;
q->next=p;
p=s;
q=pAET;
}
/**配对填充颜色**/
p=pAET->next;
while(p && p->next)
{
for(float j=p->x;j<=p->next->x;j++)
pDC.SetPixel(static_cast(j),i,RGB(255,0,0));
p=p->next->next;//考虑端点情况
}
//(改进算法)先从AET表中删除ymax==i的结点**/
q=pAET;
p=q->next;
while(p)
{
if(p->ymax==i)
{
q->next=p->next;
delete p;
p=q->next;
}
else
{
q=q->next;
p=q->next;
}
}
//计算新的交点x,更新AET**/
p=pAET->next;
while(p)
{
p->x=p->x + p->dx;
p=p->next;
}
//更新后新AET先排序*/
//断表排序,不再开辟空间
AET tq=pAET;
p=pAET->next;
tq->next=NULL;
while(p)
{
while(tq->next && p->x >= tq->next->x)
tq=tq->next;
NET s=p->next;
p->next=tq->next;
tq->next=p;
p=s;
tq=pAET;
}

可以发现y=80时，多边形内部并没有被填充，按照上面算法运行一次，可以发现其原因 算法思想参考：

《计算机图形学》徐长青第二版P38

转载来源：http://www.bccn.net/Article/kfyy/cjj/jszl/200810/8072.html 求出四条直线的两点式方程，按数学方法求两条直线交点不就OK啦？ 参考代码如下（需改进，要做四舍五入考虑）：

C/C++ code

//两点式交点
//返回结果为-1时，无交点
POINT AFX_API_EXPORT Intersection(SDLine l1, SDLine l2)
{
POINT lastP; DOUBLE k1,k2,b1,b2;
//两条非垂直线
if(l1.x1-l1.x2!=0 && l2.x1-l2.x2!=0)
{
b1=(l1.y1*l1.x2-l1.y2*l1.x1)/(l1.x2-l1.x1);
b2=(l2.y1*l2.x2-l2.y2*l2.x1)/(l2.x2-l2.x1);
k1=(l1.y1-l1.y2)/(l1.x1-l1.x2);
k2=(l2.y1-l2.y2)/(l2.x1-l2.x2);
if(k1-k2 != 0) {
lastP.x=(b2-b1)/(k1-k2);
lastP.y=(k1*b2-k2*b1)/(k1-k2);
}
else {
lastP.x=-1;
lastP.y=-1;
}
}
//两条垂直线
if(l1.x1-l1.x2==0 && l2.x1-l2.x2==0)
{
lastP.x=-1;
lastP.y=-1;
}
//一条垂直线
if(l1.x1-l1.x2==0 && l2.x1-l2.x2!=0)
{
b2=(l2.y1*l2.x2-l2.y2*l2.x1)/(l2.x2-l2.x1);
k2=(l2.y1-l2.y2)/(l2.x1-l2.x2);
lastP.x=l1.x1;
lastP.y=k2l1.x1+b2;
}
//一条垂直线
if(l1.x1-l1.x2!=0 && l2.x1-l2.x2==0)
{
b1=(l1.y1\l1.x2-l1.y2*l1.x1)/(l1.x2-l1.x1);
k1=(l1.y1-l1.y2)/(l1.x1-l1.x2);
lastP.x=l2.x1;
lastP.y=k1*l2.x1+b1;
}
return lastP;
}

(っ•̀ω•́)っ✎⁾⁾ 坚持技术学习、内容输出与分享，您的支持将鼓励我继续创作！(*/ω＼*)
( • ̀ω•́ )✧如有疑问或需要技术讨论，请留言或发邮件到 aclearzhang@qq.com.(*･ω< ) 
  • 本文作者：： AClearZhang
  • 本文链接：： 1253.html
  • 版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处！