Was ist eine effiziente Methode zur Bestimmung der Fläche des resultierenden Polygons, wenn eine Reihe von Punkten im 2D-Raum angenommen wird, die sich nicht selbst schneiden?
Nebenbei bemerkt, dies sind keine Hausaufgaben und ich suche keinen Code. Ich suche nach einer Beschreibung, mit der ich meine eigene Methode implementieren kann. Ich habe meine Ideen, eine Folge von Dreiecken aus der Liste der Punkte zu ziehen, aber ich weiß, dass es eine Reihe von Randfällen in Bezug auf konvexe und konkave Polygone gibt, die ich wahrscheinlich nicht fangen werde.
Antworten:
Hier ist die Standardmethode AFAIK. Summieren Sie grundsätzlich die Kreuzprodukte um jeden Scheitelpunkt. Viel einfacher als Triangulation.
Python-Code mit einem Polygon, das als Liste von (x, y) Scheitelpunktkoordinaten dargestellt wird und implizit vom letzten zum ersten Scheitelpunkt umläuft:
David Lehavi kommentiert: Es ist erwähnenswert, warum dieser Algorithmus funktioniert: Es ist eine Anwendung des Greenschen Theorems für die Funktionen −y und x; genau so, wie ein Planimeter funktioniert. Genauer:
Formel oben =
integral_over_perimeter(-y dx + x dy) =
integral_over_area((-(-dy)/dy+dx/dx) dy dx) =
2 Area
quelle
abs()
das Vorzeichen entfernen.Das Kreuzprodukt ist ein Klassiker.
Wenn Sie zig Millionen solcher Berechnungen durchführen müssen, versuchen Sie die folgende optimierte Version, die halb weniger Multiplikationen erfordert:
Ich benutze Array-Index zur Klarheit. Es ist effizienter, Zeiger zu verwenden. Gute Compiler erledigen das für Sie.
Es wird angenommen, dass das Polygon "geschlossen" ist, was bedeutet, dass Sie den ersten Punkt als Punkt mit dem Index N kopieren. Es wird auch angenommen, dass das Polygon eine gerade Anzahl von Punkten hat. Fügen Sie eine zusätzliche Kopie des ersten Punkts hinzu, wenn N nicht gerade ist.
Der Algorithmus wird erhalten, indem zwei aufeinanderfolgende Iterationen des klassischen produktübergreifenden Algorithmus abgewickelt und kombiniert werden.
Ich bin mir nicht so sicher, wie sich die beiden Algorithmen hinsichtlich der numerischen Genauigkeit vergleichen lassen. Mein Eindruck ist, dass der obige Algorithmus besser ist als der klassische, da die Multiplikation dazu neigt, den Genauigkeitsverlust der Subtraktion wiederherzustellen. Wenn die Verwendung von Floats wie bei der GPU eingeschränkt ist, kann dies einen erheblichen Unterschied bewirken.
EDIT: "Bereich der Dreiecke und Polygone 2D & 3D" beschreibt eine noch effizientere Methode
quelle
Diese Seite zeigt, dass die Formel
kann vereinfacht werden zu:
Wenn Sie einige Begriffe aufschreiben und sie nach gemeinsamen Faktoren von gruppieren
xi
, ist die Gleichheit nicht schwer zu erkennen.Die endgültige Summierung ist effizienter, da
n
stattdessen nur Multiplikationen erforderlich sind2n
.Ich habe gelernt , diese Vereinfachung von Joe Kington, hier .
Wenn Sie NumPy haben, ist diese Version schneller (für alle außer sehr kleinen Arrays):
quelle
Eine Reihe von Punkten ohne andere Einschränkungen definiert ein Polygon nicht unbedingt eindeutig.
Zuerst müssen Sie entscheiden, welches Polygon aus diesen Punkten erstellt werden soll - vielleicht die konvexe Hülle? http://en.wikipedia.org/wiki/Convex_hull
Dann triangulieren und Fläche berechnen. http://www.mathopenref.com/polygonirregulararea.html
quelle
Um die Triangulations- und Summen-Dreiecksbereiche zu erweitern, funktionieren diese, wenn Sie zufällig ein konvexes Polygon haben ODER wenn Sie einen Punkt auswählen, der keine Linien zu jedem anderen Punkt erzeugt, der das Polygon schneidet.
Für ein allgemeines nicht schneidendes Polygon müssen Sie das Kreuzprodukt der Vektoren (Referenzpunkt, Punkt a) (Referenzpunkt, Punkt b) summieren, wobei a und b "nebeneinander" liegen.
Angenommen, Sie haben eine Liste von Punkten, die das Polygon in der Reihenfolge definieren (die Reihenfolge ist, dass die Punkte i und i + 1 eine Linie des Polygons bilden):
Summe (Kreuzprodukt ((Punkt 0, Punkt i), (Punkt 0, Punkt i + 1)) für i = 1 bis n - 1.
Nehmen Sie die Größe dieses Kreuzprodukts und Sie haben die Oberfläche.
Dies behandelt konkave Polygone, ohne sich um die Auswahl eines guten Referenzpunkts kümmern zu müssen. Alle drei Punkte, die ein Dreieck erzeugen, das sich nicht innerhalb des Polygons befindet, haben ein Kreuzprodukt, das in die entgegengesetzte Richtung eines Dreiecks zeigt, das sich innerhalb des Polygons befindet, sodass die Flächen korrekt summiert werden.
quelle
Berechnen der Fläche des Polygons
quelle
Oder machen Sie ein Konturintegral. Mit dem Stokes-Theorem können Sie ein Flächenintegral als Konturintegral ausdrücken. Eine kleine Gauß-Quadratur und Bob ist dein Onkel.
quelle
Sprachunabhängige Lösung:
GEGEBEN: Ein Polygon kann IMMER aus n-2 Dreiecken bestehen, die sich nicht überlappen (n = Anzahl der Punkte ODER Seiten). 1 Dreieck = 3-seitiges Polygon = 1 Dreieck; 1 Quadrat = 4-seitiges Polygon = 2 Dreiecke; etc ad nauseam QED
Daher kann ein Polygon durch "Abhacken" von Dreiecken reduziert werden, und die Gesamtfläche ist die Summe der Flächen dieser Dreiecke. Versuchen Sie es mit einem Stück Papier und einer Schere. Am besten visualisieren Sie den Vorgang, bevor Sie fortfahren.
Wenn Sie 3 aufeinanderfolgende Punkte in einem Polygonpfad nehmen und mit diesen Punkten ein Dreieck erstellen, haben Sie nur eines von drei möglichen Szenarien:
Wir sind nur an Fällen interessiert, die in die erste Option fallen (vollständig enthalten).
Jedes Mal, wenn wir eines davon finden, hacken wir es ab, berechnen seine Fläche (einfach, hier wird die Formel nicht erklärt) und erstellen ein neues Polygon mit einer Seite weniger (entspricht dem Polygon mit diesem abgeschnittenen Dreieck). bis wir nur noch ein Dreieck haben.
wie man dies programmatisch umsetzt:
Erstellen Sie ein Array von (aufeinanderfolgenden) Punkten, die den Pfad um das Polygon darstellen. Beginnen Sie bei Punkt 0. Führen Sie das Array aus den Punkten x, x + 1 und x + 2 nacheinander aus. Transformieren Sie jedes Dreieck von einer Form in eine Fläche und schneiden Sie es mit einer aus Polygon erstellten Fläche. WENN der resultierende Schnittpunkt mit dem ursprünglichen Dreieck identisch ist, ist das Dreieck vollständig im Polygon enthalten und kann abgeschnitten werden. Entfernen Sie x + 1 aus dem Array und beginnen Sie erneut mit x = 0. Andernfalls (wenn sich das Dreieck außerhalb des [teilweise oder vollständig] Polygons befindet) zum nächsten Punkt x + 1 im Array wechseln.
Wenn Sie in die Kartierung integrieren möchten und von Geopunkten ausgehen, müssen Sie außerdem ZUERST von Geopunkten in Bildschirmpunkte konvertieren. Dies erfordert die Entscheidung über eine Modellierung und Formel für die Erdform (obwohl wir die Erde eher als Kugel betrachten, handelt es sich tatsächlich um ein unregelmäßiges Ovoid (Eierform) mit Dellen). Es gibt viele Modelle, für weitere Informationen Wiki. Eine wichtige Frage ist, ob Sie den Bereich als eben oder gekrümmt betrachten. Im Allgemeinen erzeugen "kleine" Bereiche, in denen die Punkte bis zu einigen km voneinander entfernt sind, keinen signifikanten Fehler, wenn sie planar und nicht konvex betrachtet werden.
quelle
Eine Möglichkeit besteht darin, das Polygon in Dreiecke zu zerlegen , die Fläche der Dreiecke zu berechnen und die Summe als Fläche des Polygons zu verwenden.
quelle
quelle
Besser als das Summieren von Dreiecken ist das Summieren von Trapezoiden im kartesischen Raum:
quelle
Die Implementierung der Schnürsenkelformel könnte in Numpy erfolgen. Angenommen, diese Eckpunkte:
Wir können die folgende Funktion definieren, um einen Bereich zu finden:
Und Ergebnisse erzielen:
Durch das Vermeiden von Schleifen ist diese Funktion ~ 50-mal schneller als
PolygonArea
:Hinweis: Ich habe diese Antwort auf eine andere Frage geschrieben . Ich erwähne dies hier nur, um eine vollständige Liste der Lösungen zu erhalten.
quelle
Meine Neigung wäre, einfach Dreiecke abzuschneiden. Ich sehe nicht ein, wie irgendetwas anderes es vermeiden könnte, schrecklich haarig zu sein.
Nehmen Sie drei aufeinanderfolgende Punkte, aus denen das Polygon besteht. Stellen Sie sicher, dass der Winkel kleiner als 180 ist. Sie haben jetzt ein neues Dreieck, dessen Berechnung kein Problem darstellen sollte. Löschen Sie den Mittelpunkt aus der Punkteliste des Polygons. Wiederholen, bis nur noch drei Punkte übrig sind.
quelle
C Art und Weise, das zu tun:
quelle
Python-Code
Wie hier beschrieben: http://www.wikihow.com/Calculate-the-Area-of-a-Polygon
Mit Pandas
quelle
quelle
cp
nimmt zwei Argumente, aber Sie nennen es mit einem.