Active Edge Table Conversion Algorithm for Polygon Filling

void  CPolygon_ConversionView::Active_Edge_Table_Conversion(int Vertices[][2], int VertexNum)
{
	// 1. 构建有效边表
	vector<vector<int>> AET; // 有效边表
	vector<vector<int>> NET; // 新边表
	for (int i = 0; i < VertexNum; i++)
	{
		// 起点坐标
		int x1 = Vertices[i][0];
		int y1 = Vertices[i][1];
		// 终点坐标
		int x2, y2;
		if (i == VertexNum - 1) // 最后一个顶点连向第一个顶点
		{
			x2 = Vertices[0][0];
			y2 = Vertices[0][1];
		}
		else
		{
			x2 = Vertices[i + 1][0];
			y2 = Vertices[i + 1][1];
		}
		if (y1 == y2) continue; // 排除水平线段
		if (y1 > y2) // 保证从上往下排序
		{
			swap(x1, x2);
			swap(y1, y2);
		}
		float k = (float)(x2 - x1) / (float)(y2 - y1);
		vector<int> edge = { y1, y2, x1, k }; // 存储边信息
		NET.push_back(edge);
	}
	// 排序
	sort(NET.begin(), NET.end(), [](vector<int> a, vector<int> b) {return a[0] < b[0]; });
	// 2. 扫描线填充
	for (int y = NET[0][0]; y <= NET[NET.size() - 1][1]; y++) // 扫描线从第一条边的起点开始，直到最后一条边的终点
	{
		// 将新边表中y坐标等于y的边添加到有效边表中
		for (int i = 0; i < NET.size(); i++)
		{
			if (NET[i][0] == y) // 新边表中的边起点和当前扫描线相交
			{
				AET.push_back(NET[i]); // 添加到有效边表中
			}
		}
		// 按照x坐标排序
		sort(AET.begin(), AET.end(), [](vector<int> a, vector<int> b) {return a[2] < b[2]; });
		// 绘制扫描线上的像素点
		for (int i = 0; i < AET.size(); i += 2) // 每两条边为一组，填充之间的像素点
		{
			for (int x = AET[i][2]; x < AET[i + 1][2]; x++)
			{
				DrawPixel(x, y);
			}
		}
		// 更新有效边表
		for (int i = 0; i < AET.size(); i++)
		{
			if (AET[i][1] == y + 1) // 边终点和扫描线相交时，从有效边表中删除
			{
				AET.erase(AET.begin() + i);
				i--;
			}
			else // 更新边的x坐标
			{
				AET[i][2] += AET[i][3];
			}
		}
	}
}

This code implements the Active Edge Table (AET) conversion algorithm for polygon filling. It takes a set of vertices as input and uses the AET to efficiently fill the polygon with pixels.

Algorithm Steps:

1. Construct the New Edge Table (NET):
   • Iterate through all the vertices of the polygon.
   • For each edge (defined by two consecutive vertices), calculate the slope (k) and store the edge information (y1, y2, x1, k) in the NET.
   • Sort the NET by the y-coordinate of the starting point (y1).
2. Scanline Filling:
   • Iterate through each scanline from the minimum y-coordinate to the maximum y-coordinate of the polygon.
   • Update the Active Edge Table (AET): For each scanline, add all edges from the NET that start at the current y-coordinate to the AET.
   • Sort the AET: Sort the edges in the AET based on their x-coordinate.
   • Fill pixels: For each pair of edges in the AET, fill all pixels between the two edges on the current scanline.
   • Update the AET: For each edge in the AET:
     • If the edge ends at the current y-coordinate, remove it from the AET.
     • Otherwise, update the x-coordinate of the edge by adding the slope (k) to it.

This algorithm ensures efficient polygon filling by only considering edges that intersect with the current scanline. This reduces the number of computations compared to other methods like the flood fill algorithm.