Schnittpunkt Linie vs. Kreis

[Medium]

Und da es schon angesprochen wurde, hier das ganze noch vektoriell in Pseudocode (um den ganzen Krams zu sparen den man betreiben muss um Vektoroperationen durch Funktionen zu ersetzen). Im Grunde läuft es auf eine pq- bzw. Mitternachtsformel hinaus.

Delphi-Quellcode:

// M : Mittelpunkt des Kreises
// r : Kreisradius
// A : Stützpunkt der zu schneidenden Strecke/Gerade
// V : Richtungsvektor der Strecke/Gerade (Wenn diese aus 2 Punkten A und B gebildet ist, ist dies B-A)
// U : Hilfsvektor
// p, q, d, x1, x2 : Hilfsvariablen (Skalare, keine Vektoren)

  U := A-M;
  p := U*V;
  q := U^2 - r^2;
  d := p^2 - q;

  if d < 0 then 
    Kein_Schnittpunkt
  else
  begin
    d  := sqrt(d / |V|);
    x1 := -p + d;
    x2 := -p - d;
  end;

  if (x2>x1) and (x1>0) then
    Schnittpunkt := A + x1*V
  else
  if (x1>x2) and (x2>0) then
    Schnittpunkt := A + x2*V
  else
    Kein_Schnittpunkt_Oder_Schnitt_Hinter_A;

Der je kleinere Wert von x1 und x2 gibt den ersten Schnittpunkt von A aus in Richtung V gesehen, die Bedingung >0 stellt sicher dass kein Punkt "hinter" der Blickrichtung "V gestützt auf A" gefunden wird. Liegt dieser in ]0|1[, ist der Schnittpunkt zwischen den Punkten A und B bzw. A und A+V.

Das ganze klappt nun auch für beliebige Dimensionen, man muss lediglich entsprechende Vektortypen und die zugehörigen Operationen nehmen. Ich hab das z.B. in der Form für 3D in einem kleinen Raytracer im Kugel-Primitive eingesetzt.