Fläche einer unregelmäßigen Form
Ich habe eine Menge von Punkten, die auf dem Bild liegen. Diese Punkte bilden eine unregelmäßige geschlossene Form. Ich muss den Bereich dieser Form finden. Wird ein beliebiger Körper, der der normale Algorithmus ist, für die Berechnung der Fläche verwendet? Oder gibt es Unterstützung in Bibliotheken wie Boost? Ich benutze C ++.
7 Antworten
Wenn das Polygon einfach ist (es gibt keinen gemeinsamen Punkt, außer für die Paare aufeinander folgender Segmente), hilft Ihnen Wikipedia dabei:
Die Formel für das Gebiet ist
(es geht davon aus, dass der letzte Punkt derselbe ist wie der erste)
Sie können es einfach als
implementieren %Vor%Natürlich müssen die Scheitelpunkte entsprechend ihrer natürlichen Folge im Polygon angeordnet sein.
Vielleicht möchten Sie präziser sein und möglicherweise sogar ein grafisches Beispiel liefern.
Wenn zum Beispiel die Punkte nur Pixel sind, entspricht die Anzahl der Pixel der Fläche. Wenn die Punkte jedoch die Ecken eines Polygons sind, ist die Fläche des Polygons nicht so einfach zu bestimmen. Sie würden Polygontriangulation verwenden und die Flächen der erhaltenen Dreiecke summieren.
Hinweis: Wenn Sie die Reihenfolge der Punkte nicht kennen und nicht garantieren können, dass Ihr Polygon konvex ist, ist es nicht möglich, die Reihenfolge der Form zu bestimmen, da möglicherweise mehr als eine mögliche Reihenfolge der Punkte vorhanden ist ein Polygon. Wenn Sie wissen, dass das Polygon konvex ist, ist es einfach, die Reihenfolge der Punkte zu bestimmen. Die Punkte werden nur nach einem bestimmten Punkt sortiert, wobei der erste Punkt derjenige ist, der eine Linie zwischen sich und dem Anfangspunkt bildet, so dass alle anderen Punkte auf derselben Seite der Linie liegen. Die Dreiecke, die durch diesen Prozess gebildet werden, können auch verwendet werden, um die Fläche zu berechnen.
Es gibt Unterstützung für die Flächenberechnung von Polygonen in Boost.Geometry (die in Boost noch nicht akzeptiert wird und die sehr verwirrend zu verwenden ist). Andernfalls müssten Sie das Polygon bestimmen, das zuerst von Ihren Punkten definiert wird. Aus dem Blickwinkel davon sind alle Ihre Punkte Eckpunkte des Polygons, also ist es einfach eine Frage der korrekten Anordnung Ihrer Punktsätze. Eine andere Möglichkeit ist, dass Sie nach der konvexen Hülle Ihrer Punktmenge suchen (siehe Ссылка ).
Ohne Bescheidenheit beziehe ich Sie auf meine Antwort auf eine andere Frage Kombinierter Bereich von überlappende Kreise . Monte Carlo ist robust, einfach zu parallelisieren und gibt Ihnen schließlich eine Antwort auf die Genauigkeit, die Sie benötigen.
Der einfachste Weg, dies zu tun, ist wahrscheinlich, Ihre Form zu triangulieren und die Fläche der Dreiecke zu berechnen. Dave Eberly hat eine Bibliothek namens (Boost-Lizenz), die bei der Triangulation helfen kann; Es gibt weitere Informationen hier . Suchen Sie zum Beispiel nach TriangulateEC.