扫描线填充多边形

一、实验目的

利用扫描线填充算法实现多边形填充

二、实验环境

Visual Studio 2019
Windows 10

三、算法分析与设计数据结构

Edge Bucket：存放边信息的结构体
```
typedef struct
{
	int ymax;
	float xofymin;
	float slopeinverse;
}EdgeBucket;
```
- ymax：本条边的最高顶点y值
- xofymin：本条边与扫描线的交点中最低点的x值（在AET中更新）
- slopeinverse： 1 m frac{1}{m} m1

Edge Table Tuple：由EdgeBucket组成的数组和包含边数目组成的结构体

typedef struct
{
	int countEdgeBucket;  // edgebuckets的个数
	EdgeBucket buckets[maxVer];
}EdgeTableTuple;

AET（Active Edge Tuple）：活性边表
```
EdgeTableTuple ActiveEdgeTuple;
```

ET（Edge Table）：边表

EdgeTableTuple EdgeTable[maxHt];  // 各扫描线对应的AET(Edge Tuple)

算法过程

由于输入为多组点坐标，为了方便修改，采用文件形式读入

逐边读入，记录本条边的 y m i n y_{min} ymin（即恰好到达本条边的扫描线高度yScan），并存入对应yScan高度扫描线的AET中，即EdgeTable[yScan]。同时在屏幕上画出这条边；
每加入一条边，对AET按边的xofymin进行升序排序，此处使用插入排序；
直到所有的边都被扫描完毕，多边形轮廓已被画出，所有边已被存储；
扫描线从下到上扫描，对每一条扫描线采取如下步骤：
- 更新高度为i的扫描线对应的AET；
- 将ymax==i的边从各AET中删除：后续更高的扫描线将不再能够与该边有交点；再次对AET进行排序；
- 按扫描线高度从下到上、交点横坐标从左到右进行填充。填充遵循如下规则
  - 两条边在交点同侧，该交点记为两个点；
  - 两条边在交点异侧，该交点记为一个点。
- 更新该扫描线高度对应的AET，将AET中每一个EdgeBucket的xofymin更新为xofymin+slopeinverse。

四、实验结果总结

五、附录

建议从drawPoly()开始阅读。

scanlinePolygonFilling.cpp

#include 
#include

using namespace std;

#define maxHt 800
#define maxWd 600
#define maxVer 10000

FILE* fp;

typedef struct
{
	int ymax;  // 本条边的最高顶点y值
	float xofymin;  // 本条边与扫描线的交点中最低点的x值（在AET中更新）
	float slopeinverse;  // 1/m
}EdgeBucket;  // 存储每一条边的信息

typedef struct
// 给出扫描线数目
{
	int countEdgeBucket;  // edgebuckets的个数
	EdgeBucket buckets[maxVer];
}EdgeTableTuple;

EdgeTableTuple EdgeTable[maxHt];  // 各扫描线对应的边表
EdgeTableTuple ActiveEdgeTuple;

void initEdgeTable()
{
	for (int i = 0; i < maxHt; i++)
	{
		EdgeTable[i].countEdgeBucket = 0;
	}

	ActiveEdgeTuple.countEdgeBucket = 0;
}

// 以交点从左向右的次序排列
void insertionSort(EdgeTableTuple* et)
{
	EdgeBucket tmp;
	for (int i = 1; i < et->countEdgeBucket; i++)
	{
		tmp.ymax = et->buckets[i].ymax;
		tmp.xofymin = et->buckets[i].xofymin;
		tmp.slopeinverse = et->buckets[i].slopeinverse;
		int j = i - 1;

		while (j >= 0 && (tmp.xofymin < et->buckets[j].xofymin))
		{
			et->buckets[j + 1].ymax = et->buckets[j].ymax;
			et->buckets[j + 1].xofymin = et->buckets[j].xofymin;
			et->buckets[j + 1].slopeinverse = et->buckets[j].slopeinverse;
			j--;
		}
		et->buckets[j + 1].ymax = tmp.ymax;
		et->buckets[j + 1].xofymin = tmp.xofymin;
		et->buckets[j + 1].slopeinverse = tmp.slopeinverse;
	}
}


