Obliczanie sferycznego centroidu wielokąta

11

Chciałbym ogólny sposób obliczania centroidów dla wielokątów na kuli.

Jak dotąd najlepszym źródłem informacji online jest:

Narzędzia do grafiki i kształtów autorstwa Jeffa Jennessa.

Opisana tam metoda sugeruje rozkład wielokąta na wiele trójkątów sferycznych i obliczenie średniej sferycznych centroidów trójkątów, ważonej przez obszar trójkąta sferycznego.

Wiem, że istnieje kilka sposobów definiowania sferycznego centroidu wielokąta, ale szukam czegoś analogicznego do następujących definicji punktów i polilinii:

  • Punkty : średnia arytmetyczna wektorów kartezjańskich reprezentujących punkty.
  • Polilinie : średnia ważona wektorów kartezjańskich reprezentujących punkty środkowe każdego segmentu linii, ważona przez (sferyczną) długość każdego segmentu.

Wydaje się, że rozsądną kontynuacją jest zdefiniowanie centroidów wielokątów jako średniej ważonej rozkładu trójkątnego, ważonej według powierzchni.

Moje pytanie brzmi, czy metoda z powyższego odniesienia będzie działać niezależnie od zastosowanego rozkładu trójkąta. W szczególności wspomina o rozkładzie na trójkąty względem dowolnego punktu, nawet zewnętrznego względem wielokąta, tak że niektóre trójkąty będą miały ujemne obszary, które mają ujemny ciężar.

Powiązane: Jak znaleźć środek geometrii obiektu?

Jason Davies
źródło

Odpowiedzi:

9

Nie będzie działać konsekwentnie, nawet jeśli wykonasz wszystkie triangulacje w stosunku do jednego, stałego punktu. Problem polega na tym, że obliczenia sferyczne i euklidesowe są mieszane bez uwzględnienia ich znaczenia.

Jednym ze sposobów, aby uczynić to oczywistym, jest rozważenie dość ekstremalnego trójkąta, takiego jak prawie połowa półkuli. Na przykład, zaczynając od (lon, lat) = (-179, 0), biegnij wzdłuż równika do (0, 0), następnie do bieguna północnego w (0, 90), a następnie z powrotem do początku o (- 179, 0). Jest to trójkąt 90-179-90 obejmujący większość północnej połowy zachodniej półkuli. Problem polega na tym, że jego punkty końcowe (pokazane na rysunku jako białe kropki) leżą praktycznie w płaszczyźnie: jedna znajduje się na słupie, a pozostałe dwa są prawie po przeciwnych stronach. Tak więc ich średnia, rzutowana z powrotem na kulę (czerwona kropka), znajduje się prawie na biegunie - ale to jest tak daleko od jakiegokolwiek rozsądnego centrum, jak można uzyskać:

Duży trójkąt kulisty

Jako inny przykład, triangulujmy wielokąt reprezentujący górną półkulę w stosunku do jej centrum, Bieguna Północnego. Zawsze podzielimy półkulę zachodnią na dwie równe połowy, z których każda ma trójkąt 90–90–90 (unikając w ten sposób problemów z dużymi trójkątami obejmującymi półkulę). Półkula wschodnia zostanie jednak podzielona na n równych pół-lun. Wierzchołki lune k ( k = 1, 2, ..., n ) mają współrzędne (lon, lat)

((k-1) * 180/n, 0),  (k * 180/n, 0),  (k * 180/n, 90).

Lunes dla k = 8

Ten rysunek pokazuje konfigurację dla k = 8. Czerwone kropki to pojedyncze „centra” trójkąta obliczone zgodnie z dokumentem „Narzędzia do grafiki i kształtów”, s. 65–67.

Na podstawie obliczeń stwierdzam, że przy k = 2 środek ważony powierzchniowo rzeczywiście znajduje się na biegunie północnym (co byłoby wskazane w rozważaniach dotyczących symetrii), ale wraz ze wzrostem n wynik szybko przesuwa się na półkulę zachodnią, a na granica, zbliża się do szerokości geograficznej 89.556 stopni wzdłuż długości -90 stopni. Jest to około 50 kilometrów na południe od samego bieguna północnego.

