Discussion :

[Guesset]

Bonjour wiwaxia,

...@Guesset: J'ai lancé l'exécution du fichier décompressé, mais n'ai vu qu'un défilement cyclique de lignes brisées quasi-verticales ... Peut-être fallait-il attendre plus longtemps ?

C'est le mode d'attente, j'ai gardé l'animation de la ligne qui parcourt les points dans l'ordre après tri. Initialement c'était pour vérifier que le classement était bon. Et puis je l'ai laissé pour le fun.

Les commandes sont simples (je ne les avais pas rappelées car elles étaient dans le post #47) :

• Clic sur Chercher (ou Alt C) recherche le plus grand rectangle (avec un ratio de dy/dx < 2/3 et un dYmini (hauteur minimale) paramétrable par le SpinEdit de droite. Le temps en ms est affiché au milieu du panel mais c'est toujours 0.
• Clic sur Chercher avec Ctrl appuyé fait la même chose en mode démo. Si la touche Ctrl est maintenue, les étapes s'enchaînent toutes les secondes sinon toutes les 0.2 secondes.
• Clic sur Nouveau opère un nouveau tirage au sort de N points réglable de 2 à 256 avec le SpinEdit de gauche.
• Clic sur Nouveau (ou Alt N) avec Ctrl appuyé fait la même chose mais enchaîne directement la recherche.
• Avec Ouvrir (ou Alt O) on peut charger un CSV (délimiteur ";") sans espace et sans titre. Format type : x;y. Les points n'ont pas besoin d'être dans un ordre particulier.
• Avec Sauvegarder (ou Alt S) on peut sauvegarder les points et le résultat en CSV. Il y a 3 colonnes : n°_originel;X;Y (pour le résultat : R0;X,Y et R1;dx;dy).
• Un clic sur l'image sélectionne simplement le point le plus proche.

J'ai depuis mis en œuvre une autre optimisation que j'appelle le dYmin (hauteur minimale) dynamique qui est calculé quand on change de scan (Xo augmente) et quand on trouve un plus grand rectangle (dYmin = Smax/(Lx-Xo)). Le gain est limité (mais quand même >10 % à 256) tendant légèrement à décroitre avec N. Si ça t'intéresse : Big_rect 5.zip (j'ai retiré la contrainte de ration qui casse l'esprit de rechercher le plus grand rectangle).

J'ai testé tes valeurs sur mon bidule, je trouve les même résultats, mais il y a un gros problème de classes : mathématicien vs tekos, repère direct contre repère inverse, repère mathématique contre repère écran
Ce n'est pas le même algo que tu as présenté initialement, apparemment tu testes tous les quadruplets de points que tu filtres. Ca fait 21⁵ = 4 millions d'itérations pas trop chargées, ça devrait tourner entre le 0.1 s et 1 s ce qui reste humainement instantané. Je pense que tu pourrais accélérer le traitement de TestL en sortant de la boucle dès que la condition est satisfaite. Si tu es sous Lazarus, ceci pourrait tomber en marche :

Code Pascal :

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

1
2
3
4
5
6
7
8
FUNCTION TestL(K1, K2, L1, L2: Byte; VAR N_: Tab_V): Boolean;
VAR m : Byte;
BEGIN
   FOR m := 1 TO Npoint DO 
      if  (N_[K1].x < N_[m].x) and (N_[m].x < N_[K2].x)
      and (N_[L1].y < N_[m].y) and (N_[m].y < N_[L2].y)) then Exit(False);
   Result := True;
END;

Salut

[wiwaxia]

Bonjour Guesset,

... Les commandes sont simples (je ne les avais pas rappelées car elles étaient dans le post #47)

Merci pour toutes ces infos qui m'avaient totalement échappé - j'étais un peu bousculé par les circonstances.
Je suis curieux de voir comment tu as pu ramener la solution à un algorithme linéaire.

... mais il y a un gros problème de classes : mathématicien vs tekos, repère direct contre repère inverse, repère mathématique contre repère écran

C'est ici secondaire, parce que cela ne change rien aux distances; et le renversement de l'image supprimerait le problème.
Cela serait par contre insupportable en imagerie 3D, où l'intervention d'un repère indirect invalide l'identification gauche/droite (c'était le cas de POV Ray).

... Ce n'est pas le même algo que tu as présenté initialement, apparemment tu testes tous les quadruplets de points que tu filtres. Ca fait 21⁵ = 4 millions d'itérations pas trop chargées, ça devrait tourner entre le 0.1 s et 1 s ce qui reste humainement instantané. Je pense que tu pourrais accélérer le traitement de TestL en sortant de la boucle dès que la condition est satisfaite ...

Effectivement, parce que mon idée initiale était totalement erronée: les contraintes imposées su les coordonnées (x, y) ne sont pas indépendantes.
La rapidité de l'exécution tient au taux d'élimination relativement élevé des paires de points; il faudrait voir ce que cela donne pour de plus grandes valeurs de (N). Je reprendrai l'emploi de la fonction TestL.

Salut.

[aj3309]

Bonsoir Guesset
Voici la table des points que j'utilise avec mon jeu d'essai réduit
RechercheRectangles NbrePoints = 5 LargeurCarte = 900 HauteurCarte = 452,25
3 ChargeTabPointsFromFeuilleData() i = 1 Tabpos(i).X = 0 Tabpos(i).Y = 451,25
3 ChargeTabPointsFromFeuilleData() i = 2 Tabpos(i).X = 75 Tabpos(i).Y = 414,5625
3 ChargeTabPointsFromFeuilleData() i = 3 Tabpos(i).X = 614,037353515625 Tabpos(i).Y = 242,120620727539
3 ChargeTabPointsFromFeuilleData() i = 4 Tabpos(i).X = 697,779418945313 Tabpos(i).Y = 37,6875
3 ChargeTabPointsFromFeuilleData() i = 5 Tabpos(i).X = 763,572631835938 Tabpos(i).Y = 387,770751953125
3 ChargeTabPointsFromFeuilleData() i = 6 Tabpos(i).X = 825 Tabpos(i).Y = 309,770355224609
3 ChargeTabPointsFromFeuilleData() i = 7 Tabpos(i).X = 899 Tabpos(i).Y = 451,25
3 est un repère m'indiquant que cette liste est établie après le tri.

Fin de la procédure RechercheRectangles() NbrePoints = 5 NbreScans = 6 j = 7 iRect = 8 en 0s 77ms , résultats faux et incomplets.

Pour passer aux deux étapes suivantes si elles existent tu écris
Si i < PosNb faire ...
Je me pose la question de savoir si dans ce cas PosNb est le nombre de points ou le plus grand indice de la table Pos().
Toi tu ne te poses pas la question car ces deux variables ont la même valeur, mais moi c'est 16 ou18 et cela change beaucoup de choses.
Pour le travail des largeurs et des hauteurs je raisonne en valeur absolue, est-ce légitme?

[Guesset]

Bonsoir,

Si c'est un indice, et i est un indice puisqu'il sert comme indice dans le tableau (idem pour j qui, transposé, va de 1 à PosNb+1). L'indice i va donc de 0 à PosNb-1 pour les points normaux transposé en 2 à PosNb+1.

Quand on vérifie que cet indice i est < PosNb, on s'assure que i n'est pas sur la bordure droite ce qui se transpose en i < PosNb + 2. D'ailleurs les explications le précisent, "Passer aux 2 étapes suivantes si elles existent". Pour qu'elles existent, il ne faut pas être déjà sur le bord droit qui correspond à PosNb transposé en PosNb+2 parce qu'alors il est impossible d'aller plus à droite.

Il devrait y avoir (n+1)² soit 36 rectangles avec cette version de l'algorithme.

Oui il est possible de travailler en valeur absolue mais ce n'est pas indispensable. On progresse de gauche à droite donc les Xo sont toujours <= aux X des côtés droits des rectangle (abscisse de l'obstacle rencontré en allant vers la droite). Pour les Ytop et Ybtm, les noms parlent d'eux mêmes Ytop < Ybtm (les valeurs croisent en descendant sur un écran).

