🕺作者： 主页

我的专栏
C语言从0到1
探秘C++
数据结构从0到1
探秘Linux

😘欢迎关注：👍点赞🙌收藏✍️留言

🏇码字不易，你的👍点赞🙌收藏❤️关注对我真的很重要，有问题可在评论区提出，感谢支持！！！

实验二、用扫描线算法实现多边形填充

一、实验目的及要求

本实验旨在掌握扫描线算法的原理和实现方法，通过编写程序实现多边形的填充。

二、实验设备

• Microsoft Visual Studio 2022

三、实验原理

扫描线算法是一种用于填充多边形的算法，其基本思想是将多边形分解成若干个梯形区域，然后对每个梯形区域进行填充。在填充时，扫描线从上往下扫描，逐个像素点地判断当前点是否位于多边形内部，并根据需要进行颜色填充。

四、实验方法与步骤

1. 算法思想

扫描线填充算法是一种计算机图形学中用于实现多边形填充的算法。它基于对多边形的扫描线进行处理，将多边形分割成一系列水平线段，并确定每条线段覆盖的像素点是否在多边形内部，从而实现多边形的填充。

2. 算法步骤

• 定义多边形数据结构，存储多边形的顶点信息。
• 根据多边形的顶点信息，计算出多边形每条边的斜率和截距等信息，并存储在一个表格中。
• 从多边形最高点开始，以每行像素点为单位，向下扫描直到最低点。
• 对于每个扫描线，遍历保存边信息的表格，计算出当前扫描线和各条边的交点，将这些交点按照x坐标大小排序并两两配对。
• 对每一对交点之间的像素点进行填充。
• 重复以上步骤，直到扫描线扫描完成。

3. 代码

// 多边形数据结构
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());
    }
}

五、实验结果

1. 扫描填充算法运行结果

六、结论

本实验是通过扫描线算法来实现多边形的填充。首先定义了多边形和边的数据结构，并且根据多边形的顶点信息计算出每条边的斜率和截距等信息，存储在一个表格中。然后从多边形最高点开始，以每行像素点为单位，向下扫描直到最低点。对于每个扫描线，遍历保存边信息的表格，计算出当前扫描线和各条边的交点，将这些交点按照x坐标大小排序并两两配对，然后对每一对交点之间的像素点进行填充。最后重复以上步骤，直到扫描线扫描完成。这种算法的优势在于可以处理任意形状的多边形，而不仅限于凸多边形。算法的时间复杂度为O(nlogn)，其中n为多边形的边数。本次实验的结果是成功实现了多边形的填充。