检查将在一个段中击中的球的最快方法

Question

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

我的目标是预测所有的红色球，白色的球会击中它的路径，并使它们变黄。

我试着迭代所有的球，把距离取到p1和p2形成的线，但是白色后面的球也变黄了，但它们不应该。我应该如何处理这个任务？有快速的方法吗？

你可以假设白色跟随它的路径，忽略所有的碰撞，唯一的目标是预测是什么球在它的方式。

​

​

Answer 1

您应该将中心位于此矩形内的球涂上颜色：

​

​

该矩形的短边通过P1-P2垂直于直线，分别穿过P1和P2中心。其长度为4x半径，线段中部为P1/P2。

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

现在你只需要检查一下红球的中点是否在这四条线的右边。

检查"How to tell whether a point is to the right or left side of a line?"如何做到这一点。

Answer 2

我想您是在使用Ax+By+C = 0来描述这一行。

在这种情况下，您可以使用Bx -Ay +C = 0获得垂直线。A和B必须匹配，但C可以不同。计算出与起始位置和结束位置对应的C1和C2。现在我们正在寻找介于这两者之间的点。更具体地说，这两个方程的迹象，结果必须是斜视。那是(Bx -Ay +C1) * (Bx -Ay +C2) <=0。这将过滤红色的球，它将碰撞在你感兴趣的部分之外。如果要在起始点和结束点捕获冲突，则可能必须沿着这条线移动起始点/结束点。

为了加快速度，你可以做一些小把戏。请记住，除法和平方根是昂贵的操作。对于距离，由于您需要除以sqrt(A*A + B*B)存储，它是逆的，并乘以它，而不是重新计算每一点。

如果您需要在一组静态球上计算许多这样的碰撞，您可以考虑一些空间分区。常规网格或更花哨的BSP或四叉树将允许您轻松删除大量测试，而牺牲更复杂的实现和一些静态设置时间。