Progetto di I.U.M. Modellazione Geometrica

• Scopo dell'esercitazione
• Formato dei file di input e di output
• File ausiliari forniti
• Scadenza e modalita' di consegna

Scopo dell'esercitazione

A parte sono fornite informazioni specifiche a seconda di quale dei due algoritmi avete scelto di implementare:

• algoritmo di Graham
• algoritmo QuickHull

Il programma da voi realizzato deve accettare un insieme di punti da un file e restiruire il loro guscio convesso su un altro file. L'eseguibile deve poter essere lanciato specificando come parametri i nomi dei file di input e di output. Ovvero digitando una linea del tipo:

nome_eseguibile nome_file_input nome_file_output

Non e' richiesto che il programma faccia alcun tipo di visualizzazione grafica dei risultati. A parte e' fornito un programmino che serve a visualizzare l'input e l'output del vostro programma.

Formato dei file di input e di output

Il guscio convesso deve essere restituito in output nello stesso formato descritto per il file di input. In questo caso pero' le coppie di float corrispondono alle coordinate dei vertici del guscio convesso, ordinati in senso antiorario lungo il contorno del poligono.

File ausiliari forniti

• Il file rndgen.c implementa un generatore di insiemi di punti casuali, utilizzabili come input per testare il vostro programma.

  Si compila digitando semplicemente gcc rndgen.c -o rndgen.
  Si lancia digitando:

  rndgen n mi ma seed

  con n intero positivo, mi,ma float, e seed (opzionale) intero.
  Genera n punti con coordinate x ed y contenute nell'intervallo [mi,ma]. Il parametro opzionale seed serve a "rimescolare" il generatore di numeri casuali. I punti generati vengono scritti su standard output, da redirezionare su file a vostro piacere.

• Il file vishull.c permette la visualizzazione contemporanea di un insieme di punti e del suo guscio convesso.

  Si compila con il makefile che gia' avete, aggiungendo le seguenti due linee:

  vishull: vishull.c
          $(CC) $(FLAGS) -g $(INCLUDE) vishull.c $(LDLIBS) -o vishull
  

  (attenzione: gli spazi all'inizio della seconda linea devono essere un solo carattere tabulazione!)

  Si lancia digitando:

  vishull xxx.pt xxx.ch

  dove xxx.pt e' un file di punti e xxx.ch (opzionale) e' il file contenente il relativo guscio convesso. Se il secondo parametro manca, viene visualizzato solo il file di punti.
  Il guscio convesso ed i suoi vertici sono marcati in nero, i punti dell'insieme sono marcati in rosso, piu' piccoli (in modo tale che i vertici del guscio convesso appaiano come un segno rosso sovrapposto ad un segno nero).

Scadenza e modalita' di consegna

• sorgenti del programma
• eventualmente makefile (nel caso che il vostro programma non si compili semplicemente con gcc nomefile.c -o nomefile)
• una brevissima documentazione contenente:
  • descrizione delle strutture dati utilizzate e stima della loro complessita' spaziale
  • stima della complessita' temporale del calcolo del guscio convesso nella vostra implementazione

La consegna puo' avvenire su dischetto oppure per posta elettronica all'indirizzo magillo@disi.unige.it. Per quanto riguarda la documentazione, e' possibile consegnarla sia in copia cartacea, che in forma elettronica (su dischetto o per email).

In ogni caso, precisare i nomi dei componenti del gruppo, e quale dei due algoritmi e' stato implementato.

La scadenza per la consegna e':

• venerdi' 21 gennaio 2000 per coloro che intendono dare l'orale il 31 gennaio
• venerdi' 11 febbraio 2000 per gli altri.

NOTA BENE

L'esercitazione e' valida per il solo anno accademico corrente. In particolare la presente esercitazione e' valida fino all'appello di febbraio 2001 incluso.