c++ 检测线与多边形关系

要检测一条直线与多边形之间的关系，需要进行以下步骤：

1. 将多边形的每个边与检测线进行交点计算，得到每个交点的坐标。

2. 对所有交点进行排序，按照从左到右的顺序排列。

3. 遍历每个交点，分别计算其左侧和右侧的交点个数。

4. 如果左侧和右侧交点个数都为奇数，则检测线与多边形相交；如果都为偶数，则检测线在多边形外部；如果一个为奇数，一个为偶数，则检测线与多边形相交于多边形的一个顶点。

以下是一个示例代码：

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

struct Point {
    double x, y;
};

struct Line {
    Point start, end;
};

// 计算两条线段的交点
Point getIntersection(Line l1, Line l2) {
    double x1 = l1.start.x, y1 = l1.start.y, x2 = l1.end.x, y2 = l1.end.y;
    double x3 = l2.start.x, y3 = l2.start.y, x4 = l2.end.x, y4 = l2.end.y;
    double d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
    double x = ((x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)) / d;
    double y = ((x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)) / d;
    return {x, y};
}

// 计算多边形的边与线段的交点
vector<Point> getIntersectionPoints(Line l, vector<Line> edges) {
    vector<Point> points;
    for (auto edge : edges) {
        Point p = getIntersection(l, edge);
        if (p.x >= min(edge.start.x, edge.end.x) && p.x <= max(edge.start.x, edge.end.x)
            && p.y >= min(edge.start.y, edge.end.y) && p.y <= max(edge.start.y, edge.end.y)) {
            points.push_back(p);
        }
    }
    return points;
}

// 判断点是否在多边形内部
bool isPointInsidePolygon(Point p, vector<Point> vertices) {
    bool inside = false;
    for (int i = 0, j = vertices.size() - 1; i < vertices.size(); j = i++) {
        if (((vertices[i].y > p.y) != (vertices[j].y > p.y)) &&
            (p.x < (vertices[j].x - vertices[i].x) * (p.y - vertices[i].y) / (vertices[j].y - vertices[i].y) + vertices[i].x)) {
            inside = !inside;
        }
    }
    return inside;
}

// 检测线段与多边形的关系
bool isLineInsidePolygon(Line l, vector<Point> vertices) {
    vector<Point> points = getIntersectionPoints(l, getEdges(vertices));
    sort(points.begin(), points.end(), [](Point a, Point b) { return a.x < b.x; });
    int leftCount = 0, rightCount = 0;
    for (auto point : points) {
        if (point.x < l.start.x) {
            leftCount++;
        } else if (point.x > l.end.x) {
            rightCount++;
        }
    }
    if (leftCount % 2 == 0 && rightCount % 2 == 0) {
        return false;
    } else if (leftCount % 2 == 1 && rightCount % 2 == 1) {
        return true;
    } else {
        return isPointInsidePolygon(l.start, vertices) || isPointInsidePolygon(l.end, vertices);
    }
}

// 获取多边形的边
vector<Line> getEdges(vector<Point> vertices) {
    vector<Line> edges;
    for (int i = 0, j = vertices.size() - 1; i < vertices.size(); j = i++) {
        edges.push_back({vertices[j], vertices[i]});
    }
    return edges;
}

int main() {
    vector<Point> polygon = {{0, 0}, {2, 0}, {2, 2}, {1, 3}, {0, 2}};
    Line line1 = {{0, 1}, {3, 1}};  // 与多边形相交
    Line line2 = {{-1, 1}, {1, 1}}; // 在多边形外部
    Line line3 = {{0, 0}, {2, 2}};  // 与多边形相交于顶点
    cout << isLineInsidePolygon(line1, polygon) << endl; // 1
    cout << isLineInsidePolygon(line2, polygon) << endl; // 0
    cout << isLineInsidePolygon(line3, polygon) << endl; // 1
    return 0;
}
``