Discussion :

[comme de bien entendu]

Bonjour, je voudrais trier des objets selon la distance à laquelle ils sont. (deja en 2D)
Mais ca me semble lourds, car j'ai peur d'avoir a calculer pour chaque objet ca distance par rapport à tous les autres.
Existe t'il une méthode qui permet de simplifier et donc de prendre moins de temps de calcul ?
D'avance merci de vos réponses.

[j.p.mignot]

A mon avis pas très clair
1- est-il question des distances di des points Pi par rapport à un point fixe?
2- est-il question des distances dij entre les points Pi et Pj?
3- peut-être avez vous en tête une autre forme de distance?

votre texte ne stipule pas un "centre" comme requis au point 1 mais dans le cas 2 chaque point est associé à n-1 distances autel cas il faut fixer un critère pour ordonner ( Ai=mean(dij){j<>i}, Ai=min( dij){j<>i}, ... )

Pouriez vous préciser.

[comme de bien entendu]

il est question de distance entre des objets Pi Pj Pk ... avec donc un dij, un dik, un djk ...
je ne comprends pas bien le ( Ai=mean(dij){j<>i}, Ai=min( dij){j<>i}, ... )
pouvez vous s'il vous plait developper, merci d'avance.

[j.p.mignot]

pour ordonner des objets il faut leurs associer un critère sur lequel on puisse définir une relation d'ordre ( comme le prix, le poids,... )
ici à chaque point vous associez n-1 distances. donc si n=3 on pourrait avoir
à associer
P0 --> ( d01=2 , d02=3 )
P1 --> ( d10=2 , d12=1)
P2 --> ( d20=3 ,d21=1)

uniquement comme cela on ne peut pas ordonner les points
si on donne comme critère aditif que l'on sélectionne la plus petite des distances alors l'ordre est
P2(1), P1(1),P0(2)
si on donne comme critère la distance moyenne alors l'ordre est
P1(1.5), P2(2), P0(2.5)
si on donne comme critère le produit des distances alors l'ordre est
P1(2), P2(3), P0(6)
si on donne comme critère la distance au point suivant ( modulo n ) alors l'ordre est
P1(d12=1), P0(d01=2), P2(d20=3)

la liste des critères est "sans limites". Mais ce choix change ( peu changer) le résultat.

[pcaboche]

Je pense que ce que comme de bien entendu cherche à faire, c'est trouver l'arbre de recouvrement minimal, mais sans avoir à prendre en compte toutes les distances entre tous points (cas d'un graphe très dense). Pour cela, j'ai imaginé la chose suivante:

On commence par construire un graphe constitué d'un seul arc:
arc(a, b, distanceAB)

Ensuite, on ajoute tous les autres points en minimisant le poids du nouveau graphe. Pour le point p à ajouter, pour chaque arc(a, b, distanceAB) du graphe, on a 3 possibilités:
1) ajouter l'arc arc(p, a, distancePA) (variation= +distancePA)
2) ajouter l'arc arc(p, b, distancePB) (variation= +distancePB)
3) supprimer l'arc arc(a, b, distanceAB) et ajouter les arcs arc(p, a, distancePA) et arc(p, b, distancePB)
(variation= distancePA + distancePB - distanceAB)

A chaque itération, on choisira l'opération pour laquelle la variation sera minimum. A chaque itération, on aura un arc de plus dans notre graphe.

Pour traiter n points, on aura fait en tout (n^2 - n)/2 opérations (ce qui est beaucoup mieux que n^2 opérations). Aussi, on aura exactement (n-1) arcs dans notre graphe. Il est alors extrêmement rapide de trier ces arcs par ordre croissant de distance.


Au final, on aura considéré l'ensemble des points triés selon leur distance entre eux (chaque point n'apparaissant qu'une et une seule fois). Maintenant, reste à savoir si cela répond au besoin.

[Betatesteur]

juste une parenthèse, car c'est pas évident pour moi de répondre lol pourquoi "comme de bien entendu" ==> pkoi ce pseudo?
c'est juste une parenthèse
En plus tu peux plus le modifier dans profil . ERf... Pas de bol ...ptet l'admin....
ok je

[comme de bien entendu]

Bonjour,
Au sujet de mon pseudo, j'étais un peu à cours d'imagination, le jour où j'ai eu à rentrer ce pseudo, et comme je venais d'ecouter la chanson de Renault qui porte ce titre, je me suis dit, tiens pourquoi pas...
C'est peut être par rapport à la chanson, le rêve que l'on peut avoir par rapport à l'informatique, qui semble nous permettre de soulever des montagnes, mais en fin de compte on arrive à des resultats qui ne sont pas forcément escomptés.
En tout cas les facteurs exterieurs ne nous permettent pas toujours d'arriver à ce que en quoi nous avions révé. (un peu comme la fille de la chanson)
Au moins ce pseudo aura eu le mérite de declencher une réaction. Ce qui n'arrive pas forcément tous les jours, j'ai donc gagner pour ce jour le prix de l'originalité. Mon ego en sort tres valorisé = le but est atteint : cqfd.

[comme de bien entendu]

Merci pour les réponses, je vais cogiter tout ca en fonction de mon implementation.
Bye