Berechnung einer Polygonfläche

Trasher

Forenlegende
Registriert
10. April 2002
Beiträge
5.842
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

Forenlegende
Registriert
10. April 2002
Beiträge
9.676
auf die idee bin ich auch schon gekommen.

:oops:


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

Forenlegende
Registriert
10. April 2002
Beiträge
5.842
Hab jetzt im Netz nen Algorithmus gefunden (n = Anzahl der Punkte):

Code:
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

Ehrenmitglied
Registriert
3. Juli 2003
Beiträge
2.237
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

Anwärter
Registriert
11. November 2003
Beiträge
23
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

Großmeister
Registriert
16. Februar 2003
Beiträge
873
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

Anwärter
Registriert
11. November 2003
Beiträge
23
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

Forenlegende
Registriert
10. April 2002
Beiträge
5.842
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:

polygon.gif


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

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

Trasher

Forenlegende
Registriert
10. April 2002
Beiträge
5.842
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

Forenlegende
Registriert
10. April 2002
Beiträge
9.676
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:


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

antimagnet

Forenlegende
Registriert
10. April 2002
Beiträge
9.676
hab nen fehhler gefunden:

antimagnet schrieb:
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:
figur2.jpg
[/quote]
 

Trasher

Forenlegende
Registriert
10. April 2002
Beiträge
5.842
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

Ehrenmitglied
Registriert
3. Juli 2003
Beiträge
2.237
@Trasher: Warum hast Du Dir die Arbeit gemacht und nicht einfach meinen Link angeschaut? Da steht die Formel fast genauso drin.
Mother_Shabubu schrieb:
Trasher schrieb:
Trasher schrieb:
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

Forenlegende
Registriert
10. April 2002
Beiträge
5.842
Stimmt. :gruebel:
Hm, das hab ich dann wohl überlesen. :oops:

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

Naja, hauptsache es funzt erstmal.
 

dannysahne

Neuling
Registriert
22. November 2006
Beiträge
1
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ß!
 
Ähnliche Beiträge

Ähnliche Beiträge

Oben