Laboratorio di Algoritmi Geometrici A.A. 2003-4

ESERCITAZIONE GUIDATA

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

Consideriamo tre problemi geometrici:

1. Orientamento di una terna di punti
2. Determinazione della posizione di un punto ("point location" o "point-in-polygon") rispetto ad un poligono convesso
3. 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.
Poiche' questi programmi di visualizzazione prendono lo stesso input dei programmi che dovete scrivere voi, vi consigliamo di recuperare la loro funzione di lettura.

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.

Una delle operazioni geometriche forndamentali, usata come operazione primitiva in un problemi piu' complessi.

Teoria

Dati tre punti A, B, C, da che parte giace C rispetto alla retta passante per A, B ed orientata da A verso B?

• C giace a destra di AB (la terna ABC definisce una svolta in senso orario),
• C giace a sinistra di AB (la terna ABC definisce una svolta in senso antiorario),
• C e' allineato con AB.

Prendere le coordinate di C, sostituirle nell'equazione della retta orientata AB, e vedere che segno ha il risultato.

Equazione della retta orientata AB:
(x-xA)/(xB-xA) = (y-yA)/(yB-yA)
(x-xA)(yB-yA) - (y-yA)(xB-xA) = 0

Polinomio che si ottiene sostituendo le coordinate di C:
(xC-xA)(yB-yA) - (yC-yA)(xB-xA)

• se e' minore di zero --> svolta a sinistra
• se e' maggiore di zero --> svolta a destra
• se e' uguale a zero --> allineati

Equivale al segno del determinante:

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

Complessita' temporale costante in quanto e' coinvolto un numero fissato di operazioni.

Esercizio

Scrivere un funzione C che ritorni il segno del determinante ovvero l'orientamento della terna di punti.

Per controllare se funziona

E' dato il programmino vis3pt che prende in input nell'ordine le coordinate di tre punti A, B, C e visualizza la retta AB ed il punto C. L'orientamento della retta e' reso sfumando da A nero verso B blu.

Si compila con: make vis3pt (qui il makefile). Si esegue con ./vis3pt xA yA xB yB xC yC dove gli argomenti in linea di comando sono le coordinate dei tre punti.
Esempio: ./vis3tp 4 4 -1 3 2 5 mostra che C=(2,5) e' a destra della retta AB.
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. Classificare la posizione di Q rispetto al poligono.

• Q giace dentro il poligono se Q giace a sinistra di tutte le rette orientate passanti per lati del poligono (la retta orientata da P(i) a P(i+1), per ogni i da 1 a n).
• Q giace fuori dal poligono se Q giace a destra di almeno una delle rette orientate sopra dette.
• Q giace sul contorno del poligono se Q e' allineato con almeno una delle rette sopra dette, e giace a sinistra delle rimanenti. In particolare:
  • se Q e' allineato con una e a sinistra delle altre, allora Q giace all'interno di un lato
  • se Q e' allineato con due e a sinistra delle altre, Q coincide con un vertice
  • non sono possibili altri casi.

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

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

Input:

• Un file contenente i punti vertici del poligono, 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.
  Esempio di file di input: poli10.txt
• Un ulteriore punto Q anche questo espresso come coppia di coordinate floating point.

Output:

• ESTERNO se Q è esterno al poligono
• INTERNO se Q appartiene all'interno del poligono
• LATO se Q giace all'interno di un lato
• VERTICE se Q coincide con un vertice del poligono

Per controllare se funziona

E' dato il programmino visptloc che prende in input un file contenente un poligono e le due coordinate di punto e li visualizza.

Si compila con make visptloc (stesso makefile di prima).
Si lancia digitando ./visptloc NOMEFILE X Y dove NOMEFILE e' il nome del file contenente il poligono e X, Y sono le coordinate del punto.
Nel caso del file poli10.txt per esempio 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 internamente a un lato, e naturalmente qualsiasi punto scritto nel file stesso e' un vertice!

(3) Test di intersezione fra due segmenti

Dati due segmenti AB e CD, controllare se si intersecano.

Due segmenti AB e CD si intersecano se e solo se

• i punti A e B giacciono da parti opposte rispetto alla retta di supporto del segmento CD, e
• i punti C e D giacciono da parti opposte rispetto alla retta di supporto di AB.

Si tratta quindi di calcolare il segno di quattro svolte. Complessita' temporale costante.

Esercizio

Scrivere un programma che, dati due segmenti, controlla se questi si intersecano.

Per controllare se funziona

E' dato il programmino visintsg che prende in input un file contenente due segmenti e li visualizza.

Si compila con make visintsg (stesso makefile di prima).
Si lancia digitando ./visintsg NOMEFILE dove NOMEFILE e' il nome del file contenente i due segmenti. Esempi:

• inters1.txt e inters2.txt (questi si intersecano)
• nonint1.txt e nonint2.txt (questi non si intersecano)

NON e' richiesto che il vostro programma tratti i casi particolari, come i seguenti:

• seg_v.txt (due segmenti con un vertice comune)
• seg_t.txt (un vertice di un segmento e' interno all'altro segmento)

Casi particolari

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

In realta' il test non si puo' esaurire con una semplice risposta booleana: si intersecano / non si intersecano. Bisogna distinguere piu' casi:

1. i due segmenti sono disgiunti
2. i due segmenti si intersecano propriamente: l'intersezione e' un punto interno per entrambi i segmenti
3. i due segmenti si toccano condividendo un estremo comune
4. i due segmenti si toccano perche' uno degli estremi di un segmento e' interno all'altro segmento

Nel caso 1, si ha che o A e B definiscono entrambi una svolta non nulla e dello stesso segno rispetto a CD, oppure viceversa C e D definiscono una svolta non nulla e dello stesso segno rispetto a AB.

Nel caso 2, A e B definiscono entrambi una svolta non nulla e di segno opposto rispetto a CD, e lo stesso si ha per C e D rispetto a AB.

Il caso 3 si puo' discriminare inserendo un controllo preliminare sulle coordinate dei punti estremi dei due segmenti. Comunque si avrebbe che uno ed uno solo fra A e B definisce una svolta nulla rispetto a CD, e uno ed uno solo tra C e D definisce una svolta nulla rispetto a AB.

Nel caso 4, si ha (supponendo che sia AB a toccare l'interno di CD con un suo estremo) che uno ed uno solo fra A e B definisce una svolta nulla rispetto a CD, ed i punti C e D definiscono svolte non nulle e di segno opposto rispetto a AB.

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

Note

Se il risultato del determinante (per il calcolo della svolta) e' molto piccolo in valore assoluto, puo' succedere che gli sia attribuito un segno errato a causa di errori di approssimazione dovuti all'aritmetica floating point. Nel caso, si puo' assumere una tolleranza epsilon>0 (molto piccola) e considerare come uguali a zero tutte le quantita' che in valore assoluto sono minori di epsilon.