Gaußsche Trapezformel
Die Fläche eines einfachen, geschlossenen, ebenen Polygons lässt sich einfach aus den cartesischen Koordinaten seiner Eckpunkte berechnen.
Für eine Realisierung als funktionales Programm werden zunächst die Eckpunkte durch Listen repräsentiert. Die Listen haben zwei Elemente: die Koordinaten für die x- und die y-Achse.
(setq make-point (curry (list _ _)))
(setq get-x first)
(setq get-y second)
Ein Polygon ist eine Liste von Punkten.
(setq make-polygon list)
Bei einem geschlossenen Polygon muss der erste dem letzten Punkt der Liste entsprechen.
(defproc is-closed-polygon? (points)
(= (first points) (first (last points))))
Um die Fläche des Polygons zu berechnen, werden für je zwei aufeinanderfolgende Ecken die Koordinaten über Kreuz multipliziert (x1 mal y2 und x2 mal y1) und die Differenz der beiden Produkte aufsummiert. Wegen des "über Kreuz" heißt die Formel im Englischen "Shoelace Formula".
(defproc shoelace-sum (points accumulator)
(cond
((null? points) accumulator)
((single? points) accumulator)
(t (shoelace-sum
(rest points)
(+ accumulator
(* (get-x (first points)) (get-y (second points)))
(* -1 (get-x (second points)) (get-y (first points))))))))
Die Summe ist äquivalent zu der aus der Gaußschen Trapezformel. Diese hat je Punktepaar zwei Summanden mehr (x1 mal y1 und -x2 mal y2), die sich aber über alle Punkte zu Null ergänzen und deswegen entfallen können.
Die gesuchte Fläche ist die Hälfte der Summe.
(defproc polygon-area (points)
(if
(not (is-closed-polygon? points))
(throw (quote error) (list "not a closed polygon" points))
(* 1/2 (shoelace-sum points 0))))
Für den offensichtlichen Fall eines Quadrats mit Seitenlänge 2
(#1=(1 3) (3 3) (3 1) (1 1) #1#)
ergibt sich das Ergebnis -4. Das Vorzeichen des Ergebnisses zeigt an, dass die Punkte mit dem Uhrzeigersinn aufgeführt sind.
Für das Polygon
(#1=(3 4) (5 6) (9 5) (12 8) (5 11) #1#)
wird der Flächeninhalt 30 errechnet.
Die hier definierten Funktionen sind zusammen mit einigen Beispielen in der unten verlinkten Datei polygon-area.sheet.xml enthalten. Diese kann mit dem Programm Calc angezeigt und ausgeführt werden.
Quellen
https://en.wikipedia.org/wiki/Shoelace_formula
https://de.wikipedia.org/wiki/Gau%C3%9Fsche_Trapezformel
Für eine Realisierung als funktionales Programm werden zunächst die Eckpunkte durch Listen repräsentiert. Die Listen haben zwei Elemente: die Koordinaten für die x- und die y-Achse.
(setq make-point (curry (list _ _)))
(setq get-x first)
(setq get-y second)
Ein Polygon ist eine Liste von Punkten.
(setq make-polygon list)
Bei einem geschlossenen Polygon muss der erste dem letzten Punkt der Liste entsprechen.
(defproc is-closed-polygon? (points)
(= (first points) (first (last points))))
Um die Fläche des Polygons zu berechnen, werden für je zwei aufeinanderfolgende Ecken die Koordinaten über Kreuz multipliziert (x1 mal y2 und x2 mal y1) und die Differenz der beiden Produkte aufsummiert. Wegen des "über Kreuz" heißt die Formel im Englischen "Shoelace Formula".
(defproc shoelace-sum (points accumulator)
(cond
((null? points) accumulator)
((single? points) accumulator)
(t (shoelace-sum
(rest points)
(+ accumulator
(* (get-x (first points)) (get-y (second points)))
(* -1 (get-x (second points)) (get-y (first points))))))))
Die Summe ist äquivalent zu der aus der Gaußschen Trapezformel. Diese hat je Punktepaar zwei Summanden mehr (x1 mal y1 und -x2 mal y2), die sich aber über alle Punkte zu Null ergänzen und deswegen entfallen können.
Die gesuchte Fläche ist die Hälfte der Summe.
(defproc polygon-area (points)
(if
(not (is-closed-polygon? points))
(throw (quote error) (list "not a closed polygon" points))
(* 1/2 (shoelace-sum points 0))))
Für den offensichtlichen Fall eines Quadrats mit Seitenlänge 2
(#1=(1 3) (3 3) (3 1) (1 1) #1#)
ergibt sich das Ergebnis -4. Das Vorzeichen des Ergebnisses zeigt an, dass die Punkte mit dem Uhrzeigersinn aufgeführt sind.
Für das Polygon
(#1=(3 4) (5 6) (9 5) (12 8) (5 11) #1#)
wird der Flächeninhalt 30 errechnet.
Die hier definierten Funktionen sind zusammen mit einigen Beispielen in der unten verlinkten Datei polygon-area.sheet.xml enthalten. Diese kann mit dem Programm Calc angezeigt und ausgeführt werden.
Quellen
https://en.wikipedia.org/wiki/Shoelace_formula
https://de.wikipedia.org/wiki/Gau%C3%9Fsche_Trapezformel