IdentifiantMot de passe
Mot de passe oublié ?Je m'inscris ! (gratuit)

Vous êtes nouveau sur Developpez.com ? Créez votre compte ou connectez-vous afin de pouvoir participer !

Vous devez avoir un compte Developpez.com et être connecté pour pouvoir participer aux discussions.

Vous n'avez pas encore de compte Developpez.com ? Créez-en un en quelques instants, c'est entièrement gratuit !

Si vous disposez déjà d'un compte et qu'il est bien activé, connectez-vous à l'aide du formulaire ci-dessous.

Identifiez-vous
Identifiant
Mot de passe
Mot de passe oublié ?
Créer un compte

L'inscription est gratuite et ne vous prendra que quelques instants !

Je m'inscris !

Algorithmes pour chemins orthogonaux non croisés avec obstacles
Traduction commentée par Jean-Luc Mathieu

Le , par Alcatîz
18 commentaires

4PARTAGES

17  0 
Algorithmes pour les chemins orthogonaux non croisés avec obstacles - Théorie de Floyd-Warshall modifiée
Une traduction commentée par Jean-Luc Mathieu, avec exemples

Ce document est une traduction de l’article de référence « Non-crossing Rectilinear Shortest Minimum Bend Paths in the Presence of Rectilinear Obstacles » sur la méthode de calcul des chemins orthogonaux non croisés à nombre minimal de virages dans des grilles 2D avec obstacles. Il a été publié dans « Journal of Telecommunications and Information Technology » en 2018. L'article a été traduit par Jean-Luc Mathieu, qui l'a également augmenté par des explications, des exemples supplémentaires à des fins pédagogiques pour que chacun puisse en tirer parti.

L’article présente un nouvel algorithme pour tracer les chemins les plus courts, non croisés et rectilignes (orientation angulaire de 90°) dans un graphique de grille dimensionnelle. Les chemins les plus courts sont déterminés en veillant à ce qu’ils ne se croisent pas et contournent les obstacles présents. Ces chemins les plus courts sont appliqués dans la conception de nombreuses applications… Lorsque plus d’un passage entre la source et la destination est possible, l’algorithme proposé sélectionne le chemin qui a le moins de virages le long du chemin. Les obstacles sont contournés par les chemins solutions de l’algorithme de Floyd-Warshall. Cependant l’auteur présente ici une version améliorée qui calcule toutes les paires des chemins possibles pour identifier les chemins les plus courts qui ne se croisent pas. Pour obtenir ce minimum de courbes (changements de direction) dans un chemin, l’article propose une modification à l’algorithme Floyd-Warshall, qui est la principale contribution de l’auteur présentée ici.

https://xmrrwallet.com/cmx.pjlmat.developpez.com/tutorie...loyd-warshall/



Et vous ?
Que pensez-vous de cet article ?
Vous avez lu gratuitement 6 articles depuis plus d'un an.
Soutenez le club developpez.com en souscrivant un abonnement pour que nous puissions continuer à vous proposer des publications.

Une erreur dans cette actualité ? Signalez-nous-la !

18 commentaires
Commenter Signaler un problème
Jlmat
Avatar de Jlmat
Membre averti https://xmrrwallet.com/cmx.pwww.developpez.com
Le 25/07/2025 à 20:33
Citation Envoyé par Alcatîz Voir le message
Algorithmes pour les chemins orthogonaux non croisés avec obstacles - Théorie de Floyd-Warshall modifiée
Une traduction commentée par Jean-Luc Mathieu, avec exemples

Ce document est une traduction de l’article de référence « Non-crossing Rectilinear Shortest Minimum Bend Paths in the Presence of Rectilinear Obstacles » sur la méthode de calcul des chemins orthogonaux non croisés à nombre minimal de virages dans des grilles 2D avec obstacles. Il a été publié dans « Journal of Telecommunications and Information Technology » en 2018. L'article a été traduit par Jean-Luc Mathieu, qui l'a également augmenté par des explications, des exemples supplémentaires à des fins pédagogiques pour que chacun puisse en tirer parti.
...
L'approche est théorique et algorithmique cependant !
Elle aura une suite avec une application pratique d'un programme de simulation de comportement de circuits électriques et électroniques dont les connexions seront optimisées justement par cet algorithme.
4  0 
Guesset
Avatar de Guesset
Expert confirmé https://xmrrwallet.com/cmx.pwww.developpez.com
Le 27/07/2025 à 12:28
Bonjour,

