Newsgroup: it.comp.lang.c++
Titolo: [lungo] Errore di segmentazione

All'interno di una classe "immagine" ho una matrice di booleani definita 
come tramite il template matrix che si trova nelle faq del NG, e quindi 
tramite un: std::vector< std::vector<bool> > flag;
Ho implementato su questa matrice un algoritmo di seeded region growing.
In soldoni questo algoritmo viene lanciato ad una certa coordinata con 
la premessa che l'elemento corrispondente sia true. La funzione 
memorizza i valori di x e y di tale punto su una list. A quel punto la 
funzione controlla se i campi limitrofi (nelle 8 direzioni) sono true e, 
in caso positivo, chiama se stessa nei suddetti punti.
Alla fine della ricorsione la list conterrà un insieme non ordinato di 
coordinate che rappresentano un'area priva di interruzioni.
void immagine::region_growing(int x, int y, std::list<elem> & cand)
{
     // Setto la posizione corrente a 'false' in modo che la funzione non
     // vi entri una seconda volta nelle successive chiamate
     flag[ix][iy] = false;
     // Inserisco le coordinate nella list
     elem e (x, y);
     cand.push_back(e);
     // Estremi della matrice
     int dimx = x_dim();
     int dimy = y_dim();
     /* Ricorsione sull'intorno del campo corrente ( indicato con *). 
Ordine di chiamata...
         x
       y -------------
         | 6 | 7 | 8 |
         -------------
         | 5 | * | 1 |
         -------------
         | 4 | 3 | 2 |
         -------------   */
     // 1
     if (x+1 < dimx)
         if (flag[x+1][y] == true)
            region_growing(x+1, y, cand);
     // 2
     if ((x+1 < dimx) && (y+1 < dimy))
        if (flag[x+1][y+1] == true)
            region_growing(x+1, y+1, cand);
     // 3
     if (y+1 < dimy)
        if (flag[x][y+1] == true)
            region_growing(x, y+1, cand);
     // 4
     if ((x-1 >= 0) && (y+1 < dimy))
        if (flag[x-1][y+1] == true)
            region_growing(ix-1, iy+1, cand);
     // 5
     if (x-1 >= 0)
        if (flag[x-1][y] == true)
            region_growing(x-1, y, cand);
     // 6
     if ((x-1 >= 0) && (y-1 >= 0))
        if (flag[x-1][y-1] == true)
            region_growing(x-1, y-1, cand);
     //7
     if (y-1 >= 0)
        if (flag[x][y-1] == true)
            region_growing(x, y-1, cand);
     //8
     if ((x+1 < dimx) && (y-1 >= 0))
        if (flag[x+1][y-1] == true)
            region_growing(x+1, y-1, cand);
}
Ora, il mio problema e' che tale funzione genera a runtime un errore di 
segmentazione, e per quanto mi sia giocato il cervello nel tentativo di 
scoprire la magagna, non riesco a venirne a capo.
Preciso che via debug scopro che la funzione lavora correttamente per un 
bel po' di chiamate, ma questo non toglie che ad un certo punto tutto 
vada a troie. E precisamente mi pare vada a troie quando si avvicina 
alla chiusura della ricorsione.
Ho pensato a una violazione d'accesso causata da un errato valore messo 
dentro qualche [], ma non mi pare questo il caso (le funzioni x_dim() e 
y_dim() sono corrette).
Quindi mi/vi chiedo: con gli 'ingredienti' sopra descritti, quali altri 
errori possono dare origine ad un segmentation fault?
Puo' essere un problema dato dalle troppe chiamate ricorsive?
Puo' essere che si è riempito l'heap?

Non ho ben capito se il contenitore che utilizzi via '[]' sia un vector 
di STL, se si mi pare di ricordare che il metodo .at() effettua i 
controlli di range sul vettore, gia' potrebbe essere un problema in meno.
Ma che mi corregga la voce divina se ho detto qualche *lollata*.....
Il Vampiro Casimiro ha scritto:


 controlli di range sul vettore, gia' potrebbe essere un problema in meno.
Si' il contenitore e' un vector di STL. Potresti spiegarmi questo metodo 
.at()? Non ne ho mai sentito parlare e nella documentazione che ho non 
e' menzionato

 menzionato
Lo usi come un metodo qualunque :-) 
nomevector.at
(indice)
La differenza è che con [] se vai fuori non è detto che ti venga segnalato, 
con at invece sì (per questo è più lento... E' utile durante il debug 
principalmente)
--- bye 

Esatto magari potresti pensare di usarlo proprio per il debug...
MaxMax ha scritto:


io sono ai rudimenti del C++, ma posso chiederi quanto e' grand e questa 
tua matrice???.
Se usi un metodo ricorsivo per far crescere l'area rischi di fare 
facilmente decine di migliaia di chiamate alla stessa funzione..e mi 
pare.. che ad ogni passo un sacco di variabili vengono messe nello stack 
ogni volta che la funzione chiama se stessa.
La mia impressione ( da programatore medio di C e pesimo programmatore 
C++) e' che la ricorsione non sia l'approccio adatto a questo problema.
Sono quasi certo che sfondi il limite dello stack.
Spero di non sbagliarmieaspetto bachettate dolorissime.=)



