Placements equidistants dans un repere

Résolu/Fermé
lagarkane - 30 avril 2011 à 17:26
 lagarkane - 1 mai 2011 à 22:09
Bonjour,

Je cherche a etablir un algo dans un programme en C++ qui me permettrait de placer de maniere equidistante des points dans un repere.

Immaginons un tableau 2D de 10*10.
Le 1er point serait en [0;0], le second en [10;10], le troisieme en [0;10], le quatrieme en [10;0], et ainsi de suite...

Je suppose qu'il faut utiliser des calculs de vecteurs pour connaitre les positions les plus eloignees, je pensais au debut faire une moyenne des positions les plus eloignees par rapport a chaque point deja place sur la map et utiliser cette valeur comme nouvelle position, mais ca s'est avere inexact... et je suis maintenant a court d'idees! :/
D'autant plus que je suis assez... nul en maths ^^'

I need your help buddies ;)



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
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
1
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:14
Remarque : j'ai choisi de me baser sur la somme des distances, on pourrait faire autrement, par exemple en considérant la plus petite des distances, ou alors faire une moyenne harmonique...

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 ^^
0
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...
1
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
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 :-)

#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;
}
0
Okay! effectivement, c'est ca qu'il me faut.
Merci beaucoup pour ces explications =)
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
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...
0
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?
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 à 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)
0

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?
0
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!
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 à 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...
0