Homework 3
Tiro al Bersaglio
Corso di Fondamenti di Informatica II
BIAR2 (Ing. Informatica e Automatica) e BSIR2 (Ing. dei Sistemi Informatici)
A.A. 2013/2014
Si vuole risolvere con un algoritmo efficiente il seguente problema: dato un bersaglio poligonale convesso, e data una sequenza di punti nel piano, determinare per
ciascuno dei punti della sequenza se esso “colpisce” (interseca) il bersaglio, oppure
no.
Si ricordi che un poligono è detto convesso se il segmento di linea tracciato tra
due qualunque suoi punti è interamente contenuto nel poligono stesso. La Figura 1
mostra due poligoni, di cui solo quello a sinistra è convesso.
Il poligono convesso sarà fornito in input attraverso la sequenza antioraria dei
suoi vertici, a partire dal vertice ad ordinata massima (vedi Figura 2).
Figura 1: Il poligono di sinistra è convesso, quello di destra non lo è
Un approccio inefficiente. È possibile risolvere il problema in maniera semplice,
ma non molto efficiente, attraverso il seguente algoritmo. Sia P il poligono convesso
di input, dato secondo la sequenza p0 , p1 , . . . , pN −1 dei suoi vertici, percorsi in senso
antiorario e a partire dal vertice con coordinata y massima; per comodità definiamo
anche pN := p0 .
Osserviamo ora che se q è un qualunque punto contenuto nel poligono, allora tutte
le terne ordinate (pi , pi+1 , q) con 0 ≤ i < N saranno ordinate in senso antiorario.
Viceversa, se il punto q è al di fuori del poligono, allora esiste una terna (pi , pi+1 , q)
1
2
p0
p1
p4
p2
p3
Figura 2: Rappresentazione standard di un poligono convesso
ordinata in senso orario. Si veda la Figura 3 per un’illustrazione. Questo dà luogo
al seguente algoritmo:
boolean contenutoIn(punto q, poligono P ):
Per i = 0, 1, . . . , N − 1:
Se (pi , pi+1 , q) è ordinata in senso orario, restituisci false
Restituisci true.
Decidere se una particolare terna (a, b, c) di punti è ordinata in senso orario oppure
no è semplice: è sufficiente calcolare1 il determinante


