叉乘判定法的核心逻辑是：点在凸多边形内当且仅当它始终位于所有有向边的同一侧，即对每条边 $p_i \to p_{i+1}$，向量叉积 $\text{cross}(p_i, p_{i+1}, q)$ 符号一致（全≥0 或全≤0），要求顶点严格按顺时针或逆时针顺序排列。
叉乘判定法的核心逻辑是什么
判断点是否在凸多边形内，本质是检查该点是否始终位于所有边的同一侧（比如左侧）。对凸多边形而言，只要点对每条有向边 p[i]→p[i+1] 的叉积符号一致（全 ≥ 0 或全 ≤ 0），就说明它在内部或边界上。
叉积公式（2D）：(p2.x - p1.x) <em> (p3.y - p1.y) - (p2.y - p1.y) </em> (p3.x - p1.x)，其中 p1,p2 是边端点，p3 是待测点。结果 > 0 表示 p3 在边的左侧，
注意：顶点顺序必须统一（顺时针或逆时针），否则叉积符号会混杂，判定失效。
如何写一个安全的 pointInConvexPolygon 函数
函数需处理边界情况（点在边上、顶点重合）、整数/浮点精度、顶点数量少于 3 等问题：
- 输入多边形顶点数组
pts必须按顺序（如逆时针）存储，且首尾不重复（即n个点对应n条边） - 对每条边
pts[i]→pts[(i+1)%n]，计算叉积cross(pts[i], pts[(i+1)%n], q) - 使用统一符号判断：若所有叉积 ≥ 0（逆时针多边形），或全部 ≤ 0（顺时针），则点在内部或边上
- 若某次叉积为 0，说明点在该边上；仍算“在内”，除非业务要求严格区分内部/边界
- 避免用
== 0判断浮点叉积，应加epsilon容差（如abs(cross_val) ）
bool pointInConvexPolygon(const vector<point>& pts, const Point& q) {
int n = pts.size();
if (n 1e-9) has_pos = true;
else if (cr <h3>为什么不能直接套用到凹多边形</h3><p>叉乘判定法依赖凸性带来的“单侧一致性”——凹多边形存在内角 > 180° 的顶点，导致点可能对某些边在左侧、对另一些边在右侧，即使它实际在内部。</p><p>例如一个“凹四边形”中，中心点可能对一条边叉积为正，对对面边叉积为负，算法误判为外部。</p><p>这不是实现缺陷，而是数学前提不满足。凹多边形需改用射线法（<code>ray casting</code>）或三角剖分等更通用方法。</p><h3>容易被忽略的边界与性能细节<ul>
<li>顶点顺序错误是最常见 bug：用 OpenCV 的 <code>convexHull</code> 输出默认是顺时针，而多数叉积教程假设逆时针，符号逻辑要反过来</li>
<li>整数坐标下，叉积是整数，可避免浮点误差，但要注意溢出（如 <code>int</code> 坐标超 1e5 时，叉积可能超 <code>int</code> 范围，应转 <code>long long</code>）</li>
<li>若需高频调用（如碰撞检测），可预计算多边形方向（通过前两条边叉积定序），避免每次循环里重复判断</li>
<li>不要省略 <code>% n</code> 取模——漏掉会导致最后一条边（<code>pts[n-1]→pts[0]</code>）没参与判定</li>
</ul>
</h3><p>真正卡住人的往往不是算法本身，而是顶点顺序没校验、浮点比较没容差、或者把凸包生成结果默认当逆时针用了。</p></point>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
