java - 计算移动的球与移动的线/多边形(2D)碰撞的时间

Question

我有一个多边形，里面有一个移动的球。如果球撞到边界，它应该反弹回来。

我目前的“解决方案”:我将多边形分成几行并计算球何时击中移动线

所有变量:

a = length of a
b = length of b
c = length of c
ax = x position of A
ay = y position of A
bx = x position of B
by = y position of B
cx = x position of C
cy = y position of C
vax = speed of A on the x-axis
vay = speed of A on the y-axis
vbx = speed of B on the x-axis
vby = speed of B on the y-axis
vcx = speed of C on the x-axis
vcy = speed of C on the y-axis
h = height (equals r, because it collides when h is r)
r = radius
t = time (one time unit equals 1 frame. not relevant)
axc = x positon of A at the collision
ayc = y positon of A at the collision
bxc = x positon of B at the collision
byc = y positon of B at the collision
cxc = x positon of C at the collision
cyc = y positon of C at the collision

1. 计算所有点的碰撞位置:

   axc:=ax+vax*tayc:=ay+vay*t

   bxc:=bx+vbx*tbyc:=by+vby*t

   cyc:=cy+vcy*tcxc:=cx+vcx*t

2. 计算所有顶点的长度

   a:=√((axc-cxc)^(2)+(ayc-cyc)^(2))

   b:=√((bxc-cxc)^(2)+(byc-cyc)^(2))

   c:=√((axc-bxc)^(2)+(ayc-byc)^(2))

3. 计算h

   h=((√(2*(a^(2)*b^(2)+b^(2)*a^(2)+c^(2)*a^(2) )-(a^(4)+b^(4)+c^(4))))/(2*c))

4. 求解 t

   求解(h=((√(2*(a^(2)*b^(2)+b^(2)*a^(2)+c^(2)*a^( 2))-(a^(4)+b^(4)+c^(4))))/(2*c)), t)

BUUUUUT:我的计算器 (Ti-Nspire CX CAS) 崩溃了。 Microsoft Mathematics 花费的时间太长了(我现在正在计算...... 1 小时但仍然没有......)

所以...帮助!

(不要质疑我的画功)

Answer 1

如果您的多边形是凸面的并且所有速度始终保持不变，您可以使用我刚刚想到的这些系列技巧(因此可能有一些更好的方法):

1) 通过简单地扩展将每一行替换为无限长的行。

只有当多边形是凸面时才能这样做。考虑下图:

红线是原始多边形，绿线是无限延伸。圆圈能否在碰到红线之前碰到绿线？不。我们现在可以专注于球击中无限长的线，这(至少对我而言)是更简单的任务。

2) 分别计算每条线的碰撞时间，然后选择最小值

如果我们想知道一个完美的圆球是否以及何时击中一条线，我们可以很容易地解决一个点是否击中一条线，考虑下图:

基本上，当圆的中心进入该线周围的区域时，圆会碰到一条线，该区域是距离该线最多 radius 的所有点，其中 radius 是圆的半径。

所以我们可以继续，只需用中心的一个点替换圆，然后将线向新创建的点移动半径。

3) 移动点命中移动线时计算

如果直线由两个移动点 a 和 b 定义，速度为 va 和 vb，如由于该点位于 c 点，速度为 vc，我们可以使点 a 静止(不移动)并位于 (0,0 ) 通过用 b-a、vb-va 和 c-a、vc-va 替换其他两点的位置和速度。

现在让我们像这样命名 b 和 c 的新坐标和速度:[bx, by], (vbx , vby) 和[cx, cy], (vcx, vcy)。我们现在可以通过求解这个公式来计算出碰撞时间的时间:

cx+t * vcx = s*bx + s*t*vbx
cy+t * vcy = s*by + s*t*vby

但是要小心:这会导致二次方程式，您必须忽略可能的负解，这可能意味着点正在远离直线或者碰撞正在发生，因此，在开始做任何事情之前，请确保球尚未发生碰撞。

还有(希望不用这么说)你把t和s替换后，你不会得到最终的碰撞点，你需要撤消您所做的所有地役权(例如添加a)

如果您需要它来处理非凸多边形，我有一个解决方法，所以请写在评论中。