Topic: problemi con un esercizio  (Letto 68 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline simone13

  • python unicellularis
  • *
  • Post: 6
  • Punti reputazione: 0
    • Mostra profilo
problemi con un esercizio
« il: Dicembre 01, 2018, 12:58 »
buongiorno. dovrei risolvere questo esercizio ma non ho idea di come ragionarci, poiché risulta difficile anche a chi ha delle basi più solide delle mie, vorrei sapere se qualcuno ha delle idee du come procedere.. non sto chiedendo il codice implementato ma se possibile un consiglio su come ragionare. grazie per l'aiuto.

l'esercizio è il seguente:
'''
Abbiamo una immagine  .PNG .
L'immagine presenta, su uno sfondo nero ( vale a dire di colore (0,0,0)),
segmenti di colore bianco (vale a dire (255,255,255)) orizzontali e verticali di diversa lunghezza.
I segmenti, in alcuni casi, nell'incrociarsi creano rettangoli.
Siamo interessati a trovare quei rettangoli di altezza e larghezza almeno 3
(compreso il bordo, quindi con la parte nera alta e larga almeno 1 pixel)
e che, tranne il bordo completamente bianco, presentano tutti i pixel al loro interno di colore nero.
A questo scopo vogliamo creare una nuova immagine identica alla prima se non per il
fatto che questi rettangoli vengono evidenziati.
Il bordo di questi rettangoli deve essere di colore verde (vale a dire (0,255,0)) e
i pixel interni devono essere di colore rosso (vale a dire (255,0,0)).

Scrivere una funzione es1(fimg,fimg1) che, presi in input gli indirizzi  di due file .PNG,
legge dal primo l'immagine del tipo descritto sopra e salva nel secondo l'immagine
con i rettangoli evidenziati.
La funzione deve infine restituire  il numero di rettangoli che risultano evidenziati.

Per caricare e salvare i file PNG si possono usare load e save della libreria immagini.

NOTA: il timeout previsto per questo esercizio รจ di 1 secondo per ciascun test.

ATTENZIONE: quando consegnate il programma assicuratevi che sia nella codifica UTF8
(ad esempio editatelo dentro Spyder o usate Notepad++)

ATTENZIONE: non sono permesse altre librerie.
'''

Offline RicPol

  • python sapiens sapiens
  • ******
  • Post: 2.821
  • Punti reputazione: 9
    • Mostra profilo
Re:problemi con un esercizio
« Risposta #1 il: Dicembre 01, 2018, 16:13 »
Mah. O c'è qualcosa che non ci dici, o questo è uno di quegli esercizi che mi fanno dubitare molto delle capacità dell'insegnante. Il problema è che dal punto di vista informatico è banale, ma ovviamente l'algoritmo è complesso da trovare. Tra l'altro, nel caso generale l'algoritmo dovrebbe saper distinguere casi come questi:

 --------       --------        ----------
 |      |       |      |        |        |
 |   ---|----   |   ---|---     |  ----  |
 |   |a |  b|   |   |a |  |     |  | a|  |
 |   ---|----   |   |  |  |     |  |  |  |
 |      |       --------  |     |  ----  |
 --------           |     |     |        |
                    -------     ----------

(Secondo la definizione di "rettangolo" dell'esercizio, nella figura a sinistra ci sono 2 rettangoli, non 3. Nelle altre figure c'è 1 rettangolo, non 2)

Non c'è niente di difficile dal punto di vista di python, una volta che ti sei studiato un algoritmo con carta e penna. Ma allora la domanda è, stai seguendo un corso di topologia o un corso di informatica?

Comunque, pazienza e coraggio. Non ti resta che metterti lì con un bel quaderno a quadretti e una matita, e venir fuori con un algoritmo. Ci sono diverse idee che puoi tentare... cerca di scomporre il problema in parti... per esempio, come trovare tutti i vertici (cioè i punti dell'immagine da cui partono almeno 2 linee)... poi potresti percorrere ciascun vertice nella sua "direzione" e vedere se c'è un percorso che chiude il rettangolo...
Per esempio, immagina di avere un'immagine così (dove i punti sono neri e gli asterischi sono bianchi):

 .....................
 .*********...........
 ...*...*.....*.......
 ...*...*********.....
 ...*...*.....*.......
 ...*****.....*.......
 .......*******.......
 .....................

La prima fase dell'algoritmo potrebbe rinoscere questi vertici:

 .....................
 .**A***B**...........
 ...*...*.....*.......
 ...*...C*****D**.....
 ...*...*.....*.......
 ...E***F.....*.......
 .......G*****H.......
 .....................

E dire che in A ci sono due vertici (in direzione "sud-ovest" e "sud-est"), in B ci sono due vertici, in D ce ne sono 4 etc etc.
La seconda fase dell'algoritmo potrebbe esaminare ciascun vertice e camminare lungo le linee finché non trova il prossimo vertice *nella direzione giusta*. Per esempio, se comincio a esaminare il vertice "sud-ovest" in A, e cammino in direzione sud, allora devo camminare fino al primo vertice in direzione "nord-ovest", e così via. L'algoritmo vede che partendo dal vertice "sud-ovest" in A non c'è nessun rettangolo perché il successivo vertice (in E) non ha la direzione voluta.
Quando invece l'algoritmo passa a esaminare il vertice in A "sud-est", trova il rettangolo A-B-F-E esaminando questi punti in successione:

 .....................
 .**A<<<B**...........
 ...v...^.....*.......
 ...v...C*****D**.....
 ...v...^.....*.......
 ...E>>>F.....*.......
 .......G*****H.......
 .....................

Siccome A è un vertice "sud-est", l'algoritmo sa che procedendo inizialmente verso sud, c'è un rettangolo solo se trova in successione:
- un vertice in direzione "nord-est"
- un vertice "nord-ovest"
- un vertice "sud-ovest"
- e poi torna al vertice iniziale
Seguendo i punti dal vertice A in direzione sud, l'algoritmo trova
- prima il vertice E (direzione corretta)
- poi il vertice F (direzione corretta)
- poi il vertice C (direzione sbagliata, ma può andare avanti e quindi va avanti)
- poi il vertice B (direzione corretta)
- e poi di nuovo il vertice A
e quindi ne consegue che esiste un rettangolo AEFB. Quando trovi un rettangolo segni le coordinate.
Nota che questo algoritmo non ti difende dai casi di rettangoli interamente contenuti in altri rettangoli... Dovrai fare un check apposta per eliminarli, successivamente.

Una volta che hai trovato tutti i rettangoli in questo modo, il resto è triviale (colorarli, etc).

Naturalmente ci sono altri algoritmi possibili, e poi ottimizzazioni, scorciatoie, furbate varie. L'importante è capire come fare la cosa con carta e penna, e poi trasportarla in codice.
« Ultima modifica: Dicembre 01, 2018, 16:15 da RicPol »

Offline simone13

  • python unicellularis
  • *
  • Post: 6
  • Punti reputazione: 0
    • Mostra profilo
Re:problemi con un esercizio
« Risposta #2 il: Dicembre 01, 2018, 17:24 »
ti ringrazio per il preziosissimo consiglio, a proposito della domanda che mi hai fatto, tutto quello che so l'ho scritto nel post, purtroppo avendo iniziato a studiare informatica all'inizio dei corsi senza avere delle basi mi risulta piuttosto difficile ragionare in questi termini, comunque grazie ancora per il consiglio proverò a implementare il mio algoritmo seguendo questa logica di ragionamento.