Berechnung einer Polygonfläche

[Trasher]

ha! schurke!
wenn man bei einem n-eck lediglich die koordinaten hat, ist die linienführung gar nicht immer klar!

Doch, wenn man die Reihenfolge der Punkte beachtet, ist die Linienführung eindeutig definiert.

aber irgendwie müssen wir der kiste sagen, was innen und was außen ist, und da reichen doch nur koordinaten nicht aus, oder?

Das war mal eine Übungsaufgabe im ersten Semester. War machbar, aber ebenfalls nicht trivial.

Zitat aus dem Usenet:
Fläche blau ausmalen lassen und Pixel zählen.

 

[antimagnet]

auf die idee bin ich auch schon gekommen.




muss bei so ner figur die summe der außenwinkel nicht einfach größer sein als die summe der innenwinkel?

shit, aber was ist ein innen-, was ein außenwinkel?

:gruebel:

 

[Trasher]

Hab jetzt im Netz nen Algorithmus gefunden (n = Anzahl der Punkte):

area := 0;

for i from 3 by 2 to n do
        area := area + (x[i-2] - x[i])*y[i-1] - (y[i-2]-y[i])*x[i-1]
end do

if ((n mod 2) = 0) then
     area := 0.5 * (area+x[n-1]*y[n]-y[n-1]*x[n]);
else
     area := 0.5 * area;
end if

Kann ich zwar so auf die Schnelle nicht nachvollziehen, aber zu funktionieren scheint es erst einmal. :gruebel:

 

[Mother_Shabubu]

Unter http://mathworld.wolfram.com/PolygonArea.html habe ich eine Formel für die Polygonfläche gefunden. Der Trick dabei ist der, daß man das Polygon in Dreiecke zerlegt, die jeweils durch den Ursprung und eine Polygonseite definiert werden. Die Fläche eines Dreiecks ist dabei jeweils die Hälfte der Fläche eines Parallelogramms, das aus den Ortsvektoren von jeweils zwei aufeinanderfolgenden Punkten gebildet wird. Dessen Fläche wiederum entspricht der Determinante der Matrix, die aus diesen beiden Vektoren besteht. Da die Determinante auch negativ sein kann, werden einige Dreiecke von der Gesamtfläche abgezogen und anscheinend entspricht die abgezogene Fläche gerade dem, was man bei den anderen Dreiecken zuviel hatte.

 

[McPhlogiston]

Es geht doch mit den Flächen unter den Kurven.
Da die Kurven alle Geraden sind, ist das Integrieren einfach.
Wenn der Rechner es berechnen soll, dann kann er auch WENN-DANN-Abfragen und Suchen nach dem kleinsten x-Wert.

zuerst nach dem Punkt mit dem kleinsten x-Wert suchen und diesen als Startpunkt (P1, bestehend aus x1/y1) festlegen.
Dann zum nächsten Punkt P2 (x2/y2).
Fläche unter Kurve berechnen. Ergebnis = A1
Zum nächsten Punkt P3 (x3/y3)
Fläche unter Kurve berechnen.
Abfrage: Wenn x3>x2 dann Ergebnis = A2.
Wenn x3<x2 dann Ergebnis * (-1) = A2.
(Wenn x3=x2 ist A2 sowieso 0 und interessiert nicht)
Weiter zum nächsten Punkt, bis der nächste Punkt Pn= P1.
SUMME A1 bis An bilden.
die noch in einen Betrag setzen, weil wenn man die Punkte "untenrum" statt "obenrum" betrachtet, kommt eine negative Fläche raus.

Kann mans verstehen?
Ich finde es relativ einfach.

 

[Lyle]

Das sollte allerdings so simpel nur solange funktionieren, die Seiten des Vielecks durch Funktionen darstellbar sind. Bei Parallelen zur y-Achse ist das aber nicht mehr möglich.

 

[McPhlogiston]

Häh?
Natürlich funktioniert es.
Die Fläche unter einer Parallelen zur y-Achse ist genau NULL.
Okay, vielleicht funktioniert das Programm so nicht, aber dann muss eben die Wenn xn = x (n-1) Abfrage VOR die Flächenberechnung gestellt werden, damit man nicht bei der Funktionssuche wegen Null im Nenner abbrechen muss.

 