Très intéressant, mais parfois un peu moins lisible qu'espéré. Par exemple, le changement de notation A(u, v) en A[u][v] pourrait se comprendre si on passait d'une notation mathématique (plutôt Au,v) à un code informatique. Mais les algorithmes ne sont pas réellement en pseudo code (lequel permettrait Au,v) et hésitent avec du C (ou autre C-like) d'où les ";" et A[u][v].

Il y a également quelques étrangetés
  • le tableau 1 qui concerne le premier chemin mais se trouve juste après le second chemin.
  • Je ne comprends pas les valeurs du tableau 1 : par exemple le chemin 2 a 7 nœuds donc 6 arêtes mais la longueur est 7, le 4 a 16 nœuds donc L=15 (pourquoi les virages 81 et 38 sont en double mais pas le 29 ?) etc.
  • la puissance de 3 qui devient 6 dans l'exemple (§ Heuristique)
  • la comparaison algorithmique qui considère que le seuil empirique de choix Floyd-Warshall vs Dijkstra est E > V²/log V. Pourtant O((V+E)log V) devient O(V²) ce qui reste meilleur que O(V³) même si O n'est pas réellement fait pour les comparaisons entre algorithmes.
  • les algorithmes supposent des XOR mais ne les utilisent pas. Exemple : (abs(i-k) >= H && abs(k-j) < H) || (abs(i-k) < H && abs(k-j) >= H) équivaut à (|i-k| >= H) xor (|k-j| >= H) ou en C-like (abs(i-k) >= H) ^ (abs(k-j) >= H). Certes ^ est un opérateur binaire et non logique mais cela fait le travail.
  • quelques répétitions (PCB et routage PCB, Layers et VLSI...)
  • Parallélisation Floyd-Warshall, si l'idée est bonne sur le division du temps cela ne change en rien la complexité O(n³) car O(n³/p) = O(n³). O sert à caractériser le comportement en évolution de charge d'un algorithme. Or si je double n le temps sera x8 qu'il y ait ou non plusieurs cœurs ou machines.
  • Le théorème des chemins non-croisés devrait peut-être préciser rectilinéaire.

La numérotation des nœuds me laisse perplexe. Utiliser deux variables entières x et y dans une structure semble plus simple et plus efficace. Il n'y a pas d'économie de place à procéder comme présenté car la réduction apparente occupera au moins 32 bits si on veut des performances correctes (pas de pb d'alignement). Grace à l'union, il reste possible de présenter Pi comme un entier non signé si nécessaire (Pi.u).

Ajout : Le point k de virage n'est pas utile dans sa détection : (Pi.x <> Pj.x) && (Pi.y <> Pj.y) suffit.

Travail de traduction remarquable. Ne pas prendre mes remarques pour des critiques. Si je ne l'avais pas trouvé bien, je n'aurais rien écrit .

Salutations
4  0 
Guesset
Avatar de Guesset
Expert confirmé https://xmrrwallet.com/cmx.pwww.developpez.com
Le 28/07/2025 à 13:39
Bonjour,

Sauf pour des critères esthétiques, je crains que le critère de poids de virage, tel qu'utilisé, soit contre-productif.

En effet les points qui sont à l'intérieur du triangle rectangle d'un coude, hors ceux du contour du coude proprement dit, soit (dx-1)*(dy-1) / 2 n'ont plus de réel intérêt comme via (d'autant moins que le principe de réduction des coudes se retourne contre leur usage) pour les autres chemins. C'est à dire qu'ils servent d'éventuelles extrémités. C'est un appauvrissement des possibilités.


Le trajet vert rend les points 18, 23, 28, 29 inintéressant comme vias, soit (3-1)*(5-1)/2 = 4 points alors que le trajet rouge ne tue aucune possibilité de vias.

Autre manière de voir cela. Imaginons une grille très dense en points, comme une image de quelques dizaines de mégapixels. Le tracé qui gène le moins sera toujours celui qui se rapprochera le plus d'une droite (Bresenham le retour). Les vues zooms laissent la distance Manhattan (D = |x1-x0| + |y1-y0| prendre le pas sur la distance euclidienne. Mais cela ne semble pas pertinent à grande échelle.