Wprawdzie błąd +/- 50 kilometrów dla wielokąta rozciągającego się na 20 000 kilometrów jest niewielki; całkowita ilość dowolnych zmian spowodowanych różnymi triangulacjami w tym przypadku wynosi tylko 0,5%. Oczywiście względne błędy mogą być dowolnie duże przez włączenie ujemnych trójkątów (wystarczy dodać i odjąć kilka naprawdę dużych trójkątów w stosunku do małego trójkąta). Niezależnie od tego, każdy, kto stara się wykonywać obliczenia sferyczne, najwyraźniej stara się uniknąć błędów projekcji, więc poszukuje wysokiej dokładności. Ta metoda triangulacji nie może być zalecana.

Whuber
źródło
Wykazałeś, że błędy mogą się kumulować dla dużej liczby n, ale nie jest jasne, czy podejście jest z konieczności błędne. Jakiej wartości n użyłeś do osiągnięcia wartości granicznej?
Jason Davies,
Dziękujemy również za wykonanie obliczeń i przyjrzenie się temu dogłębnie. Chcę tylko trochę więcej wyjaśnień, zanim będę mógł rozwiązać problem. :)
Jason Davies,
Jason, dodałem wstępny przykład, aby dać ci intuicję. Sam limit jest szybko zbliżany; kilkadziesiąt lun dostarczy ci kilka znaczących cyfr. Ale nowy przykład powinien położyć kres wszelkim utrzymującym się wątpliwościom, że ta ważona triangulacja robi coś rozsądnego - z wyjątkiem małych trójkątów, w których znacznie lepiej jest wykonać obliczenia współrzędnych rzutowanych. Jedynym powodem wykonywania obliczeń sferycznych jest fakt, że obszar analizy jest naprawdę globalny, ponieważ wówczas wszystkie prognozy wprowadzają wiele zniekształceń.
Whuber
1
Fantastycznie, dzięki. Więc jeśli dobrze rozumiem, zwykłe uśrednienie wektorów kartezjańskich nie daje rozsądnego środka ciężkości dla sferycznego trójkąta (szczególnie dużych jak twój pierwszy przykład). Zbadam lepsze metody, np. Znalezienie przecięcia median z wielkiego koła.
Jason Davies,
BTW, wciąż mam nadzieję, że centroid podobny do powyższego będzie działał. Wyobraź sobie, że każdy wielokąt otrzymuje objętość 3D, dodając wierzchołek na początku kuli. Następnie zawieś kulę za pomocą niewidzialnego sznurka związanego z jej początkiem i znajdź stabilną równowagę. Środek ciężkości jest najniżej położonym punktem (jest to rzut środka masy na powierzchnię kulistą). Powinno to działać poza kilkoma niejednoznacznymi przypadkami, np. Paskiem wokół równika, w którym mogę po prostu wybrać sensowny punkt. Z przyjemnością omawiamy nowe pytanie, jeśli uważasz, że warto.
Jason Davies,
3

Dobrym pomysłem jest wyliczenie właściwości, które powinna mieć centroid wielokąta. Oto moje kryteria:

(a) Jest to właściwość wnętrza wielokąta (zamiast wierzchołków lub krawędzi). Zatem podzielenie krawędzi na dwie części poprzez wstawienie dodatkowego wierzchołka nie powinno zmieniać położenia środka ciężkości. Zauważ, że definicja środka ciężkości według Jennessa nie spełnia tego kryterium, ponieważ położenie środka ciężkości będzie zależeć od podziału wielokąta na trójkąty.

(b) Lekkie poruszenie kształtu wielokąta powinno nieznacznie przesunąć środek ciężkości. Konieczne jest tutaj nałożenie ograniczenia na ogólny zasięg wielokąta (np. Na pojedynczą półkulę). Bez tego ograniczenia łatwo jest skonstruować przypadki, w których centroid nagle przesunie się na przeciwną stronę ziemi z lekkim ruchem wierzchołka. Ten warunek wyklucza metody wymagające, aby środek ciężkości leżał wewnątrz wielokąta.

(c) Powinien sprowadzać się do płaskiej definicji centroidu dla małych wielokątów.

Oto dwa podejścia spełniające te kryteria:

(1) Obliczyć środek ciężkości wielokąta elipsoidalnego w trzech wymiarach i rzutować z powrotem na powierzchnię elipsoidy (wzdłuż linii normalnej do elipsoidy). Duża zaleta: centroid można obliczyć, dzieląc wielokąt na prostsze kształty.

