FAST LINE-CIRCLE INTERSECTION BASED ON TRIANGLE LAWS

"EARLY" DETERMINING INTERSECTION TYPE.

(Magnitude or distance variables are starting with d)

Get the distance (magnitude) in between center point C and P1 line point and C and P2 point
using triangle method.

dP1C = sqrt((C.x - P1.x)^2 + (C.y - P1.y)^2)
dP2C = sqrt((C.x - P2.x)^2 + (C.y - P2.y)^2)


If (dP1C==r and dP2C==r) then the line is a chord, therefore the intersection points are P1 and P2
If (dP1C<r and dP2C<r) then the line is inside the circle and it does not intersects.
If (dP1C<r and dP2C==r) or (dP1C==r and dP2C<r) then the line is inside the circle and the
intersection point is P1 or P2 based on which one is on the circle (dP1C or dP2C equals to radius).
If (dP1C==r and dP2C>r) or  (dP1C==r and dP2C>r)  or (dP1C>r and dP2C>r) then
the tangent angle THETA Θ and the angle OMEGA in between P1-C and P1-P2 will define
that the line is intersecting or not.

The tangent point is T1. The angle in between tangent
and radius is always 90 degree, therefore it is a triangle with 90 degree.

The tangent angle Θ = Asin(r/dP1C)  // (sin(90) = 1.0)
The omega: Ω = acos((dP1C^2 + dP1P2^2 - dP2C^2)/(2*dP1C*dP1P2))

If (Θ>Ω and dP1C==r and dP2C>r) or (Θ>Ω and dP2C==r and dP1C>r) then the line intersects
with the circle at two point and one of the point is the P1 or P2 depends on which one
is in the circumference (dP1C==r or dP2C==r). The other intersection point have to be calculated.
If (Θ<Ω and dP1C>r and dP2C>r) Then there is two intersection point and only this time both have
to be calculated.
If (Θ=Ω and dP1C==r) or (Θ=Ω and dP2C==r ) then the line will be tangent to
the circle and There is one intersection point.
If (Θ<Ω and dP1C==r and dP2c>r) or (Θ<Ω and dP2C==r and dP1c>r)
then the end of the line is on the cirlce.
Therefore the one (dP1C or dP2c) equals to the radius that point is on the circle.

FASTEST METHOD FOR DOUBLE OR SINGLE INTERSECTION  USING TRIANGLE CHORDS LAW.
(this method cant be used when
the dP1C<r and dP2C>r  or dP1C>r and dP2C<r for this call function below)

Reuse the variables from the early determination.
To get α = asin(dP1C/ (r/sin(Ω))
To get Γ= 180 - Ω - α
To get dP1IP1 = sin(Γ)*(r/sin(Ω))
To get ß=180-α
To get ε=180-2ß
dIP1IP2 = 2r*sin(ε/2)


So the intersection points are:
IP1 = (normalize P1-P2)*dP1IP1+P1
IP2 = (normalize P1-P2)*(IP1IP2+dP1IP1)+IP1

because the magnitude calculated before at early determination the normalization can be done by hand by dividing the translated vector with the magnitude. Saves some processing time.

If dP1C==r then reorganize your code that:

ß = Ω //calculated at early determination
ε =180-(2*BETA)
IP1 = P1 //  dP1C == r  therefore P1=IP1
dP1IP1 = 0
α = No need to calculate
Γ = No need to calculate

then like above:
dIP1IP2 = 2r*sin(ε/2)
So intersection points are:
IP1 = P1
IP2 = (normalize P1-P2)*dIP1IP2 +IP1

CALCULATE SINGLE INTERSECTION IN CASE ONE OF THE POINT IS INSIDE THE CIRCLE'S DOMAIN

To get Beta ß=acos(dot (normalize C-P1) (normalize P1-P2))
To get Gamma Γ=asin(dP1C/(r/sin(ß)))
To get Epsilon ε = 180-(Γ+ß)
To get P1-IP1's magnitude: dP1IP1 = (r/sin(ß))*sin(ε)
IP2 =(normalize(P1-P2)*dP1IP1)+P1





maxscript version of this system is downloadable below, please check the header for instruction.

maxscript version of the circle-line intersection

*the use of this content is approved for wikipedia, and everybody else. If you use it on a website please link to this article.