Znaleźć środek geometrii obiektu?

Biorąc pod uwagę zestaw punktów 2D lub 3D:

Jak znaleźć środek geometrii obiektu?

Zgodnie z poniższym rysunkiem środek geometrii różni się od środka masy, jeżeli jest obliczany w najprostszej postaci, tj. Jednorodnej gęstości masy. Problem pojawia się w obliczeniach tych. Często jednym podejściem jest uśrednianie współrzędnych X i Y oddzielnie, tj. Znalezienie średniej pozycji dla danych punktów (tutaj w 2D). Może to być użyte jako środek ciężkości dla zbioru punktów reprezentujących obiekt. Jak pokazano, ze względu na dodatkowy wierzchołek wzdłuż dolnej krawędzi, dla prostego prostokąta powstały środek ciężkości wynosi (0,5,0,4), a prawidłowa odpowiedź to (0,5,0,5) .
Zauważ, że podany przykład jest zbyt prosty. Problem dotyczy jednak złożonych kształtów w 2D i obiektów w 3D, dla których dostępne są tylko współrzędne wierzchołków.
BTW, interesujący jest wydajny sposób obliczeniowy.

Wystarczy wspomnieć, że sprawdziłem niektóre łącza internetowe, takie jak Wikipedia, jednak moim obecnym problemem jest to, że istnieje grupa punktów 2D i 3D, które chcą znaleźć punkt jako reprezentatywny dla nich. W ten sposób centroid stał się interesujący. Punkty są podane bez żadnych informacji topologicznych. Możesz uznać je za chmurę punktów. Przedstawiona tutaj demonstracja ma na celu wyjaśnienie, że powszechnie znane uśrednianie współrzędnych (patrz na przykład niniejsze pytania dotyczące przepełnienia stosu ) może być niepoprawne, jak pokazano w przykładzie.

Oto kilka implementacji do porównania:

• aa = zaakceptowana odpowiedź poniżej
• chull = wypukły kadłub punktów, tj. złoty wielokąt
• cent = centroid zaproponowany w Wikipedii i omawiany w aa jako centroid wielokąta
• centl = centroid polilinii, jak wyjaśniono w aa

Wizualnie centlwygląda lepiej reprezentatywnie dla podanej geometrii w porównaniu do cent. Dwa inne wyglądają tutaj obiecująco, ale zwykle są zbyt stronnicze, jeśli rozproszenie punktów było niejednorodne, jak to zwykle bywa.
Weź również pod uwagę, że chociaż wypukły kadłub sprawia, że ​​problem jest znacznie prostszy, może jednak generować zbyt długie i zbyt krótkie krawędzie bez jakiegokolwiek symetrycznego pozycjonowania w przestrzeni, to znaczy, świadomość jest konieczna, jeśli wykonujesz proste uśrednianie (tj. Bez ważenia) w obu przypadkach : całe punkty (zielone) lub wypukłe wierzchołki wielokąta (niebieskie).

Jedną aplikację można znaleźć w Znajdowanie prostokąta o minimalnej powierzchni dla danych punktów? .

Każdy wielokąt ma co najmniej cztery odrębne „centra”:

• Barycentrum jego wierzchołków.

• Barycentrum jego krawędzi.

• Barycenter jako wielokąt.

• Specyficzne dla GIS „centrum” przydatne do etykietowania (zwykle obliczane przy użyciu nieudokumentowanych zastrzeżonych metod).

(Mogą przypadkowo zbiegać się w szczególnych przypadkach, ale dla „ogólnych” wielokątów są to odrębne punkty).

„Barycentrum” jest ogólnie „centrum masy”. Te trzy typy różnią się w zależności od miejsca, w którym przypuszczalnie znajduje się masa: albo jest całkowicie na wierzchołkach, równomiernie rozłożona na krawędziach, albo równomiernie rozłożona na całym wielokącie.

Istnieją proste metody obliczania wszystkich trzech barycentrów. Jedno podejście opiera się na podstawowym fakcie, że środek ciężkości rozłącznego połączenia dwóch mas jest średnią ważoną masą całkowitą środka ciężkości. Z tego łatwo możemy uzyskać:

1. Barycentrum dwóch (równo ważonych) wierzchołków jest ich średnią. Uzyskuje się to przez uśrednienie ich współrzędnych osobno. Geometrycznie jest to środek odcinka linii łączącego dwa wierzchołki.

2. Indukcyjnie środek ciężkości n (równo ważonych) wierzchołków uzyskuje się przez uśrednienie ich współrzędnych osobno.

3. Barycentrum odcinka linii jest jego punktem środkowym. (Wyjaśnia to symetria).

