Progetto di I.U.M. Modellazione Geometrica

SCOPO DELL'ESERCITAZIONE

Realizzare un programma che, dati un poligono semplice ed un punto P, restituisca la posizione di P rispetto al poligono.

Input

Una lista di punti (ciascun punto una coppia di coordinate) contenente i punti vertici del poligono elencati in senso antiorario. Le coordinate dei vertici sono numeri floating point.
Un ulteriore punto P (come coppia di coordinate)

Output

Uno dei quattro possibili valori:

ESTERNO se P è esterno al poligono
INTERNO se P appartiene all'interno del poligono
LATO + un numero k se P giace all'interno del k-esimo lato del poligono
VERTICE + un numero k se P coincide con il k-esimo vertice del poligono

dove la numerazione dei vertici e dei lati del poligono è come segue:

Il vertice 0-esimo è quello di coordinata x minima; se vi sono piu' vertici con x minima, il vertice 0-esimo è quello, tra essi, avente coordinata y minima
Il vertice (i+1)-esimo è quello che segue il vertice i-esimo in senso antiorario lungo il contorno del poligono, per i=0...n-1, dove n è il numero di vertici del poligono

Algoritmo

Il programma deve implementare l'algoritmo di point-location in un poligono semplice detto algoritmo della semiretta, spiegato nelle dispense del corso, capitolo 4.

Dettagli tecnici

Il programma da voi realizzato deve poter essere eseguito da linea di comando specificando come parametri:

il nome di un file contenente il poligono
un numero reale corrispondente alla x del punto P
un numero reale corrispondente alla y del punto P

e deve restituire su schermo:

una stringa s appartenente all'insieme {INTERNO, ESTERNO, LATO, VERTICE}, a seconda della posizione del punto P
nei casi s = LATO e s = VERTICE, la stringa deve essere seguita da un numero k appartenente all'intervallo [0,n-1], dove n è il numero di vertici del poligono; k corrisponde al numero d'ordine del lato o vertice sul quale cade il punto P

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.

File ausiliari forniti

Sono forniti:

Alcuni file contenenti poligoni, quali esempi di formato per il file di input (sono poligoni sia convessi che non convessi):
Il file visptloc.c permette la visualizzazione contemporanea di un poligono e di un punto, e consente di controllare visivamente la correttezza della risposta fornita dal proprio programma.
Si compila con il seguente makefile digitando: "make -f NNN visptloc", dove NNN è il nome dato al makefile.
Si lancia digitandone il nome sulla linea di comando seguito dagli stessi parametri previsti per l'esercitazione (nome file contenente un poligono + coordinate x ed y di un punto).

Scadenza e modalita' di consegna

Occorre consegnare:

I sorgenti del programma
Eventualmente makefile (nel caso che il vostro programma non si compili semplicemente con gcc nomefile.c -o nomefile o g++ nomefile.c -o nomefile)
Facoltativamente, l'eseguibile (solo se compilato per Linux)
Una brevissima documentazione contenente:
- descrizione delle strutture dati e delle primitive geometriche utilizzate e stima della loro complessita' spaziale e temporale
- stima della complessita' temporale dell'algoritmo nella vostra implementazione

Il programma deve essere scritto in ANSI C o C++.

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.

La scadenza per la consegna e':

lunedi' 22 gennaio 2000 per coloro che intendono dare l'orale l'1 febbraio
lunedi' 19 febbraio 2000 per gli altri.

NOTA BENE

L'esercitazione e' parte integrante del corso. Essa verra' valutata con un giudizio qualitativo del quale si terra' conto per il voto finale dell'esame. Per essere ammessi all'esame orale e' necessario avere consegnato l'esercitazione.

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