Laboratorio di Algoritmi Geometrici A.A. 2004-5

ESERCITAZIONE GUIDATA

Argomento: calcolo dell'orientamento di una terna di punti nel piano e sue applicazioni.

Consideriamo tre problemi geometrici:

• Orientamento di una terna di punti
• Determinazione della posizione di un punto ("point location" o "point-in-polygon") rispetto ad un poligono convesso
• Test se due segmenti si intersecano

Algoritmi per problemi 2 e 3 usano 1 come operazione ausiliaria.

Nota: i programmi che scrivete devono occuparsi solo del calcolo del risultato. Separatamente sono dati programmi grafici appositi per visualizzare la configurazione in input e controllare a vista se il risultato e' giusto.

Quest'esercitazione guidata consta di tre parti di cui la (1) e' necessaria per le altre due, mentre (2) e (3) sono indipendenti tra loro e se ne puo' fare una a scelta.

Esercizio

Scrivere una funzione C che abbia la forma:

int ThreePointTurn(float x1, float y1, float x2, float y2,
                   float x3, float y3)

• -1 se la terna di punti A=(x1,y1), B=(x2,y2), C=(x3,y3) definisce una svolta a sinistra
• 1 se la terna A, B, C definisce una svolta a destra
• 0 se i tre punti A, B, C sono allineati

Teoria

A lezione avete visto che questo equivale al calcolo del segno del determinante:

| yB-yA  yC-yA |
| xB-xA  xC-xA |

Complessita' temporale: O(1), come visto a lezione.

Per controllare se funziona

Aggiungete la vostra funzione al programma test1.c (esiste gia' l'intestazione con il corpo della funzione vuoto).

Il programma test1:

• prende in input nell'ordine le coordinate di tre punti A, B, C
• mostra la spezzata poligonale A-B-C con i tre punti resi nei tre colori A rosso, B verde, C blu
• inoltre mostra come titolo della finestra il valore di ritorno della chiamata alla funzione ThreePointTurn

Si compila con: make PROG=test1 (qui il makefile).
Si esegue con ./test1 xA yA xB yB xC yC dove gli argomenti in linea di comando sono le coordinate dei tre punti.
Esempio: ./test1 4 4 -1 3 2 5

Fate delle prove con tutte le configurazioni possibili: terne allineate, punti coincidenti, punto C interno al segmento AB...
Assicuratevi che questo funzioni prima di passare agli altri esercizi!

Teoria

Siano P1, P2, P3, ..., P(n) i vertici di un poligono convesso, ordinati in senso antiorario.
Sia Q un altro punto. La posizione di Q rispetto al poligono puo' essere:

• dentro se Q giace a sinistra di tutte le rette orientate passanti per lati del poligono (ogni terna P(i), P(i+1), Q svolta a sinistra per i=1..n)
• fuori se Q giace a destra di almeno una delle rette orientate sopra dette.
• su un lato se Q e' allineato con una delle rette sopra dette, e giace a sinistra delle rimanenti.
• su un vertice se Q e' allineato con due delle rette e giace a sinistra delle rimanenti

Complessita' temporale: O(n) dove n e' il numero di vertici del poligono. Nel caso peggione (punto interno o sul contorno), si fanno esattamente n chiamate alla funzione che controlla l'orientamento di una terna di punti.

Esercizio

Scrivere una funzione C che abbia la forma:

int PointInPolygon(int n, float xp[], float yp[], float xq, float yq)

• 0 se Q e' esterno al poligono
• 1 se Q e' interno al poligono
• 2 se Q e' su un lato
• 3 se Q e' su un vertice

Per controllare se funziona

Aggiungete la vostra funzione al programma test2.c (esiste gia' l'intestazione con il corpo della funzione vuoto).

Il programma test2:

• prende in input un file contenente un poligono e le due coordinate di un punto
• mostra il poligono in nero e il punto in rosso
• inoltre mostra come titolo della finestra il valore di ritorno della chiamata alla funzione PointInPolygon

Si compila con make PROG=test2 (stesso makefile di prima).
Si esegue con ./test2 NOMEFILE X Y dove NOMEFILE e' il nome del file contenente il poligono e X, Y sono le coordinate del punto.
Esempio: ./test2 poli10.txt 12 2
Per esempio usando come file poligono poli10.txt, i punti (0,0) (2,2) (3,1) sono interni, (-2,-3) (6,6) sono esterni, (-2,3) (3,4.5) (4.5 2.5) giacciono su un lato, e naturalmente qualsiasi punto scritto nel file stesso e' un vertice!

Il file contenente il poligono elenca i vertici ciascuno come coppia di coordinate floating point.
Il poligono deve essere convesso e i vertici devono essere elencati in senso antiorario. Se mancano queste condizioni non e' richiesto che il programma funzioni.

Teoria

Avete visto a lezione che il controllo se due segmenti AB e CD si intersechino richiede di esaminare l'orientamento delle quattro terne di punti formate dai due estremi di un segmento con un estremo dell'altro segmento.

Complessita' temporale: costante perche' si tratta di calcolare il segno di quattro svolte.

Esercizio

Scrivere una funzione C che abbia la forma:

int SegmentIntersect(float xa1, float ya1, float xa2, float ya2,
                     float xb1, float yb1, float xb2, float yb2)

• 0 se i due segmenti di estremi (xa1,ya1)-(xa2,ya2) e (xb1,yb1)-(xb2,yb2) sono disgiunti
• 1 se si intersecano propriamente (l'intersezione e' un punto interno per entrambi i segmenti)
• 2 se si toccano perche' uno degli estremi di un segmento e' interno all'altro segmento (chiamata anche "giunzione a T")
• 3 se si toccano condividendo un estremo comune

Nota: assumiamo che i due segmenti non giacciano sulla stessa retta di supporto.

Per controllare se funziona

Aggiungete la vostra funzione al programma test3.c (esiste gia' l'intestazione con il corpo della funzione vuoto).

Il programma test3:

• prende in input otto coodinate che definiscono i quattro estremi di due segmenti
• mostra i due segmenti colorati in rosso e in verde
• inoltre mostra come titolo della finestra il valore di ritorno della chiamata alla funzione SegmentIntersect

Si compila con make PROG=test3 (stesso makefile di prima).
Si lancia digitando ./test3 xa1 ya1 xa2 ya2 xb1 yb1 xb2 yb2 dove le otto coordinate definiscono due segmenti (xa1,ya1)-(xa2,ya2) e (xb1,yb1)-(xb2,yb2).
Esempi:
./test3 -3 2 -1 4 -3 6 0 -1 si intersecano
./test3 -4 -1 -3 -2 3 -2 5 1 non si intersecano
./test3 -3 2 -4 1 -4 1 0 -3 segmenti con un vertice comune
./test3 -3 2 -1 4 -2 3 0 0 un vertice di un segmento e' interno all'altro segmento (giunzione a T)

Segmenti collineari

Questa parte non e' richiesta, ma puo' essere un buon esercizio pensarci sopra.

Se i due segmenti hanno la stessa retta di supporto, quali sono i casi possibili e come si discriminano in base alle svolte?