Discussion :

[wiwaxia]

Bonsoir,

@Guesset

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

En y réfléchissant, les rectangles contiennent généralement non pas un seul point, mais beaucoup plus - jusqu'à (N - 4); la sortie de boucle se produit donc beaucoup plus tôt.

@ aj3309

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

Une petite restriction supplémentaire permet de faire apparaître des rectangles plus larges, si on le souhaite:

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
23
24
25
26
27
28
29
 PROCEDURE Enumeration(VAR N_: Tab_V; VAR W_1, W_2: Ve_2E; VAR S_m: Z_32);
   CONST C1 = 4; C2 = C1 + 10; L1 = 38; o = 4;
   VAR I1, I2, J1, J2: Byte; Dx, Dy, Smax, Sxy, Xlim: Z_32;
       W1, W2: Ve_2E; Test: Bool;
   BEGIN
     Smax:= 0; E(0014); Wt(C1, L1, '(I1, J1) = ');
     FOR I1:= 0 TO Np1 DO
       FOR I2:= 0 TO Np1 DO
         IF (N_[I2].x>N_[I1].x) THEN
           BEGIN
             We(C2, L1, I1, o); Write(I2:o);
             Dx:= N_[I2].x - N_[I1].x;
             FOR J1:= 0 TO Np1 DO
               FOR J2:= 0 TO Np1 DO
                 IF (N_[J2].y>N_[J1].y) THEN
                   BEGIN
                     Test:= TestL(I1, I2, J1, J2, Nuage);
                     Dy:= N_[J2].y - N_[J1].y;
                     Sxy:= Dx * Dy; Xlim:= Round(3.5 * Dy);
                     IF (Test AND ((Smax<Sxy) AND (Dx>Xlim))) THEN
                       BEGIN
                         Smax:= Sxy;
                         W1.x:= N_[I1].x; W1.y:= N_[J1].y;
                         W2.x:= N_[I2].x; W2.y:= N_[J2].y
                       END
                   END
           END;
     W_1:= W1; W_2:= W2; S_m:= Smax
   END;

Voici ce que l'on obtient dans le même nuage de points, dans le cas de rapports limites Rxy = ∆x/∆y respectivement égaux à 1.5 , 2.5 et 3.5:

Salut

[Guesset]

Bonsoir,

@ aj3309
Une petite restriction supplémentaire permet de faire apparaître des rectangles plus larges, si on le souhaite:

Code :

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

1
2
3
4
5
6
7
...
IF (N_[J2].y>N_[J1].y) THEN BEGIN
   Test:= TestL(I1, I2, J1, J2, Nuage);
   Dy:= N_[J2].y - N_[J1].y;
   Sxy:= Dx * Dy; Xlim:= Round(3.5 * Dy);
   IF (Test AND ((Smax<Sxy) AND (Dx>Xlim))) THEN
   ...

Je vois que nous avons fait la même erreur sur les contraintes. En ne vérifiant que le ratio et en rejetant si non satisfait, on ne s'assure pas que le rectangle retaillé pourrait rester un bon prétendant. Imaginons un grand rectangle dX = 3*dY. Il va être rejeté car dX < 3.5*dY, mais qui dit que la surface avec dY réduit à Dx/3.5 ne donnerait pas S := dX²/3.5 > Smax ? Heureusement, la faible probabilité de ce cas limite la portée de l'erreur...

Bon, j'ai résolu élégamment le problème puisque je suis revenu au problème de base sans contrainte hors dYmin (qui pourrait être mis à 0).

Salut

[wiwaxia]

Bonjour Guesset,

Je vois que nous avons fait la même erreur sur les contraintes. En ne vérifiant que le ratio et en rejetant si non satisfait, on ne s'assure pas que le rectangle retaillé pourrait rester un bon prétendant. Imaginons un grand rectangle dX = 3*dY. Il va être rejeté car dX < 3.5*dY, mais qui dit que la surface avec dY réduit à Dx/3.5 ne donnerait pas S := dX²/3.5 > Smax ? ...

