Intersection of a Line and a Sphere (or circle)

Written by Paul Bourke
November 1992

C code example by author
Source code example by: Iebele Abel.
Sphere/ellipse and line intersection code for Visual Basic by Adrian DeAngelis.
LISP version for AutoCAD (and Intellicad) by Andrew Bennett intC2.lsp and intC2_app.lsp.

Points P (x,y) on a line defined by two points P₁ (x₁,y₁,z₁) and P₂ (x₂,y₂,z₂) is described by

P = P₁ + u (P₂ - P₁)

or in each coordinate
x = x₁ + u (x₂ - x₁)
y = y₁ + u (y₂ - y₁)
z = z₁ + u (z₂ - z₁)

A sphere centered at P₃ (x₃,y₃,z₃) with radius r is described by

(x - x₃)² + (y - y₃)² + (z - z₃)² = r²

Substituting the equation of the line into the sphere gives a quadratic equation of the form

a u² + b u + c = 0

where:

a = (x₂ - x₁)² + (y₂ - y₁)² + (z₂ - z₁)²

b = 2[ (x₂ - x₁) (x₁ - x₃) + (y₂ - y₁) (y₁ - y₃) + (z₂ - z₁) (z₁ - z₃) ]

c = x₃² + y₃² + z₃² + x₁² + y₁² + z₁² - 2[x₃ x₁ + y₃ y₁ + z₃ z₁] - r²

The solutions to this quadratic are described by

The exact behaviour is determined by the expression within the square root

b * b - 4 * a * c

If this is less than 0 then the line does not intersect the sphere.
If it equals 0 then the line is a tangent to the sphere intersecting it at one point, namely at u = -b/2a.
If it is greater then 0 the line intersects the sphere at two points.

To apply this to two dimensions, that is, the intersection of a line and a circle simply remove the z component from the above mathematics.

Line Segment

When dealing with a line segment it may be more efficient to first determine whether the line actually intersects the sphere or circle. This is achieved by noting that the closest point on the line through P₁P₂ to the point P₃ is along a perpendicular from P₃ to the line. In other words if P is the closest point on the line then

(P₃ - P) dot (P₂ - P₁) = 0

Substituting the equation of the line into this

[P₃ - P₁ - u(P₂ - P₁)] dot (P₂ - P₁) = 0

Solving the above for u =

(x₃ - x₁)(x₂ - x₁) + (y₃ - y₁)(y₂ - y₁) + (z₃ - z₁)(z₂ - z₁)
-----------------------------------------------------------
(x₂ - x₁)(x₂ - x₁) + (y₂ - y₁)(y₂ - y₁) + (z₂ - z₁)(z₂ - z₁)

If u is not between 0 and 1 then the closest point is not between P₁ and P₂

Given u, the intersection point can be found, it must also be less than the radius r. If these two tests succeed then the earlier calculation of the actual intersection point can be applied.