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!

[Roland Chastain]

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.

[der§en]

J’ai lu, d’où ma modeste réflexion

[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+

[Guesset]

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 : Algo - Parcours orthogonal.ods).

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

[der§en]

C’est pour moi, l’approche optimale

[Jlmat]

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

[Guesset]

Bonjour Jlmat,

...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 10¹² 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

[der§en]

Algo Bresenham en pascal , ici:

https://rosettacode.org/wiki/Bitmap/...gorithm#Delphi

[Guesset]

Bonjour der§en,

Algo Bresenham en pascal , ici:https://rosettacode.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

[der§en]

Bonjour der§en,

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

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)

[Guesset]

Bonjour der§en,

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

[der§en]

Pour l’anti alias IGN. Tu peux regarder de ce côté:
https://www.swissdelphicenter.ch/en/...de.php?id=1812

[Guesset]

Bonjour der§en;

Pour l’anti alias IGN. Tu peux regarder de ce côté: https://www.swissdelphicenter.ch/en/...de.php?id=1812

Je te remercie. Mais la ligne dégradée est simplement une ligne qui commence par une couleur et se termine par une autre :

Je ne suis pas sûr d'être fasciné par le code (apparemment ancien) du site :

• Si la longueur est nulle (i.e. les deux points n'en sont qu'un), le code fait un moveto, puis un lineto. Je crois que c'est parce que line ne trace rien si les extrémités sont confondues. Résultat : il y a deux contrôle de bornes pour un même point là où un simple ABitmap.Canvas.Pixels[x1, y1] := AColor; aurait suffit.
• AlphaBlendPixel fonctionne en Delphi mais scanline n'est pas la bonne solution sous Lazarus (plutôt RawImage.GetLineStart) ne serait-ce que pour la portabilité.
• AlphaBlendPixel travaille avec un flottant et il trouve le moyen d'avoir 6 multiplications au lieu de 3 : a*C1 + (1-a)*C2 = C2 + a*(C1-C2) quitte à transtyper C1 et C2. Le code suivant doit être au moins 10 fois plus rapide .

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 0 <= k <= 256 : ColorMix := C1*k/256 + C2*(1-k/256)_______________________________________TCOLOR
function ColorMix(C1, C2 : TColor; K : integer): TColor; overload; assembler; nostackframe;
asm                          // ecx  = C1, edx = C2, rd8 = k
   and       r8d,  $01FF     // r8d  = k entre 0 et 511
   mov       r9d,  256       // r9d  = 256
   pxor      xmm0, xmm0      // xmm0 = 0
   cmp       r8d,  r9d       //        k > 256 ?
   movd      xmm1, ecx       // xmm1 =  0   0   0   0    Z1  B1  V1  R1 = C1
   cmovg     r8d,  r9d       // r8d  = k > 256 ? 256 : k
   movd      xmm2, edx       // xmm2 =  0   0   0   0    Z2  B2  V2  R2 = C2
   movd      xmm3, r8d       // xmm3 =  0   0   0   0     0   0   0   k
   punpcklbw xmm1, xmm0      // xmm1 =     Z1      B1        V1      R1 = C1
   pshuflw   xmm3, xmm3, 0   // xmm3 =      k       k         k       k   0 = (0,0,0,0)
   punpcklbw xmm2, xmm0      // xmm2 =     Z2      B2        V2      R2 = C2
   psubw     xmm1, xmm2      // xmm1 = xmm1 - xmm2   = C1 - C2
   psllw     xmm3, 4         // xmm3 =    16k     16k       16k     16k
   psllw     xmm1, 4         // xmm1 = 16(xmm1-xmm2) = 16(C1-C2)
   pmulhw    xmm1, xmm3      // xmm1 = 16(C1-C2)*16k div 2^16
   paddw     xmm1, xmm2      // xmm1 = (C1-C2)*k div 256 + C2
   packuswb  xmm1, xmm0      // Compression entrelacée :  0000 ZBVR
   movd      eax,  xmm1      // eax  = C2 + (C1-C2)*k div 256
end;

Salut