Flächenberechnung anhand von.

[robert c. (Gast)]

Hallo liebe Leute!


Ich habe ein neues Projekt.
Und zwar möchte ich ein Programm schreiben, welches anhand von 
Koordinaten (X,Y) mir eine Fläche berechnet.

Die Anzahl der Koordinatenpunkte ist beliebig, je mehr Punkte, desto 
genauer soll die Rechnung (logischerweise) ausfallen.

Man stelle sich also eine Art Landkarte vor, die bespielsweise 
Deutschland abbildet. So soll nun auch die Fläche aussehen, die anhand 
der Punkte am Rand (Umfang) berechnet werden soll.

Nur: Wie berechne ich sowas? Ich habe leider keine Ahnung wie ich sowas 
mache.

Vielleicht könnt ihr mir helfen?!




Vielen Dank und Gruß
Robert

[robert c. (Gast)]

Nochmals zu den Punkten selbst.

Jeder Punkt hat eine X- und Y-Koordinate.

Die Anzahl der Punkte (bestehend aus X,Y) ist beliebig.

[Oppi (Gast)]

Hallo Robert,

Sie könnten zwischen allen Punkten die jeweiligen Dreiecke bilden - 
durch einfügen einer Hilfs-Diagonalen - und dann die Teilflächen der 
Einzeldreiecke aufsummieren!

Gruß, Oppi

[robert c. (Gast)]

Ok, von dem Gauß'schen Dreiecksatz habe ich schon gehört, allerdings 
weiß ich nicht, wie ich das Programm aus so etwas Dreiecke "erkennen 
lassen kann"

:)


Danke!

[TomTom (Gast)]

Eine Triangulation ist hier nicht notwendig.

Gauss bietet da eine nette Formel:
http://de.wikipedia.org/wiki/Gau%C3%9Fsche_Trapezformel


Damit kannst du den Flächeninhalt deines Polygonzuges berechnen.

[Joe G. (feinmechaniker)]

robert c. schrieb:
> Jeder Punkt hat eine X- und Y-Koordinate.
> Die Anzahl der Punkte (bestehend aus X,Y) ist beliebig.

Wenn deine Punkte beliebige Koordinaten einer geschlossenen Kurve sind, 
wie verhinderst du z.B. solche Formen? Gehören die Flächen dazu oder 
werden sie abgezogen?

[robert c. (Gast)]

Danke erstmal für den Link mit der Formel, diesen werde ich mir genauer 
ansehen.

@Joe G.: Die "weißen Flächen" würden in diesem Fall zur Fläche (grün) 
addiert werden.

Der Sinn der Flächenberechnung ist, dass ich später auch ein Volumen 
damit berechnen kann (hoffe ich zumindest) ;-)

Würde denn nun diese Gaussche Trapezformel auch die Fläche der oben 
gezeigten Karte anhand dieser einzigen Formel berechnen? Oder muss man 
zunächst die Karte in mehrere Einzel-Polygone/Trapeze unterteilen?

Das versteh' ich noch nicht.



Gruß

[D. I. (Gast)]

Dann musst du zuallererst die konvexe Hülle deiner Punktmenge berechnen 
(zum Beispiel mit Grahams Scan Algorithmus), anschließend die Fläche mit 
dieser Formel berechnen:

http://de.wikipedia.org/wiki/Graham_Scan
http://de.wikipedia.org/wiki/Polygon#Fl.C3.A4che

[robert c. (Gast)]

ok und kann man anhand derer dann auch das Volumen berechnen?


Danke :)

[robert c. (Gast)]

Das mit der konvexen Hülle verstehe ich auch noch nicht ganz.

Wird sie auch für die Flächenberechnung eines Polygons mit einer Anzahl 
von n Punkten? Oder war deine Antwort auf das Volumenberechnen bezogen?

Ich habe ein VB-Projekt gefunden, welches ausschließlich die Gaussche 
Formel zum Berechnen der Fläche benötigt und nicht die Hülle.

Nicht dass wir aneinander vorbei reden :)

Gruß
robert

[D. I. (Gast)]

Die konvexe Hülle brauchst du um diesen Spezialfall abzufangen:

