检查将被击中的球的最快方法[关闭]。

Question

结束了。 这个问题需要 调试细节. 目前不接受回答。

---

想改进这个问题？ 请更新问题，使之成为 题外话 为Stack Overflow。

已关闭 上月.

改进这个问题

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

我的目标是预测白球在其路径上会撞到的所有红球，并将它们变成黄色。

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

你可以假设白色按照它的路径走，忽略所有的碰撞，唯一的目标是预测什么球挡在它的路上。

Answer 1

你应该给中心位于这个矩形内的球涂上颜色。

矩形的短边与P1 -P2的直线垂直，分别穿过P1和P2的中心。它们的长是4×半径，P1P2在线段的中间。

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

现在只需检查红球的中心点是否分别在这四条线段的右侧。

檢查 "如何判断一个点是在一条线的右边还是左边？" 关于如何才能做到这一点。

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或四树将允许你轻松地删除大量的测试，代价是更复杂的实现和一些静态设置时间。