Salutations

[Guesset]

Bonjour wiwaxia,

...La rapidité de l'exécution tient au taux d'élimination relativement élevé des paires de points; il faudrait voir ce que cela donne pour de plus grandes valeurs de (N).

J'ai eu une idée ce matin. Finalement tu testes 4 fois les mêmes configurations, il y a donc un gain de 4 assez facile :

Code Pascal :

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

1
2
3
4
5
   FOR I1:= 0 TO Np1-3 DO
      FOR I2:= I1+1 TO Np1-2 DO
         ...
            FOR J1 := I2+1 TO Np1-1 DO
               FOR J2 := J1+1 TO Np1 DO

Bien sûr cela demande de faire sauter le distinguo entres balayages en x et en y et modifier le code xleft = min(P.X_1..4) etc. qui pourrait être simplifié si les points étaient triés. La fonction TestL pourrait également en être améliorée en commençant à I1+1 et se terminant à J2-1 (si tri selon X primaire et Y secondaire les deux croissant).

Salut

[wiwaxia]

Bonjour Guesset,

... Finalement tu testes 4 fois les mêmes configurations, il y a donc un gain de 4 assez facile :

Code Pascal :

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

1
2
3
4
5
   FOR I1:= 0 TO Np1-3 DO
      FOR I2:= I1+1 TO Np1-2 DO
         ...
            FOR J1 := I2+1 TO Np1-1 DO
               FOR J2 := J1+1 TO Np1 DO