Là, je ne vois pas où se trouverait une erreur.
Cette version du programme sélectionne parmi tous les rectangles de dimensions positives, celui d'aire maximale et suffisamment large, c'et à dire dont la largeur dépasse un seuil arbitraire proportionnel à sa hauteur:

∆x > Rxy * ∆y ,

avec pour les exemples choisis Rxy = 1.5 , 2.5 ou 3.5 .
Peut-être avons-nous une interprétation différente du projet initial ? Le retaillage d'un rectangle me paraît en contradiction avec la recherche effectuée.

Salut.

[unanonyme]

Bonjour,

Mais je n'ai pas fait un pas à pas.

Je ne sais pas quelle solution vous avez implémenté,
au moins pour un pas-a-pas qui va de l'avant,
on peut faire un appel de fonction bloquant lorsque la résolution avance.
Il faudrait l'insérer au milieu du code de résolution.

La fonction bloquerait, selon ce qu'on veut faire,
- tant que 0.2 ne s'est pas écoulé
- tant qu'une touche de clavier particulière n'est pas pressée
- ne rien faire, pour juste poursuivre rapidement la résolution

Ce n'est peut être pas très pratique mais c'est un PoC.

Comme je le disais, j'ai bien aimé le POC.

C'est juste qu'à y réfléchir, on veut soit générer des points au hasard, soit les placer manuellement sur la surface.
Pouvoir exporter ces points (dans le presse papier ?), et inversement, les importer (déjà implémenté) (depuis le presse papier ?).

Mais le POC est bien.

[Guesset]

Bonjour wiwaxia,

...Là, je ne vois pas où se trouverait une erreur. Cette version du programme sélectionne parmi tous les rectangles de dimensions positives, celui d'aire maximale et suffisamment large, c'et à dire dont la largeur dépasse un seuil arbitraire proportionnel à sa hauteur...

