Finden Sie den Mittelpunkt der Objektgeometrie?

Für eine Reihe von 2D- oder 3D-Punkten gilt Folgendes:

Wie finde ich den Mittelpunkt der Geometrie eines Objekts?

Nach der folgenden Abbildung unterscheidet sich der Geometriemittelpunkt vom Massenmittelpunkt, wenn er in der einfachsten Form, dh der homogenen Massendichte, berechnet wird. Das Problem tritt tatsächlich bei der Berechnung dieser auf. Häufig besteht ein Ansatz darin, die X- Koordinaten und Y- Koordinaten getrennt zu mitteln, dh eine durchschnittliche Position zu den angegebenen Punkten zu finden (hier in 2D). Dies kann als Schwerpunkt für die Punktmenge verwendet werden, die ein Objekt darstellt. Wie gezeigt ist aufgrund des zusätzlichen Scheitelpunkts entlang der unteren Kante für ein einfaches Rechteck der resultierende Schwerpunkt (0,5,0,4), während die richtige Antwort (0,5,0,5) ist .
Beachten Sie, dass das angegebene Beispiel zu einfach ist. Das interessierende Problem betrifft jedoch komplexe Formen in 2D und Objekte in 3D, für die nur Koordinaten von Scheitelpunkten verfügbar sind.
Übrigens ist ein effizienter rechnerischer Weg von Interesse.

Nur um zu erwähnen, dass ich einige Weblinks wie die von Wikipedia überprüft habe. Mein aktuelles Problem ist jedoch, dass es eine Gruppe von 2D- und 3D-Punkten gibt, die einen Punkt als repräsentativ für diese finden möchten. So wurde der Schwerpunkt von Interesse. Die Punkte werden ohne topologische Informationen angegeben. Sie können sie als Punktwolke betrachten. Die hier gezeigte Demonstration soll verdeutlichen, dass die allgemein bekannte Mittelung von Koordinaten (siehe zum Beispiel diese Fragen und Antworten zum Stapelüberlauf ) möglicherweise nicht korrekt ist, wie im Beispiel gezeigt.

Hier sind einige Implementierungen zum Vergleich:

• aa = akzeptierte Antwort unten
• chull = konvexe Hülle von Punkten, dh das goldene Polygon
• cent = centroid wird in Wikipedia vorgeschlagen und in aa als Polygon-Centroid diskutiert
• centl = Schwerpunkt der Polylinie wie in aa erklärt

Optisch centlsieht die angegebene Geometrie besser repräsentativ aus als cent. Zwei andere sehen hier vielversprechend aus, aber normalerweise sind sie zu voreingenommen, wenn die Streuung der Punkte inhomogen war, wie es im Normalfall der Fall ist.
Beachten Sie auch, dass die konvexe Hülle das Problem zwar einigermaßen vereinfacht, jedoch möglicherweise zu lange und zu kurze Kanten ohne symmetrische Positionierung im Raum erzeugt. Das heißt, Sie müssen sich bewusst sein, wenn Sie für beide Fälle eine einfache Mittelwertbildung (dh ohne Gewichtung) durchführen : ganze Punkte (grün) oder konvexe Polygonscheitelpunkte (blau).

Eine Anwendung finden Sie unter Ermitteln des Mindestflächenrechtecks ​​für bestimmte Punkte. .

Jedes Polygon hat mindestens vier verschiedene "Zentren":

• Der Schwerpunkt seiner Eckpunkte.

• Der Schwerpunkt seiner Ränder.

• Sein Schwerpunkt als Polygon.

• Ein GIS-spezifisches "Zentrum", das für die Kennzeichnung nützlich ist (in der Regel mit nicht dokumentierten proprietären Methoden berechnet).

(In besonderen Fällen können sie versehentlich zusammenfallen, bei "generischen" Polygonen handelt es sich jedoch um unterschiedliche Punkte.)

Ein "Schwerpunkt" ist im Allgemeinen ein "Schwerpunkt". Die drei Typen unterscheiden sich darin, wo sich die Masse vermutlich befindet: Sie befindet sich entweder vollständig auf den Eckpunkten, verteilt sich gleichmäßig auf den Kanten oder verteilt sich gleichmäßig über das gesamte Polygon.

