I am trying to write a circle-to-line-segment collision detection algorithm, which involves determining the intersection point of the circle and the line segment. The line segment represents the trajectory of a bullet over the last frame, which means it would hit the first circle even if there's multiple circles intersecting with the line.
I would like to obtain the t value of the point of intersection, which is a measure of how far along the line segment the intersection is. Computing the t value requires solving a quadratic equation, which involves the formula t = (-b - sqrt(det)) / (2 * a). To make the code faster, I am trying to avoid using sqrt entirely, which means instead of comparing to find the smallest t over all potential circles, I will try to find the smallest t^2 for them. However, I am not sure how to find t^2 without sqrt, even given t = (-b - sqrt(det)) / (2 * a), because the binomial expansion still involves sqrt.
How to compute t^2 = ((-b - sqrt(det)) / (2 * a))^2 without using sqrt function?
You need to solve
(x0 - cx + dx * t)^2 + (y0 - cy + dy * t)^2 = r^2
for every (cx, cy, r) from a circle set. It is impossible to find t value without quadratic equation solution and sqrt in general case.
But perhaps you can (we don't know all problem details) build some space index structure (partition, i.e. kd-tree) to avoid full checking of all these circles.