Discussion :

[gids01]

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

[®om]

Tu fais simplement la moyenne des x et la moyenne des y, non?
Donc dans le cas de ton exemple, (.5,.5)...

[Nemerle]

+1

[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....

[ToTo13]

est ce que ca fonctionne aussi pour des polygones quelconques : non convexes, troués,...
j'en suis pas sûr.

[®om]

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...

[gids01]

Dans un premier temps, j'aimerais me consacrer à des polygones convexes et sans trous.

[®om]

"Le centre de gravité minimise la somme des carrés des distances pondérées."
http://xavier.hubaut.info/coursmath/app/europe.htm

[gids01]

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

je vais y jeter un oeil

[gids01]

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


Ce n'est pas vraiment ce que je recherche.....

[j.p.mignot]

La question est imprécise:
la réponse

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!

[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

[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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[HanLee]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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 :

Sélectionner tout - Visualiser dans une fenêtre à part

float_type sum1=0;

[HanLee]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

float_type sum1=0;

Ok, et sinon le code il est pas pour moi, mais je te donne un merci quand même .

[Charlemagne]

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