叉积法判断点在凸多边形内：点在内部当且仅当该点与每条有向边构成的叉积同号（全≥0或全≤0），依赖顶点绕序，无需浮点容差，高效稳定。
用叉积法判断点在凸多边形内，核心是方向一致性
对凸多边形，点在内部 ⇔ 该点与每条有向边构成的叉积同号（全 ≥ 0 或全 ≤ 0，取决于顶点顺序）。这是最轻量、最稳定的方法，不依赖浮点精度容忍度，也不需要射线交点计数。
假设多边形顶点按逆时针顺序存储在 vector<pair double>></pair> 中，点为 (x, y)：
bool isInside(const vector<pair<double, double>>& poly, double x, double y) {
int n = poly.size();
for (int i = 0; i < n; ++i) {
auto& p1 = poly[i];
auto& p2 = poly[(i + 1) % n];
// 计算向量 p1->p2 与 p1->point 的叉积
double cross = (p2.first - p1.first) * (y - p1.second) -
(p2.second - p1.second) * (x - p1.first);
if (cross < 0) return false; // 逆时针多边形要求所有叉积 ≥ 0
}
return true;
}- 若顶点是顺时针顺序，把
if (cross < 0)改成if (cross > 0) - 边界情况（
cross == 0）表示点在线段上；如需包含边界，保留<= 0或>= 0判断 - 无需归一化或除法，纯整数/浮点运算，无除零风险
别直接套用射线法（Ray Casting）到凸多边形
射线法通用但对凸多边形是“杀鸡用牛刀”，且容易因浮点误差漏判边界交点。尤其当射线恰好穿过顶点或与边共线时，isPointInPolygon 常见实现会出错。
-
std::signbit或std::abs(cross) < eps这类容差处理，在凸多边形场景下反而引入不确定性 - 射线法时间复杂度 O(n)，叉积法也是 O(n)，但常数更小、分支更少
- 如果多边形顶点顺序未知，先用叉积符号统计判断顺/逆时针（取前三个点），再统一方向
注意顶点顺序和重复点问题
叉积法严格依赖顶点绕序。若输入顶点是随机顺序或含重复点，结果必然错误——这不是算法缺陷，而是前提不满足。
立即学习“C++免费学习笔记（深入）”；
- 用
poly[0], poly[1], poly[2]算一次叉积，符号决定整体绕向；若为 0，换下一组三点，直到非零 - 预处理时用
std::unique+vector::erase清理相邻重复点，否则(i+1)%n可能产生零向量，导致叉积恒为 0 - 不要用
std::sort对坐标排序来“重建顺序”——凸包顶点排序不是按 x/y，而是按极角或格雷厄姆扫描结果
性能关键：避免动态内存与虚函数调用
在高频调用场景（如物理碰撞检测、栅格填充），把多边形顶点存为 std::array<std::pair<double, double>, N> 或 std::vector 的引用，而非值传递；禁止在循环内 new/delete 或调用 virtual 函数。
- 把
cross计算写成单行表达式，现代编译器能更好向量化 - 若多边形固定且顶点数 ≤ 8，可展开循环（unroll），消除分支预测失败开销
- 避免使用
std::complex<double>或几何库封装类型——它们往往带额外构造/拷贝，且隐藏了叉积语义
实际用的时候，最常被跳过的一步是验证顶点顺序。哪怕只错一个点的顺序，整个判断就翻车。宁可加一行检查，也别靠测试数据“碰运气”。
