Discussion :

[Guesset]

Bonjour tbc92,

Les remarques sur l'aspect optimisation sont pertinentes, mais je pense qu'elles viennent perturber le message.
Le 1er objectif, c'est d'avoir un truc qui marche.
Même s'il met 2 minutes par carte, alors qu'un truc optimisé mettrait 10 fois moins, aj3309 sera très satisfait.
En s'attaquant à l'optimisation, en s'attaquant à ces fonctions getStrXY (qui certes piquent les yeux), on s'éloigne de l'objectif.

C'est vrai que je suis un peu jusqu'au-boutiste avec les conversions qui de plus ne doivent avoir lieu qu'une fois par actualisation de carte . Mais mettre le focus sur ma réponse à un élément abordé par le PO lui-même oublie la construction et la démonstration d'un algorithme qui répond à l'objectif (initial) posé.

Un utilisateur face à un écran considère que l'application répond correctement en dessous de 3 s et que c'est trop lent au-delà de 5 s. Une réponse de 2 mn demanderait un gain de 40x pour devenir acceptable ce qui ne sera pas atteignable par un coup de rabot magique mais demandera un travail pénible de reconception (c'est très désagréable de devoir reprendre quelque chose qui fait le travail mais ne peut être utilisé). Je ne vois pas qui s'en satisferait.

Salut

[aj3309]

Bonjour,
Moi je suis de la vieille école.Pour tous les travaux sans interaction avec un utilisateur il y a les travaux batch qu'on lance le soir et le lendemain on va au résultat
Ensuite il y a les travaux temps réel pour tout processus ou il y a interaction avec ll'utilisateur.
La fabrication des cartes est un processus batch , je le lance le soir et le lendemain c' est fini ,
alors que cela dure 2 minutes ou 2h cela ne me dérange pas .
Par contre pour l'utilisation des cartes il y a un utilisateur devant l'écran qui va m'engueuler si cela ne va pas assez vite, alors là il faut optimiser.
J'ai fait la fonction getStrXY pour pallier les faiblesses de VBA pour comparer les doubles 75,1 750,2 80,5 800,1.

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
Public Function getStrXY(XY As Double) As String ' 	La fonction qui pique les yeux mais rend service
    Dim Zt As String
    Zt = Trim(str(Int(XY * 100)))
    Select Case Len(Zt)
        Case 1
            Zt = "00000" & Zt
        Case 2
            Zt = "0000" & Zt
        Case 3
            Zt = "000" & Zt
        Case 4
            Zt = "00" & Zt
        Case 5
            Zt = "0" & Zt
    End Select
    getStrXY = Zt
End Function

[aj3309]

Bonjour,
Merci tbc92 pour ta modif.
Par contre peux m'indiquer à quel endroit dans ce forum je peux trouver la doc pour afficher des images et des morceaux de de programme.
Guesset je m'apprête à programmer l'algorithme et je m'aperçois que je n'ai pas bien compris l'usage des variables Lx et Ly ,
peux-tu m'en dire plus. D'avance merci.

[Guesset]

Bonjour aj3309,

...l'usage des variables Lx et Ly...

Lx représente la largeur de la carte (1200 a priori) et Ly la hauteur de la carte (800 a priori).

Salut

[aj3309]

Merci Guesset,
C'est bien ce que je pensais , cela ne pouvait pas être autre chose. Avec Lx et Hy je n'aurai pas eu le moindre doute mais Ly m'interpellait j'aurai du penser à longueur x et longueur y.

[aj3309]

Bonjour,
Merci tbc92 , mais j'ai honte , ce que je demandais me crevait les yeux
Pour voir si j'ai compris je vous joins une carte , il ne s'agit pas des covoitureurs de mon club de rando
mais celle des prospecteurs de Circaète Jean-le-blanc en Gironde.

[Guesset]

Bonjour,

Une nouvelle version Big_rect 4.zip dont l'optimisation (corrigée et améliorée) rend le processus linéaire et non plus quadratique.

Le mode démo (CTRL + Clic sur Chercher) reprend exactement le code de la recherche effective (0.2 s par pas mais peut être ralenti à 1 s par pas si le touche CTRL est maintenue appuyée).

Pour le fun, un clic sur la carte sélectionne le point le plus proche.

Salutations

[aj3309]

Bonsoir,
Merci Guesset pour ce dernier envoi que je n'ai pas encore digéré.
En attendant voici mes premiers résultats , il me manque pas mal de rectangles, malgré que je n'ai pas mis le filtre sur le ratio et hauteur mini et largeur mini sont à 60.
Mon tableau de points commence à 1, j'ai peut-être mal traduit cela dans ton algorithme.




Pour le moment je n'ai pas fait d'optimisations , toutes mes variables de dimensions et coordonnées sont en double précision.
Le traitement complet avec affichage des rectangles sur la carte dure 60 millisecondes pour 16 points , mais ce traitement n'est pas complet.

[Guesset]

Bonjour,

C'est déjà pas mal même s'il en manque notamment en bas. Il y a un autre problème, ils sont tous collés en haut à gauche. A gauche, cela pourrait signifier qu'il n'y a que le premier scan (celui qui part du bord gauche) : vérifier la boucle qui lance les scans (en bas de du pdf de l'algo). En haut, cela pourrait être dû à l'appel réentrant de la seule partie haute : or chaque point obstacle fragmente la recherche en 2 sous recherches comme une roche qui divise un courant d'eau en 2 plus petits (ce qui n'est pas aussi simple avec l'algo optimisé).

Si ces pistes ne donnent rien je pourrais peut être regarder le code. C'est du VBA ? Il va falloir que je ramène quelques neurones. Et en plus je n'ai rien pour tester (Libre Office a remplacé depuis longtemps la suite MS).

Avec des indices commençant à 1, comment sont gérés les chiens de gardes qui représentent les deux bords gauche et droite ? Rien n'empêche de transformer -1 à PosNb en +1 à PosNb + 2. Partout où il y a un accès Pos[i] il suffit de le remplacer par Pos[i+2] sans rien changer d'autre à l'algorithme.

Je crains que la résolution des problèmes ne fasse exploser les temps en même temps que le nombre de rectangles.

Salutations

[wiwaxia]

Bonjour,

Ce sujet paraît relever simplement de la recherche du maximum d'une fonction de deux variables dans un domaine rectangulaire de dimensions (La, Ha).
Il suffit pour cela d'ajouter à la séquence des (N) points envisagés, de coordonnées (Xi, Yi) - l'indice variant de (1) à (N), les deux coins opposés de l'image:

M₀ = (X₀, Y₀) = (0, 0) et M_N+1 = (X_N+1, Y_N+1) = (La - 1, Ha - 1) .

Que (M₀) corresponde au coin gauche inférieur ou supérieur n'a pas d'importance; cela dépend du logiciel de traitement des images, et du repère présent sur la carte.

La fonction envisagée donne à un facteur près (1/4) l'aire du plus grand rectangle centré en (x, y), insérable dans le nuage de points et n'en contenant aucun:

A(x, y) = Min(|x - X_i|)*Min(|y - Y_j| pour 0 ≤ i et j ≤ (N + 1)

Si l'on veut éliminer les rectangles trop étroits, on peut calculer une aire corrigée après écrêtage des dimensions en calculant

Acorr = ∆x*∆y , avec
∆x = Min(∆x_i) pour tout ∆x_i > 0
∆y = Min(∆y_i) pour tout ∆y_j > 0
∆x_i = |x - X_i| - Lmin si |x - X_i| > Lmin sinon ∆x_i = 0
∆y_j = |y - Y_j| - Hmin si |y - Y_j| > Hmin sinon ∆y_j = 0

Si l'exécution paraît trop longue, rien n'interdit de se livrer à une recherche préalable en travaillant sur une grille à maille carrée d'arête 10, par exemple.

[Guesset]

Bonjour wiwaxia ,

...La fonction envisagée donne à un facteur près (1/4) l'aire du plus grand rectangle centré en (x, y), insérable dans le nuage de points et n'en contenant aucun:

A(x, y) = Min(|x - X_i|)*Min(|y - Y_j| pour 0 ≤ i et j ≤ (N + 1)

...

Sauf si je n'ai rien compris ce qui reste, hélas, du possible sinon du probable, cela me parait particulièrement long s'il faut utiliser les La*Ha - N couples (x,y) et prendre le Max(A(x,y)) pour trouver le plus grand rectangle. Le nombre d'opérations semblerait de l'ordre de (La*Ha-N)*N². Dans le cas d'espèce cela représente (1200*800-20)*20² soit environ 384 millions d'opérations. Je me trompe ?

Au moins, on trouve aussi de facto le centre du rectangle trouvé . Cependant cela ne trouve qu'une fois sur 4 le plus grand rectangle puisque cela ne ramène que des rectangles ayant une largeur et une hauteur paires. Certes la différence sera minime, mais je suis (un peu ?) tatillon.

Salut

[wiwaxia]

Bonjour Guesset,

... cela me parait particulièrement long s'il faut utiliser les La*Ha - N couples (x,y) et prendre le Max(A(x,y)) pour trouver le plus grand rectangle. Le nombre d'opérations semblerait de l'ordre de (La*Ha-N)*N². Dans le cas d'espèce cela représente (1200*800-20)*20² soit environ 384 millions d'opérations ...

Le nombre d'opérations est de l'ordre de La*Ha*N , soit 19.2E6 si l'on parcourt une seule fois la liste des points.
Et il est divisé par 10² = 100 si l'on travaille sur une grille d'arête élémentaire 10 pixels.
Le résultat reste énorme (1.96E5), sans qu'il constitue une barrière infranchissable.

... Au moins, on trouve aussi de facto le centre du rectangle trouvé . Cependant cela ne trouve qu'une fois sur 4 le plus grand rectangle puisque cela ne ramène que des rectangles ayant une largeur et une hauteur paires. Certes la différence sera minime, mais je suis (un peu ?) tatillon ...

C'est délibéré, parce que j'ai pensé qu'on n'en était pas à un pixel près. Il se pourrait d'ailleurs qu'on trouve pour la même raison le même maximum en deux points voisins.

... Ensuite je ne suis pas sûr que i et j peuvent être différents ..

Effectivement, l'algorithme est beaucoup trop restrictif, voire inopérant. Je me suis gouré en espérant faire apparaître un extremum à partit du nuage de points.

[aj3309]

Bonsoir,
Suite aux remarques de Guesset j'ai fait un certain nombre de corrections, j'obtiens plus de rectangles mais il en manque et certains ne sont pas vides.
Pour y voir plus clair je vais réduire drastiquement le jeu d'essai.



'TabPos(1).X = 0 ' Chien de garde : bord gauche (indice 1) le premier de TabPos
'TabPos(1).Y = HauteurCarte - 1 ' Chien de garde : bord gauche (indice 1) le premier de TabPos
'TabPos(NbrePoints + 2).X = LargeurCarte - 1 ' Chien de garde : bord droit (indice NbrePoints+2) le dernier de TabPos
'TabPos(NbrePoints + 2).Y = HauteurCarte - 1 ' Chien de garde : bord droit (indice NbrePoints+2) le dernier de

Fin de la procédure RechercheRectangles() NbreScans = 17 j = 18 iRect = 43 en 0s 257ms

[unanonyme]

Bonjour,

/digression/

Cette carte elle est navigable ? Elle est interactive ?
Que ce passera t'il lorsque l'utilisateur aura cliqué sur un point,
affiché le "fameux " rectangle, puis fait déplacer la carte.
Le rectangle bouge avec ? Quitte à sortir de l'écran ?
Le rectangle saute d'espace libre en espace libre ?

Au delà de cela, je m'interroge si ce n'est pas plus un problème d'UX/UI plutôt qu'un problème d'algo.
Les utilisateurs n'aiment pas trop les interfaces qui gigotent trop.

J'ai peut être tord de soulever cet aspect, dans le doute,
je me disais que peut être cela pourrait se révéler utile.

/fin digression/

Bonne journée.

[Guesset]

Bonjour wiwaxia,

Le nombre d'opérations est de l'ordre de La*Ha*N , soit 19.2E6 si l'on parcourt une seule fois la liste des points.

C'est beaucoup plus subtil que de balayer deux fois les points comme je l'ai cru.

...Le résultat reste énorme (1.96E5), sans qu'il constitue une barrière infranchissable...

Sans aucune modestie, je t'inciterais à regarder mon post #47 dans lequel j'ai déposé un programme qui traite 256 points avec une hauteur mini de rejet de seulement 4 (donc peu discriminante) en moins de 1 ms. L'algorithme est linéaire en N (au moins jusqu'à 256 points ). Il y a un mode démo qui permet de voir ce qu'il fait. Je pense que tu devineras sans peine la démarche sous-jacente. Pour 240 points il y a moins de 2100 étapes (cela varie un peu selon la distribution des points).

Comme il intègre un ratio limite (demande du PO) de dy/dx que j'ai mis à 2/3, les solutions plus hautes que larges ne sont pas retenues. Ca me fait penser que je n'ai pas fait la contre-vérification qu'il n'y a pas un rectangle à l'intérieur de celui en défaut qui reste suffisamment grand pour concourir même après avoir été étêté. C'est peu probable mais...

Salut

[Guesset]

Bonsoir aj3309,

Fin de la procédure RechercheRectangles() NbreScans = 17 j = 18 iRect = 43 en 0s 257ms

Avec cet algorithme il doit y avoir N+1 scans mais je ne compte que 15 points.
Le nombre de rectangles vu est de (N+1)² soit 256 pour 15 points mais certains sont hors critère (mauvais ration, trop fins, vide) mais il devrait en rester au moins 200 sauf si les critères Largeur mini et Hauteur mini sont assez grands.

Il semble effectivement que quelques points soient à l'intérieur de rectangles mais comme c'est dans la zone de forte densité et que les tracés se superposent avec des couleurs réutilisées, on peut avoir un doute. Je ne l'ai jamais constaté. Comme le fondamental de l'algorithme est de s'arrêter au premier point obstacle et de continuer de part et d'autre, il ne capte pas de points.
La seule explication qui me vienne serait que les points près du bord droit ne sont pas traités correctement.

Ajout : je rappelle que les points doivent être préalablement triés selon les x (les plus petits en premier) et, en cas de x égaux, selon les y (les plus petits en premier). Si je l'ai déjà mentionné plusieurs fois, j'aurais du le rappeler explicitement dans l'algorithme (il y a juste une référence au tri dans la description des points Pos[]).

Salut

[aj3309]

Bonjour unanonyme,
Une fois que l'algorithme de recherche m'a trouvé le rectangle d'affichage des informations , sur une feuille Excel
je superpose des shapes (formes).
En arrière plan la shape de la carte ,puis les shapes de tous les points
ensuite la shape du rectangle d'info (un TextBox)
et pour finir les shapes des 3 lignes d'infos (3 TextBox).
Je fige tout cela en groupant puis verrouillant toutes ces shapes.
A ce stade la carte ne va plus bouger , le rectangle d'infos non plus.
Quand un utilisateur va cliquer sur un point rouge il va devenir vert
et les informations relatives à ce point choisi vont être actualisées , le point vert précédent va revenir en rouge.
Pour mon application covoiturage de randonneurs , chaque randonneur a sa carte sur laquelle il voit le domicile
des 20 randonneurs domiciliés au plus près de chez lui.
Dans cette version mon application est prête , il ne me manque que le calcul automatique du placement du rectangle d'info
pour l'instant je le fais a la main , mais ce n'est pas une solution.
Bien entendu je rêve d'une deuxième version avec une carte pour plusieurs utilisateurs, donc avec une carte qui bouge
et un rectangle d'infos qui se déplace, pour que chaque utilisateur voit les 20 personnes domiciliées au plus près de chez lui, tout cela en temps réel.

[aj3309]

Bonjour Guesset ,
Suite à tes remarques , sur la carte il y a bien 16 points , 15 rouge et 1 vert (le dernier qui a été cliqué) , donc mon nombre de scans serait bon. Merci encore, je sens que je vais y arriver.

[Guesset]

Bonjour,

Je croyais que le vert représentait le lieu de l'utilisateur et donc était exclus.

Concernant mon inquiétude sur le tri des points ?

Salutations

[wiwaxia]

Comme quoi il ne faut jamais vendre la peau de l'ours avant de l'avoir tué ... J'ai repris à fond et exécuté l'algorithme sur le même tableau de vecteurs (V₀, V₁ ... V_N, V_N+1): bien que la complexité apparaisse toujours élevée (en N⁵), l'énumération et la comparaison des rectangles insérés se sont révélées, à ma grande surprise, quasiment instantanées dans le cas envisagé (N=20).

La valeur de la surface maximale correspond au coordonnées des coins opposés:

Smax = (X2 - X1)(Y2 - Y1) = (480 - 76)(747 - 42) = 284820 .

Le nuage de points et le rectangle se présentent comme ci-dessous:

Le programme a été appliqué à une image de dimensions 1200x800. Il n'intervient ici aucun critère de sélection particulier; les éventuelles restrictions peuvent s"introduire facilement comme des variantes de l'algorithme initial, qui comporte 5 boucles imbriquées:

Code Pascal :

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 ... / ...
 CONST Chemin = 'D:\Virtual_Pascal\Fichiers_VP\Z_Prog_Dev_com\' +
                'Insert_Rectangle\';
       Npoint = 20; Np1 = Npoint + 1;
 
 TYPE Ve_2E = RECORD  x, y: Z_32  END;
      Tab_V = ARRAY[0..Np1] OF Ve_2E;
 
 VAR Nuage: Tab_V;
     Ve1, Ve2: Ve_2E;
     Smax: Z_32;
 
.../...
 
 FUNCTION TestL(K1, K2, L1, L2: Byte; VAR N_: Tab_V): Bool;
   VAR m: Byte; Test, Tx, Ty: Bool;
   BEGIN
     Test:= True;
     FOR m:= 1 TO Npoint DO
       BEGIN
         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
       END;
     Result:= Test
   END;
 
 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 = 53; o = 4;
   VAR I1, I2, J1, J2: Byte; Dx, Dy, Smax, Sxy: 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;
                     IF (Test AND (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;
     W_1:= W1; W_2:= W2; S_m:= Smax
   END;

Il serait intéressant de vérifier si l'emploi de deux tableaux, respectivement ordonnés selon l'ordre croissant des valeurs de (x) ou (y), réduit significativement le temps de calcul.

@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 ?