作者：非妃是公主
专栏：《计算机图形学》
博客地址：https://blog.csdn.net/myf_666
个性签：顺境不惰，逆境不馁，以心制境，万事可成。——曾国藩

文章目录

• 专栏推荐
• 专栏系列文章
• 序
• 一、算法原理
• 二、OpenGL代码实现
• 三、效果展示
• the end……

专栏推荐

专栏系列文章

序

计算机图形学（英语：computer graphics，缩写为CG）是研究计算机在硬件和软件的帮助下创建计算机图形的科学学科，是计算机科学的一个分支领域，主要关注数字合成与操作视觉的图形内容。虽然这个词通常被认为是指三维图形，事实上同时包括了二维图形以及影像处理。

一、算法原理

有效边表法是X射线扫描转换的一种改进实现方式，相比于X射线方法，有效边表法由于不需要判断虚实交点，整体效率更高。

通过构造边表，然后随着X射线的移动不断地维护有效边表，通过两两配对边表中的有效边点亮像素，实现多边形的绘制。

具体原理如下：

排序方式按照x_ymin(y取到最小值的时候，x值的大小)排，x_ymin相等时按照

1

k

\frac{1}{k}

k1​大小排，稍加思考会发现，正常情况下，不会出现相等情况。

由于配对原则，在顶点相交处，会影响到配对，采用的做法是，在影响配对的情况下进行

y

m

a

x

=

y

m

a

x

−

1

ymax=ymax-1

ymax=ymax−1处理，通过此来保证在进行有效边交替的时候不会出现错误(即保证有效边表中的有效边数量为偶数)。

算法流程(本人在实现的时候，为编码符合自己的逻辑方式，先增加节点、再填充像素、填充后即检查是否需要删除如需要删除、最后进行各个有效边x_ymin属性的

+

1

k

+\frac{1}{k}

+k1​)：

二、OpenGL代码实现

OpenGL代码实现如下：