On pourrait aussi raisonner en ombre portée. Un segment a une ombre portée importante dans la direction orthogonale et nulle dans sa propre direction. Un parcours rectangulaire aura la même ombre portée dans la direction orthogonale mais une non négligeable dans l'axe des extrémités.
Le dessin ne montre qu'un sens comme un éclairage, mais en fait l'ombre portée est similaire dans l'autre sens. Cette ombre caractérise la gène à la propagation de chemins. Certes l'approximation de droite en escalier aura une légère ombre portée dans son axe mais sans commune mesure à celle d'un demi rectangle.

Salutations
4  0 
Jlmat
Avatar de Jlmat
Membre averti https://xmrrwallet.com/cmx.pwww.developpez.com
Le 27/07/2025 à 19:15
Citation Envoyé par Guesset Voir le message
Bonjour,

Très intéressant, mais parfois un peu moins lisible qu'espéré...
...
Travail de traduction remarquable. Ne pas prendre mes remarques pour des critiques. Si je ne l'avais pas trouvé bien, je n'aurais rien écrit .

Salutations
Merci Guesset pour tes remarques toujours pertinentes!

"mais parfois un peu moins lisible qu'espéré", c'est exactement ce que je pense, mais je cherchais un travail théorique pour démarrer mon projet et cet article est ce qui m'a permis de démarrer. Cependant j'avoue que certains choix me laissent également perplexes et je ne voulais pas donner un programme tant que je n'en maitrisais pas tous les aspects. C'est pour cette raison que j'ai décidé dans un deuxième temps, toujours dans la perspective de comprendre l'influence de divers paramètres de construire un simulateur de ces algorithmes et d'en ajouter un que j'ai construit perso qui sera sans doute modifié. Dans ce tutoriel, je voulais revenir d'ailleurs sur des notions et notations utilisées par l'auteur qui semblent différentes de ce que nous utilisons chez nous...
Tes remarques seront épluchées lors de mon prochain tuto car je souhaite en faire un outil pédagogique... Avant de proposer mon projet final de simulateur de circuits électroniques dans une version simplifiée

Tes avis sont toujours bienvenus car constructifs et me permettent de réfléchir dans la mesure de mes moyens car je ne suis pas un expert et j'ai d'autres activités prenantes... Mais ce projet final me tient vraiment à cœur!

Merci aussi à Alcatiz et f-leb qui m'ont soutenu dans cette publication que j'avais rédigée pour moi au départ... On a d'ailleurs encore quelques soucis avec l'éditeur xml ou pdf...

Bien à vous
2  0 
Roland Chastain
Avatar de Roland Chastain
Rédacteur/Modérateur https://xmrrwallet.com/cmx.pwww.developpez.com
Le 28/07/2025 à 16:53
Citation Envoyé par der§en Voir le message
Petite réflexion sans prétention: pour moi, le chemin le plus court dans beaucoup de cas est oblique!
Oui, mais les chemins obliques sont écartés par hypothèse. C'est bien précisé dans le premier message.
2  0 
Guesset
Avatar de Guesset
Expert confirmé https://xmrrwallet.com/cmx.pwww.developpez.com
Le 30/07/2025 à 23:23
Bonjour Jlmat,
Citation Envoyé par Jlmat Voir le message
...1...tes images, tu les dessine avec quelle application?
LibreOffice Draw exporté en png (il faut un peu jongler avec la taille et la résolution et je me mélange régulièrement les pinceaux).

2. Pour en revenir au problème, tu me fais découvrir l'approche de Bresenham[/B]
Je fais allusion à l'algorithme de tracé de droite de Bresenham, mais il ne recherche pas de chemin. C'est juste pour illustrer que l'approximation de droite est un escalier.

...J'ai un doute sur l'optimisation dans le cas de connexions multiples possibles sur de grandes grilles...
J'ai le même doute. Une petite grille de 100x100 va engendrer 1012 opérations soit plus de 16 minutes si on suppose avec optimisme une opération par ns. C'est quand même dommage sur une matrice à trous (creuse). Je trouve qu'on ne tire pas profit du 4-connection en appliquant un algorithme aussi généraliste.

Salut
2  0 
Guesset
Avatar de Guesset
Expert confirmé https://xmrrwallet.com/cmx.pwww.developpez.com
Le 30/07/2025 à 9:56
Bonjour,