...

Je ne crois pas, car la comparaison des points d'indices (I1, I2) porte sur les abscisses, tandis que celle sur les points d'indice (J1, J2) concerne les ordonnées.
Un peu plus de la moitié des couples envisagés à chaque stade est éliminée par les conditions:

IF (N_[I2].x>N_[I1].x) THEN ... / ... IF (N_[J2].y>N_[J1].y) THEN ...

d'où l'intérêt (sans doute discutable) de travailler sur deux listes ordonnées selon l'ordre croissant des valeurs de x et y.

Si l'on a I1 (ou I2) = J1 (ou J2), alors le point considéré se trouve à l'un des 4 coins du rectangle.
Les deux groupes d'indices sont indépendants, et le balayage doit se faire de 0 à (Npoint + 1).

J'ai adapté le programme au cas de 200 points: le délai d'exécution de l'énumération des triangles monte à 35 minutes ! Comme on pouvait s'y attendre, l'algorithme ne brille pas par sa rapidité ... mais on est très loin dans ce cas du problème initialement posé.
Je trouve ce sujet intéressant en soi.

Salut.

[unanonyme]

Bonjour,

Je me disais que quelques images feraient aussi bien pour expliquer là où j'en était dans ma tête.

Je crois que c'est la méthode déjà expliquée au préalable par balayage.

En utilisant les points triés par la valeur X, on va les parcourir de gauche à droite, de 0 à N, en faisant des recherches arrières pour trouver maxX et maxY du rectangle en cours de détermination.

État initial


Etape 1
on va buter sur P1, regarder en arrière, ne trouver aucun points, utiliser les bords.


Etape 2
on va buter sur P2, regarder en arrière, trouver P1, construire un premier rectangle avec les bords haut et bas de la fenêtre et P1 comme référence.


Etape 2-1
Puisque P1.Y < P2.Y, construire un rectangle avec P1 comme référence pour le bord haut, la fenêtre pour le reste.

* Je me rends compte, en l'écrivant que j'ai loupé une étape, il y a un rectangle intermédiaire P1/P2 avant d'aller buter sur 0.

