Help: le chemin le plus court sans croisé

[abdeleln]

Bonjour,

J'ai une liste de points: P(x,y)

Je dois relier ces points en passant par le plus court chemin et surtout il ne faut pas croiser les lignes !!


j'ai essai plusieurs algo mais j'ai toujours le probleme de croisement de ligne. :mur:

Help ! :triste:

[L.A.]

Bonjour.

Si c'est sur un exemple précis, tu peux le poster (je sais pas comment) pour qu'on puisse aider.

Si c'est un algorithme général que tu cherches , je connais pas...

[Nightmare]

Salut :happy3:

Si j'ai bien compris l'énoncé, une idée serait de considérer l'enveloppe convexe de l'ensemble de tes points puis l'enveloppe convexe des points restant en enlevant la frontière (point déjà "reliés" par la première enveloppe) etc. Tu "casses" alors un trait de chaque enveloppe et tu les relis entre elles de sorte à obtenir un genre de spiral.

[busard_des_roseaux]

Bj,

Après la spirale de NightMare

i) la courbe
si le nuage de points a la forme d'une courbe d'une fonction (droite,parabole,etc..), propriété que l'on peut tester par l'algorithme des moindres carrés, la courbe donne une "autoroute" et l'on joint ensuite
les points par des normales à cette courbe ("chemins de traverse
ou chemins campagnards")

ii)avec grandes villes et campagnes
autre idée: le flocon 1

On se donne un rayon R, on détermine pour chaque point M, une densité
de population dans la boule fermée de centre M et de rayon R.

On détermine les maxima locaux de la densité de population
(les "grandes villes") , on relie les grandes villes, et dans les boules fermées de centres "les grandes villes" , voisinages étoilés, on relie ensuite les
points intérieurs de chaque boule ("les banlieues")


iii)
autre idée: le flocon 2

si le nuage de points est équiréparti, on détermine deux
droites des moindres carrés, (à peu près perpendiculaires)
ce qui donne 4 régions du plan, donc une partition de l'ensemble
des points en 4 sous-ensembles, et on recommence un sous-algorithme
de deux segments de droites des moindres carrés
sur chaque sous-ensemble, ce qui devrait déterminer un "réseau routier"

[abdeleln]

Bonjour.

Si c'est sur un exemple précis, tu peux le poster (je sais pas comment) pour qu'on puisse aider.

Si c'est un algorithme général que tu cherches , je connais pas...

Merci d'avoir Manifester.

Exemple:

j'ai un plan 2 dimensions, avec un repaire r(0,0),

j'ai une liste de points:

Point1 (300, 0);
Point2 (20, 10)
Point3 (100, 100)
Point4 (200, 0)
Point5 (0, 400)
Point6 (300, 100)
Point7 (50, 50)
Point8 (40, 100)
Point9 (20, 20)
Point10 (50, 60)
Point11 (110, 50)
Point12 (200, 40)
Point13 (300, 30)

Si je relie les points en commençant par le Point1( Point1->Point2 ->Point3 ->Point4...->Point11) alors j'aurai un polygone ouvert et croisé !!

le But est de trier ces points dans un ordre pour obtenir une route de courte chemin et surtout pas de croisement.

Dans cette exemple l'orde des points que mon algo donne est le suivant:

Point5 (0, 400)
Point9 (40, 100)
Point11 (50, 60)
Point8 (50, 50)
Point10 (20, 20)
Point2 (20, 10)
Point3 (100, 100)
Point12 (200, 40)
Point4 (200, 0)
Point1 (300, 0);
Point13 (300, 30)
Point6 (300, 100)

Mais mon algo ne marche pas pour tous les cas ! :triste:

[abdeleln]

Bj,

Après la spirale de NightMare

i) la courbe
si le nuage de points a la forme d'une courbe d'une fonction (droite,parabole,etc..), propriété que l'on peut tester par l'algorithme des moindres carrés, la courbe donne une "autoroute" et l'on joint ensuite
les points par des normales à cette courbe ("chemins de traverse
ou chemins campagnards")

ii)avec grandes villes et campagnes
autre idée: le flocon 1