4. Barycentrum polilinii uzyskuje się przez znalezienie punktów środkowych każdego segmentu linii, a następnie utworzenie ich średniej ważonej przy użyciu długości segmentów jako wag.

   Weźmy na przykład kształt „L” wyznaczony punktami (0,0), (6,0), (6,12). Istnieją dwa segmenty: jeden o długości 6 z punktem środkowym w ((0 + 0) / 2, (0 + 6) / 2) = (3,0), a drugi o długości 12 z punktem środkowym w ((6 + 6) / 2, (0 + 12) / 2) = (6,6). Ich średnie współrzędne ważone długością wynoszą zatem (x, y)

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

   Różni się to od barycentrum trzech wierzchołków, którym jest ((0 + 6 + 6) / 3, (0 + 0 + 12) / 3) = (4,4).

   ( Edytuj Jako kolejny przykład rozważ postać w pytaniu, która choć ma kwadratowy kształt, jest reprezentowana jako pięciokąt określony przez ciąg punktów (0,0), (1 / 2,0), (1,0), (1,1), (0,1) Pięć boków ma długości 1/2, 1/2, 1, 1, 1 i punkty środkowe (1 / 4,0), (3 / 4,0), (1 , 1/2), (1 / 2,1) i (0,1 / 2), odpowiednio, a ich średnia ważona wynosi zatem

   [(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)
   

   jak można by się spodziewać, nawet jeśli sam środek wierzchołków (obliczony jak w punkcie 2 powyżej) wynosi (0,5, 0,4).)

5. Barycentrum wielokąta można uzyskać przez triangulację, aby rozłożyć go na trójkąty. Barycentrum trójkąta-qua-wielokąta pokrywa się z barycentrum jego wierzchołków. Średnia ważona powierzchniowa tych centrów barycentrycznych jest centymetrem wielokątów. Obszary trójkątów są łatwo obliczane na podstawie ich współrzędnych wierzchołków (np. Na podstawie iloczynu klina dwóch boków). Aby zilustrować takie obliczenia powierzchni, w tym sposób wykorzystania podpisanych (dodatnich lub ujemnych) obszarów, zobacz rozdział „Obszar” na mojej (starej) stronie notatek z kursu .

   ( Edytuj Weźmy na przykład wielokąt przedstawiony w pytaniu. Możemy go triangulować za pomocą trójkątów ((0,0), (1 / 2,0), (0,1)) po lewej stronie, ((0,1), (1 / 2,0), (1,1)) na środku i ((1,1), (1,0), (1 / 2,0)) po prawej stronie. Ich obszary to 1/4 Odpowiednio 1/2, 1/4 i ich centra barowe - uzyskane poprzez uśrednienie ich wierzchołków - to (1 / 6,1 / 3), (1 / 2,2 / 3) i (5 / 6,1 / 3) odpowiednio Średnia ważona powierzchni tych centrów barowych jest równa

   [(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)
   

   tak jak powinno, pomimo obecności tego piątego wierzchołka wzdłuż dolnej krawędzi).

Oczywiste jest, że każda z tych metod jest skuteczna : wymaga tylko jednego przejścia przez reprezentację wielokąta „spaghetti”, przy użyciu (dość niewielkiego) stałego czasu na każdym kroku. Zauważ, że we wszystkich przypadkach oprócz pierwszego (czystych wierzchołków) potrzeba więcej informacji niż tylko lista współrzędnych wierzchołków: musisz także znać topologię figury. W przykładzie „L” musieliśmy wiedzieć, że (0,0) było połączone na przykład z (6,0), a nie z (6,12).

To są wszystkie koncepcje euklidesowe. Można je rozszerzyć na kulę (lub elipsoidę) na kilka sposobów. Prosty przedstawia cechy jako prosty kompleks w trzech wymiarach (euklidesowych), oblicza odpowiedni środek barycentryczny, a następnie rzutuje go na zewnątrz od środka elipsoidy z powrotem na powierzchnię. Nie wymaga to żadnych nowych koncepcji ani formuł; musisz pracować tylko z trzecią współrzędną (z) oprócz pierwszych dwóch współrzędnych. (Obszary wciąż można znaleźć przy użyciu długości produktów klinowych.)

Inne uogólnienie uznaje, że metryka euklidesowa - pierwiastek kwadratowy sumy kwadratów, zgodnie z Pitagorasem - może zostać zmieniona na inne metryki Lp dla p> = 1: bierzesz piąty pierwiastek z sumy piątych mocy. Znalezienie odpowiednich „centrów barkowych” nie jest już tak proste, ponieważ piękne właściwości dodatków wykorzystane powyżej (centra barowe są ważonymi średnimi barycentrów prostszych części figury) nie są już ogólnie ważne. Często trzeba uzyskać iteracyjne przybliżone rozwiązania numeryczne. Mogą nawet nie być wyjątkowe.

Dodatkowe centra można zdefiniować dla różnych celów. Trójkąty mają wiele różnych centrów, które mogą (nieco) uogólniać na wielokąty: środek koła, środek (niektóre) maksymalnego koła, środek elipsy ograniczającej obszar minimalny i inne. Każdy zestaw może być zamknięty w różnych „kadłubach”, takich jak kadłub wypukły i uzyskane środki tych kadłubów.

Zauważ, że wiele z tych „centrów” niekoniecznie znajduje się we wnętrzu wielokąta. (Każde rozsądne centrum wypukłego wielokąta będzie jednak znajdować się w jego wnętrzu.)

Ta różnorodność podejść i rozwiązań wskazuje, że należy uważać na ogólny termin, taki jak „środek geometrii” lub po prostu „środek”: może to być wszystko.