多边形扫描转换算法（C语言实现）
原理不赘述
ET边表
AET链表
实现
该算法我实在计算机图形学的书上看到了，但是遗憾的是看懂了，并没有算法实现。该算法的优势很是很明显的对于种子填充算法来说，我在电脑上用种子算法填充一个720x960的一块多边形的C语言的堆栈需要设置到32M才能够运行起来，并且填充动态肉眼可见，不用加延时就可以看到动画效果。显然时不能使用的。
这几天一直在琢磨怎么实现算法，还是纯C的那种，于是就有下面的代码。
该算法难在ET表和AET表。这里我仅仅用到了ET表，用一个简易实现串的数据结构实现的。有兴趣的朋友可以将代码复制到自己的电脑上实现一下。
使用的图形库
程序中使用到的graphics.h库大家可以访问下面的网址获取，
Easyx
使用方法请自行查阅资料和百度
#include <graphics.h>
#include <stdio.h>
/* 多边形的点数据 */
POINT points[] = { {20,10} ,{450,70}, {200,160} ,{840,500} ,{900,700} ,{640,540} ,{500,660},{400,300}, {400,510},{300,510}, {200,700} ,{100,220} };
/* 填充多边形函数 */
void draw_Polygons(POINT pointl[],int len);
int main()
{
/* 初始化图形窗口，带控制台 可以在调试中打印一些数据方便调试 */
initgraph(960, 720,EW_SHOWCONSOLE);
/* 设置坐标原点 左下角的坐标点为原点 */
setorigin(0, 719); //设置原点坐标
/* 设置x,y轴坐标方向 电脑是以左上角为坐标原点 至左向右为x轴正方向这里不变设置第一个参数为1，至上而下为y轴正方向，与我们所熟悉的笛卡尔坐标相反，这里设置为-1 */
setaspectratio(1, -1); //设置y轴正方向
/* 传入参数开始填充多边形 */
draw_Polygons(points,sizeof(points)/sizeof(POINT));
getchar();
}
/*===========================================================================
函数描述：绘制多边形
参数 ：pointl[in] 所输入的点（有序）
返回值 ：无
============================================================================*/
void draw_Polygons(POINT pointl[],int len)
{
struct toppoint //结构体名真心不会取
{
int ymin; //该线段最小的y值
int ymax; //该线段最大的y值
int xmin; //该线段最小y的对应x值
char flag; //判断该点是否使用过
float slope; //斜率
};
int y;
int num = 0,min,max,i,j;
//使用malloc函数可控制函数的内存大小，数组必须写死，可能会出现错误溢出等情况。
struct toppoint* ET = (struct toppoint*)malloc(len*sizeof(struct toppoint)); //申请len个边表信息;这里没有内存申请失败的处理，自觉加上
int* xstack = (int*)malloc((len + 1) * sizeof(int)); //申请xstack个点；xstack[0]放置个数；这里没有内存申请失败的处理，自觉加上
/* 找到y的最小值 */
for (num = 0,min=pointl[0].y; num < len; num++)
{
if (min > pointl[num].y) min = pointl[num].y;
}
/* 找到y的最大值 */
for (num = 0, max = pointl[0].y; num < len; num++)
{
if (max < pointl[num].y) max = pointl[num].y;
}
//生成ET表
for (num = 0; num < len; num++)
{
ET[num].flag = 0; //没有使用过（不用数据结构去做浪费空间，要编写大量的代码删除将该标志位置一）;
ET[num].ymin = (pointl[num].y > pointl[(num + 1) % len].y ? pointl[(num + 1) % len].y : pointl[num].y); //两者中的最小值;
ET[num].ymax = (pointl[num].y < pointl[(num + 1) % len].y ? pointl[(num + 1) % len].y : pointl[num].y); //两者中的最大值;
ET[num].xmin = (pointl[num].y > pointl[(num + 1) % len].y ? pointl[(num + 1) % len].x : pointl[num].x);
/* 警惕除数为零的情况 */
ET[num].slope = (((float)(pointl[(num + 1) % len].y - pointl[num].y) == 0)? 0 : (float)(pointl[(num + 1) % len].x - pointl[num].x) / (float)(pointl[(num + 1) % len].y - pointl[num].y));
}
//设置填充颜色
setlinecolor(GREEN);
// 开始填充
for (y =min ; y <= max; y++)
{
// 第一个x坐标放置在 xstack[1]的位置
i = 1;
for (num = 0; num < len; num++) //开始推算 xstack值
{
if (ET[num].flag == 0 && y>ET[num].ymin) //没有被用过
{
if (ET[num].ymax < y) //失效
{
ET[num].flag = 1; //已经使用过了不用再使用；
}
else
{
//利用递增的算出下一个x坐标位置
xstack[i++] = ET[num].xmin + ET[num].slope * (y - ET[num].ymin);
}
}
}
// 记录总的x坐标值个数 //均为偶数
xstack[0] = i-1;
//开始填充 划线
// 对x坐标值进行排序
for (i = 1; i < xstack[0]; i++)
{
for (j = 1; j < xstack[0] + 1 -i; j++)
{
if (xstack[j] > xstack[j+1])
{
num = xstack[j];
xstack[j] = xstack[j + 1];
xstack[j + 1] = num;
}
}
}
//开始绘制该行的线段
for (num = 1; num <= xstack[0]; num += 2)
{
line(xstack[num], y, xstack[num + 1], y);
}
}
//设置边的颜色值
setlinecolor(RED);
for (num = 0; num <= len; num++)
{
// 画线
line(pointl[num % len].x, pointl[num % len].y, pointl[(num + 1) % len].x, pointl[(num + 1) % len].y);
}
}