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、.. 之间的逆时针角度。

您想要的段是具有最大逆时针角度的段。

要计算矢量 BX 的逆时针角度，请使用 atan2() 计算方向角a以及xBA 和 BX。那么你的逆时针角度是 (2π+xa) mod 2π。（即归一化为区间 [0,2π]）。