opencv::pointPolygonTest函数的底层实现算法是什么？

算法正式名称 #

OpenCV的cv::pointPolygonTest采用的是优化版非零环绕数判别法，部分资料也将其实现逻辑称为带符号距离叉积边测试法，你观察到的“通过待测点与多边形连续两个顶点构成的三角形方向判断”是完全正确的，核心运算就是二维向量叉积。

核心实现逻辑 #

该算法没有使用射线投射方案，整体逻辑分为两个分支：

1. 基础包含性判断（measureDist = false时）
   • 遍历多边形的每一条相邻顶点构成的边，先判断待测点是否落在当前边上，若匹配直接返回0
   • 若不在边上，通过叉积计算待测点相对于每条边的左右位置，统计环绕方向的符号变化，最终根据非零环绕数规则判定点在多边形内部（返回1）还是外部（返回-1）
2. 带符号距离计算（measureDist = true时）
   • 在完成包含性判断的基础上，额外计算待测点到所有多边形边的最短欧氏距离
   • 结合包含性结果给距离添加符号：内部点返回正距离，外部点返回负距离

认知补充说明 #

你觉得它和常规环绕数算法有区别是因为OpenCV做了工程优化：常规环绕数算法需要统计待测点相对多边形的总环绕角度，而OpenCV的实现省略了三角函数计算，仅通过叉积符号和边的轴向跨越特征做判断，运算效率更高，尤其适合小顶点数多边形的点包含测试场景。

该算法的基础逻辑可参考《计算机图形学（第四版）》中“多边形点包含测试”章节的非零环绕数优化实现方案。

内容的提问来源于stack exchange，提问作者Bronzila