C++怎么实现快速多边形填充算法

快速多边形填充算法（Scanline Fill Algorithm）是一种常见的多边形填充算法，可以用于计算机图形学中的填充、着色等应用场景。下面是 C++ 实现的步骤：

1. 定义多边形的顶点坐标数组。

2. 找到多边形的最大和最小 Y 坐标，作为扫描线的起点和终点。

3. 从最小 Y 坐标开始，向上逐行扫描，找到每一条扫描线与多边形的交点。

4. 通过判断交点的奇偶性确定当前扫描线是否在多边形内部。

5. 如果当前扫描线在多边形内部，则将该扫描线上的像素点填充。

6. 重复步骤 3~5 直到扫描到最大 Y 坐标结束。

下面是一个简单的 C++ 实现示例：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Point {
    int x, y;
    Point(int x = 0, int y = 0):x(x), y(y) {}
};

bool operator<(const Point& a, const Point& b) {
    return a.y < b.y || (a.y == b.y && a.x < b.x);
}

bool operator==(const Point& a, const Point& b) {
    return a.x == b.x && a.y == b.y;
}

int main() {
    int n;
    cin >> n;
    vector<Point> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i].x >> p[i].y;
    }
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    n = p.size();
    for (int i = 0; i < n; i++) {
        if (p[i] == p[(i+1)%n]) {
            p.erase(p.begin()+i);
            n--;
            i--;
        }
    }
    int ymin = p[0].y, ymax = p[0].y;
    for (int i = 1; i < n; i++) {
        if (p[i].y < ymin) ymin = p[i].y;
        if (p[i].y > ymax) ymax = p[i].y;
    }
    for (int y = ymin; y <= ymax; y++) {
        vector<int> xs;
        for (int i = 0; i < n; i++) {
            int j = (i+1)%n;
            if (p[i].y == p[j].y) continue;
            if (p[i].y > p[j].y) swap(i, j);
            if (y >= p[i].y && y < p[j].y) {
                double x = p[i].x + (double)(y-p[i].y)*(p[j].x-p[i].x)/(p[j].y-p[i].y);
                xs.push_back((int)x);
            }
        }
        sort(xs.begin(), xs.end());
        for (int i = 0; i < (int)xs.size(); i += 2) {
            cout << xs[i] << " " << y << endl;
            // 在这里可以填充像素点
        }
    }
    return 0;
}

上述示例中，首先读入多边形的顶点坐标，然后对其进行去重和排序。接着找到多边形的最大和最小 Y 坐标，逐行扫描多边形，找到与当前扫描线相交的点，最后根据交点的奇偶性决定是否填充像素点。