C++如何判断一个点是否在多边形内_C++计算几何射线法实现【逻辑】

射线法判断点在多边形内当且仅当水平向右射线与边界交点个数为奇数；需严谨处理顶点穿越、水平边、浮点精度，用带容差的区间检查和严格跨越判定，避免除零与误判。

射线法核心逻辑：交点奇偶性判断

点在多边形内，当且仅当从该点向任意方向（通常取水平向右）引一条射线，与多边形边界的交点个数为奇数。关键不在于“射线要长”，而在于“如何准确计数——尤其当射线经过顶点或与边共线时”。

常见错误是直接用 y 坐标比较判断是否相交，却忽略以下情况：射线穿过顶点、射线与水平边重合、浮点精度导致边界误判。

• 只考虑严格跨越：对每条边 (v[i], v[i+1])，先检查是否满足 min(y0, y1) （注意是左开右闭），排除水平边和完全在射线上方/下方的边
• 再计算交点横坐标 px_cross，仅当 px_cross > px 才计为一次有效穿越
• 顶点处理：若 py == y0 且 y0 == y1（水平边），跳过；若 py == y0 且 y0 != y1，仅当 y1 > y0（即该顶点是边的下端点）才参与计数，避免重复或遗漏

C++实现中必须处理的浮点陷阱

用 double 或 float 表示坐标时，直接比较 == 或用 /> 判定边界极易出错。例如 py == y0 几乎不可能成立，但你需要知道它“是否足够接近”。

推荐做法不是引入大 epsilon 全局容差，而是分场景处理：

立即学习“C++免费学习笔记（深入）”；

影像之匠PixPretty

商业级AI人像后期软件，专注于人像精修，色彩调节及批量图片编辑，支持Windows、Mac多平台使用。适用于写真、婚纱、旅拍、外景等批量修图场景。

下载

• 对垂直方向判断（如 py 是否在边的 y 范围内），用带容差的区间检查：if (std::min(y0, y1) - eps
• 对交点计算后的 px_cross > px 比较，**仍用严格大于**，因为射线是向右无限延伸的数学射线，容差会污染奇偶性逻辑
• 定义 const double eps = 1e-9;，并在所有涉及坐标的几何比较中显式使用，不依赖 std::numeric_limits 动态生成

代码结构建议：封装成可复用的 inline 函数

不要把射线法逻辑写进主循环里。一个清晰、无副作用的判断函数能大幅降低调试成本。

inline bool pointInPolygon(const std::vector>& poly, double px, double py) {
    const double eps = 1e-9;
    int cnt = 0;
    size_t n = poly.size();
    for (size_t i = 0; i < n; ++i) {
        auto [x0, y0] = poly[i];
        auto [x1, y1] = poly[(i + 1) % n];
        if (std::abs(y0 - y1) < eps) continue; // 水平边，跳过
        if ((y0 < py && y1 >= py) || (y1 < py && y0 >= py)) {
            double x_cross = x0 + (py - y0) * (x1 - x0) / (y1 - y0);
            if (x_cross > px + eps) cnt++;
        }
    }
    return cnt & 1;
}

注意：(i + 1) % n 自动闭合多边形；x_cross > px + eps 是为防止浮点误差导致本该计入的交点被漏掉；整个函数不修改输入，适合高频调用。

性能与边界场景验证要点

射线法平均时间复杂度是 O(n)，但实际性能受多边形顶点数和数据局部性影响。容易被忽略的是退化情况：

• 三点共线形成的“扁平”多边形：此时某些边的 y0 == y1，应被跳过，否则除零或误判
• 自相交多边形（如八字形）：射线法仍可用，但语义变为“非零环绕数”的简化版；若需严格按 winding number 判断，得换算法
• 点恰好落在边上：上述实现默认返回 false（因交点横坐标等于 px 不满足 > px + eps），如需包含边界，改为 >= px - eps 并同步调整顶点规则

最易出问题的不是主逻辑，而是顶点方向未归一化、浮点比较未加容差、以及忘记对最后一个边做 (n-1)→0 连接——这三个地方写错一个，结果就不可信。