Newsgroup: it.comp.lang.c
Titolo: Aggregazione elementi di una matrice

Ciao a tutti, ho il seguente problema. In una matrice MxN sono memorizati
degli interi. Devo raggruppare gli elementi con lo stesso valore che siano
adiacenti tra loro, identificando quindi delle "regioni" all'interno della
matrice. Faccio un esempio. Se ho la seguente matrice
1    2    5    8    6    2
1    4    5    5    9    0
1    1    9    1    5    3
devo identificare la regione ad L degli 1, la regione dei 5 e cosě via.
Sapete come posso fare?
Grazie

 ha scritto nel messaggio
news:3ctoc.179666$hc5.7...@news3.tin.it...

La prima cosa che mi viene in mente sarebbe questa:
- una prima lettura della matrice per identificare tutti i possibili valori
presenti in matrice;
   Nell'esempio: 0, 1, 2, 3, 4, 5, 6, 8, 9
- una seconda lettura per associare ad ogni valore una lista di coppie di
coordinate,
   che sono le coordinate delle celle della matrice che contengono quel
valore
   Nell'esempio:
   0 -> <1,5>
   1 -> <0,0>, <1,0>, <2,0>, <2,1>, <2,3>
   2 -> <0,1>, <0,5>
   ...
[queste due passate possono anche essere unite facilmente in una passata
sola]
- all'interno di ogni lista, identificare le regioni.
   Le regioni sono un insieme di coppie di coordinate per cui ognuna coppia
<X,Y>:
   * ha una coordinata in comune con un'altra coppia <Z,W> della stessa
regione
   * da quella coppia <Z,W> dista 1 relativamente all'altra coordinata.
   In formula: (X=Z and |Y-W| = 1) or (Y=W and |X-Z| = 1)
   Nell'esempio:
   0 -> {<1,5>}
   1 -> {<0,0>, <1,0>, <2,0>, <2,1>}, {<2,3>}
   2 -> {<0,1>}, {<0,5>}
   ...
Boh, vedi te se riesci a tradurlo in c.
Ciao,
Ema

 Grazie
Perdiana, si tratta di un arduo problema di intelligenza 
artificiale!
anche perché non è chiaro che cosa sia una "regione"
Individuare rettangoli dovrebbe essere abbastanza facile.
-- 
oggi no, domani sì

ADPUF wrote:
 > Perdiana, si tratta di un arduo problema di intelligenza
 > artificiale!
 > anche perché non è chiaro che cosa sia una "regione"