Mais dans ce rectangle qui n'a pas la bonne largeur/hauteur, il existe un rectangle qui a le bon ratio (il suffit de diminuer la hauteur). Et peut être, même si c'est peu probable, ce rectangle a une surface supérieure au Smax. Si on ne le vérifie pas, on ne peut en être sûr. Le code suivant devrait le faire (comme les multiplications et divisions prennent du temps, j'ai remonté les effets de TestL avant de faire ces calculs) :

Code Pascal :

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

1
2
3
4
5
6
7
8
9
10
11
12
IF N_[J2].y > N_[J1].y THEN BEGIN
   IF TestL(I1, I2, J1, J2, Nuage) THEN BEGIN
      Dy := N_[J2].y - N_[J1].y;
      Dy := min(Dy, Round(Dx/3.5); // ou Dy := min(Dy, (Dx+Dx) div 7);
      Sxy:= Dx * Dy; 
      IF Smax < Sxy THEN BEGIN
         Smax:= Sxy;
         W1.x:= N_[I1].x; W1.y:= N_[J1].y;
         W2.x:= N_[I2].x; W2.y:= N_[J2].y
      END
   END
END

On pourrait discuter l'arrondi de la division mais c'est l'esprit.

Quel est le compilateur utilisé ? S'il avait des exit, break et continue, le code pourrait éviter nombre d'indentations (c'est égoïste parce je m'y perds )

Salut

[Guesset]

Bonjour unanonyme,

...C'est juste qu'à y réfléchir, on veut soit générer des points au hasard, soit les placer manuellement sur la surface.
Pouvoir exporter ces points (dans le presse papier ?), et inversement, les importer (déjà implémenté) (depuis le presse papier ?).

Un PoC n'est pas une application mais seulement un moyen de prouver qu'une idée est bonne (ou mauvaise). J'ai déjà fait une entorse en lui greffant un mode Démo censé aider les gens à comprendre l'algorithme.

Bien sûr, je pourrais y ajouter maintes fonctionnalités. Mais pour moi le PoC a fait son job. J'ai seulement repoussé les limites à 512 points pour voir et il résout toujours le problème en 0 ms. La preuve de concept (en anglais Proof of Concept ou PoC) est donc faite.

Désolé

[wiwaxia]

Bonjour Guesset,

... Mais dans ce rectangle qui n'a pas la bonne largeur/hauteur, il existe un rectangle qui a le bon ratio (il suffit de diminuer la hauteur). Et peut être, même si c'est peu probable, ce rectangle a une surface supérieure au Smax. Si on ne le vérifie pas, on ne peut en être sûr. Le code suivant devrait le faire (comme les multiplications et divisions prennent du temps, j'ai remonté les effets de TestL avant de faire ces calculs) :

Code Pascal :

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

1
2
3
4
5
6
7
8
9
10
11
12
IF N_[J2].y > N_[J1].y THEN BEGIN
   IF TestL(I1, I2, J1, J2, Nuage) THEN BEGIN
      Dy := N_[J2].y - N_[J1].y;
      Dy := min(Dy, Round(Dx/3.5); // ou Dy := min(Dy, (Dx+Dx) div 7);
      Sxy:= Dx * Dy; 
      IF Smax < Sxy THEN BEGIN
         Smax:= Sxy;
         W1.x:= N_[I1].x; W1.y:= N_[J1].y;
         W2.x:= N_[I2].x; W2.y:= N_[J2].y
      END
   END
END

Quel est le compilateur utilisé ? S'il avait des exit, break et continue, le code pourrait éviter nombre d'indentations (c'est égoïste parce je m'y perds ) ...

Virtual Pascal, comme d'habitude - je n'ai d'ailleurs pas le choix, pour des raisons techniques.

J'aurais écrit le bloc d'instructions affiché comme suit:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
 IF N_[J2].y > N_[J1].y THEN 
   IF TestL(I1, I2, J1, J2, Nuage) THEN 
     BEGIN
       Dy := N_[J2].y - N_[J1].y;
       Dy := min(Dy, Round(Dx/3.5); // ou Dy := min(Dy, (Dx+Dx) div 7);
       Sxy:= Dx * Dy; 
       IF Smax < Sxy THEN 
	 BEGIN
           Smax:= Sxy;
           W1.x:= N_[I1].x; W1.y:= N_[J1].y;
           W2.x:= N_[I2].x; W2.y:= N_[J2].y
         END
     END;

les deux paires <IF ... THEN> du début pouvant être remplacées par une seule à l'aide de l'opérateur AND.
Il ne m'est pas venu à l'esprit de raboter les rectangles trop hauts - pourquoi pas ? De même, les éventuelles dérives dues à l'intervention d'un arrondi m'ont paru négligeables dans la mesure où le texte affiché figurera dans un domaine plus étroit, concentrique au rectangle choisi.

Préoccupé par la finalisation du programme et compte tenu du petit nombre de points, j'ai laissé de côté la présence de la division (Round(Dx/3.5)); je l'évite habituellement par le recours à un facteur décimal (Round(0.285714*Dx)) - ce n'est peut-être pas la solution optimale.

Salut.

[aj3309]

Bonjour Guesset,
Après une petite pause pour éviter la saturation et le découragement je reprends l'implémentation de ton algorithme,
En effet les quelques utilisateurs auxquels j'ai montré le projet préfèreraient tous (pourquoi pas c'est pas eux qui paient) que le rectangle infos ne cache aucun point.
Alors voila ou j'en suis.
Dans ton algorithme tu écris :
Tant que i < PosNb faire
Quitter la boucle si (Pos(i).Y > Ytop) et (Pos(i).Y < Ybtm)
i = i+1
Fin-boucle
Si on rentre dans la boucle avec i = PosNb - 1, en sortie de boucle on va avoir au pire i = PosNb - 1 +1 = PosNB
et Pos(i) ne va pas poser de problèmes.
Par contre pour moi en essayant d'appliquer tes recommandations cela donne
Tant que i < PosNb+2 faire
Quitter la boucle si (Pos(i+2).Y > Ytop) et (Pos(i+2).Y < Ybtm)
i = i+1
Fin-boucle
Si on rentre dans la boucle avec i = PosNb+2 - 1 = PosNb+ 1, en sortie de boucle on va avoir au pire i = PosNb + 1 +1 = PosNB + 2
et Pos(i+2) va pas poser problèmes (indice en dehors du tableau).
Voila ou je bloque car je n'arrive pas à faire abstraction de ce que tu as dit ou j'ai mal compris ce que tu as dit.

[Guesset]

...Si on rentre dans la boucle avec i = PosNb+2 - 1 = PosNb+ 1, en sortie de boucle on va avoir au pire i = PosNb + 1 +1 = PosNB + 2
et Pos(i+2) va pas poser problèmes (indice en dehors du tableau).
Voila ou je bloque car je n'arrive pas à faire abstraction de ce que tu as dit ou j'ai mal compris ce que tu as dit.

Ton tableau part de 1 jusqu'à PosNb+2 ce qui fait PosNb + 2 éléments comme celui d'origine qui va de -1 à PosNb soit -1, 0, 1 à PosNb donc PosNb+2 éléments également. Ton tableau doit donc être dimensionné pour accueillir au moins ces PosNb+2 éléments sinon problème .
Dans mon cas je l'ai dimensionné à 258 éléments (-1 à 256) puis à 514 éléments (-1 à 512) pour pouvoir augmenter PosNb jusqu'à 256 puis 512 points.

Pour simplifier, j'ai fait un petit tableau de correspondance :

Pour éviter de s'emmêler, il est aussi possible de faire une fonction GetPos(i) qui retourne Pos(i+2), et une procédure Set(i, Point) qui fait Pos[i+2] = Point. Ou par axe : GetPosX(i) qui retourne Pos(i+2).X, GetPosY(i) qui retourne Pos(i+2).Y, SetPosX(i, X) qui fait Pos[i+2].X = X, SetPosY(i, Y) qui fait Pos[i+2].Y = Y. Comme ça il est possible d'appliquer l'algorithme tel qu'écrit en remplaçant l'utilisation du tableau par ces fonctions sans se soucier des conversion d'indices.

Salut et bon courage

[Guesset]

Bonjour,

A la demande unanime, en fait je voulais dire unanonyme, j'ai finalement greffé une fonction de création manuelle à la volée Big_rect 6.zip:

• sélection de point, le plus proche du curseur, par un Clic souris
• déplacement de point directement à la souris sur l'écran (bouton gauche souris maintenu).
• ajout de point par un Shift + Clic souris sur l'écran
• suppression de point par un Ctrl + Clic souris ou du point sélectionné par la touche Suppr (il faut laisser au moins 2 points)

Si un plus grand rectangle a déjà été calculé, il est actualisé à chaque modification.

En outre le maximum est porté à 512 (mais l'affichage des n° s'arrête dès qu'on dépasse 256 points)

Salutations

[unanonyme]

Bonjour Guesset,

Je n'en demandais pas tant, mais c'est super

De mon côté j'ai avancé sur la version sans récursion.
C'est.... différent de ce que j'avais perçu initialement.
ça oblige à repasser plusieurs fois dans le même chemin,
produisant plusieurs fois les mêmes résultats, avant de commencer à bancher différemment.
Du coup, ça me plaît pas trop, en fait.

Sur 4 points, tels que

Code :

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

1
2
3
4
5
6
points := []Point{
		{25, 20},
		{5, 25},
		{40, 5},
		{45, 35},
	}

ça génère 61 résultats, doublons inclut.

Sans déjà donné d'algo de démo, ça fait trois boucles imbriquées + 1 tri initial tel que

Code :

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

1
2
3
4
5
6
7
// sort x, y
for i := 0; i < len(points); i++ {
	for l := i; l < len(points); l++ {
		for j := i; j < len(points); j++ {
		}
	}
}

Il n'y a pas de tests additionnel de contenance comme dans la méthode proposée par wiwaxia,
juste un déplacement des bords du rectangle.

Comme je n'ai pas déjà écrit votre méthode récursive, je ne sais pas comparer.
Et puis il faudrait que je le teste sur plus de points.

Bonne journée.

[Guesset]

Bonjour unanonyme,

...Sur 4 points, tels que

Code :

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

points := []Point{ {25, 20}, {5, 25}, {40, 5}, {45, 35} }

ça génère 61 résultats, doublons inclut. Sans déjà donné d'algo de démo, ça fait trois boucles imbriquées + 1 tri initial tel que :

Code :

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

1
2
3
4
5
6
7
// sort x, y
for i := 0; i < len(points); i++ {
	for l := i; l < len(points); l++ {
		for j := i; j < len(points); j++ {
		}
	}
}

...

Je ne comprends pas trop les trois boucles. La récursion simulée ne devrait en avoir que 2 me semble-t-il.

Avec les mêmes valeurs (très rassemblées dans le coin supérieur gauche) la version de base devrait avoir au plus (4+1)² = 25 itérations, la version optimisée n'a que 14 itérations (mais son avantage est surtout de ne pas être quadratique).

Les 2 sont loin de 61 d'autant que cet algorithme doit être d'ordre 3 ce qui signifie que passer de 4 à 20 induirait de l'ordre de 7600 itérations. Cela reste gérable mais augmentera très rapidement.

L'algorithme de base (qui a aussi des rectangles inutiles) a, au pire, 21² = 441 itérations pour 20 points (les alignements de points et dYmin > 0 peuvent en supprimer) tandis que l'algorithme optimisé a moins de 100 itérations en moyenne pour 20 points.

Salut

[aj3309]

Bonsoir Guesset,
Encore une fois merci pour ton aide.Une partie de mes problèmes provenaient de la persistance des données entre les appels de procédure..
Pour que cela marche je suis obligé de faire Sovj = j et de faire l'appel avec Sovj et non j.
De même j'ai été amené à faire i = iSup pour le canal supérieur et I = iInf pour le canal inférieur.
J'ai implémenté GetPos et SetPos.Je parcoure bien les deux canaux mais je ne trouve pas encore tous les rectangles (13 sur 16)




i = 1 Tabpos(i).X = 0 Tabpos(i).Y = 451
i = 2 Tabpos(i).X = 75 Tabpos(i).Y = 410
i = 3 Tabpos(i).X = 699 Tabpos(i).Y = 37
i = 4 Tabpos(i).X = 827 Tabpos(i).Y = 306
i = 5 Tabpos(i).X = 899 Tabpos(i).Y = 451

LeftCarte = 0 LargeurCarte = 900 TopCarte = 0 HauteurCarte = 452

iRect = 1 Largeur = 75 Hauteur = 451 X = 0 Y = 0
iRect = 2 Largeur = 699 Hauteur = 410 X = 0 Y = 0
iRect = 3 Largeur = 899 Hauteur = 37 X = 0 Y = 0
iRect = 4 Largeur = 899 Hauteur = 41 X = 0 Y = 410
iRect = 5 Largeur = 624 Hauteur = 451 X = 75 Y = 0
iRect = 6 Largeur = 824 Hauteur = 37 X = 75 Y = 0
iRect = 7 Largeur = 752 Hauteur = 414 X = 75 Y = 37
iRect = 8 Largeur = 824 Hauteur = 269 X = 75 Y = 37
iRect = 9 Largeur = 824 Hauteur = 145 X = 75 Y = 306
iRect = 10 Largeur = 128 Hauteur = 451 X = 699 Y = 0
iRect = 11 Largeur = 200 Hauteur = 306 X = 699 Y = 0
iRect = 12 Largeur = 200 Hauteur = 145 X = 699 Y = 306
iRect = 13 Largeur = 72 Hauteur = 451 X = 827 Y = 0

J'ai bien les 4 rectangles pleine hauteur 1 5 10 13
Je n'ai que 2 rectangles pleine largeur 3 et 4 il m'en manque 2
Au total je n'ai que 13 rectangles il m'en manque 4x4 -13 soit 3 rectangles dont deux pleine largeur.

Je prépare une version de mon code expurgée de tous les debug.print pour que cela soit lisible puis je la publierai car ce n'est pas long.

[Guesset]

...J'ai implémenté GetPos et SetPos.Je parcoure bien les deux canaux mais je ne trouve pas encore tous les rectangles (13 sur 16)

Je t'ai fait un pdf qui détaille trois des quatre phases (la dernière se réduit à un seul élement qui existe sur ton image).

Si c'est possible, je limiterais l'affichage des rectangles à ceux d'une phase. Au moment de lancer une phase, il est possible de valider un booléen, par exemple ShowScan, seulement si le numéro du scan est égal à celui qu'on veux voir et ce booléen servirait pour décider de dessiner tel ou tel rectangle. Cela devrait permettre de mieux voir ce qui manque (en regardant le pdf si je n'ai pas fait d'erreurs).

J'ai mis en pointillés ceux qui me posent question dont 2 avec un smiley grimaçant car ils sont effectivement absents. Si le dernier qui manque est également en bas, cela pourrait inciter à penser qu'on sort un peu trop tôt du scan en cours ( un< au lieu d'un <= ou l'inverse, une borne trop petite d'une unité...).

Salut

[unanonyme]

Bonjour,

Oui là je l'avais fait sans récursion, et sans liste de rectangles (pseudo récursion).
D'où le nombre de résultats foisonnant.

Avec une liste de rectangles, le problème qui se pose c'est d'accumuler des résultats utile.

très rassemblées dans le coin supérieur gauche

comme dans



?

C'est un cas particulier ça.
Dans le sort, si on récupère minLeft, maxRight, minBtm, MaxTop,
on sait dire que maxRight < surfaceWidth-maxRight,
donc on aura nécessairement un grand rectangle sur la droite, ou en bas.

La cas plus "difficile" à optimiser, il me semble, c'est


Bonne journée

[aj3309]

Bonsoir Guesset,

Comme j'affiche les rectangle , à la demande après les avoir calculés ,
lors de l'enregistrement d'un rectangle j'ai rajouté le rang du scan de création.
Ainsi en affichant et analysant les rectangles scan par scan, j'ai pu constaté que les 13 rectangles trouvés sont bien vides.
Les 3 rectangles qui manquent le sont dans le premier scan.
0,37 899 272
0,37 825 377
0,309 899 105

Voici les coordonnées des 4 rectangles trouvé lors du premier scan
1 Scan = 1 j = -1 i = 0 L = 75 H = 451 X = 0 Y = 0
2 Scan = 1 j = -1 i = 1 L = 697 H = 414 X = 0 Y = 0
3 Scan = 1 j = -1 i = 3 L = 899 H = 37 X = 0 Y = 0
4 Scan = 1 j = -1 i = 3 L = 899 H = 37 X = 0 Y = 414

Ci-dessous une trace limitée au premier scan
-------- Lancement Scan numéro 1 X0 = 0 j = -1 ----------------

Début RechercheSuivant i = -1 Ybtm = 451 Ytop = 0 HauteurSecteur = 451 j = -1 ---
Début boucle Do While i < NbrePoints i = 0 Ytop = 0 Ybtm = 451 GetPosY(i) = 410 Scan = 1
Exit do car (GetPosY(i) > Ytop) And (GetPosY(i) < Ybtm)
--- Rectangle = 1 Scan = 1 X = 0 Y = 0 Largeur = 75 Hauteur = 451 i = 0 j = -1
On passe aux 2 étapes suivantes car i = 0 NbrePoints = 3 Scan numéro 1
On va traiter le canal supérieur entre Ytop et GetPosY(iSup) iSup = 0 Ytop = 0 GetPosY(iSup) = 410

Début RechercheSuivant i = 0 Ybtm = 410 Ytop = 0 HauteurSecteur = 410 j = -1 ---
Début boucle Do While i < NbrePoints i = 1 Ytop = 0 Ybtm = 410 GetPosY(i) = 37 Scan = 1
Exit do car (GetPosY(i) > Ytop) And (GetPosY(i) < Ybtm)
--- Rectangle = 2 Scan = 1 X = 0 Y = 0 Largeur = 699 Hauteur = 410 i = 1 j = -1
On passe aux 2 étapes suivantes car i = 1 NbrePoints = 3 Scan numéro 1
On va traiter le canal supérieur entre Ytop et GetPosY(iSup) iSup = 1 Ytop = 0 GetPosY(iSup) = 37

Début RechercheSuivant i = 1 Ybtm = 37 Ytop = 0 HauteurSecteur = 37 j = -1 ---
Début boucle Do While i < NbrePoints i = 2 Ytop = 0 Ybtm = 37 GetPosY(i) = 306 Scan = 1
Do While i < NbrePoints on fait i = i + 1 pour passer au point suivant i = 3
Fin d'itération Do While i < NbrePoints i = 3
--- Rectangle = 3 Scan = 1 X = 0 Y = 0 Largeur = 899 Hauteur = 37 i = 3 j = -1
On ne passe aux 2 étapes suivantes car i = 3 NbrePoints = 3 Scan numéro 1
On va traiter le canal inférieur entre GetPosY(iInf) et Ybtm iInf = 3 Ytop = 0 GetPosY(iInf) = 451

Début RechercheSuivant i = 3 Ybtm = 410 Ytop = 451 HauteurSecteur = -41 j = -1 ---
On sort de RechercheSuivant car i >= NbrePoints i = 3 NbrePoints = 3
On va traiter le canal inférieur entre GetPosY(iInf) et Ybtm iInf = 0 Ytop = 0 GetPosY(iInf) = 410

Début RechercheSuivant i = 0 Ybtm = 451 Ytop = 410 HauteurSecteur = 41 j = -1 ---
Début boucle Do While i < NbrePoints i = 1 Ytop = 410 Ybtm = 451 GetPosY(i) = 37 Scan = 1
Do While i < NbrePoints on fait i = i + 1 pour passer au point suivant i = 2
Fin d'itération Do While i < NbrePoints i = 2
Début boucle Do While i < NbrePoints i = 2 Ytop = 410 Ybtm = 451 GetPosY(i) = 306 Scan = 1
Do While i < NbrePoints on fait i = i + 1 pour passer au point suivant i = 3
Fin d'itération Do While i < NbrePoints i = 3
--- Rectangle = 4 Scan = 1 X = 0 Y = 410 Largeur = 899 Hauteur = 41 i = 3 j = -1
On ne passe aux 2 étapes suivantes car i = 3 NbrePoints = 3 Scan numéro 1

-------- Lancement Scan numéro 2 X0 = 75 j = 0 ----------------

[Guesset]

Bonsoir aj3309,

Les 3 rectangles qui manquent le sont dans le premier scan.
0, 37 899 272
0, 37 825 377
0, 309 899 105
Voici les coordonnées des 4 rectangles trouvé lors du premier scan
1 Scan = 1 j = -1 i = 0 L = 75 H = 451 X = 0 Y = 0
2 Scan = 1 j = -1 i = 1 L = 697 H = 414 X = 0 Y = 0
3 Scan = 1 j = -1 i = 3 L = 899 H = 37 X = 0 Y = 0
4 Scan = 1 j = -1 i = 3 L = 899 H = 37 X = 0 Y = 414

Analyse

Manifestement, le retour sur l'étape précédente pour traiter le canal inférieur ne fonctionne pas.

Quand il arrive à 3 (bord droit) il devrait revenir à l'étape précédente et faire RechercheSuivant(i = 1, Ytop = 37, Ybtm = 410). Or il réessaie une recherche à partir de i=3 (ce n'est pas grave mais comment aller plus à droite quand on est déjà sur le bord droit ?) puis revient pour traiter RechercheSuivant(i = 0, Ytop = 451, Ybtm = 410) soit le canal inférieur de la toute première étape (i=-1).

Il a oublié de traiter le cas RechercheSuivant(i = 1, Ytop = 37, Ybtm = 410). Donc il ne voit jamais le point 2 d'où les 3 rectangles qui manquent.

Proposition

Sans savoir comment cela est implémenté, les variables iInf et iSup m'inquiètent beaucoup. L'algorithme n'utilise que i.

Les arguments (i, Ytop, Ybtm) de la fonction récursive sont empilés. Quand la fonction s'appelle elle même deux fois, les valeurs (i, Ytop, Ybtm) existent en trois exemplaires dans la pile, dans notre cas (0, 0, 451), (1, 0, 410), (3, 0, 37) juste avant les auto-appels. Quand le programme revient de la dernière étape, elle est retirée de la pile et il retrouve (1, 0, 410) en tête de pile. Il peut donc allègrement traiter son canal inférieur. Il n'est pas sûr que les nouvelles variables se comportent de même, auquel cas leurs valeurs évoluent sauvagement s'il n'y a pas étanchéité entre les étapes.

Je conseillerais donc de retirer ces variables iInf et iSup et revenir à i seul.

Salut

[aj3309]

Bonjour Guesset,
Encore une fois merci pour ton aide, grace a toi j'ai un algorithme qui marche.
En fait depuis le début je faisais une erreur de débutant , je ne me rappelais plus qu'en VBA les appels de procédure se faisaient par défaut en mode ByRef.
Après avoir mis tous mes appels ByVal tout est rentré dans l'ordre.
Je vais progressivement augmenter mon jeu d'essai mais tout n'est pas gagné.



iRect = 1 Scan = 1 j = -1 i = 0 L = 75 H = 451 X = 0 Y = 0
iRect = 2 Scan = 1 j = -1 i = 1 L = 697 H = 414 X = 0 Y = 0
iRect = 3 Scan = 1 j = -1 i = 3 L = 899 H = 37 X = 0 Y = 0
iRect = 4 Scan = 1 j = -1 i = 2 L = 825 H = 377 X = 0 Y = 37
iRect = 5 Scan = 1 j = -1 i = 3 L = 899 H = 272 X = 0 Y = 37
iRect = 6 Scan = 1 j = -1 i = 3 L = 899 H = 105 X = 0 Y = 309
iRect = 7 Scan = 1 j = -1 i = 3 L = 899 H = 37 X = 0 Y = 414
iRect = 8 Scan = 2 j = 0 i = 1 L = 622 H = 451 X = 75 Y = 0
iRect = 9 Scan = 2 j = 0 i = 3 L = 824 H = 37 X = 75 Y = 0
iRect = 10 Scan = 2 j = 0 i = 2 L = 750 H = 414 X = 75 Y = 37
iRect = 11 Scan = 2 j = 0 i = 3 L = 824 H = 272 X = 75 Y = 37
iRect = 12 Scan = 2 j = 0 i = 3 L = 824 H = 142 X = 75 Y = 309
iRect = 13 Scan = 3 j = 1 i = 2 L = 128 H = 451 X = 697 Y = 0
iRect = 14 Scan = 3 j = 1 i = 3 L = 202 H = 309 X = 697 Y = 0
iRect = 15 Scan = 3 j = 1 i = 3 L = 202 H = 142 X = 697 Y = 309
iRect = 16 Scan = 4 j = 2 i = 3 L = 74 H = 451 X = 825 Y = 0

[Guesset]

Bonjour aj3309,

...j'ai un algorithme qui marche...

Félicitations

Salut

[aj3309]

Bonsoir Guesset,
C'est toi qui mérite ces félicitations, en effet c'est bien toi qui a trouvé un algorithme simple pour trouver les rectangles vides dans un nuage de point.
Ton idée de cheminer a travers les 2 canaux déterminés par la rencontre d'un obstacle était vraiment la bonne.
Pour ma part je vais faire une pause sans ordi à l'occasion d'un séjour randonnée raquettes avant de reprendre pour faire tourner le jeu d'essai réel.