Beitrag "Re: Flächenberechnung anhand von."

Mit der konvexen Hülle berechnest du erstmal nur die Punktmenge aus 
deinen XY-Kooridnaten welche minimal nötig ist um alle Punkte 
einzuspannen.

Daraus kannst du dann mit der Flächenformel die Fläche berechnen.

In 3D ist das alles etwas komplizierter, da musst du schon genau sagen 
was für ein Volumen du berechnen willst.

[robert c. (Gast)]

Wiegesagt, dieser Fehler tritt nie auf, da alle Punkte so liegen, dass 
es keine "weißen Flächen" (wie in der Karte) gibt.

Mit einem Messgerät (Tachymeter) wird zum Beispiel ein Erdhaufen 
vermessen.
Die Grundfläche des Erdhaufens liegt ja komplett (ohne "weiße Fläche") 
am Boden auf, sodass das Phänomen nicht passieren kann.


D.h., dass ich die konvexe Hülle dann doch nicht benötige?

Später soll dann berechnet werden, wieviel Kubikmeter Erde z.B. sich 
dort befinden.
Wie sieht die Volumenberechnung (3D) aus?



Gruß

[Yalu X. (yalu) (Moderator)]

Die Messpunkte alleine bilden noch kein (eindeutiges) Volumen. Du musst
dich für eine Methode entscheiden, mittels der Punkte eine Oberfläche
festzulegen. Mit dieser Oberfläche ist dann auch das Volumen definiert.

Hier findest du die Begriffe, nach denen du weitersuchen kannst:

  http://en.wikipedia.org/wiki/3D_scanner#Reconstruction.2C_or_Modeling

Wahrscheinlich ist ein Polygonnetz (Polygon mesh) das, was dich weiter-
bringt. Wenn der Erdhaufen mit dem Tachymeter zeilenweise abgescannt
wird und jede Zeile aus gleichvielen Messpunkten besteht, ist die
Erstellung dieses Modells und dessen Volumenberechnung recht einfach.

Liegen die Messpunkte unregelmäßig, musst du irgendwie entscheiden, wel-
che der Punkte jeweils benachbart sind und zusammen ein Flächenelement
bilden. Dafür gibt es in der Literatur mehrere Verfahren unterschiedli-
cher Qualität und Komplexität. Die anschließende Volumenberechung ist
dann wieder einfach.

[robert c. (Gast)]

Oh mann, das wird ja lustig ...


Zielen wir mal gleich auf die Volumenberechnung..:

 - Benötige ich für die dann auch die Gaussche Formel oder berechne ich 
die dann mit einem anderen Verfahren (wie oben schon geschrieben wurde: 
Polygonnetz)?

Ich weiß leider nicht wo ich ansetzen soll.




Gruß

[Arc N. (arc)]

Volumen wird etwas komplizierter. Stichworte: Punktewolke, QuickHull 
(3d),
http://en.wikipedia.org/wiki/Convex_polyhedra#Volume
http://www.qhull.org/ (kann auch das Volumen berechnen)

[robert c. (Gast)]

Hi,

das QuickHull-Programm berechnet ja auch dieses Polygonnetz.

Aber was genau gibt es mir dann als "Ergebnis"?



Wie errechnet man denn dann das Volumen? Das Problem ist, dass man über 
dieses Programm fast nix im Netz findet und ich noch immer nicht genau 
weiß, welches Verfahren man nehmen sollte.

Nochmals konkret:

 - Für Flächenberechnung: Gaussche Formel
 - Für Volumenberechnung: QuickHull, und/oder was noch??



Gruß

[robert c. (Gast)]

Also zur Flächenberechnung habe ich nun folgenden Code in VB 2008 
geschrieben. (VB deshalb, weil man am schnellsten einen Erfolg sieht):

Imports System.IO


