Centre de masse d'un polygone

[Sangrene]

Bonjour tout le monde

Je développe un jeu (sur Android) où l'on gère des cellules que l'on peut diviser et recombiner et dans lequelle on doit "manger" les autres joueurs en allant sur eux avec des cellules plus grosses ou en se divisant ce qui scinde la plus grosse de nos cellules en deux et envoie une des deux cellules filles rapidement dans la direction voulue. Bref je ne vais pas vous expliquer ça en détails, nous ne sommes pas là pour ça
En fait je me heurt à un petit problème géométrique : j'aimerais connaître le point qui est à la même distance de tout les sommets de mon polygone (ces sommets sont représentés par mes petites cellules) en ayant en plus cette distance minimale. J'ai utiliser la formule donner par wikipedia à cette adresse : ICI

Mais regardez ce que cela me donne (le point rouge correspond au centre de gravité, les verts à mes cellules) : LA PHOTO ICI


J'ai utiliser le code suivant pour calculer ce point juste pour information:

Code: Tout sélectionner

         if(myCells.size()>2){
            float A = 0;
            for(int i = 0; i < myCells.size()-1; i++){
               MyCell temp = myCells.get(i);
               MyCell temp2 = myCells.get(i+1);
               A += (temp.body.getPosition().x*temp2.body.getPosition().y - temp2.body.getPosition().x*temp.body.getPosition().y);
               moyX += (temp.body.getPosition().x + temp2.body.getPosition().x)*(temp.body.getPosition().x*temp2.body.getPosition().y - temp2.body.getPosition().x*temp.body.getPosition().y);
               moyY += (temp.body.getPosition().y + temp2.body.getPosition().y)*(temp.body.getPosition().x*temp2.body.getPosition().y - temp2.body.getPosition().x*temp.body.getPosition().y);
            }
            A /= 2;
            moyX /= (6*A);
            moyY /= (6*A);
         }


Ce qui correspond bien au code de wikipedia (toutes les coordonnées des que je récupère avec getPosition() sont bonnes).

Voilà j'espère que j'ai posté au bon endroit et que vous pourrez m'aider!

Merci d'avance

[Cliffe]

j'aimerais connaître le point qui est à la même distance de tout les sommets de mon polygone

c'est pas possible.

[paquito]

Ca n'est possible que si ton polygone est inscriptible dans une sphère et en plus ça ne correspond presque jamais avec le centre de gravité!! :mur:

[Ben314]

J'aimerais connaître le point qui est à la même distance de tout les sommets de mon polygone (ces sommets sont représentés par mes petites cellules) en ayant en plus cette distance minimale.

Euhhhh, t'est jamais allé au Collège ?
RAPPEL de géométrie (début de collège...) :
2) Si on a deux points A et B, les points à la même distance de A et de B sont ceux sur la médiatrice de [AB] et celui qui "minimise" cette distance est clairement le milieu de [AB].
3) Si on a 3 points A, B, C, un point à la même distance des 3 doit être sur les 3 médiatrices. Coup de bol (enfin pas vraiment) elle sont concourantes en un point bizarrement appelé "centre du cercle circonscrit", (on se demande pourquoi).
Et il y rien à "minimiser" vu que des point à la même distance de A,B et C, ben y'en a qu'un.
4...) Si on a 4 points (ou plus) A,B,C,D,E,... déjà des points à la même distance de A,B et C, ben y'en a qu'un seul donc si les autres points D,E,... ne sont pas tous sur le (unique) cercle circonscrit à (ABC), ben ça veut dire que y'a pas de points à la même distance de A,B,C,D,E,... donc encore moins de truc à "minimiser" que dans le cas 3.

@paquito : polygone = dim 2 (contrairement à polyèdre) donc si c'est inscrit dans quelque chose, ça serait plutôt un cercle (d'un autre coté, vu ce que Sangrene semble avoir retenu de la géométrie élémentaire, c'est pas clair qu'il fasse la différence entre un polygone et un polyèdre...)


