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:

- in case then the line is tangent to the circle and intersects the circle in one single point.
- in case then the line intersects the circle in two points.
- in case then the line does not intersect the circle at all.

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 > ]; }

fuss/mathematics/geometry/intersections/segment_and_circle.txt ยท Last modified: 2017/02/22 18:30 (external edit)

For the copyright, license, warranty and privacy terms for the usage of this website please see the license, privacy and plagiarism pages.