Public Class Form1
    Dim AnzahlPunkte As Integer

    Dim X As New List(Of String)     'saubere aufbereitete Strings
    Dim Y As New List(Of String)
    Dim Z As New List(Of String)

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        Dim pDatei As New StreamReader("C:\test.pkn")

        Dim i As Integer                'Zählvariable
        i = 0

        Do Until pDatei.Peek() = -1
            Dim Zeile As String = pDatei.ReadLine()
            Dim trot() As String
            Dim trotz() As String
            Zeile = Zeile.Replace(".", ",")     ' Mache aus Punkt ein Komma (Trennzeichen)
            trot = Zeile.Split("  ")
            X.Add(trot(3))
            Y.Add(trot(5))
            trotz = Zeile.Split("   ")
            Z.Add(trotz(8))
            i = i + 1
        Loop

        AnzahlPunkte = X.Count        ' Zuweisung der Anzahl der Punkte
        MsgBox(gauss_area() & " m²")

    End Sub
    'Welche Einheit haben die Punkte (Koordinaten)?

    Public Function gauss_area() As Double
        Dim w As Integer
        Dim Area As Double
        Dim xs, ys, xa, ya As Double

        xs = X.Item(0)
        ys = Y.Item(0)

        For w = 0 To AnzahlPunkte - 1
            xa = X.Item(w)
            ya = Y.Item(w)
            Area = Area + (ys + ya) * (xs - xa)
            xs = xa
            ys = ya
        Next w

        ' der letzte Punkt ist wieder der erste Punkt
        xs = X.Item(0)
        ys = Y.Item(0)

        Area = Area + (ys + ya) * (xs - xa)

        ' Rückgabewert
        gauss_area = Math.Abs(Area) / 2
    End Function

End Class

Könnt gerne mal drüber schauen ob Euch ein Fehler auffällt.

Die berechnete Fläche wirkt schon noch sehr groß ;-)




Gruß
Robert

[robert c. (Gast)]

Könnte mir jemand mal Step-by-Step erklären, was ich nun (noch) machen 
muss, um das Volumen zu berechnen?


Vielen Dank!

[Arc N. (arc)]

robert c. schrieb:
> Könnte mir jemand mal Step-by-Step erklären, was ich nun (noch) machen
> muss, um das Volumen zu berechnen?
>
>
> Vielen Dank!

Bin nicht ganz so fit in diesem Bereich (Karl Heinz Buchegger kennt sich 
mit so was deutlich besser aus), aber:
Von QuickHull zum Volumen geht es z.B. über die Delaunay-Triangulation. 
Diese Triangulation kann z.T. mit dem QuickHull in n+1-Dimensionen 
berechnet werden
http://en.wikipedia.org/wiki/Delaunay_triangulation#d-dimensional_Delaunay
andere Möglichkeiten 
http://mathoverflow.net/questions/979/algorithm-for-finding-the-volume-of-a-convex-polytope
(oder in den qhull Quelltext schauen).

[robert c. (Gast)]

Ok super, vielleicht meldet sich ja Karl-Heinz mal bei mir, habe davon 
leider wirklich nicht viel Ahnung, da ich sowas noch nie gemacht habe.


Ich schau mir mal die Links durch und werde mich wieder melden, wenn ich 
fragen habe.



Gruß

[robert c. (Gast)]

So...An die Denkenden eine Frage:

Was um Himmels Willen ist in meinem Programm falsch? :)

Das Ergebnis der Fläche ist nicht richtig :o(


Könnt ihr mir sagen wo der Fehler liegt?

Ich suche seit 3 Stunden und finde nichts....



Gruß

[Läubi .. (laeubi)]

robert c. schrieb:
> Ich suche seit 3 Stunden und finde nichts....
Beispielrechnungen suchen, unittest schreiben, Zwischnergebnisse prüfen 
und nachvollziehen, für Ostern isses noch etwas weit ;)

[robert c. (Gast)]

>Beispielrechnungen suchen, unittest schreiben, Zwischnergebnisse prüfen
>und nachvollziehen, für Ostern isses noch etwas weit ;)


Soweit alles schon probiert ;)

[D. I. (Gast)]

Warum machst du so eine komplizierte for-Schleife (die eindeutig falsch 
ist)?

Ich kann kein Basic also überlasse ich dir das zu übersetzen:

double area = 0;
for (int i = 0; i < n; i++)
{
  area += (y[i] + y[(i+1)%n]) * (x[i] - x[(i+1)%n]);
}
return abs(area)/2.0;