不使用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？

Answer 1

您需要解决

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

对于圈子集合中的每个(cx, cy, r)。通常情况下，如果没有二次方程解和sqrt，就不可能找到t值。

但是您可以（我们不知道所有问题的详细信息）构建某种空间索引结构（分区，即kd-tree），以避免对所有这些圆进行全面检查。