1 pièce(s) jointe(s)
Rectangle maximum dans un nuage de points
Bonsoir,
@Guesset
Citation:
Envoyé par
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
Citation:
Envoyé par
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:
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
Rectangle maximum dans un nuage de points
Bonjour Guesset, :D
Citation:
Envoyé par
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.
Rectangle maximum dans un nuage de points
Bonjour Guesset, :D
Citation:
Envoyé par
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:
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 :oops:) ...
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:
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.
Félicitations pour Guesset
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.
