Trouver le centre de la géométrie de l'objet?

Étant donné un ensemble de points 2D ou 3D:

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

Selon la figure suivante, le centre de géométrie diffère du centre de masse s'il est calculé sous la forme la plus simple, à savoir une densité de masse homogène. Le problème apparaît, en effet, dans le calcul de ceux-ci. Généralement, une approche consiste à faire la moyenne des coordonnées X et des coordonnées Y séparément, c'est-à-dire à trouver une position moyenne par rapport aux points donnés (ici en 2D). Cela peut être utilisé comme centroïde pour l'ensemble des points représentant un objet. Comme indiqué, en raison du sommet supplémentaire le long du bord inférieur, pour un rectangle simple, le centre de gravité résultant est (0.5,0.4), tandis que la réponse correcte est (0.5,0.5) .
Notez que l'exemple donné est trop simple. Le problème qui nous intéresse concerne toutefois les formes complexes en 2D et les objets en 3D pour lesquels seules les coordonnées des sommets sont disponibles.
BTW, une méthode de calcul efficace est d’intérêt.

Juste pour mentionner que j'ai vérifié certains liens Web tels que ceux de Wikipedia, mais mon problème actuel est qu'il existe un groupe de points 2D et 3D qui souhaitent trouver un point représentatif de ceux-ci. Ainsi centroïde est devenu d'intérêt. Les points sont donnés sans aucune information topologique. Vous pouvez les considérer comme un nuage de points. La démonstration fournie ici indique clairement que la moyenne des coordonnées généralement connue (voir, par exemple, ce Q & A de débordement de pile ) peut être incorrecte, comme indiqué dans l'exemple.

Voici quelques implémentations pour la comparaison:

• aa = réponse acceptée ci-dessous
• coque = points de la coque convexe, c’est-à-dire le polygone en or
• cent = centroïde proposé dans Wikipedia et discuté dans aa comme le centroïde du polygone
• centl = centroïde de la polyligne comme expliqué dans aa

Visuellement, centlsemble mieux représenter la géométrie donnée que cent. Deux autres semblent prometteurs ici, mais ils sont généralement trop biaisés si la dispersion des points n’est pas homogène, comme c’est le cas habituel.
Et considérez également que, bien que la coque convexe simplifie considérablement le problème, elle peut toutefois générer des arêtes trop longues et trop courtes sans positionnement symétrique dans l'espace, c'est-à-dire qu'une prise de conscience est nécessaire si vous effectuez une moyenne simple (c'est-à-dire sans pondération) : points entiers (vert) ou sommets de polygone à coque convexe (bleu).

Une application pourrait être trouvée dans Trouver un rectangle minimum d’aire pour des points donnés? .

Chaque polygone a au minimum quatre "centres" distincts:

• Le barycenter de ses sommets.

• Le barycenter de ses bords.

• Son barycenter en tant que polygone.

• Un "centre" spécifique au SIG utile pour l'étiquetage (généralement calculé avec des méthodes exclusives non documentées).

(Ils peuvent coïncider accidentellement dans des cas particuliers, mais pour des polygones "génériques", ils constituent des points distincts.)

Un "barycenter" en général est un "centre de masse". Les trois types diffèrent par l'endroit où la masse est présumée localisée: elle se trouve soit entièrement sur les sommets, soit uniformément répartie sur les arêtes, soit uniformément dans tout le polygone lui-même.

Des méthodes simples existent pour calculer les trois barycentres. Une approche repose sur le fait fondamental que le barycentre de l'union disjointe de deux masses est la moyenne pondérée en masse totale des barycentres. On obtient facilement ce qui suit:

1. Le barycentre de deux sommets (de pondération égale) est leur moyenne. Ceci est obtenu en faisant la moyenne de leurs coordonnées séparément. Géométriquement, c'est le milieu du segment de droite joignant les deux sommets.

2. Inductivement, le barycenter de n sommets (à pondération égale) est obtenu en faisant la moyenne de leurs coordonnées séparément.

3. Le centre de gravité d'un segment de droite est son point milieu. (Ceci est clair par symétrie.)