xa ya 1
DET(a, b, c) := det  xb yb 1 
xc y c 1
Tale determinante è negativo quando la terna è in senso orario, positivo quando la
terna è in senso antiorario (e nullo quando i tre punti giacciono su un’unica retta).
Ad esempio, se a = (0, 0), b = (1, 0), c = (0, 1) (dove la prima componente di
ogni punto indica l’ascissa x e la seconda l’ordinata y), allora DET(a, b, c) = 1, a
riprova del fatto che la terna (a, b, c) è orientata in senso antiorario.
Si noti che i punti sul bordo del poligono sono considerati parte del poligono.
Un algoritmo efficiente. L’algoritmo appena visto ha costo O(N ), dove N è il
numero di vertici del poligono, a causa del ciclo principale, che itera su tutti i vertici.
Se si volesse verificare l’appartenza o meno di Q punti al poligono, il costo totale
sarebbe quindi O(Q · N ). Mostriamo invece come si possa preprocessare il poligono
in tempo O(N ) in modo da poter rispondere al problema del contenimento in tempo
O(log N ) per punto, per un tempo totale di O(N + Q log N ).
1
Chi disgraziatamente non sapesse calcolare il determinante di una matrice 3 × 3 può consultare
http://it.wikipedia.org/wiki/Regola di Sarrus o un qualunque testo di algebra lineare.
3
p4
p4
q
q
p3
p3
Figura 3: La terna (p3 , p4 , q) è percorsa in senso antiorario nell’esempio a sinistra, e
in senso orario nell’esempio a destra
Si ricordi che il poligono è descritto in senso antiorario e a partire dal vertice con
y massima. Ciò implica che, percorrendo la sequenza dei vertici, le coordinate y dei
vertici prima decrescono e poi crescono (Figura 4).
p0
p1
p4
p2
p3
Figura 4: Il poligono suddiviso in parte sinistra (y decrescenti, colore rosso) e parte
destra (y crescenti, colore blu).
In una fase di preprocessamento, determiniamo il vertice più “in basso” del
poligono (pB ), dal quale le coordinate y iniziano di nuovo a crescere. Ciò divide
il poligono in una parte “sinistra” (coordinate y decrescenti) e una parte “destra”
(coordinate y crescenti). Quindi, se il preprocessamento è stato fatto in maniera
opportuna, possiamo assumere che i punti del poligono siano stati posti in un array
e che si sia determinato un indice B dell’array che stabilisce dove termina la parte
sinistra del poligono e dove inizia la parte destra (nell’esempio di Figura 4 si ha
B = 3).
A questo punto procediamo nel considerare i punti dei quali vogliamo verificare
il contenimento nel poligono. Per ciascuno di questi, usiamo il seguente metodo.
Sia q il punto da verificare. Ovviamente se la coordinata y di q è maggiore della
massima coordinata y del poligono, o minore della minima coordinata y del poligo-
4
no, il punto q è al di fuori del poligono; questa verifica, se implementata in maniera
opportuna, può essere effettuata in tempo costante. Nel caso contrario, se immaginiamo di tracciare una linea orizzontale attraverso il punto q, essa intersecherà un
lato nella parte sinistra del poligono e un lato nella parte destra (Figura 5). Il punto
q è all’interno del poligono se e solo se esso è contenuto tra questi due lati. Ma per
il modo in cui il poligono è stato memorizzato, i due lati in questione possono essere
trovati in tempo O(log N ) attraverso due ricerche binarie, in quanto le coordinate
y in ciascuna parte del poligono sono ordinate. Dopo aver determinato i due lati
di interesse, è semplice verificare in tempo costante se il punto q cade tra di essi,
usando la primitiva DET discussa precedentemente.
p0
p1
p4
q
p2
p3
Figura 5: Una linea orizzontale lungo il punto q interseca il poligono in un lato della
parte sinistra (lato p1 p2 ) e un lato della parte destra (lato p3 p4 )
Avvertenza importante. Per memorizzare le coordinate dei vertici e dei punti
in questo homework è imprescindibile l’uso del tipo di dati Java long (64 bit)
anziché int (32 bit), in quanto altrimenti le moltiplicazioni necessarie nel calcolo
della funzione DET incorrerebbero in degli errori di trabocco (overflow).
Formato di Input. L’input è formato da:
• Una riga contenente il numero N di vertici del poligono (con 3 ≤ N ≤ 10000).
• N righe, ciascuna contenente una coppia di interi x, y (separati da uno spazio),
con 0 ≤ x, y ≤ 109 . Ciascuna di queste righe descrive un vertice del poligono
convesso, con coordinate (x, y). I vertici sono elencati in ordine antiorario e a
partire dal vertice p0 con coordinata y massima. Nessun lato del poligono
è parallelo all’asse x. In altre parole, ciascun vertice pi del poligono
ha coordinata y diversa da quella del vertice successivo pi+1 (questo
vale anche per la coppia (pN −1 , p0 )).
• Una riga contenente il numero Q di punti dei quali si vuole verificare il
contenimento nel poligono (con 1 ≤ Q ≤ 10000).
5
• Q righe, ciascuna contenente una coppia di interi x, y (separati da uno spazio),
con 0 ≤ x, y ≤ 109 . Ciascuna di queste righe descrive un punto q con coordinate (x, y) del quale si vuole verificare il contenimento nel poligono. Questa
sequenza di punti potrebbe contenere duplicati.
Formato di Output. L’output è formato da Q righe, una per ciascun punto q di
cui si chiedeva di verificare il contenimento. Ciascuna riga contiene la stringa true o
false a seconda che il punto q sia, rispettivamente, contenuto oppure non contenuto
nel poligono. Se il punto q è sul bordo del poligono, è da considerarsi
contenuto in esso.
Esempio di input.
3
0
0
3
5
2
2
0
0
2
4
0
1
0
1
0
2
3
Output corrispondente.
false
true
true
true
false
Limiti e requisiti
Percentuale di istanze di test che è necessario risolvere correttamente: 60%.
Limite al tempo di esecuzione:
• istanze con Q < 750: 1 secondo
• istanze con 750 ≤ Q ≤ 10000: 2 secondi
Limite alla lunghezza del codice Java: 48 Kb.
Attenzione!
L’uso di offuscatori di codice non è ammesso. Codice molto simile a quello generato
da un offuscatore di codice Java sarà escluso dalla valutazione e/o squalificato, anche
a posteriori, a discrezione del docente.