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.
2 pièce(s) jointe(s)
L'algorithme rectangles vides dans un nage de point fonctionne Bravo Guesset
Bonjour,
J'ai poursuivi mes tests en augmentant progressivement le nombre de points.
Pour donner une chance à l'algorithme de trouver tous les rectangles théoriques, sans avoir des canaux trop fins occultant un certains nombre de rectangles,
j'ai modifié quelques ordonées et mis la hauteur mini à un.
Finalement de 3 à 16 points j'ai pu trouver que mon implémentation de l'algorithme trouvait bien l'ensemble de rectangles théoriqiques.
Avec 16 points et divers valeurs de Hauteur mini cela donne
Points = 16 Scans = 17 Théoriques = 289 Trouvés = 141 TropFin = 90 AppelsTot = 231 TrouvésNon retenus = 107 Retenus = 34 AppelsSup = 107 AppelsInf = 107 ApresDernierPoint = 0
Points = 16 Scans = 17 Théoriques = 289 Trouvés = 279 TropFin = 10 AppelsTot = 289 TrouvésNon retenus = 0 Retenus = 279 AppelsSup = 136 AppelsInf = 136 ApresDernierPoint = 0
Points = 16 Scans = 17 Théoriques = 289 Trouvés = 289 TropFin = 0 AppelsTot = 289 TrouvésNon retenus = 0 Retenus = 289 AppelsSup = 136 AppelsInf = 136 ApresDernierPoint = 0
Pour choisir le rectangla associé à chaque point, j'ai d'abord fait une homtétie sur les rectangles retenus pour les ramener à la dimnsion cible et ensuite j'ai choisi le rectangle dont le centre était le plus près du point.
Avec cette méthode plusieurs points partagent le mêm rectangle.
Point = 1 X = 75 Y = 422 Rectangle choisi = 8 Xri = 180 Yri = 337
Point = 2 X = 512 Y = 322 Rectangle choisi = 18 Xri = 286 Yri = 251
Point = 3 X = 542 Y = 251 Rectangle choisi = 17 Xri = 372 Yri = 98
Point = 4 X = 591 Y = 400 Rectangle choisi = 22 Xri = 372 Yri = 417
Point = 5 X = 601 Y = 235 Rectangle choisi = 23 Xri = 590 Yri = 98
Point = 6 X = 614 Y = 250 Rectangle choisi = 23 Xri = 590 Yri = 98
Point = 7 X = 639 Y = 359 Rectangle choisi = 24 Xri = 590 Yri = 417
Point = 8 X = 687 Y = 375 Rectangle choisi = 24 Xri = 590 Yri = 417
Point = 9 X = 691 Y = 222 Rectangle choisi = 23 Xri = 590 Yri = 98
Point = 10 X = 697 Y = 45 Rectangle choisi = 23 Xri = 590 Yri = 98
Point = 11 X = 709 Y = 505 Rectangle choisi = 24 Xri = 590 Yri = 417
Point = 12 X = 724 Y = 358 Rectangle choisi = 28 Xri = 630 Yri = 415
Point = 13 X = 728 Y = 292 Rectangle choisi = 28 Xri = 630 Yri = 415
Point = 14 X = 754 Y = 381 Rectangle choisi = 32 Xri = 641 Yri = 415
Point = 15 X = 763 Y = 395 Rectangle choisi = 34 Xri = 654 Yri = 415
Point = 16 X = 825 Y = 317 Rectangle choisi = 34 Xri = 654 Yri = 415
Pièce jointe 651234
Pièce jointe 651235
Encore une fois merci à Guesset qui m'a trouvé l'algorithme que je cherchais et qui fonctionne
Avant de clore ce sujet le vais poursuivre quelques tests avec 20 points.
