检查分段中击球的最快方法

有N个红色球和一个白色球,它们都具有相同的半径。白球从位置p1移动到p2。

我的目标是预测白球将击中其路径的所有红球并将其变黄。

我尝试遍历所有球,并与由p1和p2形成的线保持一定距离,但是白色后面的球也变为黄色,但它们不应该变为黄色。我应该如何完成这项任务?有快速的方法吗?

您可以假设白色遵循其路径而忽略了所有碰撞,唯一的目的是预测球在阻碍其前进的方式。

enter image description here

评论
网名已过期
网名已过期

I assume you are using Ax+By+C = 0 to describe the line.

In this case you can get perpendicular lines using Bx -Ay +C = 0. A and B have to match but C can vary. Figure out C1 and C2 corresponding to the start and end position. Now we are looking for points that lie between these two. More specifically the signs of the two equation, results have to be oposite. That is (Bx -Ay +C1) * (Bx -Ay +C2) <=0. This will filter the red balls that would collide outside the segment you are interested in. You may have to move the start/end points along the line if you want to catch collisions at the start and end point.

To speed things up you can do few tricks. Remember that divisions and square root are expensive operations. For distance since you need to divide by sqrt(A*A + B*B) store it's inverse and multiply by it instead of recomputing for each point.

如果您需要计算一组静态球上的许多此类碰撞,则可以考虑进行一些空间划分。常规的网格或更高级的BSP或四叉树将使您轻松删除大量测试,但要付出更复杂的实现和一些静态设置时间的代价。

点赞
评论
<午夜m>
<午夜m>

您应该为中心位于此矩形内的球上色:

enter image description here

该矩形的短边垂直于穿过P1-P2的线,分别穿过P1和P2的中心。它们的长度为4 x半径,线段的中间为P1 / P2。

长边与穿过P1-P2的线平行。

现在,您只需要检查红球的中心点是否在这四条线的每条线的右侧。

Check "How to tell whether a point is to the right or left side of a line?" on how you can do that.

点赞
评论