检测静止圆列表是否与沿同一平面中的直线从起点移动到终点的另一个圆相交的算法
Algorithm to detect if a list of circles at rest intersect with another circle moving from start point to end point along straight line in same plane
我有一个圆圈（在我的游戏中是 Striker），它沿着我的 2d 平面从一个点沿着一条直线移动到另一个点。我在同一平面上还有一些其他圆圈没有移动。找到在运动过程中与运动圆相交的圆列表的最佳算法是什么。如果我想在 python 中对此进行编码，最好的方法是什么（内存效率高，因为我想针对我的问题针对许多不同的状态执行此操作）？用于此目的的最佳库是什么？
你问的是算法，而不是代码，所以这就是想法。您可能想为此使用 math 模块，但如果您了解基本的美国 11 年级解析几何，则不需要其他任何东西。
固定圆与移动圆相交的方式有两种：它可以在其路径的起点或终点与移动圆相交（以 A 和 B 为中心的红色圆圈在下图中），或者它可以与由移动圆形成的矩形（图中标记为 EGHF 的蓝色矩形）相交。
检查与端圆的交点很容易：如果圆心之间的距离不大于它们的半径之和，则圆相交。
检查与矩形的交点有点困难。如果满足两个要求，则 I 处的圆与矩形 EGHF 相交。首先，中心 I 必须位于构成矩形端点的 GH 和 EF 线之间。其次，I到AB线（动圆圆心的直线）的距离不得大于I处的静止圆半径与动圆半径之和。
检查与矩形相交的另一种更一致的方法是检查与静止圆心的距离：到移动起点和终点的垂直平分线（标记为 p 的洋红色线）圆，它必须最多是点 A 和 B 之间距离的一半，以及到线 AB 的距离，它必须最多是移动和静止圆的半径之和。
所有那些计算（两点之间的距离，GH，EF，AB等直线和垂直平分线的方程，看一个点是否在两条平行线之间，以及从一个点到一条线的距离) 在解析几何中是标准的。这些计算中的大多数只依赖于移动的圆——每个静止圆的计算很少而且很快。如果您需要这些公式的帮助，请告诉我。很可能有一个用于此类公式的模块，但我不知道有一个。
该方法涉及的内存最小，假设移动圆的半径和起止圆心坐标，以及静止圆的半径和圆心坐标已经在内存中。如果您选择我的替代方法，您可以通过预先计算移动圆的一些值来节省执行时间。如果圆心的起始坐标为(x1, y1)，结束坐标为(x2, y2)，则预先计算：
dx = x2 - x1
dy = y2 - y1
d = math.hypot(dx, dy)
det = x2 * y1 - x1 * y2
c = (x1 * x1 + y1 * y1 - x2 * x2 - y2 * y2) / 2
（请注意，对于移动圆的路径，这五个值仅存储一次。）然后对于每个静止圆，找到从该圆的中心到垂直平分线（我图中的 p）的带符号距离，然后使用它找到到起始圆、结束圆或移动线的距离。如果你有很多静止的圆圈，并且移动圆圈的路径与比赛场地相比很小，你可以使用一个边界矩形作为路径来快速消除大部分静止的圆圈。
我有一个圆圈（在我的游戏中是 Striker），它沿着我的 2d 平面从一个点沿着一条直线移动到另一个点。我在同一平面上还有一些其他圆圈没有移动。找到在运动过程中与运动圆相交的圆列表的最佳算法是什么。如果我想在 python 中对此进行编码，最好的方法是什么（内存效率高，因为我想针对我的问题针对许多不同的状态执行此操作）？用于此目的的最佳库是什么？
你问的是算法，而不是代码，所以这就是想法。您可能想为此使用 math 模块，但如果您了解基本的美国 11 年级解析几何，则不需要其他任何东西。
固定圆与移动圆相交的方式有两种：它可以在其路径的起点或终点与移动圆相交（以 A 和 B 为中心的红色圆圈在下图中），或者它可以与由移动圆形成的矩形（图中标记为 EGHF 的蓝色矩形）相交。
检查与端圆的交点很容易：如果圆心之间的距离不大于它们的半径之和，则圆相交。
检查与矩形的交点有点困难。如果满足两个要求，则 I 处的圆与矩形 EGHF 相交。首先，中心 I 必须位于构成矩形端点的 GH 和 EF 线之间。其次，I到AB线（动圆圆心的直线）的距离不得大于I处的静止圆半径与动圆半径之和。
检查与矩形相交的另一种更一致的方法是检查与静止圆心的距离：到移动起点和终点的垂直平分线（标记为 p 的洋红色线）圆，它必须最多是点 A 和 B 之间距离的一半，以及到线 AB 的距离，它必须最多是移动和静止圆的半径之和。
所有那些计算（两点之间的距离，GH，EF，AB等直线和垂直平分线的方程，看一个点是否在两条平行线之间，以及从一个点到一条线的距离) 在解析几何中是标准的。这些计算中的大多数只依赖于移动的圆——每个静止圆的计算很少而且很快。如果您需要这些公式的帮助，请告诉我。很可能有一个用于此类公式的模块，但我不知道有一个。
该方法涉及的内存最小，假设移动圆的半径和起止圆心坐标，以及静止圆的半径和圆心坐标已经在内存中。如果您选择我的替代方法，您可以通过预先计算移动圆的一些值来节省执行时间。如果圆心的起始坐标为(x1, y1)，结束坐标为(x2, y2)，则预先计算：
dx = x2 - x1
dy = y2 - y1
d = math.hypot(dx, dy)
det = x2 * y1 - x1 * y2
c = (x1 * x1 + y1 * y1 - x2 * x2 - y2 * y2) / 2
（请注意，对于移动圆的路径，这五个值仅存储一次。）然后对于每个静止圆，找到从该圆的中心到垂直平分线（我图中的 p）的带符号距离，然后使用它找到到起始圆、结束圆或移动线的距离。如果你有很多静止的圆圈，并且移动圆圈的路径与比赛场地相比很小，你可以使用一个边界矩形作为路径来快速消除大部分静止的圆圈。