Etape 3
on bute sur P3, on trouve P1/P2 comme références arrière, en commençant par P2.


Etape 3-1
on bute en arrière sur P1, en considérant P2.


Etape 3-2
on bute en arrière sur le bord de la fenêtre, en considérant P1 pour le bord bas.


Je m'arrête là, le bbcode ne m'aide pas, et ça surcharge les serveurs pour rien, je pense que c'est suffisant pour comprendre l'idée.

Fait avec https://www.photopea.com/

Bonne journée.

[Guesset]

Bonjour unanonyme,

...Je crois que c'est la méthode déjà expliquée au préalable par balayage...

Oui. Mais il y a un double balayage. Pour N points il y a N+1 (avec le bord gauche en plus) balayages qui commencent depuis le bord gauche, puis le premier point, puis le second etc.
Chaque balayage élémentaire va aller jusqu'au bord droit en se scindant en deux sous balayages à chaque fois qu'il rencontre un point obstacle (voir post #14 pour le tout premier balayage élémentaire). Les rectangles générés vont toujours jusqu'au début du balayage en cours (les rectangle - dit générateurs - du dessin prolongés jusqu'en début de scan).

Je m'arrête là, le bbcode ne m'aide pas, et ça surcharge les serveurs pour rien, je pense que c'est suffisant pour comprendre l'idée.

Les programmes que j'ai envoyé ont un mode démo (Clic+Ctrl sur Chercher) qui montrent le processus. Comme ils sont optimisés, ils ne visitent pas les (N+1)² rectangles différents, aussi certains abandons de pistes peuvent apparaître bizarre (voir post 61 pour le dernier envoi).

J'ai peut être un peu exagéré sur le nombre de points (256 qui est le max de ce PoC). Le processus est linéaire (au moins jusqu'à 256 )

• L'algorithme en bleu trouve tous les rectangles vides (N+1)², cela reste assez rapide de l'ordre de 2 à 3 ms.
• L'algorithme en rouge ne regarde pas les rectangles générateurs qui n'ont aucune chance d'engendrer un plus grand rectangle. Par exemple, dès que l'on retrouve un même rectangle générateur on abandonne. En effet cela signifie que ce rectangle et ses suivants ont déjà généré des rectangles plus grands. L'ordre est désormais linéaire. Le temps en ms reste imperturbablement à 0.
• L'algorithme en jaune reprend le précédent en modifiant progressivement la hauteur minimale en fonction de la taille du plus grand rectangle et de la distance entre le début du scan courant et le bord droit. On gagne à peu près 15% par rapport à la version précédente.

Il y a encore quelques pistes d'amélioration, mais elles me semblent relativement lourdes pour des gains limités (l'orientation par exemple)

Salut

[Guesset]

Bonjour wiwaxia ,

...on est très loin dans ce cas du problème initialement posé. Je trouve ce sujet intéressant en soi...

Je partage cet intérêt et pourtant ça prend du temps . Je trouve aussi que le problème ramené au seul intitulé initial est plus motivant.

Si ces solutions peuvent aider le PO, c'est bien mais finalement son problème ne semble pas de rechercher le plus grand rectangle mais des rectangles utilisables pour afficher des informations proche d'un point donné. Comme il semble travailler avec VBA, j'aurais même tendance à faire apparaître un hint avec les informations utiles lorsque l'on clique près d'un point. Que le hint se superpose un temps à la carte n'a guère d'importance puisqu'il n'altère pas le contenu de celle-ci.

Salut.

[unanonyme]

@Guesset,

Mais il y a un double balayage.

Pour un point en cours d'analyse, en Y au dessus et au dessous ? Si c'est de cela qu'on parle, il me semble que cet intervalle commence à 0,bottom et se réduit à chaque point antécédent rencontré.

Souvent je comprend rien à ce que vous racontez désolé pour cela, je vois bien que vous faites des efforts.

Je n'ai pas testé vos exécutables.

