多边形的扫描转换 c++

多边形扫描转换算法是将一个任意多边形转换为一系列水平扫描线与多边形的交点，然后根据这些交点构造出多边形的填充区域。以下是一个用 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);
}

struct Edge {
    Point a, b;
    Edge(const Point& a = Point(), const Point& b = Point()) : a(a), b(b) {}
};

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

vector<Point> intersection(const Edge& e1, const Edge& e2) {
    vector<Point> res;
    int x1 = e1.a.x, y1 = e1.a.y, x2 = e1.b.x, y2 = e1.b.y;
    int x3 = e2.a.x, y3 = e2.a.y, x4 = e2.b.x, y4 = e2.b.y;
    int d = (x1-x2)*(y3-y4)-(y1-y2)*(x3-x4);
    if (d == 0) return res;
    int x = ((x1*y2-y1*x2)*(x3-x4)-(x1-x2)*(x3*y4-y3*x4))/d;
    int y = ((x1*y2-y1*x2)*(y3-y4)-(y1-y2)*(x3*y4-y3*x4))/d;
    if (x < min(x1, x2) || x > max(x1, x2)) return res;
    if (x < min(x3, x4) || x > max(x3, x4)) return res;
    res.push_back(Point(x, y));
    return res;
}

vector<Point> scanline(const vector<Edge>& edges) {
    vector<Point> res;
    vector<pair<Point,int>> pts;
    for (size_t i = 0; i < edges.size(); i++) {
        if (edges[i].a.y == edges[i].b.y) continue;
        if (edges[i].a.y > edges[i].b.y) swap(edges[i].a, edges[i].b);
        pts.push_back({ edges[i].a, 1 });
        pts.push_back({ edges[i].b, -1 });
    }
    sort(pts.begin(), pts.end());
    int cnt = 0;
    for (size_t i = 0; i < pts.size(); i++) {
        if (cnt > 0) res.push_back(pts[i].first);
        cnt += pts[i].second;
    }
    return res;
}

vector<Point> polygonFill(const vector<Point>& polygon) {
    vector<Edge> edges;
    for (size_t i = 0; i < polygon.size(); i++) {
        edges.push_back(Edge(polygon[i], polygon[(i+1)%polygon.size()]));
    }
    sort(edges.begin(), edges.end());
    vector<Point> res;
    for (int y = edges[0].a.y; y <= edges.back().b.y; y++) {
        vector<Edge> activeEdges;
        for (size_t i = 0; i < edges.size(); i++) {
            if (edges[i].a.y <= y && edges[i].b.y >= y) {
                activeEdges.push_back(edges[i]);
            }
        }
        sort(activeEdges.begin(), activeEdges.end(),
             [](const Edge& a, const Edge& b) {
                 return (a.a.x + a.b.x) < (b.a.x + b.b.x);
             });
        vector<Point> pts;
        for (size_t i = 0; i < activeEdges.size(); i++) {
            auto tmp = intersection(activeEdges[i], edges[(i-1+activeEdges.size())%activeEdges.size()]);
            pts.insert(pts.end(), tmp.begin(), tmp.end());
        }
        auto scanPts = scanline(activeEdges);
        pts.insert(pts.end(), scanPts.begin(), scanPts.end());
        sort(pts.begin(), pts.end());
        for (size_t i = 0; i < pts.size(); i++) {
            if (i == 0 || !(pts[i].x == pts[i-1].x && pts[i].y == pts[i-1].y)) {
                res.push_back(pts[i]);
            }
        }
    }
    return res;
}

int main() {
    vector<Point> polygon = { {0,0}, {5,0}, {5,5}, {3,2}, {2,5}, {0,5} };
    vector<Point> fill = polygonFill(polygon);
    for (const auto& p : fill) {
        cout << "(" << p.x << "," << p.y << ")" << endl;
    }
    return 0;
}

上述代码中，`Point` 表示一个二维平面上的点，`Edge` 表示一个多边形边界上的线段。`intersection` 函数用于计算两条线段的交点，`scanline` 函数用于计算一条水平扫描线与多边形的交点，`polygonFill` 函数用于进行多边形扫描转换，返回一个包含填充点的向量。在 `main` 函数中，我们构造了一个六边形，然后进行填充并输出结果。