(2) Środek ciężkości jest punktem o minimalnej odległości geodezyjnej RMS do wszystkich punktów we wnętrzu wielokąta. Patrz Buss i Fillmore, „Średnie sferyczne i zastosowania do splajnów sferycznych i interpolacji”, Transakcje ACM na grafice 20 , 95–126 (2001). Duża zaleta: wynikowy punkt nie zależy od sposobu osadzenia powierzchni w R. 3 .

Niestety, żadna z tych definicji nie jest łatwa do wprowadzenia w życie. jednak pierwszą metodę można przeprowadzić po prostu dla kuli. Najlepszym do użycia „elementarnym” obszarem jest czworobok ograniczony krawędzią wielokąta, dwa południki przez punkty końcowe krawędzi i równik. Wynik dla całego wielokąta wymaga zsumowania wkładów na krawędziach. (Jeśli wielokąt otacza biegun), należy podjąć dodatkowe kroki.

Załóżmy, że punktami końcowymi krawędzi są (φ 1 , λ 1 ) i (φ 2 , λ 2 ). Niech azymuty krawędzi i punktów końcowych przez α 1 i α 2 . Zakładając, że promień kuli wynosi 1, powierzchnia czworoboku jest równa

  A = α 2 - α 1
      = 2 tan −1 [tan ½ (λ 2 - λ 1 ) sin ½ (φ 2 + φ 1 ) / cos ½ (φ 2 + φ 1 )]

(Ta formuła dla obszaru, ze względu na Bessela, jest znacznie lepiej zachowana numerycznie niż powszechnie stosowana formuła L'Huiliera dla powierzchni trójkąta.)

Składniki środka ciężkości dla tego czworoboku podano przez

  2 ⟨ x ⟩ = φ 2 sin (λ 2 - λ 0 ) - φ 1 sin (λ 1 - λ 0 )   2 ⟨ Y ⟩ = cos α 02 - σ 1 ) - (φ 2 cos (λ 2 - λ 0 ) - φ 1 cos (λ 1 - λ 0 ))   2 ⟨ z ⟩ = (λ 2 - λ 1 ) - sin α 01 )

2 - σ

gdzie σ 2 - σ 1 jest długością krawędzi i λ 0 i α 0 są długość i azymut krawędzi, gdzie przecina równik, a x i y osie są usytuowane tak, że przejście równik wynosi x = 1, y = 0. ( z jest oczywiście osią przechodzącą przez biegun).

cffk
źródło
Czy potrafisz wyjaśnić, dlaczego położenie centroidów Jennessa będzie zależeć od tego, jak wielokąt zostanie podzielony na trójkąty? Wiem z przykładu @ whubera, że ​​obliczenia centroidów Jennessa są nieprawidłowe dla trójkątów sferycznych, ale co, jeśli zamiast tego użyty zostanie centroid oparty na środkowych trójkątach sferycznych? Czy to nadal zawiedzie?
Jason Davies
Jenness skutecznie zastępuje sferyczny wielokąt zestawem płaskich trójkątów i oblicza ich środek ciężkości. Oczywiście (?) Wynik będzie zależał od partycjonowania. Wykonanie obliczeń, które nakreśliłem za pomocą centroidów sferycznych trójkątów, jest w porządku. Znajdują się wzór na ciężkości w JE Brock, bezwładność Tensor dla Triangle sferyczne, mechanika, J. Applied 42, 239 (1975) dx.doi.org/10.1115/1.3423535
cffk
Ponownie spojrzałem na artykuł Brocka. Jego wzór na środek masy sferycznego trójkąta obejmuje sumę na krawędziach trójkąta. Dlatego można go w prosty sposób uogólnić, aby zastosować go do wielokąta (bez konieczności dzielenia go na trójkąty).
cffk 28.12.12
Czy masz coś przeciwko, aby podać odniesienie do obliczenia powierzchni również z powodu Bessela? Wydaje mi się, że nie mogę go nigdzie znaleźć i jestem zainteresowany napisaniem szybkiej (i dokładnej) procedury sferycznego obszaru wielokąta. Dzięki!
Jason Davies,
Znalazłem to i zdałem sobie sprawę, że przetłumaczyłeś to na angielski, więc dziękuję. :)
Jason Davies,