We know that the circle equation is:
we also know that the equations for a segment passing through two points and is:
knowing that , or, in other words, .
We substitute for and for in the circle equation and obtain:
Now, we want to collect , so we expand the left hand side and obtain:
and collect :
Passing from the right-hand side to the left-hand side, we can rewrite the equation as:
We can observe that if we name the bracketed expressions in the equation above , respectively :
then we can reduce , and to:
Looking at the equation now, we have a second-degree equation in with , and :
The solutions for this equation are:
where we know , , .
Now the discriminant is and depending on we have the cases:
By substituting in the equation of the segment for respectively we obtain the point(s) of intersection between the segment and the circle:
where we know from the expression above.
The reason for simplifying , and , keeping as an relation between , and and by working symbolically we can reduce the number of operations that an implementation may have to do.
/////////////////////////////////////////////////////////////////////////// // Copyright (C) 2014 Wizardry and Steamworks - License: GNU GPLv3 // /////////////////////////////////////////////////////////////////////////// // given a circle with centre in C(x0x, c0y) and radius r and two points // p1 and p2 defining a line, the function returns the empty list if the // line p1p2 does not intersect the circle or a list containing two vectors // of the the intersection point(s). list wasLineIntersectCircle(float c0x, float c0y, float r, vector p1, vector p2) { // let dx = p1.x-p2.x // let dy = p1.y-p2.y float dx = p1.x - p2.x; float dy = p1.y - p2.y; // let dcx = c0x-p1.x // let dcy = c0y-p1.y float dcx = c0x - p1.x; float dcy = c0y - p1.y; float a = llPow(dx, 2) + llPow(dy, 2); float b = 2 * (dcx * dx + dcy * dy); float c = llPow(dcx, 2) + llPow(dcy, 2) - llPow(r, 2); // delta float delta = llPow(b, 2) - 4 * a * c; if (delta < 0) { // no intersection, no points return []; } float t1 = (-b + llSqrt(delta)) / (2 * a); float t2 = (-b - llSqrt(delta)) / (2 * a); return [ < p1.x - dx * t1, p1.y - dy * t1, 0 >, < p1.x - dx * t2, p1.y - dy * t2, 0 > ]; }