Finden Sie den Mittelpunkt der Objektgeometrie?

37

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.

Bildbeschreibung hier eingeben

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).

Bildbeschreibung hier eingeben

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

Entwickler
quelle
Ob das funktioniert? Finden Sie den Schwerpunkt eines Polygons? (StackOverflow)
blah238
3
Ich bin mir nicht sicher, was deine Frage ist. Das Zentrum der Geometrie oder (normalerweise der Schwerpunkt) kann sich vom Schwerpunkt (Schwerpunkt) unterscheiden. Dies ist eine bekannte Tatsache. Es gibt auch verschiedene Möglichkeiten, den Mittelpunkt einer Geometrie zu berechnen. Siehe: en.wikipedia.org/wiki/Triangle_center , en.wikipedia.org/wiki/Encyclopedia_of_Triangle_Centers & faculty.evansville.edu/ck6/encyclopedia/ETC.html .
Devdatta Tengshe
1
Zum Update: Wenn keine Topologie vorhanden ist, ist eine Punktwolke nur eine Punktwolke. Ihre Figur eines polygonalen Quadrats gilt nicht (und Ihr 'Schwerpunkt' von (0,5,0,4) scheint sich nicht aus einer Standardformel zu ergeben: Symmetrie spricht stark dafür, dass ein Mittelpunkt des Quadrats mit (0,5) übereinstimmt , 0.5), egal wie es definiert ist). Unter stats.stackexchange.com/questions/1927 finden Sie einige Vorschläge zur Suche nach repräsentativen oder zentralen Standorten für Punktwolken in zwei oder mehr Dimensionen .
Whuber
1
@Entwickler, ich verstehe Ihren Punkt jetzt. Ihr fünfter Punkt am unteren Rand des "Rechtecks" (eigentlich ein Polygon) bewirkt, dass eine einfache Mittelung der Scheitelpunktkoordinaten einen anderen Schwerpunkt ergibt als die eines Polygons, wie Whubers Antwort erklärt.
blah238
1
Aha! Ich habe diesen fünften Scheitelpunkt komplett verpasst, obwohl ich nach so etwas gesucht hatte. Um zukünftigen Lesern zu helfen, habe ich die Frage leicht bearbeitet, um darauf hinzuweisen. Dies bringt auch den Kern der Sache auf den Punkt: Das Einfügen oder Löschen von Eckpunkten entlang von Kanten ändert die Darstellung einer Poly {line, gon} , sollte jedoch die Berechnung ihrer angeborenen geometrischen Eigenschaften nicht ändern. Deshalb kann der Schwerpunkt der Eckpunkte eine fast beliebige Beziehung zu den Schwerpunkten eines Polygons oder seiner Grenze haben.
Whuber

Antworten:

44

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.

whuber
quelle
An die Community: Eine so gute Antwort von 'whuber' ist nur für eine gute Frage zu erwarten, da ich mit seiner Präferenz vertraut bin. Würde es Ihnen allen etwas ausmachen, die Frage auch zu verbessern, wenn Sie sie interessant finden?)
Entwickler
Ich fand es in gewissem Sinne nützlich, irgendwann andere Contirbuter als Motivation zur Beantwortung zu geben. Ich halte dies jedoch für eine akzeptable konstruktive Antwort.
Entwickler
Können Sie erklären, warum mit Keilprodukten auf einer Kugel immer noch Bereiche gefunden werden? Wäre das kugelförmige Dreieck nicht passender? Die nächste Referenz (abgesehen von dieser hervorragenden Antwort!), Die ich gefunden habe, ist: jennessent.com/downloads/Graphics_Shapes_Online.pdf - verwendet Bereiche mit kugelförmigen Dreiecken.
Jason Davies
@Jason Ich bin fasziniert: Wie schlagen Sie vor, sphärische Dreiecksflächen zu verwenden, um Barynzen kugelförmiger Merkmale zu berechnen ?
whuber
@whuber Das kugelförmige Polygon wird in kugelförmige Dreiecke zerlegt, und der Schwerpunkt jedes Dreiecks wird berechnet, indem die kartesischen Koordinaten seiner Eckpunkte gemittelt werden. Ich schlage vor, dass der Schwerpunkt des Polygons der gewichtete Durchschnitt dieser Dreiecke ist, wobei das Gewicht die Fläche des sphärischen Dreiecks und nicht die ebene Fläche ist, wie Sie in Ihrer Antwort vorgeschlagen haben (vorausgesetzt, ich verstehe das Keilprodukt richtig).
Jason Davies