在C++中编写代码实现扫描线填充算法

好的，下面是 C++ 中实现扫描线填充算法的示例代码：

#include <vector>
#include <algorithm>

// 定义二维点结构体
struct Point {
    int x;
    int y;
};

/**
 * 扫描线填充算法
 * @param points 二维点集合，按照逆时针顺序排列
 */
void scanlineFill(std::vector<Point>& points) {
    // 找出最小和最大的 y 坐标
    int minY = points[0].y;
    int maxY = points[0].y;
    for (const auto& p : points) {
        minY = std::min(minY, p.y);
        maxY = std::max(maxY, p.y);
    }

    // 初始化活性边表和交点表
    std::vector<std::vector<int>> aet(maxY - minY + 1);
    std::vector<std::vector<int>> iet(maxY - minY + 1);

    // 将点集合按照边排序
    std::vector<std::pair<Point, Point>> edges;
    int n = points.size();
    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;
        if (points[i].y != points[j].y) {
            if (points[i].y < points[j].y) {
                edges.push_back({points[i], points[j]});
            } else {
                edges.push_back({points[j], points[i]});
            }
        }
    }
    std::sort(edges.begin(), edges.end(), [](const auto& e1, const auto& e2) {
        return e1.first.y < e2.first.y;
    });

    // 扫描线从最小的 y 坐标开始
    int y = minY;
    while (y <= maxY) {
        // 将新的边加入活性边表
        for (const auto& e : edges) {
            if (e.first.y == y) {
                int x = e.first.x;
                int dy = e.second.y - e.first.y;
                int dx = e.second.x - e.first.x;
                int sign = (dx > 0 ? 1 : -1);
                int k = sign * (dx * (y - e.first.y)) / dy + e.first.x;
                aet[y - minY].push_back(k);
            }
        }

        // 按照 x 坐标排序
        std::sort(aet[y - minY].begin(), aet[y - minY].end());

        // 将所有交点加入交点表
        for (int i = 0; i < aet[y - minY].size(); i += 2) {
            iet[y - minY].push_back(aet[y - minY][i]);
            iet[y - minY].push_back(aet[y - minY][i+1]);
        }

        // 从交点表中填充像素
        std::sort(iet[y - minY].begin(), iet[y - minY].end());
        for (int i = 0; i < iet[y - minY].size(); i += 2) {
            int x1 = iet[y - minY][i];
            int x2 = iet[y - minY][i+1];
            for (int x = x1; x <= x2; x++) {
                // 在此处填充像素
            }
        }

        // 将不再跨越扫描线的边从活性边表中移除
        for (int i = 0; i < aet[y - minY].size(); i += 2) {
            int x1 = aet[y - minY][i];
            int x2 = aet[y - minY][i+1];
            if (y == maxY) {
                // 最后一行需要特殊处理，否则会出现缺口
                for (int x = x1; x <= x2; x++) {
                    // 在此处填充像素
                }
            }
            if (y >= e.second.y) {
                aet[y - minY].erase(aet[y - minY].begin()+i, aet[y - minY].begin()+i+1);
            }
        }

        // 更新交点表
        for (int i = 0; i < iet[y - minY].size(); i++) {
            if (y >= e.second.y) {
                iet[y - minY].erase(iet[y - minY].begin()+i, iet[y - minY].begin()+i+1);
            } else {
                iet[y - minY][i] += (e.second.x - e.first.x) / (e.second.y - e.first.y);
            }
        }

        // 更新扫描线位置
        y++;
    }
}

其中，`Point` 结构体定义了二维点的坐标，`scanlineFill` 函数实现了扫描线填充算法。该算法首先找出最小和最大的 y 坐标，然后将点集合按照边排序，从最小的 y 坐标开始扫描线，将新的边加入活性边表，按照 x 坐标排序，将所有交点加入交点表，从交点表中填充像素，将不再跨越扫描线的边从活性边表中移除，更新交点表和扫描线位置，直到扫描线扫描完整个图形。这样，就可以实现对任意简单封闭多边形的填充。