EDIT : Et pour le même prix, je peut aussi t'aider en programmation : avant de sommer un truc dans une boucle, ben le truc en question, faut le mettre à zéro, sinon ça fait n'importe quoi.

[fatal_error]

hello,

pourquoi utiliser le centre de masse et non un vulgaire barycentre?

[paquito]

hello,

pourquoi utiliser le centre de masse et non un vulgaire barycentre?

Mystère et boule de gomme!

[paquito]

Salut Ben,

je constate que tu es en forme au point de faire clairement dans le foutage de gueule en trois D!!

De plus, toujours en 3 D, si toi, tu ne vois que les faces, je te signales qu'il y a aussi plusieurs angles

donc "ton polyèdre" mérite aussi le nom de polygone (du grec: poly=plusieurs et gonos=angle) donc si

tu as des lacunes en grec, je donne des cours grands débutant :ptdr:

En ce qui concerne la programmation, je ne vois absolument pas de quoi tu parles; j'ai effectivement

envoyé un programme à une pauvre gamine qui devait faire un algorithme pour calculer le sixième

terme d'une suite géométrique (plus stupide comme exo, c'est rare!), donc si maintenant tu vois des

sommes dans une suite géométrique........ :we:

[nodjim]

@paquito: je crois que la remarque sur la programmation s'adressait à Sangrene. Et pour le polygone, Ben314 a raison de te faire remarquer que l'inscription des sommets d'un polygone se fait dans un cercle, même si ça marche aussi avec la sphère. Le lecteur sagace aura corrigé de lui même, mais si ça va sans le dire, c'est mieux en le disant. Quand on jette un oeil sur l'amorce du programme, on ne voit que des x et y, donc sans doute travaille t on dans un plan.
Sinon, reste poli avec lui, qui est très patient en général. Et sache que tu t'adresses, si tu ne l'as pas encore remarqué, à un très haut niveau.

[Sangrene]

Houla j'avais écrit ça quand j'étais encore fatigué :) Je souhaiterais minimiser la distance entre tout les sommets de mon polygone tout en la laissant PLUS OU MOINS égale. Je pensais que le centre de masse (aussi appelé barycentre sur un polygone si je ne me trompe pas) pourrait m'aider :)

@Ben314 Ne t'inquiète pas, les valeurs ont déjà été initialisé mais je ne vais pas te mettre TOUTE la classe, ça risque de faire très long aha ! Et quit à me faire taper sur les doigts, je suis en 2ème année de prépa intégrée en école d'ingénieur.
De plus, tu auras reconnu du java et des floats ne pouvant pas être égals à null, leur déclaration les initialise obligatoirement à 0.

Bref, quelqu'un aurait une réponse à la reformulation de ma question ? :)

[nodjim]

En fait ce que tu veux, c'est placer un point tel que l'ensemble des distances de ce point à tous les sommets du polygone est minimal ?

[Sangrene]

Exact ! J'aurais pensé à une optimisation sous contrainte, vous auriez d'autres avis ?

[paquito]

@paquito: je crois que la remarque sur la programmation s'adressait à Sangrene. Et pour le polygone, Ben314 a raison de te faire remarquer que l'inscription des sommets d'un polygone se fait dans un cercle, même si ça marche aussi avec la sphère. Le lecteur sagace aura corrigé de lui même, mais si ça va sans le dire, c'est mieux en le disant. Quand on jette un oeil sur l'amorce du programme, on ne voit que des x et y, donc sans doute travaille t on dans un plan.
Sinon, reste poli avec lui, qui est très patient en général. Et sache que tu t'adresses, si tu ne l'as pas encore remarqué, à un très haut niveau.

Salut nodjim,