Chi sono ix e iy?
Saluti  Manlio Perillo

     // 1
ascolta ... come ti regoli quando la ricerca coinvolge un 
elemento ai margini o persino agli "angoli" della matrice ?
invece di fare solo x +o- 1  e y +o- 1, non potresti aggiungere 
dei MODULO (resto, il %) per, come dire, richiudere in una sorta 
si sfera logica l'immagine, e rendere la matrice non sforabile ?
Se questo non va bene per il senso logico dei confini della 
matrice, allora hai inserito in testa le possibili condizioni di 
anti sforamento degli indici ?
Scusa se ho letto distrattamente, non le ho viste
(ovviamente non i controlli della sola casella in esame, ma sul 
suo range di ricerca, x+1, y+1, x-1 e y-1). Se uno qualsiasi di 
questi casca fuori, anche se in sola lettura, potrebbe dare cmq 
problemi
Ciao
Soviet_Mario


 Sono quasi certo che sfondi il limite dello stack.
Credo che senza ricorsione questa funzione sia praticamente impossibile 
da fare. Credo.
-- 
www.project-ring.com

 Chi sono ix e iy?
Un errore di battitura, in realta' sono x e y.
-- 
www.project-ring.com

 fuori, anche se in sola lettura, potrebbe dare cmq problemi
Puoi spiegarmi che cosa intendi per condizioni anti sforamento?
La  funzione e' chiamata per la prima volta da un algoritmo esterno che 
fa attenzione a prendere un punto interno alla matrice. Il controllo 
antisforamento sulle chiamate successive l'ho messo prima delle chiamate 
stesse, in modo da evitare chiamate inutili.
-- 
www.project-ring.com

MaxMax wrote:

perchè solo durante il debug? :-)
-- 
MSN: sirpsycho_78 -at- hotmail dot com
the last action hero... 
http://tinyurl.com/bgy5w

 
Associ ad ogni elemento della matrice un attributo tipo "passato" 
booleano.L'esapansione avviene solo verso nuovi elemnti non passati.Puoi 
tenere sempliceente una lista degli ultimi punti in cui si passato e 
scorrerla per trovare i nuovi punti sui quali andare..e poi aggiorni la 
lista iniziale.
Ancora piu' semplice fai delel scansioni successive di tutta la matricee 
  valutando punto per punto se ha punti adiacenti gia' coperti (per 
quindi fare le operaioni che devi)..


Se e' cosi' potrebbe essere qualche distruttore.
Sarebbe opportuno postare anche il codice che chiama la funzione.
Saluti  Manlio Perillo

> perchè solo durante il debug? :-)
Perchè è più lento (dovendo fare il controllo di validità) e se sai che il 
tuo codice è corretto puoi non usarlo?
Ovviamente se a priori non sai e non vuoi sapere quanti elementi ha il 
vector allora devi usarlo.
--- bye 

 da fare. Credo.
Tralasciamo che si puo' dimostrare che ogni algoritmo recursivo si puo'
trasformare in uno equivalente iterativo... ;-)
Un'idea puo' essere:
1) trovi un punto "true" nell matrice 
2) lo salvi nella lista dei punti "da fare"
3) estrai un punto "da fare" e cerchi nel suo intorno i punti "true"
4) tutti i punti "true" trovati li salvi nella lista "da fare"
5) il punto si cui stai lavorando lo salvi nella lista "fatti" e lo azzeri
6) se la lista "da fare" non e' vuota vai a 3)
...o qualcosa di simile...
Ciao!
-- 
Qual'e' il colmo per uno studente-lavoratore?
Avere un quadrato che si crede un rettangolo.

 ...o qualcosa di simile...
Si', se la cosa della ricorsione non mi va in porto mi sa che l'unica e' 
fare cosi'. Grazie per il suggerimento!
-- 
www.project-ring.com

 assurdo: non siamo mica in un sistema multithread o cose simili!
In generale la profondita' della recursione non dipende non solo dalla
dimensione della matrice, ma anche dalla disposizione delle caselle
true/false. Ad esempio questa matrice dovrebbe portare ad una recursione
massima (credo):
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFT
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
TFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
Fossi in te cercherei di misurare la profondita' massima della recursione,
per capire se i problemi saltano fuori solo quando questa supera un valore
limite.
In ogni caso un algoritmo recursivo e' (quasi) sempre meno efficiente e
robusto della sua controparte iterativa, anche se spesso e' piu' facile da
capire e da implementare.


 capire e da implementare.
Infatti. Questo perche' i computer 'pensano iterativo', quindi ogni 
tentativo di ricorsione e' una sorta di forzatura. Comunque ho rifatto 
la funzione sfruttando il tuo suggerimento e funziona. Naturalmente e' 
anche piu' veloce.
-- 
www.project-ring.com

  megacut
scusa ,
ma tu hai dei seri problemi di quoting 
http://www.freewebz.com/iosononiubbo/iosononiubbo.htm#quotare