用c++实现射线法判断一个点是否在一个图形内

射线法又称“点与多边形判断法”，它的基本思想是从该点向任意方向引一条射线，统计该射线与多边形边交点的个数，如果为奇数，则该点在多边形内，如果为偶数，则该点在多边形外。

用C++实现射线法判断一个点是否在一个图形内的代码如下：

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

struct Point {
    double x, y;
};

// 计算向量叉积
double cross_product(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

// 判断点是否在多边形内
bool point_in_polygon(Point p, vector<Point>& polygon) {
    int count = 0;
    int n = polygon.size();
    for (int i = 0; i < n; i++) {
        Point a = polygon[i];
        Point b = polygon[(i + 1) % n];
        if (a.y == b.y) continue;
        if (p.y < min(a.y, b.y)) continue;
        if (p.y >= max(a.y, b.y)) continue;
        double x = (p.y - a.y) * (b.x - a.x) / (b.y - a.y) + a.x;
        if (x > p.x) count++;
    }
    return (count % 2 == 1);
}

int main() {
    Point p = {1, 1};
    vector<Point> polygon = {{0, 0}, {2, 0}, {2, 2}, {0, 2}};
    bool result = point_in_polygon(p, polygon);
    if (result) {
        cout << "The point is in the polygon." << endl;
    } else {
        cout << "The point is not in the polygon." << endl;
    }
    return 0;
}

这里的 `cross_product()` 函数用于计算向量的叉积，用于判断两条线段是否相交。而 `point_in_polygon()` 函数则是核心函数，用于判断点是否在多边形内。该函数针对每条线段进行判断，如果该线段与射线相交，则统计交点的个数。最终，根据交点的个数是奇数还是偶数来返回判断结果。