algorithm - 找到离开顶点的最左边的线

Question

作为更大算法的一部分，我正在遍历一组互连的线段。通过线段到达任何顶点时，我需要找到从该点离开的最左边的线段。

举个例子，假设我从顶点 A 开始，沿着线段 AB 到达顶点 B，我现在需要选择最左边的线段 BC、BD、BE... 来到达下一个顶点。

我可以通过获取每对现有段的带符号区域来做到这一点。如果三角形 BDC 的有符号面积为正，则 BDC 为逆时针方向，因此 BC 落在 BD 的左侧。然后我可以将 BC 与 BE 进行比较，并以同样的方式处理其他路段以找到最左边的导出。但这仅在 CBD 角度为锐角时才有效。我将不得不添加一个特殊情况来处理钝的 CBD。

必须有一种更简单的方法来做到这一点。有什么想法吗？

Answer 1

将线段视为向量。您想要选择 BC、BD、BE、... 中最左边的一个。为此，请计算 BA(即相反方向的 AB)与其他有向线段 BC、BD、BE、... 之间的逆时针角度。

您想要的线段是 CCW 角度最大的线段。

要计算矢量 BX 的 CCW 角度，请使用 atan2() 计算 BA 和 BX 的方向角 a 和 x。那么你的 CCW 角度就是 (2π+x-a) mod 2π。 (即标准化为区间 [0,2π])。