线与多边形关系 c++实现

以下是C++实现线与多边形关系的代码：

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

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

typedef Point Vector;

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

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

int IsPointInPolygon(Point p, vector<Point>& poly) {
    int wn = 0;
    int n = poly.size();
    for (int i = 0; i < n; i++) {
        Point& p1 = poly[i];
        Point& p2 = poly[(i + 1) % n];
        if (p == p1 || p == p2) return 1; // 点在多边形顶点上
        if (p.y >= min(p1.y, p2.y) && p.y < max(p1.y, p2.y)) {
            int x = p1.x + (p2.x - p1.x) * (p.y - p1.y) / (p2.y - p1.y);
            if (x == p.x) return 1; // 点在多边形边上
            if (x > p.x) wn++;
        }
    }
    return wn & 1; // 点在多边形内部
}

int main() {
    vector<Point> poly;
    poly.push_back(Point(0, 0));
    poly.push_back(Point(2, 0));
    poly.push_back(Point(2, 2));
    poly.push_back(Point(1, 1));
    poly.push_back(Point(0, 2));
    Point p1(1, 1);
    Point p2(3, 3);
    cout << IsPointInPolygon(p1, poly) << endl; // 输出1
    cout << IsPointInPolygon(p2, poly) << endl; // 输出0
    return 0;
}

在上述代码中，我们定义了一个Point结构体表示一个点，以及一个Vector类型表示一个向量。我们还重载了-运算符，使得可以方便地计算两个点之间的向量。

我们实现了一个IsPointInPolygon函数，它接受一个点和一个多边形，判断这个点是否在多边形内部。具体思路如下：

1. 遍历多边形的所有边，判断点是否在边上或者顶点上，如果是直接返回1（点在多边形内部）。
2. 对于每条边，如果点的y坐标在边的y坐标范围内，计算出点在边上的x坐标，如果点的x坐标等于边上的x坐标，说明点在边上，直接返回1。
3. 如果点的x坐标大于这个x坐标，说明点在边的右侧，做上升射线与多边形的交点数加1。
4. 最终判断交点数是否为奇数，是则点在多边形内部，否则点在多边形外部。

我们在main函数中测试了IsPointInPolygon函数，分别传入两个点，一个在多边形内部，一个在多边形外部，并输出结果