c++实现射线法 点和闭合区域位置关系判断

#include <iostream>
#include <vector>

struct Point {
    double x;
    double y;
};

struct Polygon {
    std::vector<Point> vertices;
};


// 定义三个点的方向
// 0 --> 点 p, q, r 是共线的
// 1 --> 顺时针
// 2 --> 逆时针
int orientation(Point p, Point q, Point r) {
    double val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
  
    if (val == 0) return 0;  // 共线
    return (val > 0) ? 1: 2; // 顺时针或者逆时针
}

// 检查线段 'p1q1' 和 'p2q2' 是否相交
bool doIntersect(Point p1, Point q1, Point p2, Point q2) {
    // 判断线段 'p1q1' 和 'p2q2' 的四个点的方向
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);

    // 普通情况，四个方向都互不相同
    if (o1 != o2 && o3 != o4)
        return true;

    // 特殊情况，线段 'p1q1' 和 'p2q2' 的四个点是共线的
    if (o1 == 0 && onSegment(p1, p2, q1)) return true;
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;

    return false; // 线段 'p1q1' 和 'p2q2' 不相交
}


bool isInside(Point p, Polygon poly) {
    int n = poly.vertices.size();
    if (n < 3) return false;  // 如果多边形顶点数量小于3则无法形成封闭图形
    
    Point extreme = {INT_MAX, p.y};  // 极点，点到这个极点的直线将和所有的边进行比较
    
    int count = 0, i = 0;
    do {
        int next = (i+1)%n;
        
        // 检查线段(poly.vertices[i], poly.vertices[next])是否与线段(p, extreme)相交
        if (doIntersect(poly.vertices[i], poly.vertices[next], p, extreme)) {
            // 如果点在多边形的一个顶点上，返回 true
            if (orientation(poly.vertices[i], p, poly.vertices[next]) == 0)
                return onSegment(poly.vertices[i], p, poly.vertices[next]);
            count++;
        }
        i = next;
    } while (i != 0);
    
    // 如果 count 为奇数，返回 true
    return count & 1;
}

// 给定三个共线点 p, q, r，检查点 q 是否在线段 'pr' 上
bool onSegment(Point p, Point q, Point r) {
    if (q.x <= std::max(p.x, r.x) && q.x >= std::min(p.x, r.x) &&
        q.y <= std::max(p.y, r.y) && q.y >= std::min(p.y, r.y))
        return true;
    return false;
}


int main() {
    Polygon polygon = {{0, 0}, {10, 0}, {10, 10}, {0, 10}};
    Point p = {5, 5};
    if (isInside(p, polygon))
        std::cout << "Point is inside the polygon.";
    else
        std::cout << "Point is outside the polygon.";
    return 0;
}