[aj3309]

Bonjour wiwaxia ,



Je partage cet intérêt et pourtant ça prend du temps . Je trouve aussi que le problème ramené au seul intitulé initial est plus motivant.

Si ces solutions peuvent aider le PO, c'est bien mais finalement son problème ne semble pas de rechercher le plus grand rectangle mais des rectangles utilisables pour afficher des informations proche d'un point donné. Comme il semble travailler avec VBA, j'aurais même tendance à faire apparaître un hint avec les informations utiles lorsque l'on clique près d'un point. Que le hint se superpose un temps à la carte n'a guère d'importance puisqu'il n'altère pas le contenu de celle-ci.

Salut.

C'est vrai que c'est une solution élégante et efficace , il suffit de ne pas recouvrir le point cliqué. Je me demande pourquoi je suis allé chercher une solution aussi compliquée , c'est vrai pourquoi faire simple quand on peut faire compliqué.
Malgré tout cet algorithme me plait beaucoup et je voudrais réussir son implémentation en VBA.

[Guesset]

Bonjour unanonyme

Souvent je comprend rien à ce que vous racontez désolé pour cela, je vois bien que vous faites des efforts.

Soit c'est moi, soit c'est vous . Peut être le problème aussi

Il faut pour chaque point trouver	=> Balayage de tous les points + un bord
tous les rectangles auxquels il contribue	=> Balayage (partiel) à partir de chaque point jusqu'à l'autre bord.

Bon courage

[unanonyme]

C'est peut être moi.


Quand je m'autorise à exécuter votre binaire,
ça fait la même chose que mes images de dessus,
mais en marche avant, il me semble.

Mais ça ne m'explique toujours pas votre
split de recherche en 2, ou très vaguement.

Il me semble que pour un point,
on commence toujours avec un rectangle dont la hauteur est égal à la hauteur de la surface,
la largeur est égale N.X - N-1.X en marche arrière, ou N+1.X-N.X en marche avant.

Ensuite pour chaque point rencontré, qu'on aille de l'avant ou en arrière,
si la valeur de N-2.Y (ou N+2.Y) est au dessus du point du départ, on réduit le top,
si la valeur est en dessous, on réduit le bottom,
si c'est égal, on peut s'arrêter, si c'est égal, on en aura un au dessus , un en dessous, ça split,
on continue jusqu'à rencontrer un bord vertical (selon la direction choisie).

En fait, il n'y a bien que pour le premier ou dernier point, selon la direction choisie,
et le cas particulier où le point directement précédent possède la même valeur Y
que la recherche doit être réalisée deux fois.

Edit : Il faudrait tout de même le doubler avec un scan vertical. C'est malheureux, mais facile à //iser, du coup.

[wiwaxia]

Bonsoir

@ Guesset: je viens de reprendre l'expression de la fonction booléenne TestL:

Code Pascal :

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

1
2
3
4
5
6
7
8
9
10
11
12
 FUNCTION TestL(K1, K2, L1, L2: Byte; VAR N_: Tab_V): Bool;
   VAR m: Byte; Test, Tx, Ty: Bool;
   BEGIN
     Test:= True; m:= 0;
     REPEAT
       Inc(m);
       Tx:= ((N_[K1].x<N_[m].x) AND (N_[m].x<N_[K2].x));
       Ty:= ((N_[L1].y<N_[m].y) AND (N_[m].y<N_[L2].y));
       IF (Tx AND Ty) THEN Test:= False
     UNTIL ((NOT Test) OR (m = Npoint));
     Result:= Test
   END;

Le délai d'inventaire des rectangles est tombé à 6 minutes ... Fantastique !
Je ne m'attendais pas à ce que le temps de calcul soit divisé par 6 !

@ aj3309

... Malgré tout cet algorithme me plait beaucoup et je voudrais réussir son implémentation en VBA.

