【计算机图形学】实验二 用扫描线算法实现多边形填充

// 多边形数据结构
struct Polygon {
    int numVertices; // 多边形顶点数
    int vertices[100][2]; // 多边形顶点坐标
};

// 边数据结构
struct Edge {
    double x; // 边与扫描线的交点x坐标
    double slope; // 边斜率倒数
    int ymax; // 边在扫描线之上的端点y坐标
};

// 填充多边形
void FillPolygon(Polygon poly) {
    // 计算多边形顶点中的最大和最小y坐标
    int maxY = INT_MIN, minY = INT_MAX;
    for (int i = 0; i < poly.numVertices; i++) {
        if (poly.vertices[i][1] > maxY) {
            maxY = poly.vertices[i][1];
        }
        if (poly.vertices[i][1] < minY) {
            minY = poly.vertices[i][1];
        }
    }

    // 创建边表，存储所有的边信息
    vector<Edge> edgeTable;
    for (int i = 0; i < poly.numVertices; i++) {
        Edge e;
        // 获取当前边和下一个顶点的坐标
        int x1 = poly.vertices[i][0], y1 = poly.vertices[i][1];
        int x2 = poly.vertices[(i + 1) % poly.numVertices][0], y2 = poly.vertices[(i + 1) % poly.numVertices][1];

        // 如果y1 == y2，说明该边不需要加入边表
        if (y1 == y2) {
            continue;
        }

        // 如果y2 < y1，则交换两个顶点的坐标
        if (y2 < y1) {
            swap(x1, x2);
            swap(y1, y2);
        }

        // 计算出边与扫描线的交点x坐标和斜率倒数
        e.x = x1;
        e.slope = (double)(x2 - x1) / (y2 - y1);
        e.ymax = y2 - 1;

        // 将边加入边表中
        edgeTable.push_back(e);
    }

    // 对边表按照交点x坐标排序
    sort(edgeTable.begin(), edgeTable.end(), [](const Edge& a, const Edge& b) { return a.x < b.x; });

    // 创建活动边表，存储所有与当前扫描线有交点的边信息
    vector<Edge> activeEdgeTable;

    // 从多边形最高点开始，逐行扫描
    for (int y = maxY; y >= minY; y--) {
        // 将与当前扫描线有交点的边加入活动边表中
        for (int i = 0; i < edgeTable.size(); i++) {
            if (edgeTable[i].ymax >= y) {
                activeEdgeTable.push_back(edgeTable[i]);
            }
        }

        // 按照交点x坐标排序
        sort(activeEdgeTable.begin(), activeEdgeTable.end(), [](const Edge& a, const Edge& b) { return a.x < b.x; });

        // 填充扫描线
        int x1 = INT_MAX, x2 = INT_MIN;
        for (int i = 0; i < activeEdgeTable.size(); i += 2) {
            x1 = (int)ceil(activeEdgeTable[i].x);
            x2 = (int)floor(activeEdgeTable[i + 1].x);

            // 如果是偶数条边，则说明有完整的矩形区域需要填充
            if (i + 1 < activeEdgeTable.size()) {
                for (int x = x1; x <= x2; x++) {
                    SetPixel(x, y);
                }
            }
        }

        // 更新活动边表
        for (int i = 0; i < activeEdgeTable.size(); i++) {
            activeEdgeTable[i].x += activeEdgeTable[i].slope;
            activeEdgeTable[i].ymax--;
        }

        // 从活动边表中移除不再与扫描线相交的边
        activeEdgeTable.erase(remove_if(activeEdgeTable.begin(), activeEdgeTable.end(), [](const Edge& a) { return a.ymax <= 0; }), activeEdgeTable.end());
    }
}