Berechnung der Fläche eines Polygons

Hi,

ich habe mir gerade folgenden Algorithmus zur Berechnung der Fläche einer speziellen Kategorie von Polygonen überlegt:
Das Polygon soll sternförmig sein, d.h. es gibt keine Überlappungen im Polygon (anschaußlich z.B. wenn man die Ecke eines Vierecks umknickt). Ich bin mir nicht sicher ob man die Voraussetzung noch allgemeiner wählen kann.

Das Vorgehen: Man kennt alle Eckpunkte des Polygons und weiß immer den linken und rechten Nachbar von jedem Punkt.
Jetzt nimmt man einen Punkt b aus der Menge der Eckpunkte P, sowie den linken Nachbar a und den rechten Nachbar c. Durch abc wird ein Dreieck aufgespannt, da das Polygon sternförmig ist schneidet die Strecke ab keine Strecke zwischen zwei Eckpunkten des Polygons. Man kann diese Fläche leicht ausrechnen, man fährt nun rekursiv/iterativ fort auf der Menge P' in welcher der Punkt b entfernt wurde und die Verbindungsstrecken ab und bc durch ab ersetzt wurden.

Was meint ihr? Das haut für die angegebene Menge von Polygonen doch auf jeden Fall hin. Geht die Voraussetzung noch allgemeiner, so dass Polygone wie folgendes ausgenommen sind?

A-------------B
   |            /
   |  D        /
   |/   \     / 
   E     \   /
          \ /
           C

Jester

Das funktioniert noch nicht richtig. Woher weißt Du, dass die Strecke ac überhaupt im inneren des Polygons verläuft? Die kann genausogut außerhalb verlaufen. Letztlich benötigst Du aber eigentlich das sternförmig garnicht. Wichtig ist, dass das Polygon einfach ist (die Kontur hat keine Schnitte und es gibt keine Löcher). Dann kannst Du das Polygon einfach triangulieren und die Flächen der Dreiecke aufsummieren. Das geht theoretisch in Linearzeit, praktisch wohl eher in O(n log n) Zeit, wobei n die Anzahl der Eckpunkte bezeichnet.

MiP

Für konvex/konkave Polygone ist auch die Gaußsche Trapezformel zu empfehlen:
http://de.wikipedia.org/wiki/Gau%C3%9Fsche_Trapezformel

Ok, danke für die Korrektur

Wie berechnet man die Fläche eines beliebigen Polygons? Bzw. geht das überhaupt? Ich stelle mir das schwer vor, wenn man z.B. ein Rechteck nimmt wie dieses:

-----------------
|               |
-----------------

Und zum Beispiel die linke Hochkante festhält und die andere Hochkante dreht, so dass der rechte obere Punkt rechts unten und umgekehrt ist. Dann hat man so eine Art Schleife.

Da stellt sich mir zuerst einmal die Frage wie man bei diesem Polygon überhaupt die Fläche definiert

Chuck

Und das ist, wie du dir bestimmt denken kannst, nicht einheitlich.
Was ist mit Rändern, die innerhalt anderen Rändern verlaufen, also eine
Schleife, die sich im Inneren des Polygons befindet? Schneiden diese wieder
ein Stück der Fläche heraus oder nicht?

Definiere dir es so wie du es brauchst

DerAltenburger

for (i=1;i<RPPTemp.Count;i++)
      { //Alle Punkte auf Punkt[0] normieren
        RPPTemp.Point[i]->X=RPPTemp.Point[i]->X - RPPTemp.Point[0]->X;
        RPPTemp.Point[i]->Y=RPPTemp.Point[i]->Y - RPPTemp.Point[0]->Y;
      }
      RPPTemp.Point[0]->X=0;
      RPPTemp.Point[0]->Y=0;

      TotArea=0;
      for (i=2;i<RPPTemp.Count;i++)
      { Area=RPPTemp.Point[i -1 ]->X * RPPTemp.Point[i    ]->Y -
             RPPTemp.Point[i    ]->X * RPPTemp.Point[i  - 1]->Y;
        TotArea=TotArea + Area;
      }
      TotArea=TotArea / 2.0;