Je m'en suis tenu à un algorithme de base ne contenant aucune restriction sur la forme ou les dimensions des rectangles.
Rien n'empêche a priori d'introduire dans la sélection des contraintes supplémentaires; en présence d'une vingtaine de points et compte tenu de la rapidité d'exécution de l'algorithme, cela ne devrait pas poser de problèmes.

[Guesset]

Quand je m'autorise à exécuter votre binaire, ça fait la même chose que mes images de dessus, mais en marche avant, il me semble.
Mais ça ne m'explique toujours pas votre split de recherche en 2, ou très vaguement...

1. Pour la bordure gauche puis chaque point (x,y) j'initialise un scan élémentaire : X devient alors Xo pour désigner l'abscisse de ce scan (la verticale rouge sur la démo).
2. Je n'ai qu'une marche avant. Lorsque je commence un scan à partir d'un point (xo,Yo), j'ai toute la hauteur Ytop = 0 et Ybtm = Ymax.
3. Au premier point (x,y) rencontré entre Ytop et Ybtm (n'importe lequel au début fera l'affaire), j'ai un rectangle (Xo, Ytop, X, Ybtm) dont je calcule la surface et l'enregistre si plus grand.
4. Ensuite je partage de part et d'autre du point rencontré : un couloir avec Ytop, Ybtm = Y, l'autre avec Ytop = Y, Ybtm. Ils sont moins hauts mais restent en visibilité de Xo sans obstacle.
5. Pour chaque couloir je réitère en 3.

J'utilise une procédure récursive qui permet de gérer élégamment les deux couloirs qui vont se fragmenter encore et encore. Comme chaque fragmentation évite les obstacles, dans chaque couloir, on est toujours en visibilité direct de la ligne de départ en Xo. On peut donc sans risque définir les rectangles par projection x vers Xo avec la largeur actuelle du couloir.
La profondeur de récursion est relativement faible. C'est au début qu'elle est la plus forte (pour Xo = 0, bord gauche) elle est en racine(W/H*n) pour 256 cela représente 16*racine(3/2) soit moins de 20 niveaux d'appels.
L'optimisation tue la plupart des bifurcations mais on peut encore les voir sur le premier scan (celui qui part du bord gauche et non d'un point) car il tue relativement peu d'embranchements. Sur ce point, la première version (voir post #23) est plus fruste mais colle mieux à cet algorithme.

Salut

[Guesset]

Bonsoir wiwaxia,

Je ne m'attendais pas à ce que le temps de calcul soit divisé par 6 !

A vrai dire moi non plus, j'aurais tablé sur un rapport 2 en supposant que la condition est satisfaite à mi parcours en moyenne.

Bonne nuit.

[unanonyme]

Bonjour,

En réfléchissant plus, en effet, j'arrive à imaginer des cas où on est obliger de passer par les deux branches à chaque fois.
ça m'ennuie profondément car cela génère un tas de déchets.

Sur la récursivité, il me semble qu'on peut arriver à l'éliminer en utilisant un triplet.
I, l'index du point en cours d'évaluation
J, le nombre d'étapes en avant / en arrière que l'on va parcourir.
L, le nombre d'étapes desquels on veut forcer le branchement alternatif, dans le parcours courant.

Dans une marche arrière, pour le point d'indice 5, on aura I= 5, Jmax=5, Lmax=5.
Du coup, on peut lister les étapes tels que
I=5, J=0, L=0
I=5, J=1, L=0
I=5, J=2, L=0 // pour tous les J 0 1 2, on prend toujours la branche "vers le haut"
...
I=5, J=0, L=0
I=5, J=1, L=1
I=5, J=2, L=1
I=5, J=2, L=2
I=5, J=3, L=1
I=5, J=3, L=2 // pour tous les J=0 et J=1, on prend la branche "vers le bas" puis vers "le haut".
I=5, J=3, L=3
...
I=5, J=5, L=5 // on branche en permanence vers le bas

