多边形扫描线填充算法 - 活性边表转换实现

多边形扫描线填充算法 - 活性边表转换实现

该函数 Active_Edge_Table_Conersion 用于将多边形的顶点信息转换为活性边表，并使用活性边表进行扫描线填充。

void  CPolygon_ConversionView::Active_Edge_Table_Conersion(int Vertices[][2], int VertexNum)
{
	// 1. 找出多边形的边界
	int ymax = Vertices[0][1]; // 最高点
	int ymin = Vertices[0][1]; // 最低点
	for (int i = 1; i < VertexNum; i++)
	{
		if (Vertices[i][1] > ymax)
			ymax = Vertices[i][1];
		if (Vertices[i][1] < ymin)
			ymin = Vertices[i][1];
	}

	// 2. 初始化活性边表和活性点表
	vector<EDGE> AEL; // 活性边表
	vector<int> APL; // 活性点表
	vector<EDGE> ET; // 边表
	EDGE edge;
	for (int i = 0; i < VertexNum; i++)
	{
		int x1 = Vertices[i][0];
		int y1 = Vertices[i][1];
		int x2 = Vertices[(i + 1) % VertexNum][0];
		int y2 = Vertices[(i + 1) % VertexNum][1];

		// 如果边不是水平的，则加入边表
		if (y1 != y2)
		{
			if (y1 > y2) // 确保y1<y2，即边从下到上
			{
				swap(x1, x2);
				swap(y1, y2);
			}
			edge.x = x1;
			edge.ymin = y1;
			edge.ymax = y2;
			edge.k = (float)(x2 - x1) / (float)(y2 - y1);
			ET.push_back(edge);
		}
	}
	sort(ET.begin(), ET.end(), cmp); // 按 ymin 升序排序

	// 3. 从上到下按扫描线处理多边形
	for (int y = ymax; y >= ymin; y--)
	{
		// 3.1 将y = y 的边加入到活性边表
		for (auto it = ET.begin(); it != ET.end();)
		{
			if (it->ymin == y)
			{
				AEL.push_back(*it);
				it = ET.erase(it);
			}
			else
				it++;
		}

		// 3.2 从活性边表中删除y = y 的边
		for (auto it = AEL.begin(); it != AEL.end();)
		{
			if (it->ymax == y)
				it = AEL.erase(it);
			else
				it++;
		}

		// 3.3 更新活性边表中所有边的x值
		for (auto it = AEL.begin(); it != AEL.end(); it++)
			it->x += it->k;

		// 3.4 将活性边表中的边按x值升序排序
		sort(AEL.begin(), AEL.end(), cmpx);

		// 3.5 根据活性边表中的边绘制像素
		for (int i = 0; i < AEL.size(); i += 2)
		{
			int x1 = (int)ceil(AEL[i].x);
			int x2 = (int)ceil(AEL[i + 1].x);
			for (int x = x1; x < x2; x++)
				DrawPixel(x, y);
		}
	}

	return;
}

// 比较函数，用于按照 ymin 升序排序
bool cmp(const EDGE& e1, const EDGE& e2)
{
	return e1.ymin < e2.ymin;
}

// 比较函数，用于按照 x 值升序排序
bool cmpx(const EDGE& e1, const EDGE& e2)
{
	return e1.x < e2.x;
}

代码解析：

1. 找到多边形的边界： 首先，找到多边形的最高点和最低点，用于确定扫描线的范围。
2. 初始化边表 (ET) 和活性边表 (AEL)： 初始化边表，将所有非水平边存储在边表中，并按 ymin 值升序排序。
3. 扫描线处理： 从最高点到最低点进行扫描，并执行以下步骤：
   • 将当前扫描线上的边加入 AEL： 将 ymin 值等于当前扫描线 y 值的边加入 AEL。
   • 从 AEL 中删除 ymax 值等于 y 的边： 将 ymax 值等于当前扫描线 y 值的边从 AEL 中删除。
   • 更新 AEL 中边的 x 值： 根据边斜率，更新 AEL 中每条边的 x 值，以便在下一行扫描时，x 值对应于该边的交点。
   • 对 AEL 按 x 值排序： 对 AEL 中的边，根据其 x 值进行升序排序。
   • 绘制像素： 根据 AEL 中的边，绘制对应扫描线上的像素。

代码中的关键数据结构：

• EDGE: 表示多边形的一条边，包含以下属性：
  • x: 当前扫描线上的交点 x 坐标
  • ymin: 边的最小 y 坐标
  • ymax: 边的最大 y 坐标
  • k: 边的斜率
• ET: 边表，存储所有非水平边，并按 ymin 升序排序
• AEL: 活性边表，存储当前扫描线上的所有边，并按 x 值升序排序
• APL: 活性点表，暂未使用

总结：

该代码实现了使用活性边表进行多边形扫描线填充的算法。通过将边存储在活性边表中，并根据扫描线的移动对活性边表进行更新，该算法可以高效地绘制多边形的内部区域。

注意：

• 该代码使用了 DrawPixel 函数，需要根据实际情况进行定义和实现。
• 由于 EDGE 结构体中包含 x 属性，该属性用于记录当前扫描线上的 x 坐标。在每次扫描线移动时，需要根据边的斜率更新 x 属性的值，以便在下一行扫描时，x 属性对应于该边的交点。
• 为了保证 AEL 中的边按 x 值升序排序，需要在每次扫描线移动后对 AEL 进行排序。
• 该算法仅适用于凸多边形，对于凹多边形，需要进行额外的处理。
• 该算法的实现方式可以根据具体情况进行调整和优化。