math - 不使用 sqrt 计算二次方程的平方解

Question

我正在尝试编写一个圆到线段的碰撞检测算法，该算法涉及确定圆和线段的交点。线段表示子弹在最后一帧上的轨迹，这意味着即使有多个圆圈与线相交，它也会击中第一个圆圈。

我想获得t交叉点的值，这是对交叉点沿线段有多远的度量。计算该t值需要求解一个二次方程，其中涉及公式t = (-b - sqrt(det)) / (2 * a)。为了使代码更快，我试图避免sqrt完全使用，这意味着t我不会比较找到所有潜在圆圈中的最小值，而是尝试t^2为它们找到最小的。但是，我不确定如何找到t^2没有sqrt，甚至给出t = (-b - sqrt(det)) / (2 * a)，因为二项式展开仍然涉及sqrt。

t^2 = ((-b - sqrt(det)) / (2 * a))^2不使用函数如何计算sqrt？

标签： mathcollision-detectionintersectionquadratic

Answer 1

你需要解决

(x0 - cx + dx * t)^2 + (y0 - cy + dy * t)^2 = r^2

对于每一个(cx, cy, r)来自一个圆圈集。t在一般情况下，如果没有二次方程解和 sqrt，就不可能找到值。

但也许你可以（我们不知道所有问题细节）建立一些空间索引结构（分区，即kd-tree）来避免对所有这些圈子进行全面检查。