// 用于ET和AET的存储
// *：存储地址，方便后续传地址调用函数
void storeEdgeInTuple(EdgeTableTuple* receiver, int ym, int xm, float slopeInv)
{
	(receiver->buckets[(receiver)->countEdgeBucket]).ymax = ym;
	(receiver->buckets[(receiver)->countEdgeBucket]).xofymin = (float)xm;
	(receiver->buckets[(receiver)->countEdgeBucket]).slopeinverse = slopeInv;

	insertionSort(receiver);

	(receiver->countEdgeBucket)++;
}

void storeInTable(int x1, int y1, int x2, int y2)
{
	// 不保存平行线
	if (y2 == y1)
		return;

	float m = 0;  // 斜率
	float mInv = 0; // 斜率的倒数
	if (x1 != x2)
	{
		m = (float)(y2 - y1) / (x2 - x1);
		mInv = (float)1.0/m;
	}
	else mInv = 0;
	

	int yScan = y1 > y2 ? y2 : y1;  // 传入能扫到这条边的最低扫描线y值
	int ymax = y1 > y2 ? y1 : y2;  // 传入这条边的最大y值
	int xx = y1 > y2 ? x2 : x1;  // 传入与这条扫描线相交的x值

	storeEdgeInTuple(&EdgeTable[yScan], ymax, xx, mInv);
}

// 将已达到ymax的边移出AET
void removeEdgeByYmax(EdgeTableTuple* tup, int yy)
{
	for (int i = 0; i < tup->countEdgeBucket; i++)
	{
		if (tup->buckets[i].ymax == yy)
		{
			for (int j = i; j < tup->countEdgeBucket - 1; j++)
			{
				tup->buckets[j].ymax = tup->buckets[j + 1].ymax;
				tup->buckets[j].xofymin = tup->buckets[j + 1].xofymin;
				tup->buckets[j].slopeinverse = tup->buckets[j + 1].slopeinverse;
			}
			tup->countEdgeBucket--;
			i--;
		}
	}
}

void updateX(EdgeTableTuple* tup)
{
	for (int i = 0; i < tup->countEdgeBucket; i++)
	{
		(tup->buckets[i]).xofymin += (tup->buckets[i]).slopeinverse;
	}
}

void scanLineFill()
{
	for (int i = 0; i < maxHt; i++)
	{
		// 1. 更新高度为i的扫描线对应的AET
		for (int j = 0; j < EdgeTable[i].countEdgeBucket; j++)
		{
			storeEdgeInTuple(&ActiveEdgeTuple, EdgeTable[i].buckets[j].ymax,
				EdgeTable[i].buckets[j].xofymin,
				EdgeTable[i].buckets[j].slopeinverse);
		}

		// 2. 将ymax==i的边从各AET中删除
		removeEdgeByYmax(&ActiveEdgeTuple, i);

		insertionSort(&ActiveEdgeTuple);

		// 3. 按扫描线y从下到上、交点从左到右填充
		int j = 0;
		int x1 = 0, x2 = 0;
		int ymax1 = 0, ymax2 = 0;
		int fillFlag = 0;  // 是否要填充
		int coordCount = 0;  // 用作判断当前扫入点编号的奇偶性
		while (j 2)
		{
			x1 = x2;
			y1 = y2;
			count = 2;
		}
		if (count == 1)
		{
			fscanf(fp, "%d,%d", &x1, &y1);
		}
		else
		{
			fscanf(fp, "%d,%d", &x2, &y2);
			printf("n%d,%d", x2, y2);
			glBegin(GL_LINES);
			glVertex2i(x1, y1);
			glVertex2i(x2, y2);
			glEnd();
			storeInTable(x1, y1, x2, y2);  // 将边存进ET


			glFlush();
		}
	}


}

void drawPoly(void)
{
	initEdgeTable();
	drawPolyMargin();  // 画边
	scanLineFill();  // 填充
}

void main(int argc, char** argv)
{
	fp = fopen("tmp.txt", "r");
	if (fp == NULL)
	{
		printf("Could not open file");
		return;
	}
	glutInit(&argc, argv);
	glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
	glutInitWindowSize(maxHt, maxWd);
	glutInitWindowPosition(100, 150);
	glutCreateWindow("scanlinePolygonFilling");
	myInit();
	glutDisplayFunc(drawPoly);

	glutMainLoop();
	fclose(fp);
}

tmp.txt

参考：
https://blog.csdn.net/DUGUjing/article/details/83049407?spm=1001.2014.3001.5506
https://www.geeksforgeeks.org/scan-line-polygon-filling-using-opengl-c/

扫描线填充多边形

C/C++/C#相关栏目本月热门文章