algorithm - 运动圆与固定线段的二维碰撞

Question

在游戏程序的上下文中，我有一个移动的圆圈和一个固定的线段。该段可以具有任意大小和方向。

• 我知道圆的半径:r
• 我知道移动前圆的坐标:(xC1, yC1)
• 我知道移动后圆的坐标:(xC2, yC2)
• 我知道线段末端的坐标:(xL1, yL1) - (xL2, yL2)

我在尝试计算时遇到困难:

• 一个 bool 值:如果圆的任何部分在从 (xC1, yC1) 移动到 (xC2, yC2) 时碰到线段
• 如果 bool 值为真，圆心的坐标(x, y)当它碰到线段时(我的意思是当圆第一次与线段相切时)

Answer 1

我将用伪算法来回答——没有任何代码。在我看来，有两种情况我们可能会返回 true，如下图所示:

这里蓝色是你的圆圈，虚线是轨迹线，红线是你给定的线。

• 我们构建了一条辅助轨迹线，从两个圆的中心到两个圆的中心。如果此轨迹线与给定线相交 - 返回 true。参见 this question关于如何计算该交叉点。
• 在第二种情况下，第一个测试没有通过我们，但可能恰好是圆圈在通过轨迹时轻推了直线。我们将需要以下构造:

从轨迹我们建立到每个点 A 和 B 的法线。然后这些线被截断或扩展成辅助线(Ha 和 Hb)，以便它们A 和 B 的长度正好是圆的半径。然后我们检查每条辅助线是否与轨迹线相交。如果它们确实返回 true。

• 否则返回false。