多边形扫描转换-扫描线算法

#include <graphics.h>
#include <vector>
#include <algorithm>
#include<iostream>
using namespace std;
 
struct EdgeNode {
    int ymin;  // 边的最小y坐标
    double x;  // 当前x坐标
    double dx; // △x
    int ymax;  // 边的最大y坐标
};
 
void polygon_fill(vector<vector<int>>& polygon) {//i*2矩阵
    int y_min = INT_MAX;
    int y_max = INT_MIN;
 
    // 找到多边形的最小和最大y坐标
    for (const auto& point : polygon) {
        y_min = min(y_min, point[1]);
        y_max = max(y_max, point[1]);
    }
 
    vector<vector<EdgeNode>> NET(y_max + 1); 
 
    // 构造NET
    for (int i = 0; i < polygon.size(); i++) {
        int next_idx = (i + 1) % polygon.size();
        int x1 = polygon[i][0];
        int y1 = polygon[i][1];
        int x2 = polygon[next_idx][0];
        int y2 = polygon[next_idx][1];
 
        int ymin = min(y1, y2);
        int ymax = max(y1, y2);
        double dx = (double)(x2 - x1) / (y2 - y1);// △x
 
        if (ymax != ymin) {
            if (ymin == y1) {
                NET[ymin].push_back({ ymin, (double) (x1), dx, ymax });
            }
            else if (ymin == y2) {
                NET[ymin].push_back({ ymin, (double)(x2), dx, ymax });
            }
        }
    }
 
    vector<EdgeNode> AET; 
    //int ynow = y_min; // 当前扫描线号
 
    for (int i = y_min; i <= y_max; i++) { // 对每一条扫描线
        for (auto& edge : NET[i]) { // 把ymin=i的边放入AET
            if (edge.ymin == i) {
                AET.push_back(edge);
            }
        }
    }
    for (int i = y_min; i <= y_max; i++) { // 对每一条扫描线
        // 使用插入排序法对AET按x坐标递增顺序排序
        for (int j = 1; j < AET.size(); j++) {
            int k = j - 1;
            EdgeNode key = AET[j];
            while (k >= 0 && AET[k].x > key.x) {
                AET[k + 1] = AET[k];
                k--;
            }
 
            AET[k + 1] = key;
        }
 
        // 若允许多边形的边自交，用冒泡排序法对AET重新排序
        for (int j = 0; j < AET.size() - 1; j++) {
            for (int k = 0; k < AET.size() - j - 1; k++) {
                if (AET[k].x > AET[k + 1].x) {
                    swap(AET[k], AET[k + 1]);
                }
            }
        }
        // 遍历AET，找到配对的交点并填色
        for (int j = 0; j < AET.size(); j += 2) {
            int x_start = (int)(ceil(AET[j].x));
            int x_end = (int)(ceil(AET[j + 1].x));
 
            for (int x = x_start; x < x_end; x++) {
                putpixel(x, i, WHITE);
            }
        }
 
        // 遍历AET，更新x值，删除ymax=i的边
        vector<EdgeNode> new_AET;
        for (const auto& edge : AET) {
            if (edge.ymax > i) {
                EdgeNode new_edge = edge;
                new_edge.x += new_edge.dx;
                new_AET.push_back(new_edge);
            }
        }
        AET = new_AET;
    }
}
 
int main() {
    initgraph(800, 480);
 
    vector<vector<int>> polygon = { {100,200}, {200,200}, {150,150} };//三角形
    polygon_fill(polygon);
 
   polygon = { {300,150},{300,200}, {500,200 },{500,150}};//矩形
    polygon_fill(polygon);
 
    polygon = { {600,150}, {630,200 },{600,200},{630,150} };//漏斗形
    polygon_fill(polygon);
    system("pause");
    closegraph();
    return 0;
}