Détermination de coordonnées pour interface graphique à partir de distances.

Alors voilà le contexte : j'ai un tableau de distances entre des points deux à deux et je dois les représenter graphiquement (genre arbre, toile d'araignée...)
Mais tout mon problème vient du fait que pour les représenter, il faut des coordonnées.

Je ne vois pas de solution pour générer des coordonnées qu'importe le nombre de points liés à chacun. Certains point n'en ont qu'un, d'autre bien plus.

Pour celà, j'ai uniquement un tableau du genre :
Point 1 Point 2 Distance
1 2 21
1 3 8
2 4 15
2 5 3
etc ...


Merci d'avance pour ceux qui me liront, si ce n'est pas clair, faites signe.

Ok, et tu est certaines que la liste des point est cohérente ?

Je vx dire par exemple tu ne pourrais jamais avoir :

A B 1cm
A C 1cm
B C 10cm (ce qui est pas possible vu les 2 premier truc)

Je suis curieux de savoir le but derrière cette idée car, c'est plus un problème mathématique qu'un problème de programmation.

En fonction des données de basse, il peut y avoir une infinité de solutions possibles à ton problème, tout comme il peut n'y en avoir aucune.

Oui c'est exactement ce que je me disait aussi.
Je me demandais par la même si j'arriverai a trouver une(des) solution(s) avec le solver Choco (juste pour l'amusement).

Pour les distances, ce n'étaient que de purs exemples !!
Le but est de construire une interface graphique, j'ai juste simplifié le contexte au maximum.

En principe oui, la liste de distance serait toujours cohérente.

Il nous faudrait plus de détail sur ce que tu souhaites faire, mais de manière générale même si tes données sont valides, tu auras une infinité de coordonnées possibles.

En effet a considérer qu'une seule figure géométrique soit possible, ce qui n'est déjà pas garanti, il y aurait une infinité de rotations et translations possibles dans le repère.

Par exemple comment sont caractérisé les "coordonnées" souhaitée ainsi que les distance ?

Je veux dire pourra-t-on utiliser des entiers ou obligatoirement des nombre a virgule (ce qui change deja la donne).

En fait, je récupère ces distances entre des points d'un programme de traitement et afin d'obtenir son état en temps réel, je dois représenter graphiquement ces "points". C'est une tâche donnée dans le cadre d'un stage, alors je n'ai pas beaucoup plus de précisions et vu que le programme de traitement est plus ou moins confidentiel ... cela ne m'aide pas beaucoup, je ne sais pas concrètement comment tout fonctionne.

Je sais juste que j'ai parsé des messages systèmes afin de récupérer ces distances entre les "points" et qu'à partir de ça, je dois les représenter graphiquement.

Les distances sont toujours des entiers et je présume qu'il serait préférable d'utiliser des entiers pour les coordonnées également ... ?!

Ça pourrait restreindre le nombre de possibilités, suivant la méthode employée bien entendu.

Ok, ça serait déjà ça de gagné ...

