最近在学习计算机图形学，刚好老师有布置使用OpenGL实现任意多边填充算法，考虑到要使用品字形或者井字形填充，因此我采用了Y连贯算法来进行多边形的填充。
基本思路和标准的多边形填充算法存在一点差异，大致思路如下：
由于我使用AET表进行更新，因此在后续中并不需要使用ET边表，所以并未创建ET边表。
(1) 初始化：构造AET表；
(2) 从小达到遍历AET表，取出每个y值所包含的边，根据yi+1=yi+1,xi+1=xi+1/m计算并修改AET表中y+1值所包含的边，若y=ymax则不需要将边添加到y+1中。
(3) 对AET表每个扫描线所包含的点对按照x的值进行排序。
(4) 遍历AET表，取出点对进行填充。
链表的插入排序借鉴了这篇博客：C++之链表的三种排序-归并/插入/快速_永不为辅的博客-CSDN博客_c++分治法 链表排序
效果图如下：
主要的填充函数为YFill，第一个变量为输入的点对数量，第二个变量为点对的容器，第三个变量为x方向的填充间隔，第四个变量为y方向的填充间隔，第五个变量为填充模式（0为井字形填充，1为品字形填充），最后一个变量是每个坐标填充的形状（1为三角形，2为正方形，3为竖线，4为缺4分之一的正方形）。
注：品字形填充时，dx必须大于等于2。
大致代码如下：
void YFill(int nums, vector<int> &point, int dx, int dy, int mode, int type)
{
vector<START> et, aet;
int ymin = 999, ymax = 0;
// 获取到所有顶点的最大y值和最小y值
for (int i = 0; i < point.size(); ++i) {
++i;
if (point[i] > ymax)
ymax = point[i];
if (point[i] < ymin)
ymin = point[i];
}
// 构造ET边表
for (int i = ymin; i <= ymax; i++)
{
START *temp = new START;
temp->next = NULL;
temp->y = i;
aet.push_back(*temp);
}
// 将点存储到结构体容器中
vector<MyPoint> points;
for (auto iter=point.cbegin();iter!=point.cend();iter++)
{
MyPoint* point1 = new MyPoint;
point1->x = *iter;
iter++;
point1->y = *iter;
points.push_back(*point1);
}
// 将边存储到ET表中
for (int i = 0; i < points.size(); i++)
{
// 获取到直线两端的点
auto last = points[i];
int x0 = last.x, y0 = last.y;
MyPoint now;
if (i == points.size() - 1)
now = points[0];
else
now = points[i + 1];
int x1 = now.x, y1 = now.y;
int line_ymin = y0 > y1 ? y1 : y0;
//获取到y值最小的点将该直线添加到ET边表中
AET* temp_line = new AET;
temp_line->k = (x1 - x0) * 1.0 / (y1 - y0);
temp_line->x = y0 > y1 ? x1 : x0;
temp_line->y_max = y0 > y1 ? y0 : y1;
temp_line->next = NULL;
//更新et边表
if (aet[line_ymin - ymin].next == NULL) {
aet[line_ymin - ymin].next = temp_line;
}
else {
auto iter_et = aet[line_ymin - ymin].next;
while (iter_et->next != NULL) {
iter_et = iter_et->next;
}
iter_et->next = temp_line;
}
}
// 将ET边表拷贝到AET表中
/*for (auto iter_et : et) {
// 新创建一个y节点
START *new_start = new START;
new_start->y = iter_et.y;
new_start->next = NULL;
// 对ET表中的每个节点进行循环拷贝
AET* line_next;
auto iter_line = iter_et.next;
while (iter_line != NULL) {
AET* new_line = new AET;
new_line->k = iter_line->k;
new_line->next = NULL;
new_line->x = iter_line->x;
new_line->y_max = iter_line->y_max;
// 判断y是否等于ymax来确定是否加入ymax中
if (new_start->y!= iter_line->y_max) {
if (new_start->next == NULL) {
new_start->next = new_line;
line_next = new_line;
}
else {
line_next->next = new_line;
line_next = new_line;
}
}
iter_line = iter_line->next;
}
aet.push_back(*new_start);
}*/
//根据AET表依次更新，并删除y=ymax的边
for (vector<START>::iterator iter_aet = aet.begin(); iter_aet != aet.end() - 1; iter_aet++) {
// 获取迭代子下一个
auto next_iter = next(iter_aet);
// 获取下一行扫描的y值
int y = next_iter->y;
auto next_iter_end = next_iter->next;
// 获取下一个扫描行的末尾指针
while (next_iter_end != NULL and next_iter_end->next != NULL)
next_iter_end = next_iter_end->next;
auto iter_line = iter_aet->next;
float x, k;
int ymax;
while (iter_line != NULL) {
x = iter_line->x; ymax = iter_line->y_max; k = iter_line->k;
if (ymax != y) {
x += k;
AET* new_line = new AET;
new_line->k = k;
new_line->next = NULL;
new_line->x = x;
new_line->y_max = ymax;
if (next_iter_end == NULL) {
next_iter->next = new_line;
next_iter_end = new_line;
}
else {
next_iter_end->next = new_line;
next_iter_end = next_iter_end->next;
}
}
iter_line = iter_line->next;
}
}
// 至此，所有AET和ET表均构建完成
// 对AET表进行排序
for (auto &iter_aet : aet) {
iter_aet.next = insertionSortList(iter_aet.next);
}
// 直接开始填充
glColor3f(0.0f, 0.0f, 1.0f);
// 定义两个变量用于与dx和dy进行比对
int now_x = 0, now_y = 0;
// 此处取得第一个填充点的信息，以便于后续的奇偶判断
auto start_iter = aet.cbegin();
auto start_aet = start_iter->next;
int x0_temp = int(start_aet->x + 0.5);
auto aet_x_temp = start_aet->next;
int xmax_temp = int(start_aet->x + 0.5);
// 为了避免出现奇数，因此对x0和xmax进行奇偶判定
if (x0_temp % 2 != 0)
x0_temp += 1;
if (xmax_temp % 2 != 0)
xmax_temp += 1;
int flag_x = x0_temp % 2;
// 定义一个变量用于判断是否进行绘制
int flag = 0;
for (auto iter_aet = aet.cbegin(); iter_aet != aet.cend() - 1; iter_aet++) {
now_y += 1;
if (now_y != dy) {
continue;
}
now_y = 0;
int y = iter_aet->y;
auto aet_x = iter_aet->next;
while (aet_x != NULL) {
int x0 = int(aet_x->x + 0.5);
aet_x = aet_x->next;
int xmax = int(aet_x->x + 0.5);
// 为了避免出现奇数，因此对x0和xmax进行奇偶判定
if (x0 % 2 != 0)
x0 += 1;
if (xmax % 2 != 0)
xmax += 1;
// 每一行的第一个点默认进行绘制
now_x = dx - 1;
for (int i = x0; i < xmax; i ++) {
// 直接绘制矩形
now_x += 1;
if (now_x == dx) {
int flag_y;
flag_y = (y - ymin) / dy % 2;
int is_x = abs(i - x0_temp) % dx;
// 进行模式判断，品或者井
if (mode == 1) {
flag = 1;
now_x = 0;
}
else if (mode == 0 && is_x == 0 && flag_y == 0) {
flag = 1;
now_x = 0;
}
else if (mode == 0 && is_x == (dx + 1) / 2 && flag_y == 1) {
flag = 1;
now_x = 0;
}
else
now_x -= 1; // 此处else是为了避免该填充时now_x未归零
if (flag == 1) {
// 三角形
if (type == 1) {
glBegin(GL_TRIANGLES);
glVertex2d(2 * GLint(i), 2 * GLint(y));
glVertex2d(2 * GLint(i) + 1, 2 * GLint(y) + 2);
glVertex2d(2 * GLint(i) + 2, 2 * GLint(y));
glEnd();
}
// 正方形
else if (type == 2) {
glRectd(2 * GLint(i), 2 * GLint(y), 2 * GLint(i) + 2, 2 * GLint(y) + 2);
}
// 竖线
else if (type == 3) {
glBegin(GL_LINES);
glVertex2d(2 * GLint(i) + 1, 2 * GLint(y));
glVertex2d(2 * GLint(i) + 1, 2 * GLint(y) + 2);
glEnd();
}
// 正方形缺一角
else if (type == 4) {
glRectd(2 * GLint(i), 2 * GLint(y), 2 * GLint(i) + 1, 2 * GLint(y) + 1);
glRectd(2 * GLint(i), 2 * GLint(y) + 1, 2 * GLint(i) + 1, 2 * GLint(y) + 2);
glRectd(2 * GLint(i) + 1, 2 * GLint(y), 2 * GLint(i) + 2, 2 * GLint(y) + 1);
}
}
flag = 0;
}
// glVertex2d(i, y);
}
aet_x = aet_x->next;
}
}
glEnd();
// 最后绘制直线
glColor3f(0.0f, 0.0f, 0.0f);
glLineWidth(4.0f);
glBegin(GL_LINE_STRIP);
for (auto i : points) {
glVertex2d( 2 * i.x, 2 * i.y);
}
glVertex2d(2 * points[0].x, 2 * points[0].y);
glEnd();
glLineWidth(1.0f);
// 绘制顶点
glColor3f(1.0f, 0.0f, 0.0f);
for (auto i : points) {
glRectd(2 * i.x, 2 * i.y, 2 * i.x + 2, 2 * i.y + 2);
}
}