/**************************
?*?Includes
?*
?**************************/

#include?
#include?
#include?“gl/glut.h“
#include?“windows.h“
const?int?POINTNUM=7;?//多邊形點數.

/******定義結構體用于活性邊表AET和新邊表NET***********************************/
?typedef?struct?XET
?{
??float?x;
??float?dxymax;
??XET*?next;
?}AETNET;

/******定義點結構體point******************************************************/
?struct?point
?{
??float?x;
??float?y;
?}
?polypoint[POINTNUM]={2505055015055040025025010035010010012030};//多邊形頂點

?void?PolyScan（）
{
/******計算最高點的y坐標（掃描到此結束）****************************************/
?int?MaxY=0;
?int?i;
?for（i=0;i??if（polypoint[i].y>MaxY）
???MaxY=polypoint[i].y;
??
/*******初始化AET表***********************************************************/
??AET?*pAET=new?AET;
??pAET->next=NULL;
??
/******初始化NET表************************************************************/
??NET?*pNET[1024];
??for（i=0;i<=MaxY;i++）
??{
???pNET[i]=new?NET;
???pNET[i]->next=NULL;
??}
??glClear（GL_COLOR_BUFFER_BIT）;????????//賦值的窗口顯示.??
??glColor3f（0.00.00.0）;?????????????//設置直線的顏色紅色
??glBegin（GL_POINTS）;
/******掃描并建立NET表*********************************************************/
??for（i=0;i<=MaxY;i++）
??{
???for（int?j=0;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*****************************************************/
for（i=0;i<=MaxY;i++）
??{
?//計算新的交點x更新AET
???NET?*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;
???}
?//（改進算法）先從AET表中刪除ymax==i的結點****************************************/
???AET?*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;
????}
???}
?//將NET中的新點加入AET并用插入法按X值遞增排序**********************************/
???p=p