Polygon - Mittelpunkt und Schwerepunkt?
-
@Finnegan sagte in Polygon - Mittelpunkt und Schwerepunkt?:
Entweder man gewichtet die Vertex-Koordinaten mit der Dreiecksfläche
WIe funktioniert das?
Ich stelle mir da z.B. das Achteck von https://de.wikipedia.org/wiki/Datei:Putnam-Achteck_1.svg vor. Wie gewichte ich den mittleren Punkt, welcher ja zu 8 Dreiecken gehört?
Wie funktioniert überhaupt die Schwerpunktberechnung über eine Vermaschung?
-
Um das nochmal zu betonen: Für jedes beliebige Polynom (konstanter Dichte) kann man einfach die Eckpunkte in eine Formel einsetzen, die man überall nachschlagen kann, wo es mathematische Formeln gibt. Da braucht man nix mit Dreiecksnetz. Wenn das Netz also ein Polynom beschreibt, kann man die ganzen Dreiecke weglassen und einfach nur alle außenliegenden Ecken in die Formel einsetzen. Dann kommt das gleiche Ergebnis raus.
Was Finnegan hier mit der Gewichtung nach Dreieicksfläche meint, ist auch buchstäblich das "Gewicht" des Dreiecks. Da man konstante Dichte annimmt, ist die Fläche ja gleichzeitig das Gewicht. Man kann also den Beitrag eines Dreiecks zum Gesamtschwerpunkt eines Objekts aus vielen Dreiecken ermitteln, indem man die jeweiligen Schwerpunkte dieser Dreiecke mittelt, wobei halt jedes Dreieck mit seinem Gewicht (äquivalent seiner Fläche) beiträgt. Das funktioniert dann auch mit 3D-Körpern, oder mit verrückten Objekten mit Überschneidungen oder die nicht zusammenhängen, was ganz nützlich ist.
-
@Quiche-Lorraine sagte in Polygon - Mittelpunkt und Schwerepunkt?:
@zeropage sagte in Polygon - Mittelpunkt und Schwerepunkt?:
Ein Gegenbeispiel:
Betrachten wir mal das Polygon (0, 0), (1, 0), (1,1), (0, 1). Der Schwerpunkt liegt hier bei (0.5, 0.5). Der Mittelwert der Vektoren liegt ebenfalls bei (0.5, 0.5).
Betrachten wir aber nun das Polygon (0, 0), (1, 0), (1,1), (0, 1), (0, 0), (0, 0), (0, 0). Der Schwerpunkt liegt unverändert bei (0.5, 0.5), wohingegen der Mittelwert der Vektoren bei (2/7, 2/7) liegt.
Das stimmt, ja. Aber wenn man ein Rechteck zeichnen will, gibt man dem doch nicht noch zusätzliche Nullpunkte hinzu. Das Extreme wäre dann ein Polygon nur aus Nullpunkten. Ich kann mir jetzt in meinem beschaulichen Horizont keine Notwendigkeit dafür vorstellen.
-
@zeropage sagte in Polygon - Mittelpunkt und Schwerepunkt?:
Das stimmt, ja. Aber wenn man ein Rechteck zeichnen will, gibt man dem doch nicht noch zusätzliche Nullpunkte hinzu. Das Extreme wäre dann ein Polygon nur aus Nullpunkten. Ich kann mir jetzt in meinem beschaulichen Horizont keine Notwendigkeit dafür vorstellen.
Aber das bringt dich nicht zum Nachdenken, was an deiner Methode falsch sein soll? Nimm ein Quadrat, das hat seinen Schwerpunkt wo du es intuitiv erwartest. Nun nimm das gleiche Quadrat und mach in einer Ecke viele kleine feine Zacken, aber im großen und ganzen immer noch ein Quadrat. Nach deiner Methode ist der Schwerpunkt nun auf einmal in der Ecke mit den Zacken. Verstehst du jetzt, was mit der Methode nicht stimmt?
-
@SeppJ sagte in Polygon - Mittelpunkt und Schwerepunkt?:
Nach deiner Methode ist der Schwerpunkt nun auf einmal in der Ecke mit den Zacken. Verstehst du jetzt, was mit der Methode nicht stimmt?
Ja, ok, dieses Beispiel habe ich verstanden. Aber es ist wie in einen Ameisenhaufen treten. Am besten einen großen Bogen drum machen. Aber besten sind immer die Vorwürfe, das man "lügt", wenn man nicht alle Einzelheiten des Gegenüber vorhergesehen hat.
In meinem Asteroid Example funktioniert es sehr gut mit der Mittelpunktdrehung und es sind am Ende auch Polygone. Ich habe ein Bild und den Code geliefert. Ja, der ist wahrscheinlich so eh Scheiße, aber es ging doch.
-
@zeropage sagte in Polygon - Mittelpunkt und Schwerepunkt?:
In meinem Asteroid Example funktioniert es sehr gut mit der Mittelpunktdrehung und es sind am Ende auch Polygone. Ich habe ein Bild und den Code geliefert. Ja, der ist wahrscheinlich so eh Scheiße, aber es ging doch.
Bild? Code? Du hast nichts geliefert außer einer klar falschen Antwort.
Und jetzt ist es plötzlich "Der Lüge bezichtigen", wenn man einen mathematischen Fehler aufzeigt? Wo kommst du denn her?
-
Nee, Du behauptest, das meine Behauptung, meine Mittelpunktrechnung funktioniert in meinen Fällen, sei gelogen.
-
@zeropage sagte in Polygon - Mittelpunkt und Schwerepunkt?:
Nee, Du behauptest, das meine Behauptung, meine Mittelpunktrechnung funktioniert in meinen Fällen, sei gelogen.
Und das ist unverschämt!
???
Ich habe sogar ausdrücklich betont, dass ich dir glaube, dass du wahrscheinlich irgendeinen komischen Sonderfall hast, wo es funktioniert!
@SeppJ sagte in Polygon - Mittelpunkt und Schwerepunkt?:
Das ist eine ganz schön großzügige Auslegung dessen, was zeropage gesagt hat. Aber ich habe ja auch selber vermutet, dass er etwas wesentliches weggelassen hat, wenn es angeblich doch funktioniert, was ich ihm ja auch glaube
Aber ist halt ein komischer Sonderfall, den du verschweigst (regelmäßiges Polynom?), wo du nur Glück hast. Oder nicht genau genug misst, um zu merken, dass dein Ergebnis falsch ist.
In der Mathematik nicht Lesen oder Verstehen zu wollen, weil man es nicht als Wahrheitsfindung sondern als irgendeinen komischen persönlichen Wettkampf sieht, das ist unverschämt! Eigentlich ist es was anderes, aber das sage ich mal lieber nicht laut.
-
@Quiche-Lorraine sagte in Polygon - Mittelpunkt und Schwerepunkt?:
@Finnegan sagte in Polygon - Mittelpunkt und Schwerepunkt?:
Entweder man gewichtet die Vertex-Koordinaten mit der Dreiecksfläche
WIe funktioniert das?
Ich stelle mir da z.B. das Achteck von https://de.wikipedia.org/wiki/Datei:Putnam-Achteck_1.svg vor. Wie gewichte ich den mittleren Punkt, welcher ja zu 8 Dreiecken gehört?
Wie funktioniert überhaupt die Schwerpunktberechnung über eine Vermaschung?
Das hab ich tatsächlich etwas zu grob und unpräzise formuliert. Man nimmt nicht die Vertices des Mesh, sondern die geometrischen Schwerpunkte der Dreiecke, gewichtet mit deren Fläche.
Der Algorithmus, den ich dabei im Hinterkopf hatte, sieht etwa so aus:
mesh_centroid = [ 0, 0, 0 ] total_area = 0 for (triangle : mesh) { // Fläche des Dreiecks (z.B. via Kreuzprodukt zweier Kantenvektoren des Dreiecks, // das ja einen Vektor liefert, dessen Länge der Fläche des von den Vektoren // aufgespannten Parallelogramms entspricht). triangle_area = area(triangle) // Schwerpunkt des Dreiecks, dieser lässt sich für ein Dreieck tatsächlich durch // Mitteln berechnen :-) triangle_centroid = (triangle.p0 + triangle.p1 + triangle.p2) / 3 // Dreiecks-Schwerpunkte aufsummieren und mit Fläche gewichten mesh_centroid += triangle_centroid * triangle_area // Gesamtfläche mitführen total_area += triangle_area } // Statt durch die Anzahl der aufsummierten Vektoren, hier durch die Gesamtfläche // teilen, wodurch jeder Dreiecksschwerpunkt-Vektor im Verhältnis seiner Dreiecks- // fläche in das Endergebnis einfliesst. Ein Dreieck mit 25% der Gesamtfläche fliesst // also z.B. mit dem Faktor 0.25 in den resultierenden Schwerpunktvektor ein. mesh_centroid /= total_areaDadurch ergibt sich das Problem mit dem hohen Rang des zentralen Vertex erst gar nicht, da jedes Dreieck nur einmal in das Ergebnis einfliesst.
Edit: Achja, und wenn alle Dreiecke die gleiche Fläche haben, dann zerfällt das tatsächlich zu
(p_0 + p_1 + ... p_n) / n, d.h. für eine gute Triangulierung erhält man selbst mit der falschen Methode eine "ziemlich richtiges" Ergebnis... aber eben nur unter ganz bestimmten Voraussetzungen
-
Dieser Beitrag wurde gelöscht!
-
Also dann so? Jetzt liegt der Schwerpunkt aber außerhalb des Polygons!
#include <vector> #include <iostream> namespace std { vector<double> calculateCenterOfGravity(vector<vector<double>> poly) { vector<double> result; double sum1 = 0; double sum2 = 0; for (auto p : poly) { double x = p[0]; double y = p[1]; double s1 = (x + x + 1) * (x * y + 1 - x + 1 * y); double s2 = (y + y + 1) * (x * y + 1 - x + 1 * y); sum1 += s1 / 6.0; sum2 += s2 / 6.0; } double area = 0; for (size_t i = 0; i < poly.size() - 1; i++) { auto p1 = poly[i]; auto p2 = poly[i + 1]; double s = p1[0] * p2[1] - p2[0] * p1[1]; area += s * 0.5; } result.push_back(sum1 / area); result.push_back(sum2 / area); return result; } } // namespace std int main(int argc, char const *argv[]) { std::vector<std::vector<double>> poly; poly.push_back(std::vector<double>{10, 10}); poly.push_back(std::vector<double>{30, 20}); poly.push_back(std::vector<double>{15, 15}); auto r = calculateCenterOfGravity(poly); std::cout << "x:" << r[0] << " y:" << r[1] << "\n"; return 0; }
-
Wenn in einer Formel
steht, dann ist nicht
gemeint. Das hast du gründlich missverstanden. Aber ich kann dir nicht im Rahmen eines Forenbeitrags die Indexschreibweise in der Mathematik beibringen. Gemeint ist das "(i+1)'te x", aber das erklärt es nicht wirklich, oder? Zumal das darauf hindeutet, dass du dann bloß den nächsten Teil missverstehen würdest. Du gehst noch zur Schule und hast so etwas noch nie gesehen?
-
So könnte die korrekte Umsetzung in Python aussehen:
import dataclasses import itertools @dataclasses.dataclass class Point2D: x: float y: float def polygon_centroid(polygon: list[Point2D]): # Voraussetzung der Formel: Punkt N ist wieder Punkt 0 polygon = polygon + [polygon[0]] area = 1 / 2 * sum( (point1.x * point2.y - point2.x * point1.y) for point1, point2 in itertools.pairwise(polygon) ) print(area) centroid_x = 1 / (6 * area) * sum( (point1.x + point2.x) * (point1.x * point2.y - point2.x * point1.y) for point1, point2 in itertools.pairwise(polygon) ) centroid_y = 1 / (6 * area) * sum( (point1.y + point2.y) * (point1.x * point2.y - point2.x * point1.y) for point1, point2 in itertools.pairwise(polygon) ) return Point2D(centroid_x, centroid_y) polygon = [Point2D(10, 10), Point2D(30, 20), Point2D(15, 15)] print(polygon_centroid(polygon))Es ist leider ein bisschen schwer zu verstehen, was da genau passiert, weil es halt einfach keine ganz einfache Formel ist. Man geht durch ein Eckpunktpaar nacheinander (in meinem Programm dann jeweils
point1undpoint2), verwurstet dann deren x- und y-Koordinate zu einer Zahl, und summiert das über all diese Eckpunktpaare. Verständlicher kann ich das leider nicht erklären, außer ich könnte es dir an einer Tafel aufzeichnen. Ich hoffe, es wird wenigstens halbwegs klar, was mit der Schreibweise auf Wikipedia (oder wo immer du das nachgeschlagen hast), gemeint ist, indem du das Programm und die Formel vergleichst.PS: Das Ergebnis für dein Polygon ist
Da das ein Dreieck ist, hätte man das natürlich auch einfacher haben können, weil beim Dreieck ist der Schwerpunkt tatsächlich der Mittelwert der x- und y- Koordinaten (jeweilig). Zeigt aber, dass das Programm funktioniert.
-
@SeppJ sagte in Polygon - Mittelpunkt und Schwerepunkt?:
Wenn in einer Formel
steht, dann ist nicht
gemeint. Das hast du gründlich missverstanden. Aber ich kann dir nicht im Rahmen eines Forenbeitrags die Indexschreibweise in der Mathematik beibringen. Zumal das darauf hindeutet, dass du dann bloß den nächsten Teil missverstehen würdest. Du gehst noch zur Schule und hast so etwas noch nie gesehen?
Pardon! Jetzt hab ich's:
#include <vector> #include <iostream> namespace std { vector<double> calculateCenterOfGravity(vector<vector<double>> poly) { vector<double> result; double sum1 = 0; double sum2 = 0; double area = 0; for (size_t i = 0; i < poly.size() - 1; i++) { auto p1 = poly[i]; auto p2 = poly[i + 1]; double x0 = p1[0]; double x1 = p2[0]; double y0 = p1[1]; double y1 = p2[1]; double s1 = (x0 + x1) * (x0 * y1 - x1 * y0); double s2 = (y0 + y1) * (x0 * y1 - x1 * y0); double s3 = x0 * y1 - x1 * y0; sum1 += s1 / 6.0; sum2 += s2 / 6.0; area += s3 * 0.5; } result.push_back(sum1 / area); result.push_back(sum2 / area); return result; } } // namespace std int main(int argc, char const *argv[]) { std::vector<std::vector<double>> poly; poly.push_back(std::vector<double>{10, 10}); poly.push_back(std::vector<double>{30, 20}); poly.push_back(std::vector<double>{15, 15}); auto r = calculateCenterOfGravity(poly); std::cout << "x:" << r[0] << " y:" << r[1] << "\n"; return 0; }$ g++ Polygone.cpp -o out $ ./out x:18.3333 y:15Das scheint ja nun richtig zu sein.
@SeppJ sagte in Polygon - Mittelpunkt und Schwerepunkt?:
Du gehst noch zur Schule und hast so etwas noch nie gesehen?
Ich gehe zur Schule.
Verstehe aber nicht, was das damit zu tun hat.
-
@SeppJ sagte in Polygon - Mittelpunkt und Schwerepunkt?:
was mit der Schreibweise auf Wikipedia (oder wo immer du das nachgeschlagen hast), gemeint ist, indem du das Programm und die Formel vergleichst.
-
Ja, das sieht (beim Diagonallesen) so aus, als würde es passen.
@TaucherOne sagte in Polygon - Mittelpunkt und Schwerepunkt?:
Ich gehe zur Schule.
Verstehe aber nicht, was das damit zu tun hat.Weil das in der Mathematik der Oberstufe (aber eventuell auch nur im Leistungskurs) drankommen würde, und dir offenbar noch nicht bekannt war. Und wenn du noch zur Schule gehst, sollte ich bei den Erklärungen nicht zu viel der typischen Ausdrucksweise der Hochschulmathematik benutzen.
Dann verstehe ich auch, wieso dir nach unseren ersten Antworten offenbar nicht so schnell klar wurde, wieso es im allgemeinen keinen Punkt gibt, der von allen Ecken gleich weit entfernt ist, oder wieso der Schwerpunkt nochmal ganz was anderes wäre. Das war von der Erklärung her wahrscheinlich zu knapp für die Schule, wo man mit so etwas gerade erst anfängt und kein intuitives Gefühl dafür hat.
-
@SeppJ Sorry, ich kannte diese Schreibweise einfach noch nicht:
X = SUM[(Xi + Xi+1) * (Xi * Yi+1 - Xi+1 * Yi)] / 6 / A Y = SUM[(Yi + Yi+1) * (Xi * Yi+1 - Xi+1 * Yi)] / 6 / A
-
Eben. Das kommt in der 11? Oder gar der 12? Keine Ahnung, bin schon lange nicht mehr in einer Schule gewesen
Dann brauchst du das aber auch noch nicht kennen. Und selbst dann ist das hier nicht gerade die üblichste Schreibweise.
-
Der Vollständigkeit wegen hier noch ein Monte-Carlo-Ansatz... (probabilistisches Verfahren)
#include <vector> #include <iostream> namespace std { vector<double> calculateCenterOfGravity(vector<vector<double>> poly) { double sum1 = 0; double sum2 = 0; double area = 0; for (size_t i = 0; i < poly.size() - 1; i++) { auto p1 = poly[i]; auto p2 = poly[i + 1]; double x0 = p1[0]; double x1 = p2[0]; double y0 = p1[1]; double y1 = p2[1]; double s1 = (x0 + x1) * (x0 * y1 - x1 * y0); double s2 = (y0 + y1) * (x0 * y1 - x1 * y0); double s3 = x0 * y1 - x1 * y0; sum1 += s1 / 6.0; sum2 += s2 / 6.0; area += s3 * 0.5; } vector<double> result; result.push_back(sum1 / area); result.push_back(sum2 / area); return result; } vector<double> calculateCenterOfGravityMonteCarlo(vector<vector<double>> poly, const unsigned int seed) { srand(seed); double maxx = -(double)(unsigned int)(-1), minx = (unsigned int)(-1), maxy = -(double)(unsigned int)(-1), miny = (unsigned int)(-1); for (auto p : poly) { if (p[0] > maxx) { maxx = p[0]; } if (p[0] < minx) { minx = p[0]; } if (p[1] > maxy) { maxy = p[1]; } if (p[1] < miny) { miny = p[1]; } } double x, y; double currentBest = (unsigned int)(-1); for (size_t i = 0; i < 5000; i++) { double rx = (double)rand() / RAND_MAX * (maxx - minx) + minx; double ry = (double)rand() / RAND_MAX * (maxy - miny) + miny; double rbest = -(double)(unsigned int)(-1); for (auto p : poly) { double d = (p[0] - rx) * (p[0] - rx) + (p[1] - ry) * (p[1] - ry); if (d > rbest) { rbest = d; } } if (rbest < currentBest) { x = rx; y = ry; currentBest = rbest; cout << " Found: " << x << " " << y << "\n"; } } vector<double> result; result.push_back(x); result.push_back(y); return result; } } // namespace std int main(int argc, char const *argv[]) { std::vector<std::vector<double>> poly; poly.push_back(std::vector<double>{10, 10}); poly.push_back(std::vector<double>{30, 20}); poly.push_back(std::vector<double>{5, 5}); auto r = calculateCenterOfGravity(poly); std::cout << "x:" << r[0] << " y:" << r[1] << "\n"; r = calculateCenterOfGravityMonteCarlo(poly, 7); std::cout << "x:" << r[0] << " y:" << r[1] << "\n"; return 0; }Seltsamerweise ist das bei mir aber ziemlich ungenau... Ich habe da
x:17.2598 y:12.9228anstattx:15 y:11.6667raus. Ich kann mir das nicht erklären.
-
@TaucherOne sagte in Polygon - Mittelpunkt und Schwerepunkt?:
Seltsamerweise ist das bei mir aber ziemlich ungenau... Ich habe da
x:17.2598 y:12.9228anstattx:15 y:11.6667raus. Ich kann mir das nicht erklären.Ist ja schonmal die richtige Grössenordnung
... ich kenne den Algo nicht und hab ihn mir nicht genau angesehen, aber vielleicht konvergiert der einfach nicht sonderlich gut (sofern korrekt implementiert). Hast du mal mit der Anzahl der Iterationen gespielt? Ich würde so ins Blaue vermuten, dass das die 5000in Zeile 57 ist. Wirds mit10000oder100000eventuell besser?
