描述多边形扫描转换的扫描线算法并写伪码

多边形扫描转换的扫描线算法是一种常用于计算机图形学中的多边形填充算法。其基本思想是将多边形沿着 y 轴方向分割成若干条线段，然后从上往下逐条扫描，使用扫描线与多边形边界的交点来确定多边形内部的区域，并进行填充。

以下是多边形扫描转换的扫描线算法的伪代码：

// 输入多边形的顶点列表 vertices，以及多边形边界的最大和最小 y 坐标值 ymax 和 ymin
ScanLineFill(vertices, ymax, ymin) {
    // 定义边表结构体，用于存储多边形边界的信息
    struct Edge {
        float x; // 边界与扫描线的交点的 x 坐标
        float dx; // 边界的斜率的倒数
        int ymax; // 边界的最大 y 坐标
    };

    // 定义活动边表和等待边表
    vector<Edge> AET, NET;

    // 从最小 y 坐标开始，逐条扫描每条扫描线
    for (int y = ymin; y <= ymax; y++) {
        // 将所有与当前扫描线有交点的边界添加到等待边表中
        for (int i = 0; i < vertices.size(); i++) {
            if (vertices[i].y == y) {
                // 如果多边形的顶点与当前扫描线重合，则将该顶点作为交点添加到等待边表中
                Edge e;
                e.x = vertices[i].x;
                e.dx = 0;
                e.ymax = vertices[i].y;
                NET.push_back(e);
            }
            else if (vertices[i].y == y-1) {
                // 如果多边形的边界与当前扫描线相交，则计算交点并添加到等待边表中
                Edge e;
                if (vertices[i].y < vertices[(i+1)%vertices.size()].y) {
                    e.x = vertices[i].x + (vertices[(i+1)%vertices.size()].x - vertices[i].x) * (y - vertices[i].y) / (vertices[(i+1)%vertices.size()].y - vertices[i].y);
                } else {
                    e.x = vertices[i].x + (vertices[(i+1)%vertices.size()].x - vertices[i].x) * (y - vertices[(i+1)%vertices.size()].y) / (vertices[i].y - vertices[(i+1)%vertices.size()].y);
                }
                e.dx = (vertices[(i+1)%vertices.size()].x - vertices[i].x) / (vertices[(i+1)%vertices.size()].y - vertices[i].y);
                e.ymax = max(vertices[i].y, vertices[(i+1)%vertices.size()].y) - 1;
                NET.push_back(e);
            }
        }

        // 根据交点的 x 坐标对等待边表进行排序
        sort(NET.begin(), NET.end(), [](const Edge& a, const Edge& b) {
            return a.x < b.x;
        });

        // 将等待边表中的边界添加到活动边表中
        for (int i = 0; i < NET.size(); i++) {
            AET.push_back(NET[i]);
        }
        NET.clear();

        // 根据交点的 x 坐标对活动边表进行排序
        sort(AET.begin(), AET.end(), [](const Edge& a, const Edge& b) {
            return a.x < b.x;
        });

        // 遍历活动边表，将两两相邻的边界之间的区域进行填充
        for (int i = 0; i < AET.size(); i += 2) {
            int x1 = ceil(AET[i].x);
            int x2 = floor(AET[i+1].x);
            for (int x = x1; x <= x2; x++) {
                drawPixel(x, y);
            }
        }

        // 更新活动边表中每条边界的交点 x 坐标
        for (int i = 0; i < AET.size(); i++) {
            AET[i].x += AET[i].dx;
        }

        // 删除活动边表中 ymax 达到当前扫描线的边界
        for (int i = 0; i < AET.size(); i++) {
            if (AET[i].ymax == y) {
                AET.erase(AET.begin() + i);
                i--;
            }
        }
    }
}

其中，`drawPixel(x, y)` 是用来填充像素点的函数，可以根据具体的实现方式来定义。