Bonjour,
mon probleme n'est pas directement lié a Java, mais c'est un probleme d'algo
 
je dispose dune liste de points (noeuds) (x,y) avec lequels je dois tracer des routes dans un espace graphique 2d.
 
mon probleme est que : le placement des points doit etre fait par le programme afin de simplifier au maximum le tracé des routes (minimum de route qui se croisent, pas de route en diagonal!). bref, faire un peu comme les logiciel qui tracent les routes de circuit electronique.
 
est ce que quelqu'un a des information ou un debut de piste pour realiser une telle chose ??
car j'avoue ne pas trop savoir comment m'y prendre  
 
 
ps : chaque noeud a un nombre differents de conexions (minimum 1 maximum X)

c'est super chaud ... y a des gars qui font des théses sur ce sujets.
 
En tout cas , regarde du côté de la Recherche Opérationnelle et de la théorie des graphes.

regarde du coté de Bellman ou Dijkstra!

oulaa, je crois que je veux m'attaquer a plus fort que moi :s
 
jai regardé du coté des recherche operationnelles, j'y ai pas trouvé grand chose d'interressant se rapportant a mon probleme.
 
 
l'algorithme de Dijkstra est utilisé pour trouver la route la plus courte entre deux noeuds quand il existe plusieurs chemins, il est notement utilisé dans les routeurs qui supportent les protocoles de routage a état des liaisons (ospf). quant a l'algo de Bellman, il permet au contraire d'etablire la route la plus longue!
 
moi ce que je souhaite faire, c'est dessiner 'graphiquement' ma route, nayant comme element de depart uniquement les differentes routes et noeuds, et cherchant a obtenir un placement (plus ou moins) optimisé de mes noeuds sur un repere!
 
je sens que je vais pas dormir beaucoup durant mes prochaines nuits

Bellman permet de trouver le plus cour chemin également, très utilisé ds les calculateur d'itinéraire!
sinon c'est un peu la meme chose mais à l'envers
mais etudie bien la theorie des graphes (listes de successeur, predecessuer, connexité etc..)!
c'est à mon avis ce qu'il te faut!

En partant de Bellman tu devrais arriver a quelque chose.
La partie chaude c'est la contrainte de non-croisement

A mon avis tu devrais regarder du coté de l'optimisation combinatoire ... (tu veux minimiser qq chose... ) et à mon avis c'est du NP-complet.
 
Essaye de "formaliser" le probleme avant de penser à creer un algo, ceci dans le but de converger vers une strategie "ad-hoc"
 
Voila une formalisation éventuelle:
 

 
A partir de là  tu vas sur : http://www.nada.kth.se/~viggo/wwwc [...] de276.html
 
Et tu cherche comme un malade en te munissant d'un dico d'anglais et de beaucoup de patience (sur ce site il y a a peu pres tous les algos "modeles" "formalisés"  qui peuvent etre imaginés par un esprit humain )
 
Sinon on pourrait faire encore plus d'abstraction en considerant un graphe (en entrée) ou E est l'ensemble des arretes tel qu'il existe une arrete entre
deux sommets si et seulement si il n'y a pas de route diagonale ... regarde aussi la methode pour dire si un graphe est planaire ou pas.
 
UNDERSTAND => ABSTRACT => FORMALIZE => APPROXIMATE => WIN

Pour eviter les chemins qui se croisent :
1) Relient tes points à la même manière que resoudre le PVC
2) Une fois tes points tous réliés, applique l'heuristie 2-Opt ou 3-Opt et tes croisements disparaitront. Sur ce site, ils en parlent, sinon regarde sur google avec '2-Opt heuristic'

Bon en cherchant sur google (sans vouloir, en faite c t pour autre chose le but de ma recherche ) j'ai pensé a toi et j'ai trouvé CE link de la mort :
 
http://www.fsa.ulaval.ca/personnel [...] 0Essai.pdf
 
 
...honnêtement, tu prends a partir de la page 50 et tu peux difficilement trouver mieux comme information

Ya plus qu'à recroiser toutes ces infos ;-)
Juste une précision :
la recherche des plus courts chemins, c l'algorithme
de Bellman ET Kalaba, Richard et Robert quoi !
 

tu peux aussi voir du cote des algorithmes genetiques.
en plus c tres marrant comme truc... enfin je trouve.
 

Et la théorie des graphe ça ne peut pas t'aider ?

Une réponse aussi vague, c'est sûr que ça ne peut pas l'aider  

Giz : one point  

 
T1 ! c'est pas de bol ça, le lien viens juste de tomber en rad.
J'ai le fichier sur mon dur si ca interesse kk1
 
EDIT : le lien google du pdf (si le link se remet a marcher)
http://www.google.fr/search?source [...] ssai%2Epdf
 
=> et la version HTML marche

je sens qu'on oublie ce topic super important
et j'affirme (ou je confirme ^^^) qu'il y a une solution de 10-15* lignes en C++ qui donne des graphes planaires à coups sûrs et dans un temps plus qu'honorable.

Ca pourrait m'intéresser pour un soft qui doit tracer les connexions réseaux entre des machines situées dans une salle...

oui, jai laissé tombé
mais je suis quand meme interressé par tes 10/15lignes de code

Je demande à voir, parce que les layouts de graphe, y en a des tas, et à part quelques uns qui sont payant très cher qui donnent des résultats intéressants, je n'ai rien vu qui soit vraiment convaincant.

pas le choix du language!
l'enoncé est :  
on possede un schema electronique et on souhaite realiser l'implementation sur un circuit imprimé monoface!
- pas le droit de croiser les connexions!
- utiliser le minimum d'espace possible!
- uniquement des liaisons verticale et horizontale!
- placement des composants libre (et optimisé)!

ouais enfin, le choix du langage... tu peux toujours passer par jini.
 
Par contre, le problème de représentation de graphe est bien np-complet et ne peut se résoudre qu'avec des euristiques. Du coup, je me pose des questions sur ton énoncé: soit il y a des contraintes supplémentaires sur les graphes que tu ne nous a pas dit, soit ce sera purement et simplement impossible pour la plupart des graphes.