Déterminer le centre de gravité

Version imprimable

29/09/2006, 11h20
gids01

Déterminer le centre de gravité

Bonjour,

Je réalise une application en PHP, qui récupère des fichiers contenant des formes diverses.

Pour le moment, je récupère les formes de la manière suivante:

J'obtiens les coordonnées (x, y) des différents points du polygone.

Par exemple pour un carré: j'ai 4 points dont les coord sont:

1. (0,0)
2. (0,1)
3. (1,0)
4. (1,1)

Maintenant, j'aimerais trouver les coordonnées du centre de gravité de ce polygone, indépendamment du nombre de cotés.

Le polygone n'est simplement pas concave et ne contient pas d'arcs de cercle pour le moment.

Qqun peut-il m'aider?

Merci
29/09/2006, 11h51
®om

Tu fais simplement la moyenne des x et la moyenne des y, non?
Donc dans le cas de ton exemple, (.5,.5)...
29/09/2006, 11h54
Nemerle

+1
29/09/2006, 12h05
gids01

Oui ca marche avec un carré tout simple.

Mais si tu prends un polygone de 8 cotés quelconque par exemple(pas un octogone régulier), je ne crois pas que ta technique marche?

Dans tous les cas, merci pour ta réponse....
29/09/2006, 12h07
ToTo13

est ce que ca fonctionne aussi pour des polygones quelconques : non convexes, troués,...
j'en suis pas sûr.
29/09/2006, 12h08
®om

Citation:

Envoyé par gids01

Oui ca marche avec un carré tout simple.

Mais si tu prends un polygone de 8 cotés quelconque par exemple(pas un octogone régulier), je ne crois pas que ta technique marche?

Exact, si par exemple tu mets plein de points sur la gauche, mais qui ne changent pas grand chose à la forme, et 1 seul sur la droite, le point de gravité serait à gauche, ce qui est stupide...

Ca ne marche donc que pour les polygones réguliers...
29/09/2006, 12h09
gids01

Dans un premier temps, j'aimerais me consacrer à des polygones convexes et sans trous.
29/09/2006, 12h10
®om

"Le centre de gravité minimise la somme des carrés des distances pondérées."
http://xavier.hubaut.info/coursmath/app/europe.htm
29/09/2006, 12h21
gids01

Merci, ca a l'air très intéressant....

je vais y jeter un oeil
29/09/2006, 13h14
gids01

En fait ca parle également de masse positionnée à chaque pont.

Ce n'est pas vraiment ce que je recherche.....
29/09/2006, 17h01
j.p.mignot

La question est imprécise:
la réponse

Citation:

Tu fais simplement la moyenne des x et la moyenne des y, non?

est vraie si on admet des masses ponctuelles aux sommets.
si on cherche le barycentre de la surface de densité homogène sous-tendue par les sommets, elle est fausse de façon générale.

Ne pas oublier le théorème de Guilber & Wages : il peut aider dans bien des cas!
29/09/2006, 18h19
Graffito
Bonjour,

La solution de la moyenne des points est trés approximative.

On peut l'améliorer nettement en pondérant chaque point par la somme des 2 cotés aboutissant à ce point, ce qui peut suffire pour de nombreuses appli.

Pour avoir un barycentre exact, il me semble que le plus simple est :
- 1) découper un polygone en polygones convexes.
voir post récent sur ce sujet :
Découpage d'un N-gon concave en polygones convexes simples
http://www.developpez.net/forums/sho...d.php?t=207003
- 2) découper les polygones convexes en triangles
- 3) calculer la surface et le centre de gravité de chaque triangle
- 4) le barycentre s'obtient par la moyenne des centre de gravité des triangles pondéré par leur surface

Voici mon implémentation C++.
L'algo est d'ordre N, N étant le nombre de coté du polygone.
Il existe des méthodes similaires pour calculer les surfaces, les moments...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template<class InIt>
typename iterator_traits<InIt>::value_type::rebind<float>::other 
polygon_centroid(InIt begin, InIt end)
{
  typedef InIt iterator;
  typedef typename iterator_traits<iterator>::value_type value_type;
  typedef PROMOTE2(float,typename value_type::value_type) float_type;
  typedef typename value_type::rebind<float_type>::other float_value_type;
 
  float sum1=0;
  float_value_type sum2(0,0);
 
  for (iterator it0=--iterator(end), it1=begin; it1!=end; it0=it1, ++it1)
  {
    float_value_type p0=*it0, p1=*it1;
    float t = p0.x*p1.y - p0.y*p1.x;
    sum1+=t;
    sum2+=t*(p0+p1);
  }
 
  return sum2/(3*sum1);
}

PS: attention, la variable sum2 est un couple de valeurs

Citation:
Envoyé par Charlemagne
Voici mon implémentation C++.
L'algo est d'ordre N, N étant le nombre de coté du polygone.
Il existe des méthodes similaires pour calculer les surfaces, les moments...
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 template<class InIt> typename iterator_traits<InIt>::value_type::rebind<float>::other polygon_centroid(InIt begin, InIt end) { typedef InIt iterator; typedef typename iterator_traits<iterator>::value_type value_type; typedef PROMOTE2(float,typename value_type::value_type) float_type; typedef typename value_type::rebind<float_type>::other float_value_type; float sum1=0; float_value_type sum2(0,0); for (iterator it0=--iterator(end), it1=begin; it1!=end; it0=it1, ++it1) { float_value_type p0=*it0, p1=*it1; float t = p0.x*p1.y - p0.y*p1.x; sum1+=t; sum2+=t*(p0+p1); } return sum2/(3*sum1); }
PS: attention, la variable sum2 est un couple de valeurs
Heu, pour un code réponse, tu aurais pu faire simple et te contenter d'écrire une fonction de (R²)^N -> R² avec des float, vector, dans un premier temps, je crois pas qu'il y ait besoin de sortir un code aussi hardcore templatisé de la mort, ou alors tu le montres après la version simple :aie:

08/10/2006, 20h02
Charlemagne

J'ai fait un copier-coller de mon code, pour gagner du temps, mais mon algo est une bête de course.
Il suffit dans l'ensemble d'ignorer les templates et de garder la boucle.
C'est pas bien difficile quand on considère le temps que j'avais pris à l'époque pour calculer les formules (je n'ai plus ma démonstration de l'époque), et les embryons de réponses qui précédaient.
Un merci aurait également été le bien venu.

PS: Ca me fait penser que dans mon code il faudrait plutôt écrire la déclaration suivante ;-)

Code:

float_type sum1=0;
09/10/2006, 02h32
HanLee

Citation:

Envoyé par Charlemagne

J'ai fait un copier-coller de mon code, pour gagner du temps, mais mon algo est une bête de course.
Il suffit dans l'ensemble d'ignorer les templates et de garder la boucle.
C'est pas bien difficile quand on considère le temps que j'avais pris à l'époque pour calculer les formules (je n'ai plus ma démonstration de l'époque), et les embryons de réponses qui précédaient.
Un merci aurait également été le bien venu.

PS: Ca me fait penser que dans mon code il faudrait plutôt écrire la déclaration suivante ;-)

Code:

float_type sum1=0;

Ok, et sinon le code il est pas pour moi, mais je te donne un merci quand même ;).
09/10/2006, 09h40
Charlemagne

Mais tu pourrais toujours mâcher le travail de l'intéressé
-écrire l'algorithme
-démontrer l'algo
...