[Trasher]

Achtung, der Algorithmus, den ich oben gepostet habe, liefert in manchen Fällen keine exakten Ergebnisse.
Hab nochmal recherchiert, die Polygonfläche kann auch so berechnet werden:

Verdammt kurz, was? Gibt bei mir gerade mal 4 Codezeilen.

Jetzt würde ich nur noch gern verstehen, warum das so ist.

 

[antimagnet]

was heißt denn "det"?

und was ist, wenn x4<x3? geht das dann auch noch?

 

[Trasher]

Ja, geht alles. Vorausgesetzt, die Punkte spannen auch wirklich eine Fläche auf.

det(M) heißt Determinante der Matrix M und wird bei einer 2x2-Matrix so berechnet:

det([[a,b][c,d]]) = a * d - b *c

Die erste Determinante wäre also x1*y2-y1*x2, die zweite x2*y3-y2*x3 usw.

 

[antimagnet]

moment:

[15, 0]; [90,25]; [90,65]; [55,90]; [0, 75]

also:

a=1/2*[(15*25)-(0*90)]+[(90*65)-(25*90)]+[(90*90)-(65*55)]+[(55*75)-(90*0)]
=1/2*[(375-0)+(5850-2250)-(8100-3575)+(4125-0)]
=1/2*[375+3600+4525+4125]
=1/2*12625
=6312,5



das hatt ich vorher raus:

5825.

moment mal, irgendwie hab ich das da ganz ähnlich berechnet... wo liegt denn jetzt der fehler?

 

[antimagnet]

hab nen fehhler gefunden:

15/0 90/0 90/25
90/65 90/90 55/90
55/90 0/90 0/65
0/65 0/0 15/0

das muss 75 heißen. also:

15/0 90/0 90/25
90/65 90/90 55/90
55/90 0/90 0/75
0/65 0/0 15/0

das rechteck außen bleibt:

0/0 90/0 90/90 0/90

hat also die größe 90*90=8100

die dreiecke

(90-15)*25 /2=937,5
(90-65)*(90-55) /2=437,5
55*(90-75) /2=412,5
65*15 /2=487,5

kacke, da hatt ichs schon richtig. war kein fehler...

mal nachrechnen...

:gruebel:

find nix. es bleibt bei:

zusammen:

2275.

das von 8100 abziehen.

8100-2275=5825.

das ist die größe deines fünfecks.

zu erinnerung:

[/quote]

 

[Trasher]

Also, der Determinanten-Algorithmus spuckt aus: 5750


Nach Deiner Variante:

A_Rechteck = 90 * 90 = 8100

A_Dreieck1 = 75*25*0.5 = 937.5
A_Dreieck2 = 25*35*0.5 = 437.5
A_Dreieck3 = 55*15*0.5 = 412.5
A_Dreieck4 = 75*15*0.5 = 562.5 <= hier haste wohl den falschen Punkt angesetzt
======================
A_Dreiecke_Summe = 2350

Rechteck - Dreiecke: 8100 - 2350 = 5750

 

[Mother_Shabubu]

@Trasher: Warum hast Du Dir die Arbeit gemacht und nicht einfach meinen Link angeschaut? Da steht die Formel fast genauso drin.

Jetzt würde ich nur noch gern verstehen, warum das so ist.

Schau Dir doch mal meinen Erklärungsversuch an. Der ist zwar auch kein richtiger Beweis, aber fürs erste sollte er doch reichen.

 

[Trasher]

Stimmt. :gruebel:
Hm, das hab ich dann wohl überlesen.

Werd mir das bei Gelegenheit wohl mal aufzeichnen müssen, um es zu verstehen.

Naja, hauptsache es funzt erstmal.

 

[dannysahne]

Hallo zusammen!

Als alter Landvermesser ist es mir die Lösung dieses Problems schon in die Wiege gelegt worden. Die obige Formel ist letzlich die gleiche, aber prinzipiell gehts mit der Flächenformel nach Gauss/Elling.

Findest du auf diversen Seiten im Netz, z.B. auch auf dieser:
http://www.xyz-roemer.de/wie.htm#Fl_projektion

Hiermit kannst du die Fläche jedes beliebigen Vielecks berechnen, außer verschränkte Figuren.

Viel Spaß!