Wie berechnet man die Fläche einer unregelmäßigen Form?

17

Ich habe ein Raumobjekt, das durch eine Sammlung von Liniensegmenten definiert ist, für die ich die Fläche berechnen muss. Die Klassen können wie folgt beschrieben werden (in Pseudocode):

class Point {
    float x; 
    float y;
    ...
    float distanceFrom(Point p);
}

class Segment {
    Point start;
    Point end;
    ...
    float length();
}

class Room {
    List<Segment> walls;
    ...
    float area();
}

Die Wände eines Raums können sich niemals irgendwo schneiden, sondern an den Endpunkten der Segmente. Außerdem werden alle erstellten "Teilschleifen" in einen neuen Raum aufgeteilt. Die Lösung muss nicht absolut genau sein (10% Fehlerquote sind akzeptabel) und wird auch nicht sehr oft berechnet (<1 / s).

algorithm geometry
quelle
7
Sinnvoller wäre es, Roomeine Liste von Points zu enthalten , und dann die Segmente zu erhalten, indem jeder Punkt miteinander verbunden und dann in einer Schleife wieder herumgeführt wird. Andernfalls ist es bei Ihrer aktuellen Konfiguration sehr östlich, falsche Werte zu erhalten (z. B. nicht geschlossener Raum, Raum mit Wand in der Mitte usw.). Dies wäre die beste Option.
MCMastery,
Eine weitere Option ist die obere Triangulierung der Form und die Berechnung der Flächen jedes Dreiecks. Der schwierige Teil ist die Triangulation. Machbar, aber nicht immer schön. Die Antwort auf die Schnürsenkel ist immer noch viel besser.
Draco18s
@MCMastery Diese Lösung funktioniert nicht, da Rooms immer vollständig sein muss und dies möglicherweise nicht der Fall ist, wenn der Player das Rooms mit Segments erstellt. Außerdem ist eine Funktion für geschlossene Räume einfach zu definieren (durchlaufen Sie einfach die Segments und stellen Sie sicher, dass sie einen Raum erstellen).

Antworten:

31

Sie können die Schnürsenkelformel von Gauß verwenden :

Sie müssen die x-Koordinate jedes Punktes nehmen, sie mit der y-Koordinate des nächsten Punktes multiplizieren, dann die y-Koordinate des aktuellen Punktes multipliziert mit der x-Koordinate des nächsten Punktes vom Ergebnis subtrahieren und zur Gesamtfläche hinzufügen. Nachdem Sie dies für jeden Punkt getan haben, halbieren Sie die Gesamtfläche, um die tatsächliche Fläche des Polygons zu erhalten. Wenn der aktuelle Punkt der letzte ist, ist der nächste der erste.

A = 0

for (i = 0; i < points.length; i++) do

    A += points[i].x * points[(i + 1) % points.length].y - points[i].y * points[(i + 1) % points.length].x

end

A /= 2
Bálint
quelle
2
Ich habe das immer verwendet, um das Kreuzprodukt zweier Vektoren zu berechnen, ohne zu wissen, dass es als Schnürsenkel-Algorithmus bezeichnet wurde
Sidar,
3
Beachten Sie, dass dies erweitert werden kann, um das Volumen eines unregelmäßigen 3D-Objekts aus Dreiecken zu berechnen, und es kann als trivialer Fall des Grundsatzes der Analysis betrachtet werden.
Dietrich Epp
5
Das Gebiet hier ist ausgeschildert. Gehen Sie die Punkte in die andere Richtung durch und das Finale Awird annulliert. Je nach Ziel A = |A|kann ein benötigt werden. Bei negativer Vorwahl kann die Fläche auf einem unregelmäßigen Donut anhand der inneren und äußeren Punkteliste (eine in umgekehrter Reihenfolge) ermittelt werden.
chux - Wiedereinsetzung von Monica
6
Denn natürlich hat entweder Gauß oder Euler eine Formel dafür.
corsiKa
0

Wir könnten auch eine Monte-Carlo-Methode anwenden.

