判断点是否在多边形或多面体内
哪些公司问过
答案要点
- 射线法:从点发出射线统计与边的交点数,奇数在内、偶数在外,适用于凹多边形
- 边界处理:射线过顶点用半开区间规则,点在边上单独判断
- 凸多边形用叉积判断点是否在所有边同侧,可二分优化到 O(log n)
- 凸多面体用半空间测试:法向统一朝外,各面有符号距离均不大于零即在内部
- 凹多面体用三维射线法或先凸分解,浮点比较需加容差
易错点
- 射线经过顶点时重复计数,导致奇偶判断错误
- 面法向朝向不统一,半空间测试符号判断失效
- 浮点比较不加容差,边界点结果不稳定
面试官常见追问
- 如果是凹多边形怎么办?
- 环绕数法和射线法有什么区别?
- 游戏里大量点做检测怎么加速?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。