Quelle est la meilleure façon de calculer un centroïde 3D (ou n-D)?

Question

Dans le cadre d’un projet en cours, je dois calculer le centroïde d’un ensemble de points dans l’espace 3D. Pour le moment, je le fais d'une manière qui semble simple mais naïve - en prenant la moyenne de chaque ensemble de points, comme dans:

centroid = average(x), average(y), average(z)

où x , y et z sont des tableaux de nombres à virgule flottante. Il semble que je me souvienne qu'il existe un moyen d'obtenir un centroïde plus précis, mais je n'ai pas trouvé d'algorithme simple pour le faire. Quelqu'un a des idées ou des suggestions? J'utilise Python pour cela, mais je peux adapter des exemples d'autres langages.

Answer 1

Contrairement au refrain commun, il existe différentes façons de définir (et de calculer) le centre d’un nuage de points. Vous avez déjà suggéré la première solution, la plus courante, et je ne ferai pas valoir qu'il n'y a rien de mal à cela:

centroïde = moyenne (x), moyenne (y), moyenne (z)

Le " problème " voici qu'il va "déformer" votre point central en fonction de la répartition de vos points. Si, par exemple, vous supposez que tous vos points se trouvent dans une boîte cubique ou dans une autre forme géométrique, mais que la plupart d'entre eux se trouvent dans la moitié supérieure, votre point central se déplacera également dans cette direction.

Pour éviter cela, vous pouvez utiliser le milieu mathématique (la moyenne des extrema) dans chaque dimension:

milieu = milieu (x), milieu (y), milieu (z)

Vous pouvez l'utiliser lorsque vous vous souciez peu du nombre de points, mais plus du cadre de sélection global, car c'est tout: le centre du cadre de sélection autour de vos points.

Enfin, vous pouvez également utiliser la médiane (l'élément au milieu) dans chaque dimension:

médiane = médiane (x), médiane (y), médiane (z)

Cela fera en quelque sorte le contraire du milieu et vous aidera réellement à ignorer les points aberrants dans votre nuage de points et à trouver un point central basé sur la répartition de vos points.

Un moyen plus efficace de trouver un "bon" Le point central pourrait consister à ignorer les 10% supérieur et inférieur de chaque dimension, puis à calculer le moyen ou le médiane . Comme vous pouvez le constater, vous pouvez définir le point central de différentes manières. Ci-dessous, je vous montre des exemples de 2 nuages ??de points 2D en tenant compte de ces suggestions.

Le point bleu foncé est le centroïde moyen (moyen). La médiane est indiquée en vert. Et le milieu est montré en rouge. Dans la deuxième image, vous verrez exactement ce dont je parlais plus tôt: le point vert est "plus proche". la partie la plus dense du nuage de points, le point rouge étant plus éloigné, en tenant compte des limites les plus extrêmes du nuage de points.

Answer 2

Non, c’est la seule formule pour le centroïde d’un ensemble de points. Voir Wikipedia: http://fr.wikipedia.org/wiki/Centroid

Answer 3

Vous mentionnez vaguement "un moyen d’obtenir un centroïde plus précis". Peut-être que vous parlez d'un centroïde qui n'est pas affecté par les valeurs aberrantes. Par exemple, le revenu moyen du ménage aux États-Unis est probablement très élevé, car un petit nombre de riches très biaisent la moyenne; ce sont les "aberrants". Pour cette raison, les statisticiens utilisent plutôt la médiane . Une façon d'obtenir la médiane consiste à trier les valeurs, puis à sélectionner celle-ci à mi-chemin dans la liste.

Peut-être cherchez-vous quelque chose comme ça, mais pour des points 2D ou 3D. Le problème est que, en 2D et plus, vous ne pouvez pas trier. Il n'y a pas d'ordre naturel. Néanmoins, il existe des moyens de se débarrasser des valeurs aberrantes.

Une solution consiste à rechercher la coque convexe des points. La coque convexe a tous les points sur le "à l'extérieur" de l'ensemble des points. Si vous faites cela et que vous jetez les points qui se trouvent sur la coque, vous rejetterez les valeurs aberrantes, et les points qui resteront donneront une image plus "représentative". centroïde. Vous pouvez même répéter ce processus plusieurs fois et le résultat est un peu comme éplucher un oignon. En fait, on l'appelle "pelage de coque convexe".

Answer 4

vous pouvez utiliser la somme de la précision augmentée - la somme de Kahan - était-ce ce à quoi vous pensiez?

Answer 5

Potentiellement plus efficace: si vous calculez cela plusieurs fois, vous pouvez l'accélérer un peu en gardant deux variables permanentes

N  # number of points
sums = dict(x=0,y=0,z=0)  # sums of the locations for each point

puis changez N et les sommes lorsque des points sont créés ou détruits. Cela change les choses de O (N) à O (1) pour les calculs au prix de plus de travail chaque fois qu'un point est créé, déplacé ou détruit.

Answer 6

Un "centroïde plus précis" Je crois que le centroïde est défini comme vous l'avez calculé. Par conséquent, il ne peut y avoir de "centroïde plus précis".

Answer 7

Oui, c'est la formule correcte.

Si vous avez un grand nombre de points, vous pouvez exploiter la symétrie du problème (cylindrique, sphérique, miroir). Sinon, vous pouvez emprunter des statistiques et faire la moyenne d'un nombre aléatoire de points et commettre quelques erreurs.

Answer 8

Vous l'avez. Ce que vous calculez, c’est le centroïde, ou le vecteur moyen.