Discussion :

[Lintel-oo]

Bonjour à tous,

je ne savais pas vraiment dans quelle catégorie poster ce message, donc je l'ai mis là (c'est pas très spécifique au langage lui même, mais ça peut passer partout )
Voila donc ce problème :
j'ai un tableau dynamique d'int à double entrée dont chaque élément représente une couleur. Je souhaite effectuer des opérations sur ce tableau, et celle dont j'ai actuellement besoin, c'est une fonction qui me retourne des "blocs" de même couleur (pour simplifier dans un rectangle englobant tous les pixels dans un premier temps).
Je pensais que cela ne poserait aucun problème, et à vrai dire l'algorithme est tellement simple qu'il se passe d'explication : on se place sur chaque case qui n'a pas été visitée précédemment, et on calcule le bloc correspondant (qui englobe tous les pixels identiques à celui sur la case sur laquelle on se place initialement et accessible depuis elle en suivant un chemin de même couleur).

Ce qui donne quelque chose du genre :

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
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
 
void analyseRects(const std::vector<std::vector<int> > &t, std::vector<RECT> &ret)
{
    std::vector<std::vector<bool> > casesLooked(t.size());
    for(unsigned int i=0;i<casesLooked.size();i++)
    {
        casesLooked[i].resize(t[i].size());
        for(unsigned int j=0;j<casesLooked[i].size();j++)
            casesLooked[i][j] = false;
    }
 
    RECT currentRect;
    for(unsigned int i=0;i<casesLooked.size();i++)
        for(unsigned int j=0;j<casesLooked[i].size();j++)
        {
            if(!casesLooked[i][j])
            {
                currentRect.top = i;
                currentRect.bottom = i;
                currentRect.left = j;
                currentRect.right = j;
                itere((int)i,(int)j,t[i][j],t,casesLooked,currentRect);
                ret.push_back(currentRect);
            }
}
 
void itere(int i, int j, int color, const std::vector<std::vector<int> > &t, std::vector<std::vector<bool> > &casesLooked, RECT &currentRect)
{
    if(i<0||j<0||i>=casesLooked.size()||j>=casesLooked[i].size())
        return;
    if(casesLooked[i][j]||!sameRGBColors(color,t[i][j]))
        return;
 
    casesLooked[i][j] = true;
    if(i<currentRect.top)
        currentRect.top = i;
    else if(i>currentRect.bottom)
        currentRect.bottom = i;
    if(j<currentRect.left)
        currentRect.left = j;
    else if(j>currentRect.right)
        currentRect.right = j;
 
    itere(i+1,j,color,t,casesLooked,currentRect);
    itere(i-1,j,color,t,casesLooked,currentRect);
    itere(i,j+1,color,t,casesLooked,currentRect);
    itere(i,j-1,color,t,casesLooked,currentRect);
}
 
bool sameRGBColors(int c1, int c2)
{
    if(((c1&255)==(c2&255))&&(((c1>>8)&255)==((c2>>8)&255))&&(((c1>>16)&255)==((c2>>16)&255)))
        return true;
    else
        return false;
}

Bon je passe sur le fait qu'on puisse sans doute rendre le code plus beau (lambda etc ...), et que j'utilise la classe RECT fournie par windows (comme c'est un projet spécifique à cet OS ça ce pose pas de problèmes).
Le fait est, que, dans la fonction itere (le coeur du problème), les indices sont bons, les tailles des tableaux jamais dépassées, l'erreur est impossible. De plus, pas de boucle infinie : les cases du tableau casesLooked, une fois visitées, sont mises à true, et ne peuvent dont ultérieurement plus être visitées.

Sauf que, toujours à partir d'un certain rang d'itération (par exemple souvent autour de i=800 et j=30), le programme crashe, et le debugger m'indique qu'il n'y a rien à la référence de casesLooked[i][j]. J'ai remplacé la référence par un pointeur pour en savoir d'avantage, le même problème se produit, à savoir qu'on ne peut pas accéder à (*casesLooked)[i][j]. Cependant, on peut accéder à la taille du tableau (qui est correcte, j'ai vérifiée à maintes reprises). Je n'y comprends rien, puisqu'on passe toujours le tableau en argument à l'itération suivante, éventuellement avec une case modifiée.

Y a-t-il un nombre d'itérations maximal au delà duquel la taille en mémoire de tout cet emboîtement est trop importante ? J'ai cru lire que la taille du heap était de 1Mo pour windows, 8 pour linux (enfin ça dépend mais actuellement, pour beaucoup de monde). Cependant, cela n'a pas de raison d'être cela, je ne "crée" aucune donnée dans la fonction itere ...

Avez-vous une idée ? Des pistes ? Des tests à effectuer pour mieux cerner le problème, car je dois avouer que je suis coincé ^^ !

Merci d'avance

[Iradrille]

Salut,

Cependant, cela n'a pas de raison d'être cela, je ne "crée" aucune donnée dans la fonction itere ...

Bien sur que si.
A chaque appel de fonction, tu auras au strict minimum l'adresse de retour qui sera ajoutée sur la pile (+ très probablement les arguments).

Code :

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

1
2
3
4
5
6
7
bool sameRGBColors(int c1, int c2)
{
    if(((c1&255)==(c2&255))&&(((c1>>8)&255)==((c2>>8)&255))&&(((c1>>16)&255)==((c2>>16)&255)))
        return true;
    else
        return false;
}

Un peu hors-sujet, mais ça peut se simplifier

Code :

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

1
2
3
4
bool sameRGBColors(int c1, int c2)
{
    return (c1 & 0xffffff) == (c2 & 0xffffff);
}

[Lintel-oo]

En effet merci pour la simplification

Donc tu penses que c'est probablement ces ajouts d'adresses sur la pile qui sont à l'origine de ce problème ? Dans ce cas je vais passer le code en itératif pour voir si cela fonctionne, je vous tiens au courant !

Merci pour ta réponse rapide en tout cas

[Lintel-oo]

En effet ça fonctionne comme cela, sujet résolu donc !