Intersection of a Line and

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

For a line segment between P₁ and P₂ there are 5 cases to consider.

• Line segment doesn't intersect and on outside of sphere, in which case both values of u wll either be less than 0 or greater than 1.

• Line segment doesn't intersect and is inside sphere, in which case one value of u will be negative and the other greater than 1.

• Line segment intersects at one point, in which case one value of u will be between 0 and 1 and the other not.

• Line segment intersects at two points, in which case both values of u will be between 0 and 1.

• Line segment is tangential to the sphere, in which case both values of u will be the same and between 0 and 1.

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.