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