avec ça on peut aller à n'importe qu'elle étape de la recherche avec un triplet de valeur, il me semble.

Il faudrait que je m'y colle plus sérieusement.

[Guesset]

Bonjour unanonyme,

...En réfléchissant plus, en effet, j'arrive à imaginer des cas où on est obligé de passer par les deux branches à chaque fois. Ca m'ennuie profondément car cela génère un tas de déchets.

Sur la récursivité, il me semble qu'on peut arriver à l'éliminer en utilisant un triplet.
I, l'index du point en cours d'évaluation
J, le nombre d'étapes en avant / en arrière que l'on va parcourir.
L, le nombre d'étapes desquels on veut forcer le branchement alternatif, dans le parcours courant.

Il est toujours possible d'éviter la récursivité. C'est même simple s'il n'y a qu'un seul auto-appel dans la fonction. L'exemple pathétique de la factorielle qui devient une simple boucle est un grand classique. C'est sensiblement plus difficile avec deux auto-appelsl dans la fonction. Sauf erreur, un seul triplet ne suffira pas, il va falloir mémoriser les états en attentes pendant qu'on progresse sur une branche pour pouvoir y revenir et attaquer l'autre branche. En résumé, on va recréer une gestion de pile au sein de la fonction.

Qu'est-ce qui te gène dans l'utilisation de la récursivité ? Hormis le fait qu'il faut faire attention à la profondeur d'auto-appels pour ne pas faire exploser la pile, il n'y a rien de sorcier. Je trouve l'obstacle suivant, je calcule la surface, l'enregistre si > Smaxi, puis sauf si je suis dans le mur, je recommence cette phrase pour la partie haute puis la partie basse. Le problème de profondeur jouera aussi dans le dimensionnent du tableau de mémorisation des états.

Mais peut-être utilises tu un langage qui ne permet pas la récursion ?

Salut

[unanonyme]

Mais peut-être utilises tu un langage qui ne permet pas la récursion ?

J'avoue ne pas en connaître. Après la TCO, il y a des langages qui aiment plus ou moins cela ^^
https://github.com/golang/go/issues/22624

J'ai finalement opté pour du JS, alors, la récursion, ça connaît.
C'est un peu la plaie de ce langage.
J'ai mis de côté GIO pour l'instant, ça me gonflait un peu par certains aspect,
et là ce n'est pas pour la perf du runtime que je code,
plutôt dans l'idée d'avoir une base de travail partageable,
donc compatible, facile à exécuter, facile à écrire (? ^^).

J'ai bien aimé ton exé mais pour reproduire des cas,
ou pour faire du pas-à-pas, ou juste étendre le code,
ces choses là ne semblait pas possible.

Maintenant que le problème m'a sérieusement titillé,
je me dit autant essayé de faire un truc pratique,
par ailleurs.

La récursion, en général, j'évite si je peux.
J'étais d'accord avec vous sur les globales dans un autre thread, sur ce point,
je suis un peu dogmatique. C'est comme les regexp, si je peux j'évite.

il va falloir mémoriser les états en attentes

Oui, ça m'a traversé l'esprit aussi. Mais je n'arrives pas déjà à voir si loin.

[Guesset]

J'ai bien aimé ton exé mais pour reproduire des cas, ou pour faire du pas-à-pas, ou juste étendre le code, ces choses là ne semblait pas possible.

Il est possible de charger des listes de points en CSV valeur_x;valeur_y ligne suivante etc. Il suffit donc de taper ou récupérer deux colonnes (x et y) sous un tableur et de faire un export CSV en définissant le séparateur ";". Les valeurs doivent être des entiers dans la plage 0 à 1199 en x et 0 à 799 en y. Ce n'est peut être pas très pratique mais c'est un PoC.

Pour mieux voir la démo, il est possible de la ralentir en gardant la touche CTRL appuyée : on passe d'une étape toutes les 0.2 s à une étape par seconde. Mais je n'ai pas fait un pas à pas.

Salut