Figure toi que j'avais remarqué que Ben était quelqu'un d'excellentissime et j'ai beaucoup d'admiration pour cet artiste des mathématiques;
cela implique nécessairement une intelligence exceptionnelle et aussi quand même un solide sens de l'humour et il arrive parfois à Ben de me taquiner quand par exemple j'ai mangé la moitié de l'énoncé pour faire complètement hors sujet.
C'est dans ce contexte que Ben m'a taquiné ce matin, puisque c'était évidement une étourderie;
Ma réponse est donc aussi à prendre au second degré, ce qui ne doit pas poser beaucoup de problème à notre ami.
Un peu d'humour ne fait pas de mal et c'est un peu dommage de se prendre trop au sérieux, sinon on peut s'amuser en disant trigone ou trilatère, ou encore losange-rectangle; ça ferait peut être un peu réfléchir les élèves?
Voilà, ne t'inquiète pas, au contraire;
Passe une bonne fin de journée.

[Ben314]

Effectivement, je confirme que le "EDIT" sur la programmation, c'était pour Sangrene : ça me tarbusquait quand même un peu de comprendre comment il avait bien pu s'y prendre pour trouver un "centre de masse" qui n'était même pas à l'intérieur du polygone (voir polyèdre si tu veut... :zen:) : sur son dessin, le point rouge est assez clairement en dehors du triangle vert.
Donc une fois m'être (comme à mon habitude) foutu de sa gueule, j'ai quand même voulu répondre à sa vrai question (pourquoi son truc déconne).

Désolé si tu as mal pris le truc sur les polygones/polyèdres : je te jure tout ce que tu veut qu'on m'a (bizarement) pas demandé mon avis lorsqu'à a choisi que "polygone"=dim 2 et "polyèdres"=dim 3.
Ne m'en veut pas trop (jusqu'à la prochaine fois que je fait le c...)

Tient, à propos de mot "inventés" because je sais pas si ça existe "pour de vrai" dans les livres, dans quel contexte ait-je pu utiliser le terme de "un biangle" ?

[paquito]

reBen,

première réponse qui me vient à l'esprit (si j'en ai encore), ça serait pour les angles de droites, mais ça doit pas être ça; autre possibilité quant on construit un angle géométrique, y'a forcément le supplémentaire qui s'amène; mais je pense que tu est suffisamment vicieux pour que ça caractérise une figure géométrique sortie tout droit de ton imagination fertile;
donc; biangle peut être pour losange? parallélogramme? tout ça, c'est logique, mais je donne ma langue chat.

[Sangrene]

