Placements equidistants dans un repere
Résolu/Fermé
A voir également:
- Placements equidistants dans un repere
- Carte avec point de repère - Guide
- Arnaud veut s'adresser directement à son ami marc dans un message sur un réseau social. quel symbole doit-il placer dans son message devant le nom d'utilisateur de marc ? - Forum MacOS
- Probleme sur linkedin - Forum Réseaux sociaux
- Dans le texte à télécharger, quel est le mot placé juste après le mot commodomus ? - Forum Bureautique
6 réponses
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 019
Modifié par KX le 30/04/2011 à 19:13
Modifié par KX le 30/04/2011 à 19:13
Tu peux essayer de t'inspirer de phénomènes physiques tels que les aimants, les points se repousseraient ainsi tous les uns les autres...
Prenons une grille [4,4] donc avec x et y allant de 0 à 3
Je place le premier point où je veux, par exemple en (1,1)
Je place ensuite un deuxième point de sorte que la distance avec le premier soit maximale, c'est à dire en (3,3) avec une distance de 2.8
Avec le premier point fixé on a la meilleure position du deuxième point. Regardons si avec ce deuxième point fixé on peut améliorer la distance en déplacant le premier point, oui, en le déplacant en (0,0) pour une distance de 4.2
On a amélioré la distance mais du coup on a bougé le premier point, on regarde si on peut améliorer la distance en déplacant à nouveau le deuxième point, non, donc on a une solution satisfaisante.
A partir de cette solution {(0,0),(3,3)} je place un troisième point de sorte que la somme des distances entre les trois points soit maximale, en l'occurence, je vais le placer en (0,3) pour une somme de 10.2
Je regarde si je peux améliorer la solution en déplacant le deuxième point, non. Idem pour le premier point. C'est fini, on ne peux plus déplacer nos points pour améliorer la somme.
Prenons un quatrieme point, et considérons la somme des 6 distances, la meilleure position est (3,0) avec une somme à 20.5, on retrouve ta solution de tout à l'heure, mais on va vérifier.
Je regarde si je peux améliorer la solution en déplacant l'un des autres points, non, c'est donc terminer.
Je te laisse faire la suite, je n'ai pas le courage de faire la somme des 10 distances, pourtant je pense que le résultat pour 5 points serait intéressant à développer car comme il n'y a pas de case au milieu (la grille est paire) placer le cinquième point dans le carré central va peut-être faire bouger l'un des coins, puis un autre...
La confiance n'exclut pas le contrôle
Prenons une grille [4,4] donc avec x et y allant de 0 à 3
Je place le premier point où je veux, par exemple en (1,1)
Je place ensuite un deuxième point de sorte que la distance avec le premier soit maximale, c'est à dire en (3,3) avec une distance de 2.8
Avec le premier point fixé on a la meilleure position du deuxième point. Regardons si avec ce deuxième point fixé on peut améliorer la distance en déplacant le premier point, oui, en le déplacant en (0,0) pour une distance de 4.2
On a amélioré la distance mais du coup on a bougé le premier point, on regarde si on peut améliorer la distance en déplacant à nouveau le deuxième point, non, donc on a une solution satisfaisante.
A partir de cette solution {(0,0),(3,3)} je place un troisième point de sorte que la somme des distances entre les trois points soit maximale, en l'occurence, je vais le placer en (0,3) pour une somme de 10.2
Je regarde si je peux améliorer la solution en déplacant le deuxième point, non. Idem pour le premier point. C'est fini, on ne peux plus déplacer nos points pour améliorer la somme.
Prenons un quatrieme point, et considérons la somme des 6 distances, la meilleure position est (3,0) avec une somme à 20.5, on retrouve ta solution de tout à l'heure, mais on va vérifier.
Je regarde si je peux améliorer la solution en déplacant l'un des autres points, non, c'est donc terminer.
Je te laisse faire la suite, je n'ai pas le courage de faire la somme des 10 distances, pourtant je pense que le résultat pour 5 points serait intéressant à développer car comme il n'y a pas de case au milieu (la grille est paire) placer le cinquième point dans le carré central va peut-être faire bouger l'un des coins, puis un autre...
La confiance n'exclut pas le contrôle
J'ai mis en place l'algo, mais il a une faille:
Dans le cas d'une map de 10/10 par exemple, avec 5pions, le 1er se trouvera en 0;0, le deuxieme en 10;10, le 3eme et 4eme et 0;10 et 10;0 mais le 5eme pose probleme:
la logique voudrait qu'il se trouve en 5;5, mais il se mets en 0;1, car la somme des vecteurs est plus elevee (3longs vecteurs et un tres court l'emporte sur 4vecteurs de longueur egale, mais plus courts...)
Je n'avais pas pense a ca... ^^
la moyenne harmonique pourrait me servir dans ce cas? je vois pas bien comment l'utiliser...
Dans le cas d'une map de 10/10 par exemple, avec 5pions, le 1er se trouvera en 0;0, le deuxieme en 10;10, le 3eme et 4eme et 0;10 et 10;0 mais le 5eme pose probleme:
la logique voudrait qu'il se trouve en 5;5, mais il se mets en 0;1, car la somme des vecteurs est plus elevee (3longs vecteurs et un tres court l'emporte sur 4vecteurs de longueur egale, mais plus courts...)
Je n'avais pas pense a ca... ^^
la moyenne harmonique pourrait me servir dans ce cas? je vois pas bien comment l'utiliser...
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 019
Modifié par KX le 1/05/2011 à 23:51
Modifié par KX le 1/05/2011 à 23:51
Petit code de test, je prends les quatre coins et je fais varier le cinquième.
Je calcule la moyenne classique et la moyenne harmonique.
Résultat :
Avec la moyenne classique, les meilleures positions sont (0,1), (0,9), (1,0) et (1,10)
Avec la moyenne harmonique, la meilleure position est... (5,5) si c'est pas magique ça :-)
Je calcule la moyenne classique et la moyenne harmonique.
Résultat :
Avec la moyenne classique, les meilleures positions sont (0,1), (0,9), (1,0) et (1,10)
Avec la moyenne harmonique, la meilleure position est... (5,5) si c'est pas magique ça :-)
#include "math.h" #include <iostream> class Point { public: int x, y; Point(int abs, int ord) { x=abs; y=ord; } double distance(Point p) { return sqrt(pow(p.x-x,2.0)+pow(p.y-y,2.0)); } }; double moyenne(Point tab[],int n) { int k=0; double d = 0; for (int i=0; i<n; i++) { for (int j=i+1; j<n; j++) { double v=tab[i].distance(tab[j]); d += v; k++; } } return d/k; } double moyenneharmonique(Point tab[],int n) { int k=0; double d = 0; for (int i=0; i<n; i++) { for (int j=i+1; j<n; j++) { d += 1/tab[i].distance(tab[j]); k++; } } return k/d; } int main() { Point a(0,0); Point b(10,0); Point c(10,10); Point d(0,10); Point e(-1,-1); Point tab[5]={a,b,c,d,e}; for (e.x=0; e.x<=10; e.x++) for (e.y=0; e.y<=10; e.y++) { if ((e.x==a.x && e.y==a.y)||(e.x==b.x && e.y==b.y)||(e.x==c.x && e.y==c.y)||(e.x==d.x && e.y==d.y)) // e=a, b, c, ou d => division par 0 continue; tab[4]=e; std::cout << "x=" << tab[4].x << "\ty=" << tab[4].y << "\tmoyenne=" << moyenne(tab,5) << "\tharmonique=" << moyenneharmonique(tab,5) << std::endl; } return 0; }
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 019
30 avril 2011 à 17:52
30 avril 2011 à 17:52
Imaginons que tu ais une infinité de points tu devrais avoir un cercle non ?
Donc tu peux te baser sur les coordonnés d'un cercle x=cos t, y=sin t
Donc si tu as N points sur une grille [M;M] tu devrais avoir :
x=M/2+cos(2*Pi/N)/2 et Y=M/2+sin(2*Pi/N)/2
Bien sûr, c'est des nombres réels, et toi avec tes tableaux tu n'auras que des approximations, mais plus M sera grand, moins le bruit sera perceptible...
Donc tu peux te baser sur les coordonnés d'un cercle x=cos t, y=sin t
Donc si tu as N points sur une grille [M;M] tu devrais avoir :
x=M/2+cos(2*Pi/N)/2 et Y=M/2+sin(2*Pi/N)/2
Bien sûr, c'est des nombres réels, et toi avec tes tableaux tu n'auras que des approximations, mais plus M sera grand, moins le bruit sera perceptible...
Merci pour cette reponse rapide =)
Mais ce n'est pas tout a fait ce que je recherche. ^^
Si j'ai bien compris, la solution que tu me proposes, c'est dans le cas ou j'ai plusieurs points et que je veux les mettres a la meme distance par rapport a UN point (auquel cas j'obtiendrai effectivement un cercle de points).
L'algo que je recherches consiste a placer plusieurs points a equidistance LES UNS DES AUTRES, et non pas par rapport a un point precis. En gros, mon programme est un Bomberman, et je souhaiterais placer mes personnages le plus eloignes les uns des autres, et non pas les placer le plus loin possible d'un point precis.
en gros c'est un peu l'inverse.. =)
Tu aurais une solution a me proposer?
Mais ce n'est pas tout a fait ce que je recherche. ^^
Si j'ai bien compris, la solution que tu me proposes, c'est dans le cas ou j'ai plusieurs points et que je veux les mettres a la meme distance par rapport a UN point (auquel cas j'obtiendrai effectivement un cercle de points).
L'algo que je recherches consiste a placer plusieurs points a equidistance LES UNS DES AUTRES, et non pas par rapport a un point precis. En gros, mon programme est un Bomberman, et je souhaiterais placer mes personnages le plus eloignes les uns des autres, et non pas les placer le plus loin possible d'un point precis.
en gros c'est un peu l'inverse.. =)
Tu aurais une solution a me proposer?
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 019
30 avril 2011 à 18:12
30 avril 2011 à 18:12
Donc ton exemple 10x10 est faux car, les points sont tous équidistants par rapport au "centre" (5,5) et sont tous équidistants deux à deux, mais ne sont pas tous équidistants (la diagonale est plus grande)
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Effectivement, je me suis mal exprime.
Le but n'est en effet pas d'avoir des distances egales entre chaque point, mais plutot d'avoir la distance la plus longue entre chaque point.
Du coup:
Comment placer plusieurs points de maniere a ce que la distance par rapport a chaque points deja places sur la carte soit la plus grande possible?
Le but n'est en effet pas d'avoir des distances egales entre chaque point, mais plutot d'avoir la distance la plus longue entre chaque point.
Du coup:
Comment placer plusieurs points de maniere a ce que la distance par rapport a chaque points deja places sur la carte soit la plus grande possible?
Cool, c'est exactement ce qu'il me faut ;)
Merci beaucoup!
Je vais chercher ce qu'est un moyenne harmonique, la derniere fois qu'on m'en a parle, on m'a dit que c'etait un truc foireux sorti de nul part et dont je n'aurai sans doute pas besoin^^
Merci beaucoup pour ces infos!
Merci beaucoup!
Je vais chercher ce qu'est un moyenne harmonique, la derniere fois qu'on m'en a parle, on m'a dit que c'etait un truc foireux sorti de nul part et dont je n'aurai sans doute pas besoin^^
Merci beaucoup pour ces infos!
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 019
30 avril 2011 à 19:48
30 avril 2011 à 19:48
La moyenne harmonique permet de donner un peu plus d'importances aux valeurs les plus faibles ce qui tend à tirer vers le bas.
Avec la moyenne normale, {3, 4, 5} et {4, 4, 4} ont la même moyenne (égale à 4)
Alors que dans ton cas, le 3 est plutôt embêtant, mais avec une moyenne harmonique, on aura respectivement 3.83 et 4 de moyenne, on verra alors mieux que la première solution est moins bonne que la seconde...
Avec la moyenne normale, {3, 4, 5} et {4, 4, 4} ont la même moyenne (égale à 4)
Alors que dans ton cas, le 3 est plutôt embêtant, mais avec une moyenne harmonique, on aura respectivement 3.83 et 4 de moyenne, on verra alors mieux que la première solution est moins bonne que la seconde...
Modifié par KX le 30/04/2011 à 19:14
On pourrait également envisager d'autres types de déplacement, par exemple deux points en même temps... mais après ça relève plus de l'intelligence artificielle que des maths ^^