So klappt das ganz gut.

ACHTUNG:
Das Ergebnis kann positiv oder negativ sein!!!
Je nachdem, wie das Polygon umlaeuft.

RPPTemp ist 'ne Klasse, die beliebig viele Objekte der Klasse RealPoint enthaelt.
RealPoint ist 'ne Klasse, die x,y als double- Werte umfasst (und noch einige andere Daten).
Kann aber einfach auf ein einfaches ARRAY umgestellt werden.

Gruss
Frank

jule37

ein versuch eines algorithmus zur flächenberechnung beliebiger polynome:

m(n) = knotenmarkierung, start bei 0
ngewählt = aktuell gewählter knoten

1. lege einen graphen über das polygon
2. anzahl(knoten) = anzahl(kanten) && deg(von allen n)=2? ja: weiter bei 3, nein: ende. es ist kein polygon
3. wähle einen beliebigen knoten n1 markiere ihn mit m=0
4. wähle einen beliebigen knoten der adjazent zu n1 ist und markiere ihn mit m++
4. wähle den knoten mit der höchsten markierung. gibt es einen unmarkierten knoten der adjazent zu diesem ist?
   ja: markiere diesen unmarkierten knoten mit m++, wiederhole 4. nein: gehe zu 5
5. wähle den knoten ngewählt mit der geringsten markierung
6. ziehe eine kante vom gewählten zum knoten mit m(ni)=m(ngewählt)+2
   liegt die kante [ngewählt,ni] außerhalb des polygons?
   ja: lösche die kante und wähle den nächsten adjazenten knoten zu ngewählt. wiederhole 6.
   nein: gehe zu 7.
7. wähle ngewählt=(zielknoten der soeben gezogenen kante)
   sind ngewählt und n mit m(ni)=m(ngewählt)+2 adjazent?
   ja: weiter mit 8. nein: ziehe eine kante zum knoten mit m(ni)=m(ngewählt)+2 und wiederhole 7
8. die soeben dem graphen hinzugefügten kanten bilden nun (evtl zusammen mit bereits bestehenden kanten) einen kreis
   verbinde alle knoten, die auf diesem kreis liegen und nicht adjazent sind mit einer kante.
9. es liegen nur noch dreiecke vor. berechne die flächen
10. summiere die flächen der dreiecke. der erhaltene wert ist die gesuchte fläche

dieser algorithmus ist noch nicht computergerecht und evtl. nicht hocheffizient. mehr ein versuch eine allgemeine, formale herangehensweise für das problem zu finden. es wäre sinnvoll den graphen als adjazenzliste zu speichern.
ich habe den algorithmus mit den abgebildeten beispielpolygonen (stern, 5-eck, 4-eck) getestet und jedesmal korrekte ergebnisse bekommen.
es viel mir schwer die anweisungen möglichst genau zu formulieren. ich hoffe man versteht, was ich da meine.
selbst wenn dieser algorithmus nicht die gesuchte lösung zu dem problem dieses beitrags ist, fände ich es toll ein wenig feedback zu erhalten. man will ja schließlich aus fehlern lernen
weiterhin habe ich noch nicht genau darüber nachgedacht, wie man feststellt, ob eine kante innerhalb des polynoms liegt. man könnte die koordinaten der nachbarknoten zuhilfe nehmen.
ich hoffe ich konnte eine hilfreiche anregung geben

Werner Salomon

Mathe-Genie? schrieb:

Wie berechnet man die Fläche eines beliebigen Polygons?

Hier findest Du eine komplette Implementierung.

Gruß
Werner

MiP

Ich will mich ja nicht aufdrängen, aber Flächen beliebiger Polygone berechnet man immer noch sehr einfach mit der schon oben erwähnten Gaußschen Trapezformel. Schau dir den Link einfach mal an. Lass dich von den mathematischen Herleitungen nicht irritieren, du brauchst nur eine der beiden Formeln (welche ist egal) ganz am Anfang des Beitrags. Leichter gehts nun wirklich nicht mehr!

http://de.wikipedia.org/wiki/Gau%C3%9Fsche_Trapezformel