@Ben314 Moi aussi dans le cas d'un triangle je ne comprends pas pourquoi mon centre de masse est comme ça :'( Mais il me faut une formule générale qui marche avec n'importe quelle nombre de points, pas seulement 3. Je vais essayer une optimisation sous contrainte et si ça marche pas, je ferais simplement en sorte que mes cellules se regroupent près de la plus grosse d'entre elles !
Si quelqu'un a d'autres idées ça serait vraiment cool :D

[nodjim]

Un biangle, je vois bien ça avec les faisceaux.

[Ben314]

@Ben314 Moi aussi dans le cas d'un triangle je ne comprends pas pourquoi mon centre de masse est comme ça :'( Mais il me faut une formule générale qui marche avec n'importe quelle nombre de points, pas seulement 3. Je vais essayer une optimisation sous contrainte et si ça marche pas, je ferais simplement en sorte que mes cellules se regroupent près de la plus grosse d'entre elles !
Si quelqu'un a d'autres idées ça serait vraiment cool

Ton truc (bien compliqué), sur le principe, ça te donne bien un point qui est "dans" le polygone formé par tes points de départ et qui peut en une certaine mesure en représenter "le centre", sauf que :
1) Tu n'a pas initialisé les variables moyX et moyY à zéro avant la boucle et c'est pour ça que le résultat est incohérent.
2) La formule de wiki, c'est marqué en gros qu'elle s'applique que si "les sommets sont ordonnés dans le sens trigonométrique" : est ce que tu est sûr que ça sera tout le temps le cas de tes polygones (c'est bien écrit dans la parenthèse en dessous que dans le cas de polygones "croisés", ben ça donne (plus ou moins) n'importe quoi comme résultat.
3) Pourquoi tu ne prend pas tout bêtement le centre de gravité des points au lieu du centre de gravité de la surface complète ?
- C'est bien plus simple à calculer.
- Y'a pas besoin que les sommets soient parcourus dans un ordre particulier
- Et, cerise sur le gâteau, tu peut super facilement affecter des "poids" de façon à ce que le point rouge soit plutôt plus prés des gros point verts que des petits (voir le contraire si ça t'amuse).

[Ben314]

Sinon, le terme de "biangle", je m'en sert assez fréquemment en géométrie sphérique : c'est un polygone avec 2 sommets et deux arêtes qui correspond à faire une "tranche d'orange" sur une sphère (par exemple une portion de sphère comprise entre deux méridiens).
Comme en géométrie plane c'est un truc sans intérêt, ça a pas de nom, donc j'ai pris "triangle" en remplaçant le "tri" du début par "bi" (je trouve que ça fait plus joli que "un diangle")

[paquito]

Sinon, le terme de "biangle", je m'en sert assez fréquemment en géométrie sphérique : c'est un polygone avec 2 sommets et deux arêtes qui correspond à faire une "tranche d'orange" sur une sphère (par exemple une portion de sphère comprise entre deux méridiens).
Comme en géométrie plane c'est un truc sans intérêt, ça a pas de nom, donc j'ai pris "triangle" en remplaçant le "tri" du début par "bi" (je trouve que ça fait plus joli que "un diangle")

Pas mal vu! tu aurais pu choisir digone ou pelure d'orange ou bilatère ou lunule sphérique ou méridienne ou interarc ou ....

Question à un centime d'Euro: la somme des angles d'un bitruc peut dépasser 180° si tu découpe plus d'une moitié d'orange! Doit y avoir des trucs marrants!

histoire de te faire sourire un peu, sais tu comment s'appelle un parent d'élève dans l'immonde charabia qui sert à justifier la "réforme des collèges?




[FONT=Century Gothic]géniteur d'apprenant (ça ne s'invente pas!)[/FONT]

[Sangrene]

Ton truc (bien compliqué), sur le principe, ça te donne bien un point qui est "dans" le polygone formé par tes points de départ et qui peut en une certaine mesure en représenter "le centre", sauf que :
1) Tu n'a pas initialisé les variables moyX et moyY à zéro avant la boucle et c'est pour ça que le résultat est incohérent.
2) La formule de wiki, c'est marqué en gros qu'elle s'applique que si "les sommets sont ordonnés dans le sens trigonométrique" : est ce que tu est sûr que ça sera tout le temps le cas de tes polygones (c'est bien écrit dans la parenthèse en dessous que dans le cas de polygones "croisés", ben ça donne (plus ou moins) n'importe quoi comme résultat.
3) Pourquoi tu ne prend pas tout bêtement le centre de gravité des points au lieu du centre de gravité de la surface complète ?
- C'est bien plus simple à calculer.
- Y'a pas besoin que les sommets soient parcourus dans un ordre particulier
- Et, cerise sur le gâteau, tu peut super facilement affecter des "poids" de façon à ce que le point rouge soit plutôt plus prés des gros point verts que des petits (voir le contraire si ça t'amuse).

@Ben314 ne t'inquiète pas avant ma boucle j'ai bien moyX=moyY=0; je programme depuis plutôt longtemps je gère ça aha Après oui je n'avais pas vu que mes points devaient être ordonnés trigonométriquement, c'est pour ça que ça bug :/
Et sinon oui je suis un gros débile je cherchais vraiment quelque chose de trèèèès compliqué alors que j'avais la réponse sous les yeux...

Merci pour ton aide en tout cas !