HW4bis - ES3 - Ricerca parentele padre-figlio tramite coordinate,diramazioni

AdrianH (840 points)
0 8 17
asked Feb 26, 2019 in HW4bis by AdrianH (840 points)
recategorized Mar 2, 2019 by andrea.sterbini
Salve,

Mi sono bloccato con questo esercizio e non so come andare avanti,

Avevo deciso di fare cosi':

salvare tutte le coordinate dei punti bianchi,nodi e radice,per poi lavorare solo con essi.

poi come continuo?

Ho pensato di unire la liste di tutte le coordinate(ovviamente avendo comunque un modo per differenziare i nodi dai bianchi),per poi ,partendo dalla radice,attraversare tutte le coordinate bianche adiacenti(con x o y spostati di massimo 1 ) finche' non trovo un nodo(che quindi sara' figlio).

(penso che sia piu' lento)Altrimenti ho pensato di girare nodi e radice e vedere tutte le combinazioni tra essi e vedere se ci stanno coordinate contigue che li collegano.

Ma il problema rimane lo stesso,come amministro le diramazioni e figli multipli?

per la prima soluzione dovrei provare tutte le possibili direzioni(con un a funzione a 4 if) dei bianchi che partono da piu' parti da un nodo o si diramano,ma dubito fortemente che lo farebbe in meno di un 1 secondo.

per la seconda soluzione non so neanche dove andare a sbattere con le diramazioni.

c'e' un modo per risolvere questo dilemma?

1 Answer

Best answer
_andrea_ (45670 points)
2 40 297
answered Feb 26, 2019 by _andrea_ (45,670 points)
selected Feb 26, 2019 by AdrianH
Trova il pixel radice nell'immagine, parti da quello con la funzione quadridirezionale (si, quella con 4 if). La funzione fa così: la chiami su un pixel e ti ritorna l'insieme dei nodo che trova percorrendo quella strada. Parti da x,y che è la radice, la funzione ti ritorna quindi l'insieme dei suoi figli, i quali avranno i loro figli i quali avranno i loro figli ecc... La funzione la strutturi così: caso base, se hai un pixel nero ritorni l'insieme vuoto (significa che da quel pixel ottieni un insieme vuoto di figli). Se hai un pixel rosso, lo aggiungi all'insieme di figli che ritornerai, e chiami la funzione quadridirezionale anche su quellp (per fargli ottenere i suoi figli), se invece trovi un pixel bianco vai avanti nelle 3 direzioni (3 perché da una ci vieni e non devi tornare indietro MAI!). Alla fine la funzione ti tornerà i figli del nodo su cui l'hai chiamata, quindi quelli della radice (se la fai bene)
AdrianH (840 points)
0 8 17
commented Feb 26, 2019 by AdrianH (840 points)
Ok per la ricorsione, ma per le diramazioni?
Nella ricerca a 4 if come a ministro pixel bianchi in piu' di una direzione?
_andrea_ (45670 points)
2 40 297
commented Feb 26, 2019 by _andrea_ (45,670 points)
Le diramazioni SONO la ricorsione. Da x,y ti muovi a x+1,y, x-1,y, x,y+1, x,y-1 (eccetto una, quella da cui provieni)
AdrianH (840 points)
0 8 17
commented Feb 26, 2019 by AdrianH (840 points)
Giusto, avevo capito male io, my bad.
Grande grazie!
_andrea_ (45670 points)
2 40 297
commented Feb 26, 2019 by _andrea_ (45,670 points)
Fammi sapere se ti viene o hai altri problemi dopo
f.cocci (650 points)
1 13 17
commented Mar 25, 2019 by f.cocci (650 points)
Ciao, sono alle prese con questo esercizio. anche io.

Non sono del corso in presenza e volevo sapere se questa funzione 4IF fosse una qualche modulo "noto" presente da qualche parte o al quale ci si possa ispirare un po come per Diametro Albero.

In piu' volevo capire cosa si intende per costruire l'albero corrispondente. Io potrei rappresentare un albero come voglio in teoria, per esempio utilizzando le classi Nodo definendo come attributi il valore e la lista dei figli che sono a loro volta oggetti di tipo nodo corretto? il valore sara' rappresentato da una tupla.Corretto?

Poi se ho capito bene, partendo dal nodo radice, che inizialemente avra' la listi dei figli vuota, devo partire dai suoi 4 confini: se il pixel e' nero torno nulla, se e' rosso, istanzion un nuovo nodo e lo aggiungo come figlio del precedente, se e' bianco vado con la ricorsione. e' corretto?

Non mi e' chiaro, siccome all'inizio parto con l'esplorare le quattro coordinate che si diramano dalla radice, come faccio poi con la ricorsione a escludere quella da cui arrivo.

Thanks, F.
_andrea_ (45670 points)
2 40 297
commented Mar 25, 2019 by _andrea_ (45,670 points)
Non so se esista una specie di linea guida per la funzione a 4 direzioni ma è quello il modo per esplorare un'immagine. Se stai in x,y e devi muoverti in orizzontale e verticale devi esplorare (x+1,y), (x-1,y), (x,y+1) e (x,y-1). Riguardo la rappresentazione, puoi decidere tu, basta che alla fine ritorni l'immagine giusta perché non mi pare ci siano istruzioni riguardo a come arrivare al risultato. Inoltre per quanti riguarda la funzione gli step sono quelli che hai detto ma con una cosa in più: se trovi un rosso devi ritornare quel nodo, ma a quel nodo devi aggiungere i suoi figli, quindi ancora ricorsione (che bello)
f.cocci (650 points)
1 13 17
commented Mar 25, 2019 by f.cocci (650 points)
Grazie 1000 Andrea, provo a pestare un attimino e vedo cosa ne viene fuori, sono ancora all'inizio e per esperienza ne avro per tutta la settimana.

Per lo meno a differenza dell'es2 qui ho gia un ragionamento. Come metterlo in pratica e' un di cui :-)

Pero se ho capito bene qui  scorrere l'immagine vuole dire procedere un pixel alla volta (nelle diverse direzioni) non c'e' da iterare, tranne che nella prima fase in cui si vanno a identificare le coordinate del nodo radice e dei nodi figli (R).
_andrea_ (45670 points)
2 40 297
commented Mar 25, 2019 by _andrea_ (45,670 points)
No nella prima parte non devi trovare i figli, solo la radice
f.cocci (650 points)
1 13 17
commented Mar 25, 2019 by f.cocci (650 points)
ah perfetto, allora solo una riga di codice da eliminare, in effetti non mi serve visto che devo analizzare i collegamenti bianchi per determinare chi e figli di chi.

Mi sfugge purtroppo ancora come innescare la ricorsione e sopratuto come differenziarla in base alla direzione che prendo.

Io ho la mia radice V di coordinate x,y. Parto da qui. Da qui dev ocontrollare quello che succede a x,y-1, x+1,y, x,y+1 e x-1,y che sono 4.

Mettiamo che trovi che x,y-1 sia White. Su questo devo richiamare la funzione, ma questa a sua volta non effettua il controllo sui suoi confinanti, compreso da dove e' arrivata?.
_andrea_ (45670 points)
2 40 297
commented Mar 25, 2019 by _andrea_ (45,670 points)
Blocchi la direzione da cui vieni. I 4vif si riferiscono a questo
f.cocci (650 points)
1 13 17
commented Mar 25, 2019 by f.cocci (650 points)
Purtroppo continua a non essermi ancora chiaro come dovrebbe funzionare questa 4if, chiedo venia.