Calcul d'un centroïde de polygone sphérique

11

Je voudrais une façon générale de calculer les centroïdes pour les polygones sur une sphère.

Jusqu'à présent, la meilleure référence en ligne semble être:

Outils pour les graphiques et les formes par Jeff Jenness.

La méthode décrite ici suggère de décomposer le polygone en plusieurs triangles sphériques et de calculer la moyenne des centroïdes triangulaires sphériques, pondérée par la zone du triangle sphérique.

Je sais qu'il existe plusieurs façons de définir un polygone centroïde sphérique, mais je cherche quelque chose d'analogue aux définitions suivantes pour les points et les polylignes:

  • Points : moyenne arithmétique des vecteurs cartésiens représentant les points.
  • Polylignes : moyenne pondérée des vecteurs cartésiens représentant les points médians de chaque segment de ligne, pondérée par la longueur (sphérique) de chaque segment.

Il semble raisonnable de continuer à définir les centroïdes de polygones comme la moyenne pondérée de la décomposition triangulaire, pondérée par zone.

Ma question est de savoir si la méthode de la référence ci-dessus fonctionnera quelle que soit la décomposition triangulaire utilisée. En particulier, il mentionne la décomposition en triangles par rapport à un point arbitraire, même extérieur au polygone, de sorte que certains triangles auront des zones négatives qui contribuent à un poids négatif.

Connexe: Comment trouver le centre de la géométrie d'un objet?

Jason Davies
la source

Réponses:

9

Cela ne fonctionnera pas de manière cohérente même lorsque vous effectuez toutes les triangulations par rapport à un seul point fixe . Le problème est que les calculs sphériques et euclidiens sont mélangés sans aucune considération de ce qu'ils pourraient signifier.

Une façon de rendre cela évident est de considérer un triangle plutôt extrême, comme près de la moitié d'un hémisphère. Par exemple, en commençant à (lon, lat) = (-179, 0), parcourez l'équateur jusqu'à (0, 0), puis jusqu'au pôle nord à (0, 90), puis revenez au début à (- 179, 0). Il s'agit d'un triangle 90-179-90 comprenant la majeure partie de la moitié nord de l'hémisphère occidental. Le problème est que ses extrémités (représentées par des points blancs sur la figure) se trouvent pratiquement dans un plan: l'une est au pôle et les deux autres sont presque sur des côtés opposés. Ainsi, leur moyenne, projetée vers la sphère (le point rouge), est presque au pôle - mais c'est à peu près aussi loin de tout centre raisonnable que possible:

Grand triangle sphérique

Comme autre exemple, triangulons un polygone représentant l'hémisphère supérieur par rapport à son centre, le pôle Nord. Nous diviserons toujours l'hémisphère occidental en deux moitiés égales, chacune d'elles un triangle 90-90-90 (évitant ainsi tout problème avec d'énormes triangles couvrant l'hémisphère). L'hémisphère oriental, cependant, sera divisé en n demi-lunes égales. Les sommets de la lune k ( k = 1, 2, ..., n ) ont des coordonnées (lon, lat)

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

Lunes pour k = 8

Cette figure montre la configuration pour k = 8. Les points rouges sont les "centres" des triangles individuels calculés selon le document "Outils pour les graphiques et les formes", pp 65-67.

En faisant les calculs, je trouve qu'avec k = 2, le centre pondéré par zone est en effet au pôle Nord (comme l'indiqueraient les considérations de symétrie), mais à mesure que n augmente, le résultat se déplace rapidement dans l'hémisphère occidental et, dans le limite, approche une latitude de 89,556 degrés le long de -90 degrés de longitude. C'est à environ 50 kilomètres au sud du pôle Nord lui-même.

Certes, une erreur de +/- 50 kilomètres pour un polygone couvrant 20 000 kilomètres est faible; la quantité totale de variation arbitraire due à différentes triangulations dans ce cas n'est que de 0,5%. Évidemment, les erreurs relatives peuvent être rendues arbitrairement grandes en incluant des triangles négatifs (il suffit d'ajouter et de soustraire des triangles vraiment grands par rapport à un petit triangle). Quoi qu'il en soit, quiconque fait l'effort de faire des calculs sphériques essaie évidemment d'éviter les erreurs de projection, il recherche donc une grande précision. Cette méthode de triangulation n'est pas recommandée.

whuber
la source
Vous avez démontré que les erreurs peuvent s'accumuler pour les grands n, mais il n'est pas clair que l'approche soit nécessairement défectueuse. Quelle valeur de n avez-vous utilisée pour atteindre la valeur limite?
Jason Davies
Merci également d'avoir fait les calculs et d'avoir étudié cela en profondeur. Je veux juste un peu plus de précisions avant de pouvoir régler la question. :)
Jason Davies
Jason, j'ai ajouté un exemple préliminaire pour vous donner une certaine intuition. La limite elle-même est rapidement approchée; quelques dizaines de lunes vous procureront plusieurs chiffres significatifs. Mais le nouvel exemple devrait reposer sur tous les doutes persistants que cette triangulation pondérée fasse quoi que ce soit de raisonnable - sauf pour les petits triangles, où vous feriez bien mieux de faire les calculs en coordonnées projetées en premier lieu. La seule raison de faire des calculs sphériques est lorsque votre domaine d'analyse est vraiment global, car alors toutes les projections introduisent beaucoup de distorsion.
whuber
1
Fantastique, merci. Donc, si je comprends bien, la simple moyenne des vecteurs cartésiens ne donne pas un centroïde raisonnable pour un triangle sphérique (en particulier les grands comme votre premier exemple). J'explorerai de meilleures méthodes, par exemple trouver l'intersection des médianes du grand cercle.
Jason Davies
BTW, j'espère toujours qu'un centroïde pondéré en surface sphérique similaire à celui ci-dessus fonctionnera. Imaginez que chaque polygone reçoive un volume 3D en ajoutant un sommet à l'origine de la sphère. Ensuite, suspendez la sphère par une chaîne invisible connectée à son origine et trouvez un équilibre stable. Le centroïde est le point le plus bas (c'est la projection du centre de masse sur la surface sphérique). Cela devrait fonctionner en dehors de quelques cas ambigus, par exemple une bande faisant le tour de l'équateur, où je peux simplement choisir un point sensible. Heureux de discuter dans une nouvelle question si vous pensez que cela en vaut la peine.
Jason Davies
3

