C++ 判断点是否在多边形内：射线法实现

本文将介绍使用射线法判断一个点是否在多边形内的 C++ 代码实现。该方法通过计算从给定点向右水平方向延伸的射线与多边形边的交点个数来判断点是否在多边形内。

代码示例：

#include <iostream>
#include <algorithm>

using namespace std;

struct Point {
    int x;
    int y;
};

struct Side {
    Point start;
    Point end;
};

// 判断两条线段是否平行于 x 轴
bool isParallel(double slope) {
    return slope == 0 || slope == std::numeric_limits<double>::infinity();
}

// 判断点是否在边上
bool isOnSide(Point p, Side s) {
    return (p.x >= std::min(s.start.x, s.end.x) && p.x <= std::max(s.start.x, s.end.x)) &&
           (p.y >= std::min(s.start.y, s.end.y) && p.y <= std::max(s.start.y, s.end.y));
}

// 判断射线与边是否相交
bool isIntersecting(Point p, Side s) {
    double slope = (s.end.y - s.start.y) / (s.end.x - s.start.x);
    double y_intercept = s.start.y - slope * s.start.x;
    return p.y < slope * p.x + y_intercept;
}

// 计算交点个数
int countIntersections(Point p, Side Sides[], int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (!isParallel((Sides[i].end.y - Sides[i].start.y) / (Sides[i].end.x - Sides[i].start.x))) {
            if (isOnSide(p, Sides[i])) {
                count++;
            }
            else if (isIntersecting(p, Sides[i])) {
                count++;
            }
            else if ((p.y == Sides[i].start.y || p.y == Sides[i].end.y) && p.x >= std::min(Sides[i].start.x, Sides[i].end.x) && p.x <= std::max(Sides[i].start.x, Sides[i].end.x)) {
                if (Sides[i].start.y < Sides[i].end.y) {
                    if (p.y == Sides[i].start.y) {
                        continue;
                    }
                    else {
                        count++;
                    }
                }
                else {
                    if (p.y == Sides[i].start.y) {
                        count++;
                    }
                    else {
                        continue;
                    }
                }
            }
        }
    }
    return count;
}

int main() {
    Point p = { 2, 1 };
    Side Sides[] = { {{0, 0}, {2, 0}}, {{2, 0}, {1, 1}},{{1, 1}, {2, 2}}, {{2, 2}, {0, 2}}, {{0, 2}, {0, 0}} };
    int n = sizeof(Sides) / sizeof(Sides[0]);
    int intersections = countIntersections(p, Sides, n);
    if (intersections % 2 == 1) {
        printf("点在多边形内\n");
    }
    else {
        printf("点在多边形外\n");
    }
    return 0;
}

解释：

countIntersections() 函数：该函数计算从给定点 p 向右水平方向延伸的射线与多边形边的交点个数。
循环遍历多边形的每条边：对于每条边，首先判断边是否平行于 x 轴，如果平行则不计算交点。
判断点是否在边上：如果点在边上，则计数器加 1。
判断射线与边是否相交：如果射线与边相交，则计数器加 1。
处理射线穿过端点的情况：如果射线穿过端点，则根据边的方向和端点的坐标进行判断，决定是否计数。
判断点是否在多边形内：如果交点个数为奇数，则点在多边形内；如果交点个数为偶数，则点在多边形外。

示例：

在上面的代码中，点 (2, 1) 与多边形的5条边分别相交了1次、0次、1次、1次、1次，交点个数为奇数，因此点在多边形内。

总结：

射线法是一种简单且有效的判断点是否在多边形内的算法，通过计算射线与多边形边的交点个数，可以快速得出判断结果。该算法易于理解和实现，适用于各种场景。