检查将被击中的球的最快方法
Fastest way to check balls that will be hit in a segment
有N个红球和一个白球，它们的半径都相同。白球从位置p1移动到p2。
我的 objective 是预测白球将在其路径上击中的所有红球并将它们变成黄色。
我尝试遍历所有球并计算到 p1 和 p2 形成的线的距离，但是白色后面的球也变成了黄色，但它们不应该。我应该如何处理这个任务？有快速的方法吗？
你可以假设白棋会忽略所有碰撞，沿着它的路径前进，唯一的objective 是预测有什么球挡住了它的路。
我假设您正在使用 Ax+By+C = 0 来描述该行。
在这种情况下，您可以使用 Bx -Ay +C = 0 获得垂直线。 A 和 B 必须匹配，但 C 可以不同。找出C1和C2对应的开始和结束位置。现在我们正在寻找介于这两者之间的点。更具体地说，两个方程的符号，结果必须相反。即(Bx -Ay +C1) * (Bx -Ay +C2) <=0。这将过滤掉会在您感兴趣的线段外碰撞的红球。如果您想在起点和终点捕捉碰撞，您可能需要沿线移动 start/end 点。
要加快速度，您可以采取一些技巧。请记住，除法和平方根是昂贵的操作。对于距离，因为您需要除以 sqrt(A*A + B*B) 存储它的倒数并乘以它而不是为每个点重新计算。
如果您需要在一组静态球上计算许多此类碰撞，您可以考虑一些 space 分区。常规网格或更花哨的 BSP 或四叉树将允许您轻松删除大量测试，但代价是更复杂的实现和一些静态设置时间。
您应该为中心位于该矩形内的球着色：
该矩形的短边垂直于通过P1-P2 的线，分别通过P1 和P2 的中心。它们的长度是 4 x 半径，P1/P2 在线段的中间。
长边与通过 P1-P2 的线平行。
现在只需要检查红球的中心点是否在这四条直线的右侧即可。
检查 "How to tell whether a point is to the right or left side of a line?" 如何做到这一点。
有N个红球和一个白球，它们的半径都相同。白球从位置p1移动到p2。
我的 objective 是预测白球将在其路径上击中的所有红球并将它们变成黄色。
我尝试遍历所有球并计算到 p1 和 p2 形成的线的距离，但是白色后面的球也变成了黄色，但它们不应该。我应该如何处理这个任务？有快速的方法吗？
你可以假设白棋会忽略所有碰撞，沿着它的路径前进，唯一的objective 是预测有什么球挡住了它的路。
我假设您正在使用 Ax+By+C = 0 来描述该行。
在这种情况下，您可以使用 Bx -Ay +C = 0 获得垂直线。 A 和 B 必须匹配，但 C 可以不同。找出C1和C2对应的开始和结束位置。现在我们正在寻找介于这两者之间的点。更具体地说，两个方程的符号，结果必须相反。即(Bx -Ay +C1) * (Bx -Ay +C2) <=0。这将过滤掉会在您感兴趣的线段外碰撞的红球。如果您想在起点和终点捕捉碰撞，您可能需要沿线移动 start/end 点。
要加快速度，您可以采取一些技巧。请记住，除法和平方根是昂贵的操作。对于距离，因为您需要除以 sqrt(A*A + B*B) 存储它的倒数并乘以它而不是为每个点重新计算。
如果您需要在一组静态球上计算许多此类碰撞，您可以考虑一些 space 分区。常规网格或更花哨的 BSP 或四叉树将允许您轻松删除大量测试，但代价是更复杂的实现和一些静态设置时间。
您应该为中心位于该矩形内的球着色：
该矩形的短边垂直于通过P1-P2 的线，分别通过P1 和P2 的中心。它们的长度是 4 x 半径，P1/P2 在线段的中间。
长边与通过 P1-P2 的线平行。
现在只需要检查红球的中心点是否在这四条直线的右侧即可。
检查 "How to tell whether a point is to the right or left side of a line?" 如何做到这一点。