寻找相对于已知光源点的多边形两个边界顶点的低计算量方法

完全可以用向量叉乘替代atan2计算相对极角顺序，整体时间复杂度和原方案一致都是O(n)，但完全规避了三角函数调用，计算开销低很多。

核心原理 #

你要找的两个边界顶点，本质就是多边形所有顶点相对点p的极角的最小值和最大值对应的点。判断两个向量极角的相对大小，不需要算出实际角度，仅通过符号判断+二维叉乘就能完成，全程无三角函数调用：

设从p指向两个顶点的向量分别为 a = (ax, ay)、b = (bx, by)，先通过向量y分量的符号判断所在半平面：

1. 若ay > 0且by < 0：b的极角更大（b在x轴下半平面，极角范围π_{2π，大于上半平面的0}π）
2. 若ay < 0且by > 0：a的极角更大
3. 若二者y分量同号（含y=0的边界情况）：计算二维叉乘 cross = ax * by - bx * ay
   • cross > 0：a在b的逆时针方向，a极角更大
   • cross < 0：b极角更大
   • cross = 0：两向量共线，取距离p更远的点作为边界点即可

具体实现步骤 #

• 预处理：对每个多边形顶点v_i，先计算相对p的向量 vec_i = (v_i.x - p.x, v_i.y - p.y)
• 初始化：取第一个顶点的向量作为初始的极角最小、最大候选向量，对应的顶点为初始v_min、v_max
• 遍历剩下的所有顶点：
  • 把当前顶点的向量和vec_min比较，若当前向量极角更小，更新vec_min和v_min
  • 把当前顶点的向量和vec_max比较，若当前向量极角更大，更新vec_max和v_max
• 遍历结束后得到的v_min、v_max就是你要的两个边界顶点

方案优势 #

1. 计算开销极低：全程只有加减乘四则运算，没有atan2这类超越函数调用，在常规CPU上单步运算开销仅为atan2方案的1/8~1/15
2. 精度更高：避免了三角函数计算带来的浮点数精度损失，边界判断的准确性更好
3. 时间复杂度和原方案一致，都是O(n)，n为多边形顶点数，不需要额外的排序开销

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