Discussion :

[minours]

Bonjour à tous

Je souhaite pouvoir calculer une zone isochrone à partir d'un réseau routier. Par exemple, je voudrais colorier les zones sur une carte situées à moins de 30 minutes en voiture d'une grande ville. Pour cela, j'imagine le réseau routier sous forme de graphe et grâce à l'algorithme de dijkstra, je récupère les sommets situés à moins de 30 minutes.

Mon problème est donc comment, à partir du nuage de points résultants, retrouver une zone polygonale (parfois avec des trous) ?

Je me suis penché sur les algorithmes de calcul de l'enveloppe convexe (parcours de graham ou la marche de jardis) mais la forme résultante n'est pas correcte s'il on imagine une autoroute qui part de la grande ville...

Merci de votre aide...

[PRomu@ld]

Pour ton problème, ça n'est pas le calcul d'une enveloppe convexe, mais plutôt non convexe pour un nuage de points.

J'espère que ceci pourra t'aider :

http://www.iag.asso.fr/articles/nuage.htm

Tu peux aussi chercher sur le forum, il me semble qu'il y a déjà eu une discussion à ce sujet.

[minours]

Bonjour,

Effectivement, il s'agit bien d'une enveloppe non convexe. Ton lien est fort intéressant. Néanmoins, la réflexion n'aboutit pas sur un algorithme efficace. L'idée de départ est bonne et j'en prends note.

Après quelques recherches sur le net, il ne semble pas y avoir de solution simple et performante. Surtout que la zone dessinée peut être trouée par un village difficile d'accès par le réseau routier (zone montagneuse au bord de la grande ville).

Le problème ne manque donc pas d'intérêt.

[PRomu@ld]

Une idée que j'ai lu dans un des posts précédents consiste à faire croître un polygone au fur et à mesure de tes calculs, ça peut peut-être être une bonne idée à creuser.

[FrancisSourd]

Une autre piste:

Une des difficultés du problème est de modéliser la vitesse de progression en dehors du réseau routier.

Pour chaque arête AB de l'arbre de Dijkstra, tu peux te poser le problème suivant: sachant que je suis à l'instant t0 au point A et à l'instant t1 à B, quels points du plans puis-je atteindre à l'instant t>t0 (en utilisant une vitesse arbitraire (celle de la marche à pied?) en dehors de l'axe AB).

Cela donne une surface convexe (pas exactement un polygône mais on peut l'approcher par un polygône) qui entoure A (et qui entoure AB si t>t1). Je peux de les définir si tu ne vois pas comment le faire.

En calculant toutes ces surfaces puis en faisant l'union de toutes ces surfaces pour les arêtes de l'arbre des plus courts chemins, on obtient une bonne approximation de la surface recherchée.

Faire l'union des surfaces n'est pas très facile (mais faisable!). Par contre, si tu as juste besoin de tracer la surface, c'est facile: il suffit de tracer chaque surface associée à une arête.

[JeitEmgie]

Bonjour,

Effectivement, il s'agit bien d'une enveloppe non convexe. Ton lien est fort intéressant. Néanmoins, la réflexion n'aboutit pas sur un algorithme efficace. L'idée de départ est bonne et j'en prends note.

Après quelques recherches sur le net, il ne semble pas y avoir de solution simple et performante. Surtout que la zone dessinée peut être trouée par un village difficile d'accès par le réseau routier (zone montagneuse au bord de la grande ville).

Le problème ne manque donc pas d'intérêt.

si vous poursuiviez votre réflexion dans cette voie, vous constateriez que votre énoncé de départ est basé sur un a priori erroné : qu'il y ait effectivement une "surface" (convexe ou non, avec ou sans trou…) comme solution au problème !

ce n'est pas du tout acquis…

cas simple :
prenez un cercle avec un certain nombre de "villes" réparties dessus…
mettons que l'on puisse faire le tour du cercle en moins de X minutes, X étant votre critère de sélection (donc les villes du cercle sont dans la zone isochrone X)

mettez un deuxième cercle à l'intérieur (votre zone montagneuse)
posez comme critère que les points de ce cercle sont accessibles entre eux en temps 2X et de tout point du cercle extérieur en temps 3X…

-> votre zone isochrone X n'a pas vraiment de surface dont la limite soit définie par des points existants…

il faudrait sans un pré-traitement :

entre tout couple de points (A,B) reliés directement par un temps T > à votre critère X, rajouter deux points fictifs (Xa, Xb) reliés aux points extrèmes originaux par un temps X et entre eux par un temps T-2X
(Attention, si T == 2X, n'en rajouter qu'un seul…, si T - 2X < 0 alors cas particulier : il faut inverser Xa et Xb et les distances deviennent d(A,Xa) = T-X, d(Xa,Xb) = 2X-T, d(Xb,B) = T-X )
et supprimer (ou marquer comme "inutilisée") l'arête A-B du graphe…

ce pré-traitement devrait garantir que la solution ait une surface quelle qu'elle soit… (en fait une liste de surfaces…)


NB
si vous changez l'énoncé et dites que tous les points du cercle intérieur sont accessibles entre eux en X1 <= X, et que vous utilisez un algorithme d'extension de polygone sans le pré-traitement, ils vont être absorbés graphiquement dans le cercle extérieur alors qu'il existe une "barrière"…
càd que la solution vous donnera sans doute 2 polygones séparés mais si vous les dessinez ils n'auront pas de frontière car ils vont se toucher et la coloriage fera apparaître l'ensemble comme une zone unique ce qui est faux…

[minours]

Merci pour tout ces conseils. Vos remarques sont intéressantes. Pour illustrer ce à quoi j'aimerais tendre :

http://www.emif.fr/rationimpl/index.php

La solution de constituer l'enveloppe convexe est très rapide mais la surface est trop importante. Pour ce qui est de créer un algorithme qui nécessite un union de polygone, je préfère éviter car les performances seront trop réduites. Faire croitre un polygone peut être intéressant...je vais y réfléchir.

Pour répondre à JeitEmgie, je ne comprends pas bien la mise en scène de vos cercles. Le but ici est de reconstituer sous une forme polygonale, un nuage de points qui est le résultat de l'algorithme de dijkstra. Le lien ci-dessus pourra peut être éclaircir mon besoin...

Merci pour toutes ces réflexions

[JeitEmgie]

Merci pour tout ces conseils. Vos remarques sont intéressantes. Pour illustrer ce à quoi j'aimerais tendre :

http://www.emif.fr/rationimpl/index.php

La solution de constituer l'enveloppe convexe est très rapide mais la surface est trop importante. Pour ce qui est de créer un algorithme qui nécessite un union de polygone, je préfère éviter car les performances seront trop réduites. Faire croitre un polygone peut être intéressant...je vais y réfléchir.

Pour répondre à JeitEmgie, je ne comprends pas bien la mise en scène de vos cercles. Le but ici est de reconstituer sous une forme polygonale, un nuage de points qui est le résultat de l'algorithme de dijkstra. Le lien ci-dessus pourra peut être éclaircir mon besoin...

Merci pour toutes ces réflexions

l'exemple des "cercles" ne sert qu'à vous montrer que l'on peut construire des situations où la reconstitution sous forme polygone à partir des seuls données originales ne donnera pas le résultat escompté… notamment le cas des "iles" illustré par 2 cercles imbriqués… (mais il y a d'autres cas pour lesquels les données originales peuvent générer des solutions inattendues…)

et que rajouter des points fictifs au graphe - avant de lui appliquer dijkstra - est une manière simple de garantir une solution dont la représentation graphique finale ne sera pas ambigue… et qui sera aussi plus précise…