线段和 多边形交点 C++源代码

以下是求线段和多边形交点的C++代码，使用了向量叉积的方法：

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

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

typedef Point Vector;

Vector operator+(Vector A, Vector B) {
    return Vector(A.x + B.x, A.y + B.y);
}

Vector operator-(Point A, Point B) {
    return Vector(A.x - B.x, A.y - B.y);
}

Vector operator*(Vector A, double p) {
    return Vector(A.x * p, A.y * p);
}

double Dot(Vector A, Vector B) {
    return A.x * B.x + A.y * B.y;
}

double Cross(Vector A, Vector B) {
    return A.x * B.y - A.y * B.x;
}

bool OnSegment(Point p, Point a1, Point a2) {
    return Cross(a1 - p, a2 - p) == 0 && Dot(a1 - p, a2 - p) < 0;
}

int InsidePolygon(Point p, vector<Point> poly) {
    int n = poly.size(), wn = 0;
    for (int i = 0; i < n; i++) {
        Point v1 = poly[i], v2 = poly[(i + 1) % n];
        if (OnSegment(p, v1, v2)) return -1; // 点在边界上
        if (v1.y <= p.y) { // 从左侧进入或从右侧出发
            if (v2.y > p.y && Cross(v2 - v1, p - v1) > 0) wn++;
        } else { // 从左侧出发或从右侧进入
            if (v2.y <= p.y && Cross(v2 - v1, p - v1) < 0) wn--;
        }
    }
    return wn == 0 ? 0 : 1; // wn为正在内部，为负在外部，为零在边界上
}

Point GetLineIntersection(Point P, Vector v, Point Q, Vector w) {
    Vector u = P - Q;
    double t = Cross(w, u) / Cross(v, w);
    return P + v * t;
}

vector<Point> GetPolyIntersection(vector<Point> poly, Point A, Point B) {
    poly.push_back(poly[0]);
    vector<Point> res;
    int n = poly.size();
    for (int i = 0; i < n - 1; i++) {
        Point C = poly[i], D = poly[i + 1];
        if (Cross(B - A, C - A) * Cross(B - A, D - A) < 0 &&
            Cross(D - C, A - C) * Cross(D - C, B - C) < 0) {
            res.push_back(GetLineIntersection(A, B - A, C, D - C));
        }
    }
    return res;
}

int main() {
    vector<Point> poly{{0, 0}, {0, 2}, {2, 2}, {2, 0}};
    Point A(1, 1), B(3, 1);
    vector<Point> res = GetPolyIntersection(poly, A, B);
    for (auto p : res) {
        cout << "(" << p.x << ", " << p.y << ")" << endl;
    }
    return 0;
}

其中，`InsidePolygon`函数用于判断点是否在多边形内部，返回值分别表示在外部、边界上和内部。`GetLineIntersection`函数用于求得线段AB和CD的交点。`GetPolyIntersection`函数用于求得线段AB和多边形的交点。以上三个函数都使用了向量叉积的方法。