Newsgroup: it.comp.lang.c
Titolo: Algoritmo ricerca celle adiacenti

Buongiorno,
sono alle prese con un problema di ricerca di celle (per esattezza 
quadrate) adiacenti, posizionate su di una griglia quadrettata 
bidimensionale.
L'adiacenza è semplicemente definita come avere un lato in comune o uno 
spigolo in comune.
Per il momento le celle sono memorizzate in una tabella hash.
Devo quindi trovare gruppi di celle adiacenti (o un solo gruppo se sono 
tutte adiacenti.
Per ora, considerata una cella quadrata e la relazione di adiacenza 
specificata, verifico che gli otto quadrati che la "circondano" siano 
presenti - e dunque adiacenti. Quindi, per ogni quadrato individuato, 
verifico ancora nell' "intorno" degli otto quadrati supposti adiacenti.
Così facendo, per ogni quadrato individuato devo eseguire al massimo 8 
operazioni di ricerca...
Dal momento che mi sembra di intravedere una soluzione di programmazione 
dinamica, vorrei sapere se esiste già un algoritmo (senza reinventare 
l'acqua calda) che risolva in maniera adeguata il problema 
dell'adiacenza, o della documentazione inerente a questo problema.
Può anche essere che  stia sbagliando l'approccio e che la soluzione sia 
più semplice di quanto previsto... Boh, per il momento è 2 notti che non 
  mi fa chiuder occhio :-)
Grazie per eventuali risposte,
Gabriele

 bidimensionale. [...]
Interessante, ma non vedo l'attinenza col linguaggio C.
--
Cingar
--------------------------------
Inviato via 
http://arianna.libero.it/usenet/

 
Il fatto è che devo implementare un siffatto algoritmo in C. 
Effettivamente avrei solo bisogno di uno pseudo-codice, se ne esiste 
uno, e poi "tradurre" in C. Se però esistesse già qualcosa, eviterei 
sprechi di tempo:-)
Saluti,
Gabriele

 sprechi di tempo:-)
Suggerirei allora it.comp.programmare, che mi pare è il posto giusto per
discutere di algoritmi in generale.
Comunque, personalmente, non ho capito la descrizione del problema: vedi un
po' se hai messo tutte le informazioni necessarie. In particolare, cosa vuol
dire che usi una "tabella di hash"? Non mi pare che le celle di una matrice
abbiano una "chiave" di cui si possa fare uno hash.



 Ciao Gabriele,
io avevo un problema analogo durante la mia tesi: ho risolto immaginando la
tua griglia come un grafo i cui nodi sono costituiti dalle singole celle. Ti
crei le liste di adiacenza e quindi eseguendo la visita in profondità
risolvi il problema.
Ciao

 
Dunque, individuata una cella, cerco sempre la prima cella adiacente, e 
di quest'ultima la propria adiacente, ecc. fino ad una foglia, quindi 
risalgo e ricomincio... Ciò dovrebbe garantire che gli eventuali nodi 
rimasti esclusi alla fine possano essere "sorgenti" di altri blocchi di 
celle adiacenti. Ripetendo dunque la visita su questi nodi, fino ad 
esaurimento, dovrei ottenere una foresta di blocchi di celle di 
adiacenza... devo provare! :-)
Grazie!

 
Vedo se riesco a descrivere meglio: ho un piano potenzialmente infinito, 
diviso in celle quadrate di lato (supponiamo) 1. Ovviamente non posso 
utilizzare una struttura fissa tipo matrice, quindi la scelta è ricaduta 
  su una tabella hash, viste le prestazioni per inserimenti e 
cancellazioni. Ogni cella è identificata da coordinate (x,y) riferite 
all'angolo inferiore sinistro. Una funzione hash deve distribuire in 
maniera appropriata le chiavi. Se ordiniamo le coppie (x,y) nel modo 
seguente:
(0,0) (0,1) (0,2) ...
(1,0) (1,1) (1,2) ...
(2,0) (2,1) (2,2) ...
ordinando per diagonale si può dimostrare che esiste una funzione iniettiva:
f(x,y)=((x+y)^2 * (3*x) + 1 ) / 2
che può essere utilizzata per determinare il valore di una funzione hash 
su coppie di interi (per inciso: la documentazione l'ho trovata in rete 
:-> )
Grzie di nuovo,
Gabriele


Esattamente è proprio quello che ho fatto io.
Spero di esserti stato utile, ciao