Veramente non e' un problema di intelligenza artificiale
e non e' arduo per niente.
Nel messaggio sopra ha specificato che una regione e'
costituita dalle celle adiacenti con lo stesso valore,
quindi mi sembra chiarissimo cosa intende per regione.
Magari dovrebbe specificare se due celle possono essere
adiacenti anche in diagolae o solo per lato, ma e' un
dettaglio che non modifica lo spirito del programma.
Ci sono diverse strade percorribili, e la scelta
potrebbe dipendere anche dalla dimensione della matrice
e dalla velocita' con la quale si vuole fare la cosa, dal
numero di regioni, etc.etc.
Per esempio si puo' fare cosi', in una manciata di linee di codice C,
ecco una idea dello pseudo-codice:
1) ci si fa una copia di lavoro della matrice
(nel caso la si voglia conservare), perche' la ammazzero' visitandola.
2) si definisce una routine ricorsiva
Pippo(C, L) che prende
una cella C (in realta' le 2 coordinate che determinano C)
e una lista L (cioe' un puntatore al primo elemento di una lista, che 
conterra' i riferimenti alle celle che compongono la regione attuale).
la routine ricorsiva Pippo
inserisce il riferimento C nella lista L, azzera (con un valore
speciale che non e' tra quelli che posso trovare normalmente nella
matrice) la cella C, poi invoca se stessa su tutte le celle
adiacenti a C che contengano il valore V che la cella C conteneva
originariamente (memorizzarlo prima di azzedrarla), passando 
opportunamente L in modo da aggiornarla.
3) Si definisce la routine principale che fa la seguente cosa:
Scandisce la matrice cella per cella.
Se trova una cella che contiene ancora un valore (non-speciale),
allora ha trovato una cella che appartiene ad una regione non
ancora esplorata. Quindi si memorizza il valore contenuto in C e
invoca Pippo(C, NULL) cioe' invoca Pippo su quella cella e con una lista 
vuota.
Al ritorno da Pippo avra' una lista delle celle che compongono la
regione e potra' salvarsela come gli pare.
ciao,
g,

Ciao Giovanni, io avevo pensato di fare in questo modo:
vedere la matrice com eun grafo, quindi per ogni cella mi creo la lista di
adiacenza e poi, facendo una visita in profondà o in ampiezza ritrovare le
regioni. Riprendendo l'esempio originale, avrei ad esempio:
0 -> 6
1 ->
2 -> 8 -> 9
3 ->
4 ->
5 ->
6 -> 1 -> 12 -> 13
e così via.....
Ti dico che la matrice è composta da circa 400 celle. Ti sembra una buona
idea? Codsa ne pensi rapportata alla tua proposta?
Grazie per le risposte, ciao.


La matrice e' insignificantemente piccola :-)
Quindi probabilmente non e' cosi' critico l'approccio.
Quello che hai delineato sopra e' esattamente lo stesso approccio
che ti suggerivo io, solo che non sapendo se sapevi cosa e' un grafo
etc.etc. avevo translato tutto in un'altra notazione.
In ogni caso non e' necessario costruirsi esplicitamente la lista di
adiacenze, visto che le celle adiacenti le puoi determinare nel
momento in cui fai la visita. E' piu' veloce farsi banalmente una
copia della matrice da utilizzare come area di lavoro (visto che
facendo la visita hai la necessita' di marcare le celle).
Quindi, come dicevo, scandisci la matrice un elemento alla
volta. Se l'elemento corrente non e' stato gia' marcato allora
fa parte di una nuova regione inesplorata. A quel punto la si esplora
con una visita (in profondita' direi che e' meglio) e nel farlo
si marcano tutte le celle (e si memorizzano in una lista o in un
vettore). Dopo di che si ritorna a scandire la matrice alla ricerca
di celle non ancora marcate.
Il tutto in poche righe di C.
ciao,
g.

 con una visita (in profondita' direi che e' meglio)
Ciao Giovanni,
grazie, ho risolto proprio facendo il grafo, e facendo poi la visita in
profondità.
Ti chiedo ancora una cosa: siccome questo procedimento va faccio per un
numero N di volte (ogni matrice non l'ho detto ma rappresenta un frame di
una sequenza video), per liberare la memoria devo necessariamente
richiamrela procedura free() per ogni nodo, oppure esiste un metodo per
liberare in un'unica volta l'intero grafo???
Ho provato a far girare il programma senza mai liberare la memoria e
comunque il pc non sembra risentirne; inoltre non è necessario effettuare
tutte le ottmizzazioni di velocità poichè è solo un software sperimentale
che sarà poi realizzato in con le opportune ottimizzazioni nel caso porti a
risultati soddisfacenti. Grazie per l'aiuto, ciao Maurizio

 liberare in un'unica volta l'intero grafo???
No, non esiste una procedura che possa liberare automaticamente una
struttura dati che crei tu a tuo piacimento.
Comunque la cosa puo' essere risolta molto semplicemente:
ti gestisci tu la memoria. In questo caso la cosa e' molto semplice
perche', presumo, durante una iterazione dell'algoritmo tu allochi
via via degli elementi, e poi vorresti deallocarli tutti e ricominciare,
cioe' non hai il caso in cui deallochi solo qualche elemento, ma solo
tutti insieme.
In pratica funziona cosi' (e puo' essere piu' efficiente
di usare delle malloc per allocare via via gli elementi della
lista o della matrice etc.etc.):
supponiamo che il tuo problema sia allocare delle liste
in cui un elemento sia di tipo Pippo, che contiene alcuni
campi di dati piu' un puntatore a Pippo (che punta al successivo
elemento della lista).
Siccome in questo caso tu puoi stimare a priori quanti elementi 
allocherai (uno per ogni elemento della matrice, ad esempio) allora
ti puoi allocare (dinamicamente o staticamente) un array di Pippo
diciamo
Pippo MyMem[1000];
e poi ti dichiari un bell'intero GLOBALE
int nMem=0;
che ti dice quante celle hai gia' allocato.
A questo punto, nel codice che alloca gli elementi della lista,
dove avevi una cosa del tipo
Pippo *pu;
pu = malloc(sizeof(Pippo));
avrai invece una chiamata ad una tua funzione:
pu = MyMalloc();
dove
Pippo *MyMalloc()
{
    return & ( MyMem[ nMem++]);
}
in pratica sposti in avanti nMem e restituisci il puntatore
all'elemento che hai "saltato".
Il resto dell'algoritmo rimane uguale.
(Alternativamente puoi sostituire i puntatori con degli
interi che fanno da indice in MyMem, ma allora devi cambiare
anche altre cose).
Alla fine, tra una iterazione e l'altra, per "deallocare"
tutta la memoria non dovrai fare altro che nMem=0;
Spero ti averti trasmesso l'idea generale della gestione
della memoria "fai-da-te". Poi puoi infiocchettarla un po'.
ciao,
g.