Es gibt einfache Methoden, um alle drei Schwerpunktbereiche zu berechnen. Ein Ansatz beruht auf der grundlegenden Tatsache, dass der Schwerpunkt der disjunkten Vereinigung zweier Massen der nach Gesamtmasse gewichtete Durchschnitt der Schwerpunkt ist. Daraus erhalten wir leicht die folgenden:

1. Das Schwerpunktszentrum zweier (gleichgewichteter) Eckpunkte ist ihr Durchschnitt. Dies wird erhalten, indem ihre Koordinaten getrennt gemittelt werden. Geometrisch ist es der Mittelpunkt des Liniensegments, das die beiden Eckpunkte verbindet.

2. Induktiv wird der Schwerpunkt von n (gleichgewichteten) Eckpunkten erhalten, indem deren Koordinaten separat gemittelt werden.

3. Der Schwerpunkt eines Liniensegments ist sein Mittelpunkt. (Dies ist klar durch Symmetrie.)

4. Der Schwerpunkt einer Polylinie wird erhalten, indem die Mittelpunkte jedes Liniensegments ermittelt werden und dann ihr gewichteter Durchschnitt unter Verwendung der Segmentlängen als Gewichte gebildet wird.

   Betrachten Sie zum Beispiel die "L" -Form, die durch die Punkte (0,0), (6,0), (6,12) abgegrenzt ist. Es gibt zwei Segmente: eines der Länge 6 mit Mittelpunkt bei ((0 + 0) / 2, (0 + 6) / 2) = (3,0) und eines der Länge 12 mit Mittelpunkt bei ((6 + 6) / 2, (0 + 12) / 2) = (6,6). Ihre längengewichteten Durchschnittskoordinaten sind daher (x, y) mit

   x = (6*3 + 12*6) / (6+12) = 5,  y = (6*0 + 12*6) / (6+12) = 4.
   

   Dies unterscheidet sich vom Schwerpunkt der drei Eckpunkte, der ((0 + 6 + 6) / 3, (0 + 0 + 12) / 3) = (4,4) ist.

   ( Bearbeiten Betrachten Sie als weiteres Beispiel die Abbildung in der Frage, die zwar quadratisch ist, jedoch als Fünfeck dargestellt wird , das durch die Abfolge der Punkte (0,0), (1 / 2,0), (1,0) bestimmt wird. (1,1), (0,1) Die fünf Seiten haben Längen 1/2, 1/2, 1, 1, 1 und Mittelpunkte (1 / 4,0), (3 / 4,0), (1 , 1/2), (1 / 2,1) bzw. (0,1 / 2) .Ihr gewichteter Durchschnitt ist daher gleich

   [(1/2)*(1/4, 0) + (1/2)*(3/4, 0) + (1)*(1, 1/2) + (1)*(1/2, 1) + (1)*(0, 1/2)] / (1/2+1/2+1+1+1)
   = (2/4, 2/4) = (0.5, 0.5)
   

   wie man hoffen würde, obwohl der Schwerpunkt der Eckpunkte alleine (berechnet wie in # 2 oben) (0,5, 0,4) ist.

5. Der Schwerpunkt eines Polygons kann durch Triangulation erhalten werden, um es in Dreiecke zu zerlegen. Der Schwerpunkt eines Dreiecks-Qua-Polygons fällt mit dem Schwerpunkt seiner Eckpunkte zusammen. Der flächengewichtete Durchschnitt dieser Barytzentren ist das Barytzentrum des Polygons. Dreiecksflächen lassen sich leicht anhand ihrer Scheitelpunktkoordinaten berechnen (z. B. anhand des Keilprodukts von zwei der Seiten). Eine Illustration solcher Flächenberechnungen, einschließlich der Verwendung von vorzeichenbehafteten (positiven oder negativen) Flächen, finden Sie im Abschnitt "Fläche" auf meiner (alten) Seite mit Kursnotizen .

   ( Bearbeiten Betrachten Sie beispielsweise das in der Frage dargestellte Polygon. Wir könnten es mit den Dreiecken ((0,0), (1 / 2,0), (0,1)) links, ((0,1), (1 / 2,0), (1,1)) in der Mitte und ((1,1), (1,0), (1 / 2,0)) auf der rechten Seite. Ihre Flächen sind 1/4 , 1/2, 1/4 und ihre Barytzentren - erhalten durch Mittelung ihrer Eckpunkte - sind (1 / 6,1 / 3), (1 / 2,2 / 3) und (5 / 6,1 / Der flächengewichtete Durchschnitt dieser Barytzentren ist gleich

   [(1/4)*(1/6,1/3) + (1/2)*(1/2,2/3) + (1/4)*(5/6,1/3)] / (1/4 + 1/2 + 1/4)
   = (12/24, 6/12)
   = (0.5, 0.5)
   

   wie es sollte, trotz des Vorhandenseins dieses fünften Scheitelpunktes entlang der Unterkante.)

Es ist offensichtlich, dass jede dieser Methoden effizient ist : Es ist nur ein einziger Durchgang über die "Spaghetti" -Darstellung des Polygons erforderlich, wobei bei jedem Schritt (ziemlich wenig) konstante Zeit verwendet wird. Beachten Sie, dass in allen Fällen außer der ersten (von reinen Scheitelpunkten) mehr Informationen als nur eine Liste von Scheitelpunktkoordinaten erforderlich sind: Sie müssen auch die Topologie der Figur kennen. Im "L" -Beispiel mussten wir beispielsweise wissen, dass (0,0) mit (6,0) und nicht mit (6,12) verbunden war.

Dies sind alles euklidische Konzepte. Sie können auf verschiedene Arten auf die Kugel (oder das Ellipsoid) ausgedehnt werden. Ein einfacher Benutzer betrachtet die Merkmale als einen einfachen Komplex in drei (euklidischen) Dimensionen, berechnet das entsprechende Schwerpunktzentrum und projiziert es dann vom Mittelpunkt des Ellipsoids nach außen zurück auf die Oberfläche. Dies erfordert keine neuen Konzepte oder Formeln. Sie müssen nur mit einer dritten (z) Koordinate zusätzlich zu den ersten beiden Koordinaten arbeiten. (Bereiche werden immer noch mit Längen von Keilprodukten gefunden.)

Eine andere Verallgemeinerung erkennt, dass die euklidische Metrik - die Quadratwurzel einer Quadratsumme nach Pythagoras - für p> = 1 in eine andere Lp-Metrik geändert werden kann : Sie nehmen die p-te Wurzel der Summe der p-ten Potenzen. Geeignete "Barytzentren" zu finden, ist nicht mehr so ​​einfach, da die oben ausgenutzten schönen additiven Eigenschaften (Barytzentren sind gewichtete Mittelwerte von Barytzentren aus einfacheren Teilen einer Figur) im Allgemeinen nicht mehr gelten. Oft müssen iterative numerische Näherungslösungen erhalten werden. Sie könnten nicht einmal einzigartig sein.

Zusätzliche Zentren können für verschiedene Zwecke definiert werden. Dreiecke haben viele verschiedene Zentren, die (etwas) zu Polygonen verallgemeinern können: das Zentrum des Kreises, das Zentrum des (einen) maximalen Kreises, das Zentrum einer Begrenzungsellipse mit minimaler Fläche und andere. Jeder Satz kann in verschiedene "Rümpfe" eingeschlossen werden, wie den konvexen Rumpf und die Mittelpunkte dieser erhaltenen Rümpfe.

Beachten Sie, dass sich viele dieser "Zentren" nicht unbedingt im Inneren eines Polygons befinden. (Jedes vernünftige Zentrum eines konvexen Polygons liegt jedoch innerhalb seines Inneren.)

Diese Vielzahl von Ansätzen und Lösungen deutet darauf hin, dass man sich vor einem allgemeinen Begriff wie "Zentrum der Geometrie" oder nur "Zentrum" hüten sollte: Es könnte so gut wie alles sein.