4. Le barycenter d’une polyligne est obtenu en recherchant les points centraux de chaque segment de ligne, puis en formant leur moyenne pondérée en utilisant les longueurs de segment comme pondérations.

   Par exemple, considérons la forme en "L" délimitée par les points (0,0), (6,0), (6,12). Il existe deux segments: l’un de longueur 6 avec le milieu à ((0 + 0) / 2, (0 + 6) / 2) = (3,0) et l’autre de longueur 12 avec le milieu à ((6 + 6) / 2, (0 + 12) / 2) = (6,6). Leurs coordonnées moyennes pondérées en longueur sont donc (x, y) avec

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

   Cela diffère du barycentre des trois sommets, qui est ((0 + 6 + 6) / 3, (0 + 0 + 12) / 3) = (4,4).

   ( Modifier Comme autre exemple, considérons la figure en question, qui , bien que de forme carrée, est représentée comme un pentagone déterminée par la séquence de points (0,0), (1 / 2,0), (1,0), (1,1), (0,1) .Les cinq côtés ont les longueurs 1/2, 1/2, 1, 1, 1 et les points médians (1 / 4,0), (3 / 4,0), (1 , 1/2), (1 / 2,1) et (0,1 / 2), respectivement, leur moyenne pondérée est égale à

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

   comme on peut l’espérer, même si le barycentre des sommets seul (calculé comme au n ° 2 ci-dessus) est égal à (0.5, 0.4).)

5. Le barycentre d'un polygone peut être obtenu par triangulation pour le décomposer en triangles. Le barycenter d'un triangle-qua-polygone coïncide avec le barycenter de ses sommets. La moyenne pondérée en fonction de la superficie de ces barycentres est le barycentre du polygone. Les zones de triangle sont facilement calculées en termes de coordonnées de sommet (par exemple, en fonction du produit de coin de deux des côtés). Pour une illustration de tels calculs de surface, y compris comment exploiter des zones signées (positives ou négatives), voir la section "Zone" de la page de mon (ancien) cours .

   ( Edit Considérons le polygone décrit dans la question par exemple. Nous pourrions le trianguler avec des triangles ((0,0), (1 / 2,0), (0,1)) à gauche, ((0,1), (1 / 2,0), (1,1)) au centre et ((1,1), (1,0), (1 / 2,0)) à droite. , 1/2, 1/4 respectivement et leurs barycentres - obtenus en faisant la moyenne de leurs sommets - sont (1/6,1 / 3), (1/2 / 3/3) et (5 / 6,1 / 3), respectivement. La moyenne pondérée en fonction de la surface de ces barycentres est égale à

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

   comme il se doit, malgré la présence de ce cinquième sommet le long du bord inférieur.)

Il est évident que chacune de ces méthodes est efficace : il suffit d’un seul passage sur la représentation "spaghetti" du polygone, en utilisant (relativement peu) le temps constant à chaque étape. Notez que dans tous les cas, sauf le premier (des sommets purs), il faut plus d' informations qu'une simple liste de coordonnées de sommets: vous devez également connaître la topologie de la figure. Dans l'exemple "L", nous avions besoin de savoir que (0,0) était connecté à (6,0) et non à (6,12), par exemple.

Ce sont tous des concepts euclidiens. Ils peuvent être étendus à la sphère (ou à l'ellipsoïde) de plusieurs manières. Un simple considère les caractéristiques comme un complexe simplicial en trois dimensions (euclidiennes), calcule le barycentre approprié, puis le projette vers l'extérieur depuis le centre de l'ellipsoïde. Cela ne nécessite pas de nouveaux concepts ou formules; vous devez uniquement travailler avec une troisième (z) coordonnée en plus des deux premières coordonnées. (On trouve encore des zones en utilisant des longueurs de produits de coin.)

Une autre généralisation reconnaît que la métrique euclidienne - la racine carrée d’une somme de carrés, selon Pythagore - peut être remplacée par une autre métrique de Lp pour p> = 1: vous prenez la racine pth de la somme des pouvoirs. Trouver les "barycentres" appropriés n’est plus aussi simple, car les belles propriétés additives exploitées plus haut (les barycentres sont des moyennes pondérées des barycentres de parties plus simples d’une figure) ne tiennent plus en général. Des solutions numériques approximatives itératives doivent souvent être obtenues. Ils pourraient même ne pas être uniques.

Des centres supplémentaires peuvent être définis à différentes fins. Les triangles ont beaucoup de centres différents qui peuvent se généraliser (quelque peu) aux polygones: le centre du cercle circonscrit, le centre du cercle restreint maximal (certains), le centre de l'ellipse de surface minimale, et les autres. Tout ensemble peut être enfermé dans diverses "coques", telles que la coque convexe et les centres de ces coques obtenues.

Notez que beaucoup de ces "centres" ne sont pas nécessairement situés à l'intérieur d'un polygone. (Cependant, tout centre raisonnable d'un polygone convexe sera situé à l'intérieur de celui-ci.)

Cette variété d'approches et de solutions indique qu'il faut se méfier d'un terme générique tel que "centre de géométrie" ou simplement "centre": cela pourrait être n'importe quoi.