Si le problème est de trouver des chemins avec le moins de coudes, l'approche de l'article est bonne nonobstant le fait qu'ajouter une partie fractionnaire pour le poids de virage n'est pas optimal.

Mais si l'objectif est de trouver simplement des chemins, il s'avère que la prise en compte des virages telle que prévue diminue les chances de l'heuristique. C'est ce que j'ai tenté d'exprimer de plusieurs manières.

Les vias désignent les points de passages intermédiaires. Si le programme favorise les coudes simples, les points à l'intérieurs d'un de ces coudes ne sont utilisables comme via que pour atteindre un autre point de ce coude. En effet, passer par eux pour joindre des extrémités hors ce coude suppose une multiplication de coudes, ce contre quoi lutte l'algorithme proposé.

J'ai repris le schéma suivant (issu de l'article) et calculé la longueur de parcours minimal de tous les 2nd liens (s, t) après avoir mis en place le chemin rouge ou vert.


Pour chaque 2nd chemin possible (il y en a 465), le tableau calcule le dépassement de l'idéal (|dx|+|dy|) : avec le premier chemin vert, le dépassement moyen dépasse de 47 % celui provoqué par un premier chemin rouge. Cela exprime la surconsommation de points (tableau : [ATTACH]669088d1/a/a/a" />).

Si l'esthétique prime il est toujours possible de faire un post-traitement comme celui bricolé ci après (il est peut être possible de l'intégrer dans la recherche car il ne semble pas remettre en cause le non croisement tout en libérant des points - à voir) :


Pour la maîtrise de la taille on repassera

Salutations
1  0 
Jlmat
Avatar de Jlmat
Membre averti https://xmrrwallet.com/cmx.pwww.developpez.com
Le 30/07/2025 à 21:48
Citation Envoyé par Guesset Voir le message
Bonjour,

...
J'ai repris le schéma suivant (issu de l'article) et calculé la longueur de parcours minimal de tous les 2nd liens (s, t) après avoir mis en place le chemin rouge ou vert.
...
Merci pour tes éclaircissements et illustrations...

1. J'aime bien tes images, tu les dessine avec quelle application?

2. Pour en revenir au problème, tu me fais découvrir l'approche de Bresenham que je connaissais pas et qui semble performante. il faut que je fasse une comparaison avec floyd-warshall. J'ai un doute sur l'optimisation dans le cas de connexions multiples possibles sur de grandes grilles => problème mémoire! C'est vrai que si je pouvais me débarrasser de la mémorisation d'une matrice intermédiaire, ça m'arrangerait! Il me semble que Floyd-Warshall soit lent à trouver le premier chemin exploitable, ça me chagrine... Bon, ça me donne des idées pour la suite...

Je viensde voir ton message der§en, merci

Bien à toi
1  0 
Guesset
Avatar de Guesset
Expert confirmé https://xmrrwallet.com/cmx.pwww.developpez.com
Le 02/08/2025 à 10:53
Bonjour der§en,

Citation Envoyé par der§en Voir le message
Algo Bresenham en pascal , ici:https://xmrrwallet.com/cmx.prosettacode.org/wiki/Bitmap/...gorithm#Delphi
C'est le "Hello world" du graphique ! Certains ne se sont pas cassé la tête en appelant simplement une fonction de tracé de droite.

Salut
1  0 
Guesset
Avatar de Guesset
Expert confirmé https://xmrrwallet.com/cmx.pwww.developpez.com
Le 02/08/2025 à 19:56
Bonjour der§en,

Citation Envoyé par der§en Voir le message
Heu, dans l'exemple on dessine la ligne pixel par pixel, très utile quand on veux faire des trucs plus complexe (comme je l'ai fait pour un éditeur de heightmap de ma composition)
Oui pour Delphi et de nombreux langages, les auteurs ont fait le job et réécrit la fonction Line, mais dans quelque cas le code se contente d'appeler une fonction. Soit la paresse s'est exprimée, soit ils considèrent que le tracé de ligne est intrinsèque au langage. Soit les deux .

Cela étant, travailler pixel par pixel en langage évolué est souvent très pénalisant, car il y a des vérifications pour chaque point. Par exemple pour faire des lignes en dégradés de couleurs, je dois me résoudre à passer, au moins partiellement, en assembleur.

Salut
1  0 
Commenter Signaler un problème