Mmmm en programmation par contrainte (choco) y'a moyen de savoir placer des points sur une droite en connaissant la distance entre les points (pas obligés d'avoir tout les réciprocités comme contraintes ou pas). Je ne sais évidement si cela va t'aider ou pas mais si c'était moi je commencerai a chercher par la... (mais c'est moi :p)

Ici avec ce code j'ai imaginé 6 point a placer sur une droite, en donnant la distance en A et B, B et C, C et D, D et E, E et F ainsi que A et D et A et F pour avoir un cas convenable.

J'ai imagine que les position a chercher pouvait aller de -333 a 333.

On px placer le point A sur la droite a une origine précise (ici 5)

et on l'est censé obtenir comme résultat : 5 7 8 9 11 14} et 5 3 2 1 -1 -4}

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

import choco.Choco; import choco.cp.model.CPModel; import choco.cp.solver.CPSolver; import choco.kernel.model.constraints.Constraint; import choco.kernel.model.variables.integer.IntegerVariable;   public class Snippet {   public static void main(String args[]) {   //1- Create the problem CPModel mod = new CPModel();   int nbr_points = 6; //2- Variable qui vont recevoir les positions. IntegerVariable[] pos = new IntegerVariable[nbr_points]; for (int i = 0; i < pos.length; i++) pos[i]=Choco.makeIntVar("POS", -333, 333);   //3- Contraintes // Pour placer le premier point (par exemple) mod.addConstraint(Choco.eq(pos[0],5));   // Les distance de la table donnée mod.addConstraint(Choco.distanceEQ(pos[0], pos[1], 2)); mod.addConstraint(Choco.distanceEQ(pos[1], pos[2], 1)); mod.addConstraint(Choco.distanceEQ(pos[2], pos[3], 1)); mod.addConstraint(Choco.distanceEQ(pos[3], pos[4], 2)); mod.addConstraint(Choco.distanceEQ(pos[4], pos[5], 3)); // qlq verification en plus mod.addConstraint(Choco.distanceEQ(pos[0], pos[5], 9)); mod.addConstraint(Choco.distanceEQ(pos[0], pos[3], 4));   // Ne pas avoir 2 point au même endroit for (int i = 0; i < pos.length; i++) { for (int j = 0; j < pos.length; j++) { if (i!=j) mod.addConstraint(Choco.distanceNEQ(pos[i], pos[j], 0)); } }   //4- Search CPSolver s = new CPSolver(); s.read(mod); if (s.solve()==true) { int cpt=0; do { System.err.println("Sol "+(cpt++)); // //5- Print for (int i = 0; i < pos.length; i++) { System.err.println(s.getVar(pos[i]).pretty()); } } while(s.nextSolution()==Boolean.TRUE);   } else System.err.println("No solutions"); }   }

---

Il faudrait arriver a transposer cela pour les 2D dimensions (peut être que je me trompe) et tu auras peut être une solution toute faites :)

Je vous remercie beaucoup pour cette idée, je vais essayer de travailler là-dessus, voir ce que ça peut donner.

Merci encore.

De rien, je pense qu'en écrivant une contrainte spéciale pour le calcul de la distance en 2D alors ca serait probablement possible. A voir :)

Mais peut être va-t-on de donner une méthode qui marche mieux.

Vous pensez qu'il est possible avec du code de transformer ce traitement pour qu'il génère des coordonnées (2D) et non plus des positions sur une droite ?

Vu que je suis un peu débutante en la matière, j'avoue que j'ai un peu de mal à voir comment cela pourrait être possible :S

Au lieu d'avoir 1 tableau de positions, il faut 2 tableau (1 X et 1 Y) pour commencer.

Je l'ai fait hier si ce n'est qu'il y'a un problème pour calculer la contrainte de distance entre 2 point en 2D.

En effet il faut utiliser une racine carrée qui n'est pas disponible dans Choco (en tout cas j'ai cherché apres et j'ai meme essayer de la coder moi meme) ... cela pose problème mais sinon ca serait possible je pense... Il faudrait demander au gens qui ont codé le truc. ( dist = sqrt(delta(x)^2+delta(y)^2)). Il existe bien power qui pourrait utiliser pow(1/2) pour faire une racine carrée mais c'est dommage car ca fontionne qu'avec des entier ce pow :(

sinon utilisé une autre solution :)

Pour moi, au pif c'est compliqué, voire impossible, selon la provenance de la liste de distances... On peut par exemple imaginer un ensemble de distances qui représente une série de points en 3D mais pas en 2D...

A priori ou pourrait penser que ça peut se faire de proche en proche : on s'occupe du point le plus près du premier point, on le place, pour le suivant on pivote autour du points dont on a la distance jusqu'à ce que ce soit compatible, et ainsi de suite... Seulement on n'a aucun moyen de trouver / prouver que la solution existe ou est la seule, c'est au pif typiquement un problème NP-complet, ce qui implique l'utilisation d'une solution heuristique.

Oula, tout ca devient bien compliqué pour moi tout ca ...
Je vais essayer de méditer sur ca !!

slt,
On aimerai, si c'est possible, avoir plus de précisant sur le domaine d'application, pour pouvoir te donné une idée sur la manière de génération des coordonnées . (en d'autres termes, explique nous mieux ton problème) .
Sinon, en ayant les coordonnées, si tu rencontre des problèmes pour la représentation graphique des différents points, il t'est préférable d'utiliser le dessin en 2D disponible en JAVA, pour le faire, tu peut définir une extension d'un JPanel, dans la quelle, tu ré-implémente la méthode paint (Graphics g), et ensuite, dessiner des polygones .

Code:

---

1 2 3 4 5 6 7 8 9

public class myclass extends JPanel{ public void paint (Graphics g) {//paint g.setColor (Color.BLACK); int xPoint [n]; int yPoint [n]; g.fillPolygon (xPoint, yPoint, n); //n : nombre de points }//paint }

---

A+ , bonne chance ;).

Bonjour,

Je ne peux pas vous donner vraiment plus de précisions, cette interface est réalisée afin de voir l'état d'une architecture cognitive. Une classe principale lance tout le reste, et de là, je récupère uniquement les distances entre les différentes "connaissances" activées dans l'architecture et je dois les représenter graphiquement. Mais je n'ai que des distances deux à deux.

Pour les dessiner, j'utilise effectivement la classe Graphics de Java. J'arrive à les dessiner deux à deux avec la distance correspondante, mais quand il s'agit de les dessiner reliés comme ils sont censés être dans l'espace, j'ai un soucis de génération de coordonnées.

J'ai besoin de savoir quel est la figure que tu désire obtenir .
Quelle la logique qui vas permettre la représentation de ces différents points
:roll:.

Vu le nombre de possibilités, elle ne saurait pas le dire ça.

Voici en pièce jointe l'aspect plus ou moins attendu. Mais vu il y a beaucoup de possibilités pour les "angles" ... ca ne ressemblera pas forcément à cela.

Si tu veut les représentées sous forme d'un arbre, il te faut d'abord trouver une relation hiérarchique entre tes différents points, en suite, les arcs représenterons la relation père-fils, et en suite, imaginer un algorithme qui vas te permettre de rajouter tes objets, je te propose de commencer toujours par un point que tu vas définir, en suite, utiliser des variables qui vont être incrémenter après chaque insertion, ou teste qui vas vérifie si l'emplacement ou va se faire l'insertion est vide, ou pas .
A+, et bonne chance ;) :ccool: .

Nan mais bon c'est une blague ce truc : si tu n'as qu'une liste de distances entre points, sans autre information (on n'a même aucune garantie que ce soit en 2D ni même en 3D, ni même que ce soit un espace euclidien...), c'est un problème NP-complet, et il faut un algorithme heuristique. Bon, en plus si les coordonnées ne sont pas des entiers, c'est pire...

Merci à ceux qui ont tenté de m'apporter de l'aide.
Pour information si des personnes ont le même soucis, il y a une bibliothèque magique appelée JUNG qui trace un des graphes possibles à partir des différentes liaisons entre les points.