Zeichnen Sie ein Rechteck um die beliebige Form. Nehmen Sie eine gleichmäßig verteilte PRNG-Quelle, z. Mersenne Twister, dann die Ausgabe durch Rechteck X, Y Längen mit Modulo-Funktion gebunden. Zähle die Nr. von zufälligen Punkten, die in Ihrer Form landen. Teilen Sie durch die Gesamtanzahl der generierten Punkte. Multiplizieren Sie diesen Quotienten mit der Fläche des Rechtecks. Mit jeder Iteration konvergieren Sie zum wahren Bereich. Der Algorithmus ist lächerlich parrallelisierbar und kann verwendet werden, um beliebig dimensionale Formvolumina zu berechnen, solange Sie feststellen können, ob eine R ^ N-Koordinate innerhalb der R ^ N-Grenze der Form liegt.

.

Hier verwendet jemand diese Methode, um die Kreisfläche zu finden, und verwendet sie dann zur Berechnung von pi https://www.youtube.com/watch?v=VJTFfIqO4TU

FranG
quelle
2
-1: Sie möchten kein Modulo verwenden, um es in Reichweite zu bringen. Sie möchten eine einheitliche Verteilung oder eine andere Verteilung verwenden. Wenn Sie das Modulo verwenden, treten alle möglichen statistischen Probleme auf.
user1997744
12
Diese Methode kann nützlich sein, wenn wir kein einfaches Polygon haben, sondern eine Art implizite Form, deren Rand schwer auszudrücken ist, wie ein Fraktal- oder Metaball-Blob. Für den Fall eines Polygons wie in der Frage scheint es jedoch unnötig teuer zu sein.
DMGregory
Wie @DMGregory betonte, ist dies nicht das, wonach ich gesucht habe. Ich denke jedoch, dass es eine +1 verdient, falls jemand anderes es braucht.
Das ist interessant, aber würden die Kosten für die Inklusionstests nicht unerschwinglich werden? Wenn Sie also eine Form haben, die komplex genug ist, um diesen Ansatz zu rechtfertigen, wären die Inklusionstests dann auch sehr teuer, sodass Sie nicht massenweise davon machen möchten? (unter der Annahme von Polygonen)
Mattia
Ok, Modulo ist zwar problematisch, aber es ist eine einfache Lösung. Was wir wirklich bekommen, ist zufälliges P = 1/2 Bits 0/1, was wir also bekommen, ist eine gleichmäßige Verteilung von Zahlen, z. für 3 Bits von 0 bis 7. Wenn Rand% 5 den Wert 6 oder 7 annimmt, wird er auf 1 oder 2 abgebildet, wodurch die Häufigkeit um 1,2 erhöht und die Verteilung ungleichmäßig wird. Um dies zu vermeiden, benötigen Sie so etwas wie eine Zustandsmaschine, die das Mapping dreht, z. 6,7 karten auf 1,2 dann auf 3,4 dann auf 5,0 und es geht weiter. Wir könnten auch 6,7 wegwerfen, wenn sie auftauchen. Wie auch immer, das ist ein Implementierungsproblem der Bibliothek.
Freitag,
-1

Ein anderer Ansatz: Nicht.

Stattdessen:

while (Segments.Count > 3)
{
    Segment A = Segments[Segments.Count - 2];
    Segment B = Segments[Segments.Count - 1];
    Segment C = new Segment(B.End, A.Start);
    Triangle T = new Triangle(A, B, C);
    Segments[Segments.Count - 2] = C;
    Segments.RemoveAt(Segments.Count - 1);
    if (B is inside the new shape Segments)
        Area -= T.Area;
    else
        Area += T.Area;
}
Area += new Triangle(Segments[0], Segments[1], Segments[2]).Area;

Im Grunde genommen ein Dreieck abschneiden. Die Fläche eines Dreiecks ist einfach und auf diese Weise haben wir die Segmentanzahl des Rests um eins verringert. Wiederholen, bis noch ein Dreieck übrig ist.

Loren Pechtel
quelle
2
Die Formel von Gauß 'Schnürsenkel ist eine Abkürzung dafür, die die Anzahl der Berechnungen halbiert oder zu einem Drittel reduziert. Arbeite es aus.
Pieter Geerkens