Kreis durch drei Punkte

Bei dem Problem des Kreises durch drei Punkte sind drei Punkte P1, P2 und P3 gegeben, die nicht auf einer Geraden liegen. Gesucht ist ein Kreis durch diese drei Punkte, speziell dessen Mittelpunkt M und Radius r.

Ein Kreis ist definiert als alle Punkte P = (xp yp), die zu seinem Mittelpunkt M = (xm ym) den Abstand r haben:

  (xp - xm)² + (yp - ym)² = r²

Diese Gleichung formt man durch Ausmultiplizieren und Umstellen um

  xp² - 2 xp xm + xm² + yp² - 2 yp ym + ym² = r²
  - 2 xp xm + xm² - 2 yp ym + ym² - r² = - xp² - yp²
  (xm² + ym² - r²) + (- 2 xm) xp + (- 2 ym) yp = - xp² - yp²

und definiert dann

  A = xm² + ym² - r²
  B = -2 xm
  C = -2 ym

was zu

  A + B xp + C yp = - xp² - yp²

führt.

Für einen Kreis durch die drei Punkte P1 = (x1 y1), P2 = (x2 y2) und P3 = (x3 y3) gilt dann

  A + B x1 + C y1 = - x1² - y1²
  A + B x2 + C y2 = - x2² - y2²
  A + B x3 + C y3 = - x3² - y3²

analog zu der Betrachtung für den Punkt P oben. Das ist ein lineares Gleichungssystem mit der Matrix

  ((1 x1 y1)
   (1 x2 y2)
   (1 x3 y3))

und

  (-x1²-y1² -x2²-y2² -x3²-y3²)

als Spaltenvektor. Aus den Unbekannten A, B und C des Gleichungssystems kann man nach dessen Lösung xm, ym und r anhand von

  xm = -B/2
  ym = -C/2
  r² = xm² + ym² - A

bestimmen.

Die Realisierung als Funktion arbeitet wie die mathematische Beschreibung. Sie stellt das lineare Gleichungssystem auf, löst es und bestimmt aus der Lösung die drei Größen xm, ym und r². Die Funktion liefert diese Werte als drei-elementige Liste.

(defproc circle-3p (x1 y1 x2 y2 x3 y3)
  (let
    ((abc
      (.
        (solve-linear-equations
           (create-matrix x1 y1 x2 y2 x3 y3)
           (create-column-vector x1 y1 x2 y2 x3 y3))
         elements)))
    (let
      ((xm (get-xm abc))
       (ym (get-ym abc)))
      (list xm ym (get-r-square xm ym abc)))))

Dabei werden einige Hilfsfunktionen verwendet. Die Funktionen create-matrix und create-column-vector stellen das oben beschriebene Gleichungssystem auf.

(defproc create-matrix (x1 y1 x2 y2 x3 y3)
  (new matrix 3 3
    (list
      (list 1 x1 y1)
      (list 1 x2 y2)
      (list 1 x3 y3))))

(defproc create-column-vector (x1 y1 x2 y2 x3 y3)
  (new column-vector 3
    (list
      (- (square-sum x1 y1))
      (- (square-sum x2 y2))
      (- (square-sum x3 y3)))))

Das Gleichungssystem wird mit solve-linear-equations gelöst (siehe Cramersche Regel). Aus der Lösung des Gleichungssystems extrahieren die Funktionen get-xm und get-ym den Mittelpunkt des gesuchten Kreises.

(defproc get-xm (abc)
  (* -0.5 (first (second abc))))

(defproc get-ym (abc)
  (* -0.5 (first (third abc))))

Das Quadrat des Radius des Kreises wird von der Funktion get-r-square geliefert.

(defproc get-r-square (xm ym abc)
  (- (square-sum xm ym) (first (first abc))))

Die an einigen Stellen verwendete Hilfsfunktion square-sum liefert die Summe der Quadrate ihrer beiden Argumente.

(defproc square-sum (x y)
  (+ (* x x) (* y y)))

Die unten verlinkte Datei enthält die Funktionen und kann mit dem Programm Calc interaktiv verwendet werden.


3-point-circle.sheet.xml