Discussion :

[Alcatîz]

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://jlmat.developpez.com/tutorie...loyd-warshall/



Et vous ?
Que pensez-vous de cet article ?

[Jlmat]

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.

[Guesset]

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 A_u,v) à un code informatique. Mais les algorithmes ne sont pas réellement en pseudo code (lequel permettrait A_u,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

[Jlmat]

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

[Guesset]

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

[der§en]

Petite réflexion sans prétention: pour moi, le chemin le plus court dans beaucoup de cas est oblique!

[Jlmat]

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

En relisant ton message du 27/07/2025 (12h28), tu parles de coude, donc de triangle ou de détection d'un changement de direction? Dans mon idée, j'ai adopté la philosophie suivante: Partant du principe d'une grille aussi fine que l'exige le projet (paramètre du programmeur ou de l'utilisateur), elle est donc constituée de carrés. Les virages seront à éviter au maximum... Je ne sais pas encore trop comment limiter la recherche de chemins les plus courts dans mon projet (car le déplacement d'un obstacle entraine le recalcule de l'ensemble des chemins pour toutes les connexions). Le programme fonctionne si je ne préoccupe pas des croisements, mais dès que j'essaie d'appliquer l'algorithme de Floyd-Waeshall, les virages ne sont pas les plus courts et comportent des virages inutiles, non optimisés...

Dans l'article, au paragraphe VI-C-1 (ordre de traitement), il est clairement montré que si l'on détermine un chemin court en premier (fig. 6a, et que l'on ne travaille qu'avec une seule matrice, la recherche suivante (et réellement la plus courte) ne pourra pas être trouvée (fig.6b). D'où peut-être la nécessité de garder une matrice temporaire en mémoire afin de pouvoir explorer d'autres chemins qui seraient effacés par une première évaluation. Je crois que la variable k est comme un pivot de plusieurs directions possibles.

Le programme fait ses recherches à partir des voisins libres d'un noeud : Ces directions sont de 4 au maximum pour un nœud entouré d'autres nœuds, de 3 directions possibles pour un nœud sur un bord (mais pas les coins) et de 2 pour les quatre coins. Il faut donc bien indiquer les nœuds retenus. Donc, lorsque tu écris

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

, tu veux dire que l'on peut enchainer l'exploration des chemins sans faire appel aux poids? Peux-tu expliquer plus concrètement? par exemple en reprenant l'exemple de la figure 6a et 6b de l'article.
Bon va falloir que je m'y colle, mais je suis peu disponible en ce moment... Il faut que je fasse un essai sur une petite matrice...

...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.

Que signifie "comme via"?
Mais l'appauvrissement ne vient-il pas justement de la notion d'ordre de la recherche et la mémorisation d'un point pivot pour explorer les autres chemins à partir des voisins libres d'un Noeud pivot k ou autre?

merci pour tes éclaircissements!
A+