多邊形掃描轉換演算法（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);
	}
}

效果展示：