C'est une bonne idée d'énumérer les propriétés que le centroïde d'un polygone devrait avoir. Voici mes critères:

(a) C'est une propriété de l'intérieur du polygone (au lieu des sommets ou des bords). Ainsi, la division d'un bord en deux en insérant un sommet supplémentaire ne devrait pas changer la position du centroïde. Notez que la définition de Jenness du centroïde échoue sur ce critère, car la position du centroïde dépendra de la façon dont un polygone est divisé en triangles.

(b) La perturbation d'un peu de la forme du polygone devrait déplacer un peu le centroïde. Il est nécessaire ici d'imposer une restriction sur l'étendue globale du polygone (par exemple, à un seul hémisphère). Sans cette restriction, il est facile de construire des cas où le centroïde basculera soudainement du côté opposé de la terre avec un léger mouvement d'un sommet. Cette condition exclut les méthodes qui exigent que le centroïde se trouve à l'intérieur du polygone.

(c) Il devrait se réduire à la définition plane du centroïde pour les petits polygones.

Voici deux approches répondant à ces critères:

(1) Calculer le centroïde du polygone ellipsoïdal en trois dimensions et projeter de nouveau sur la surface ellipsoïdale (le long d'une normale à l'ellipsoïde). Gros avantage: le centroïde peut être calculé en divisant le polygone en formes plus simples.

(2) Le centroïde est le point avec une distance géodésique RMS minimale à tous les points à l'intérieur du polygone. Voir Buss et Fillmore, "Moyennes sphériques et applications aux splines sphériques et interpolation", ACM Transactions on Graphics 20 , 95-126 (2001). Gros avantage: le point résultant ne dépend pas de la façon dont la surface est intégrée dans R 3 .

Malheureusement, aucune de ces définitions n'est simple à mettre en pratique. Cependant , la première méthode peut être effectuée simplement pour une sphère. La meilleure zone "élémentaire" à utiliser est le quadrilatère délimité par une arête du polygone, deux méridiens passant par les extrémités de l'arête et l'équateur. Le résultat pour l'ensemble du polygone implique l'addition des contributions sur les bords. (Des mesures supplémentaires doivent être prises si le polygone encercle un pôle.)

Supposons que les extrémités du bord soient (φ 1 , λ 1 ) et (φ 2 , λ 2 ). Soit les azimuts du bord et des extrémités par α 1 et α 2 . En supposant que le rayon de la sphère est 1, l'aire du quadrilatère est

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

(Cette formule pour l'aire, due à Bessel, se comporte sensiblement mieux numériquement que la formule couramment utilisée par L'Huilier pour l'aire d'un triangle.)

Les composantes du centroïde pour ce quadrilatère sont données par

  2 Ax ⟩ = φ 2 sin (λ 2 - λ 0 ) - φ 1 sin (λ 1 - λ 0 )
  2 Ay ⟩ = cos α 02 - σ 1 ) - (φ 2 cos (λ 2 - λ 0 ) - φ 1 cos (λ 1 - λ 0 ))
  2 Az ⟩ = (λ 2 - λ 1 ) - sin α 02 - σ1 )

où σ 2 - σ 1 est la longueur du bord, et λ 0 et α 0 sont la longitude et l'azimut du bord où il traverse l'équateur, et les axes x et y sont orientés de sorte que le croisement de l'équateur soit à x = 1, y = 0. ( z est l'axe passant par le pôle, bien sûr.)

cffk
la source
Pouvez-vous expliquer pourquoi la position des centroïdes de Jenness dépendra de la façon dont un polygone est divisé en triangles? Je sais d'après l'exemple de @ whuber que le calcul du centroïde de Jenness est incorrect pour les triangles sphériques, mais que se passe-t-il si un centroïde basé sur des médianes triangulaires sphériques est utilisé à la place? Cela échouera-t-il encore?
Jason Davies
Jenness remplace efficacement le polygone sphérique par un ensemble de triangles plans et calcule leur centroïde. Clairement (?), Le résultat dépendra du partitionnement. Faire le calcul que j'ai décrit en utilisant les centroïdes des triangles sphériques est très bien. Vous pouvez trouver la formule pour le centroïde dans JE Brock, Le tenseur d'inertie pour un triangle sphérique, J. Applied Mechanics 42, 239 (1975) dx.doi.org/10.1115/1.3423535
cffk
J'ai jeté un nouveau coup d'œil au journal de Brock. Sa formule pour le centre de masse d'un triangle sphérique implique une somme sur les bords du triangle. Il peut donc être généralisé de manière triviale pour s'appliquer à un polygone (sans avoir besoin de le décomposer en triangles).
cffk
Cela vous dérange-t-il de fournir également une référence pour le calcul de la surface due à Bessel? Je n'arrive pas à le trouver nulle part, et je suis intéressé à écrire une routine de polygone sphérique rapide (et précise). Merci!
Jason Davies
Je l'ai trouvé et j'ai réalisé que vous l'aviez traduit en anglais, alors merci. :)
Jason Davies