// 有效边表法(AET)绘制填充多边形
void AETPolygon(vector<Point> pnts) {
	vector<Point>::iterator min_iter = min_element(pnts.begin(), pnts.end());
	vector<Point>::iterator max_iter = max_element(pnts.begin(), pnts.end());
	int min_y = min_iter->y;
	int max_y = max_iter->y;
	int dist = max_y - min_y + 1;
	vector<ETNode*> ET;		// 边表
	for (int i = 0; i < dist; i++) {
		ET.push_back(new ETNode(0, 0, 0));
	}
	
	for (int i = 0; i < pnts.size(); i++) { // 建立边表
		// 建立边表节点的属性值
		double x_ymin, y_max, rev_k;
		if (pnts[i].y > pnts[(i + 1) % pnts.size()].y) {	// 找出y最小值对应的x值
			x_ymin = pnts[(i + 1) % pnts.size()].x;
			y_max = pnts[i].y;
			// 如果为一个顶点的情况，y_max--
			if ((pnts[(i - 1 + pnts.size()) % pnts.size()].y - pnts[i].y) * (pnts[(i + 1 + pnts.size()) % pnts.size()].y - pnts[i].y) < 0) {
				y_max--;
			}
		}
		else {
			x_ymin = pnts[i].x;
			y_max = pnts[(i + 1) % pnts.size()].y;
			// 如果为一个顶点的情况，y_max--
			if ((pnts[(i + pnts.size()) % pnts.size()].y - pnts[i + 1].y) * (pnts[(i + 2 + pnts.size()) % pnts.size()].y - pnts[i + 1].y) < 0) {
				y_max--;
			}
		}
		// 计算 1/k
		rev_k = (double)(pnts[(i + 1) % pnts.size()].x - pnts[i].x) / (pnts[(i + 1) % pnts.size()].y - pnts[i].y);// 计算 (1/斜率)
		ETNode* tmp = new ETNode(x_ymin, y_max, rev_k);
		ETNode* tmpFirstNode = ET[x_ymin - min_y];
		// 寻找合适的插入位置
		while (tmpFirstNode->next != nullptr && *(tmpFirstNode->next) < *tmp)
		{
			tmpFirstNode = tmpFirstNode->next;
		}
		// 插入
		tmp->next = tmpFirstNode->next;
		tmpFirstNode->next = tmp;
	}
	// 建立活动边表
	ETNode* AET = new ETNode(0, 0, 0); // AET为头节点，不储存边表节点，后续节点才储存
	// 从下到上进行 x 射线扫描
	for (int i = min_y; i < max_y; i++) {
		ETNode* tmp_ETNode = ET[i - min_y];
		ETNode* tmp_AETNode = AET;
		while (tmp_ETNode->next != nullptr) {
			tmp_AETNode = AET;
			// 寻找AET中的插入位置
			while (tmp_AETNode->next != nullptr && *(tmp_AETNode->next) < *(tmp_ETNode->next)) {
				tmp_AETNode = tmp_AETNode->next;
			}
			//ET[i - min_y]->next = tmp_ETNode->next->next;
			 将tmp->next加入到 AET中
			//tmp_ETNode->next->next = tmp_AETNode->next;
			//tmp_AETNode->next = tmp_ETNode->next;
			//tmp_ETNode = ET[i - min_y];
			// 将tmp加入到 AET 中
			ETNode* tmp = new ETNode(tmp_ETNode->next->x_ymin, tmp_ETNode->next->y_max, tmp_ETNode->next->rev_k);
			tmp->next = tmp_AETNode->next;
			tmp_AETNode->next = tmp;
			tmp_ETNode = tmp_ETNode->next;
		}
		// 添加完以后进行画点
		tmp_AETNode = AET;
		while (tmp_AETNode->next != nullptr && tmp_AETNode->next->next != nullptr) {
			int fillBegin = (int)(tmp_AETNode->next->x_ymin + 0.5);
			int fillEnd = (int)(tmp_AETNode->next->next->x_ymin + 0.5);
			glColor3f(0.0f, 1.0f, 0.0f);			// 设置颜色为绿色进行填充
			glBegin(GL_POINTS);
			for (int j = fillBegin; j <= fillEnd; j++) {
				glVertex2i(j, i);
			}			
			glEnd();
			// 填充之后删除y=y_max的边
			if (i == tmp_AETNode->next->y_max || i == tmp_AETNode->next->next->y_max) {
				if (i == tmp_AETNode->next->y_max && i == tmp_AETNode->next->next->y_max) { // 删两个
					ETNode* del = tmp_AETNode->next;
					tmp_AETNode->next = tmp_AETNode->next->next;
					delete del;
					del = tmp_AETNode->next;
					tmp_AETNode->next = tmp_AETNode->next->next;
					delete del;
				}
				else if(i == tmp_AETNode->next->y_max) { // 删第一个
					ETNode* del = tmp_AETNode->next;
					tmp_AETNode->next = tmp_AETNode->next->next;
					delete del;
					tmp_AETNode = tmp_AETNode->next;
				}
				else {			// 删第二个
					ETNode* del = tmp_AETNode->next->next;
					tmp_AETNode->next->next = tmp_AETNode->next->next->next;
					delete del;
					tmp_AETNode = tmp_AETNode->next;
				}
				continue;
			}
			tmp_AETNode = tmp_AETNode->next->next;
		}
		// 更新AET表中的x值
		tmp_AETNode = AET;
		while (tmp_AETNode->next != nullptr)
		{
			tmp_AETNode->next->x_ymin += tmp_AETNode->next->rev_k;
			tmp_AETNode = tmp_AETNode->next;
		}
	}
	// 进行析构
	// 析构AET
	ETNode* AEThead = AET;
	while (AEThead != nullptr) {
		ETNode* del = AEThead;
		AEThead = AEThead->next;
		delete del;
	}
	// 析构ET
	for (int i = 0; i < ET.size(); i++) {
		ETNode* EThead = ET[i];
		while (EThead != nullptr) {
			ETNode* del = EThead;
			EThead = EThead->next;
			delete del;
		}
	}
}

三、效果展示

有效边表法的多边形扫描转换效果如下：

the end……

有效边表法的多边形扫描转换算法到这里就要结束啦~~到此既是缘分，欢迎您的点赞、评论、收藏！关注我，不迷路，我们下期再见！！

😘😘😘 我是Cherries，一位计算机科班在校大学生，写博客用来记录自己平时的所思所想！
💞💞💞 内容繁杂，又才疏学浅，难免存在错误，欢迎各位大佬的批评指正！
👋👋👋 我们相互交流，共同进步！

注：本文由非妃是公主发布于https://blog.csdn.net/myf_666，转载请务必标明原文链接：https://blog.csdn.net/myf_666/article/details/128226399