Algoritmo Per Colorare Un'area Ben Definita

[masmil1988]

Sto lavorando a un programma per disegnare sul cellulare, ed essendo già a buon punto dovrei creare il tool per riempire un'area delimitata da un contorno...

Avevo pensato a un algoritmo ricorsivo che, partendo da un punto si espandesse colorando a poco a poco tutto intorno.

L'algoritmo funziona dal punto di vista teorico, ma dal punto di vista pratico richiede parecchia memoria e quindi il cellulare non è in grado di eseguirlo...

Questo è forse il perchè nessun programma di disegno per cellulare ha questa funzione...

Qualcuno conosce un algoritmo NON RICORSIVO che faccia la stessa cosa?

[pandipo]

imagedesiner ha questa funzione

in pys60

[masmil1988]

Si ma per quel che mi risulti i 2nd edition hanno uno schermo più piccolo quindi è normale che richiedano meno risorse di un 640x360...

Ho trovato un altro algoritmo ma la quantità di memoria utilizzata è sempre troppo elevata...

sigh...

[Il.Socio]

Male che vada, puoi trasformare l'algoritmo ricorsivo che stai utilizzando, in forma iterativa, appoggiandoti ad una pila (aka stack).

Modificato 17 Agosto 2009 da Il.Socio

[memoryn70]

pixel_coord=[] #Array che conterrà le coordinate di tutti i pixel
for y in xrange(640):
 pixel_coord+=[(x,y) for x in xrange(360)]
#Poi puoi fare
colors=image.getpixel(pixel_coord)
#...e avrai rgb di tutti i pixel
#Puoi anche colorare tutti in un colpo facendo
image.point(pixel_coord, fill=0)

Prova a vedere una cosa del genere...

[masmil1988]

@ Socio:

Ho provato anche con una pila, ma da sempre errore di memoria insufficiente, perchè purtroppo per poter avere la funzione che annulli l'ultima operazione effettuata devo memorizzare due immagini complete, per un totale di 600x360x2 pixel, e purtroppo mShell ha soltanto il tipo numerico, che alloca lo stesso spazio per ogni numero qualunque esso sia, anche se tutto questo spazio non serve...

@ Memory:

Io ho già i colori di ogni singolo pixel, ma se devo colorare un'area devo sapere quali pixel sono racchiusi in quell'area...

Credo che più che questo debba vedere come poter gestire in maniera più intelligente tutto il resto (se possibile)...

[Il.Socio]

@ Socio:

Ho provato anche con una pila, ma da sempre errore di memoria insufficiente, perchè purtroppo per poter avere la funzione che annulli l'ultima operazione effettuata devo memorizzare due immagini complete, per un totale di 600x360x2 pixel, e purtroppo mShell ha soltanto il tipo numerico, che alloca lo stesso spazio per ogni numero qualunque esso sia, anche se tutto questo spazio non serve...

Questo e' un problema differente... Quindi ti trovi a dover fare i conti con 2 problemi di memoria!

Il primo problema, di stack overflow dell'algoritmo ricorsivo, lo risolvi usando una pila.

Per quel che riguarda il secondo problema di salvare tutti quei dati in memoria, puoi appoggiarti ad un file, cosi' da tenere in memoria sempre e solo 1 immagine e su file tieni il "backup" che ti serve per annullare l'operazione effettuata.

Eventualmente, il file lo puoi salvare nell'unita' D: (ammesso che sia possibile da mShell) cosi' facendo il file si trovera' comunque in RAM e l'accesso a quei dati sara' veloce.

Modificato 17 Agosto 2009 da Il.Socio

[masmil1988]

Questa di utilizzare un file potrebbe essere una soluzione, e a questa non avevo pensato... Mi metto all'opera :-) speriamo bene! Grazie!

[masmil1988]

Ho modificato un po' il programma utilizzando i file come suggerito e ora il problema del riempimento col metodo ricorsivo non crea problemi, finquando l'area da colorare non è troppo estesa...

Pensi che con la pila vengano usate meno risorse rispetto alla ricorsione?

[dany88]

sicuramente, con il metodo iterativo non c'è da riempire lo stack, al contrario di quello che avviene per ogni chiamata ricorsiva.

Modificato 20 Agosto 2009 da dany88

[Il.Socio]

Pensi che con la pila vengano usate meno risorse rispetto alla ricorsione?

Per la precisione, con la pila vengono usate nel complesso maggiori risorse rispetto alla ricorsione, ma la differenza fondamentale e' che la ricorsione utilizza fortemente lo stack (che e' molto piccolo), mentre gestendo "a manina" una pila si utilizza lo heap (che e' molto piu' grande).

Giusto per buttare giu' due numeri campati un "po' in aria" per esprimere il concetto...

Se un algoritmo ricorsivo ti porta via complessivamente 4kb di memoria (stack), un algoritmo iterativo ti portera' via complessivamente 5kb di memoria (di cui 50 byte di stack, ed il restante di heap) ---> quindi porta via + risorse.

Ma considera che, nei tuoi programmi, potresti avere a disposizione "solo" 5kb di stack, ma averne 30mb di heap! ---> quindi evita la ricorsione in questo caso e vai di pila!

Link per un piccolo ripasso...

http://it.wikipedia.org/wiki/Allocazione_d...a_della_memoria

Modificato 19 Settembre 2009 da Il.Socio

[masmil1988]

Perdonate l'ignoranza a riguardo ma sono cose che toccheremo fortemente quest'anno (terzo anno) e che abbiamo appena guardato in questi due anni... inoltre è la prima volta che ho a che fare con problemi di memoria

Vi ringrazio comunque!

Comprendo benissimo e vado avanti nel lavoro ;-)

Modificato 20 Agosto 2009 da masmil1988