On se donne un rayon R, on détermine pour chaque point M, une densité
de population dans la boule fermée de centre M et de rayon R.

On détermine les maxima locaux de la densité de population
(les "grandes villes") , on relie les grandes villes, et dans les boules fermées de centres "les grandes villes" , voisinages étoilés, on relie ensuite les
points intérieurs de chaque boule ("les banlieues")


iii)
autre idée: le flocon 2

si le nuage de points est équiréparti, on détermine deux
droites des moindres carrés, (à peu près perpendiculaires)
ce qui donne 4 régions du plan, donc une partition de l'ensemble
des points en 4 sous-ensembles, et on recommence un sous-algorithme
de deux segments de droites des moindres carrés
sur chaque sous-ensemble, ce qui devrait déterminer un "réseau routier"

Je suis informaticien :doh: , il me faut un Algo :briques: , pouvez-vous peut etre simplifier !! :marteau:

[Imod]

Je ne sais pas ce que ça donne du point de vue programmation mais si ton chemin contient deux segments [AB] et [CD] qui se coupent , en remplaçant [AB] et [CD] par [AD] et [CB] tu ne romps pas la continuité du chemin et qui plus est tu diminues sa longueur .

Imod

[busard_des_roseaux]

re,

d'où vient cet énoncé ? pourquoi les arêtes du graphe ne doivent pas s'intersecter ? Quelle est la forme du nuage de points
? la densité des points est-elle uniforme ?

dans l'exemple cité, il s'agit,très approximativement, de la réunion de trois segments de droites de pente 1,-1 et

[abdeleln]

Je ne sais pas ce que ça donne du point de vue programmation mais si ton chemin contient deux segments [AB] et [CD] qui se coupent , en remplaçant [AB] et [CD] par [AD] et [CB] tu ne romps pas la continuité du chemin et qui plus est tu diminues sa longueur .

Imod

Mais il faut commencer par trouver le plus court chemin :hein:

[abdeleln]

re,

d'où vient cet énoncé ? pourquoi les arêtes du graphe ne doivent pas s'intersecter ? Quelle est la forme du nuage de points
? la densité des points est-elle uniforme ?

dans l'exemple cité, il s'agit,très approximativement, de la réunion de trois segments de droites de pente 1,-1 et

et bien c'est une problématique réel, je m'explique :

je developpe une Application qui affiche sur l'écran (sur un plan) des installations éléctric (donc des petites figures qui possedent des coordonées x y sur le plan de l'écran) le nombre de Points (figures) ne dépasse pas 15 points mias il n'est fixe.Mon cahier de charges est :

l

1) tracer une courbe (Ligne,segment) qui passe par toutes les figures,
2) le chemain trouvé doit étre le plus court (le plus optimal)
3) la ligne ne dois pas croisé.

Donc je dois trié ces l points dans un tableau puis je relie par programation le point N au Piont suivant N+1.

Peut etre que c'est un proplem de recherche operationel !!?

[john32]

J'ai du m'interesser a de tels algos (mais d'assez loin quand meme :we: ) dans le cadre dans projet.
Regarde du cote d'algo pour determiner les enveloppes convexes ca devrait donner des idees je pense.

http://www-sop.inria.fr/geometrica/courses/slides/enveloppe-convexe-od.pdf

Apres je ne suis pas sur que cela reponde au probleme pose (minimisation) mais bon c'est a voir.

PS : Les points que tu cherches a relier sont dans un espace de deux dimensions ? :hein:

[abdeleln]

J'ai du m'interesser a de tels algos (mais d'assez loin quand meme :we: ) dans le cadre dans projet.
Regarde du cote d'algo pour determiner les enveloppes convexes ca devrait donner des idees je pense.

http://www-sop.inria.fr/geometrica/courses/slides/enveloppe-convexe-od.pdf

Apres je ne suis pas sur que cela reponde au probleme pose (minimisation) mais bon c'est a voir.

PS : Les points que tu cherches a relier sont dans un espace de deux dimensions ? :hein:

Merci pour la piste, :id: oui ils sont dans un espace 2 dim (Coordonées X,Y).