In alcuni casi possiamo costruire un algoritmo più e ciente dell'algoritmo 1, ciò dipende da come possiamo esprimere la crescita dell'area di un data regione tra segmenti rispetto alla trasformazione di tempo t. In un campo vettoriale orizzontale si può ottenere un algoritmo più rapido dell'algoritmo precedente e che è garantito che trovi un minimo, ovvero la trasformazione di S che genera la minore intersezione possibile con T . Ecco l'algoritmo:
Algorithm 2 Metodo iterativo dei breakpoint
Traforma S in modo tale che S(0) sia prima di T rispetto alle linee di campo. Trova gli insiemi di segmenti di frontiera Sb e Tb.
Inizializza un insieme vuoto di breakpoint B. for ogni a ∈ Sb do
for ogni b ∈ Tb do
if R(a, b) è non vuoto then
Cerca un valore temporale t in cui a e b iniziano ad intersecarsi. Cerca un valore temporale t0 in cui a e b niscono di intersecarsi.
Segna i breakpoint rispettivamente come primario e secondario. Salva i valori t e t0 come i breakpoint in B.
end if end for end for
Ordina i breakpoint in B in ordine ascendente.
Inizializza la più piccola intersezione trovata, min = ∞. Inizializza una funzione area di intersezione, Int(x) = 0. for ogni breakpoint t ∈ B do
if t è un breakpoint primario then
Una nuova regione tra i segmenti sta "crescendo". Trova una funzione A(x) che ri ette questo fatto.
else if t è un breakpoint secondario then
Una regione tra i segmenti già esistente sta "cambiando". Trova una funzione A(x) che ri ette questo fatto.
end if
Poni Int(x) = Int(x) + A(x).
Poni tmp = il minimo di Int(x) in [t, t0]dove t0 è il breakpoint successivo.
(ignorando casi particolari ad esempio per accertare che S sia all'interno della regione del campo vettoriale). if tmp < min then Poni min = tmp. end if end for return min.
L'algoritmo 2 si compone di tre fasi fondamentali: colleziona, ordina ed itera i breakpoint. Nella prima fase, i breakpoint vengono catalogati come primari o secondari, e questo si renderà utile nella terza fase dove risiede il cuore dell'algoritmo. A dierenza dell'algoritmo1 i breakpoint vengono ordi- nati; in questo modo la terza fase diventa semplice.
Risulta che non c'è bisogno di usare il teorema dell'intersezione ripetutamente perchè l'insieme dei breakpoint coinvolti in t1 è un sottoinsieme dell'insieme dei breakpoint in t2, con t2> t1.
Per utilizzare l'algoritmo 2 dobbiamo fare qualche calcolo in più rispetto all'algoritmo 1. Trovare i breakpoint non è diverso da come lo si faceva per l'algoritmo 1. La parte nuova consiste nel trovare funzioni che ci dicono come cambia l'area di una regione durante la traslazione.
Nella guraB.4 sono mostrati i vari casi di una regione tra segmenti.
Si può dimostrare che tra il primo ed il secondo breakpoint la regione tra i segmenti è un'area triango- lare, mentre dopo il secondo breakpoint diventa un'area trapezoidale. Cerchiamo di descrivere queste aree in funzione del tempo di traslazione.
L'area del trapezoide è molto semplice da descrivere: è semplicemente l'area di un triangolo più una semplice espressione lineare che si basa sull'altezza del trapezio.
69
Figura B.4: Un'immagine di Nielsen and Odgaard(2003). (a) La regione tra i segmenti è vuota no al primo breakpoint. (b) L'area cresce in modo quadratico tra i due breakpoint. (c) Al secondo breakpoint cambia la crescita dell'area. (d) L'area cresce in modo lineare.
Se h è l'altezza del triangolo e del trapezio, c è la base del triangolo e t00 è la base minore del trapezio
rettangolo, abbiamo:
As(t00) = ht00+
hc 2 ,
dove As è l'area della regione tra i segmenti dopo il secondo breakpoint t00.
Il ragionamento per l'area triangolare tra il primo ed il secondo breakpoint è un po' più di cile. L'osservazione importante è che l'altezza del triangolo h0 (al breakpoint t0) deve essere h
ct
0 (deriva dalle
relazioni di similitudine tra triangoli). Segue facilmente: Ap(t0) = h0t0 2 = h 2c(t 0)2,
dove Ap è l'area della regione tra i segmenti tra il breakpoint primario e quello secondario.
Ora, le funzioni qua sopra dipendono dai valori di traslazione t0 e t00 che vengono posti a zero nel primo
e secondo breakpoint rispettivamente.
Per sommare queste funzioni dobbiamo riformularle utilizzando lo stesso oset t. Poniamo tp, ts
le distanze di traslazione ai breakpoint rispettivamente primario e secondario (i valori di tempo dei breakpoint nell'algoritmo) e sostituiamo nelle formule precedenti le seguenti espressioni: t0 = t − t
p,
t00= t − ts. Allora le formule diventano:
Ap(t) = h 2c(t − tp) 2= h 2c(t 2− 2t pt + t2p) = h 2ct 2−htp c t + ht2 p 2c , As(t) = h(t − ts) + hc 2 = ht − hts+ hc 2 .
Sommando questo tipo di funzioni si ottengono comunque espressioni al più quadratiche, di cui è sem- plice calcolare il minimo.
Osserviamo che sebbene i calcoli appena fatti riguardino la traslazione orizzontale, il ragionamento si applica in modo analogo alla traslazione verticale. In generale, utilizzando appropriati calcoli di aree si può estendere alla traslazione in qualsiasi direzione. Quello che restringe le forme ad essere poligoni sono i calcoli delle aree: utilizzando altre forme come ad esempio cerchi, potrebbe non essere possibile sommare le funzioni in modo e ciente, complicando così il calcolo dell'intersezione ad un generico breakpoint, e quindi anche la ricerca del minimo. Questo è anche uno dei problemi più grossi della sezione successiva che studia le rotazioni.
B.0.4 Rotazione di poligoni
Arontiamo il problema di trovare la rotazione ottima di un poligono, ovvero: di che angolo un poligono deve essere ruotato per ottenere la minima intersezione possibile con tutti gli altri poligoni.
In questo caso si presentano due problemi:
• I lati del poligono non possono essere utilizzati come segmenti di frontiera, poichè alcuni lati possono avere parti sia di segno positivo che negativo. Questi lati sono facili da identi care e possono essere divisi in due. Osserviamo che i segmenti di frontiera neutri sono punti singolari, poichè una linea retta non può mai sovrapporsi ad una linea di campo.
• Di cilmente è possibile posizionare le linee di taglio senza dividere qualche poligono (in modo particolare quello che deve essere ruotato). Queste forme vìolano quindi la condizione secondo la quale tutte le forme devono essere contenute dentro la regione del campo vettoriale. Questo problema non è facilmente risolvibile. Nella trattazione seguente assumeremo che le linee di taglio siano coincidenti e non si sovrappongano a nessuna forma. Una soluzione pratica potrebbe essere quella di dividere tutti i poligoni in due parti nella linea di taglio, ma questo non risulta poi di facile gestione.
Nonstante i poligoni siano normalmente dati in coordinate cartesiane, in questo contesto utilizzeremo le coordinate polari. Il centro di queste coordinate sarà il centro del poligono che dovrà essere ruotato. Le coordinate possono essere precalcolate per il poligono che deve essere ruotato, ma devono essere ricalco- late per tutti gli altri poligoni. Date coordiante cartesiane (x, y) le coordinate polari (r, θ) sono date da:
r =px2+ y2, tan θ = y
x.
Esattamente come per la traslazione, una regione tra segmenti di frontiera R(a, b) passa attraverso tre fasi: nessuna sovrapposizione, al più un'area triangolare, un trapezoide. Queste situazioni sono illustrate nelle immaginiB.5.
A questo punto è facile vedere un'implementazione dell'algoritmo1: trovare i breakpoint signi ca cal- colare intersezioni tra cerchi e segmenti, inoltre i calcoli delle aree non comprendono molto più di un calcolo di intersezione tra due segmenti di frontiera.
La domanda fondamentale a questo punto è se possiamo o no costruire un algoritmo iterativo co- me abbiamo fatto per il problema della traslazione. Gli autori eettuano il calcolo dell'area in modo analogo a come si è fatto per le traslazioni. Le aree da sommare in questo caso sono l'area di un segmento circolare (dati due punti in una circonferenza il segmento circolare è l'area tra l'arco di cir- conferenza e la corda tra i due punti) e quella di un triangolo. Ne risulta che le funzioni necessarie a descrivere l'area variano molto in complessità e questo in uisce sul tempo di esecuzione di una varia- zione rotazionale dell'algoritmo2. Non è semplice sommare le funzioni con l'eccezione delle espressioni lineari, e trovare il minimo tra due breakpoint è complicato.
71
(a) Un'immagine di Nielsen and Odgaard (2003). Una regione tra segmenti ha tre stadi: 1. Nessuna sovrapposizione. 2. Un'area quasi triangolare. 3. Un'area trapezoidale.
(b) Un'immagine diNielsen and Odgaard(2003). L'area tra due segmenti ha due variazioni. In questo esempio i segmenti di retta si intersecano più vicini al centro, mentre nella guraB.5a
è l'opposto.
Fast neighboorhood search: una variante
Come abbiamo visto nell'appendice precedenteB, il metodo fast neighborhood search basa la sua cor- rettezza sul teorema dell'intersezione.
Egeblad et al.(2007) costruiscono una variante di questo teorema per arontare il problema di trovare la traslazione orizzontale ottima di un poligono rispetto agli altri poligoni già posizionati.
Gli autori de niscono i poligoni che vogliono gestire: De nizione C.1 (Lato):
Un lato e è de nito dai suoi estremi ea, eb ∈ R2. Esso è denotato in modo parametrico da e(t) =
ea+ t(eb− ea)dove t ∈ [0, 1]. Dato un punto p = (px, py) ∈ R2 ed un lato e diciamo che p ∈ e se e solo
se p = e(t0) per qualche t0 ∈ [0, 1]e py 6= min(eay, eby).
La condizione py 6= min(eay, eby)serve a gestire alcuni casi speciali.
De nizione C.2 (Funzione Conteggio dei Lati):
Dato un insieme di lati E de niamo due funzioni di conteggio dei lati, ←f−E(p),
−→ fE(p) : R2→ N0, ←− fE(p) = |{e ∈ E | ∃x0 < px : (x0, py) ∈ e}|, −→ fE(p) = |{e ∈ E | ∃x0 ≥ px : (x0, py) ∈ e}|. De nizione C.3 (Poligono):
Un poligono P è de nito da un insieme di lati E. I lati devono formare uno o più cicli e nessuna coppia di lati di E può intersecarsi. La parte interna del poligono è de nita dal seguente insieme:
˜
P = {p ∈ R2|←f−E(p) ≡ 1(mod 2)}.
Dato un punto p ∈ R2 scriviamo p ∈ P se e solo se p ∈ ˜P.
Osserviamo che questa è una de nzione molto generale per un poligono: i poligoni qua possono essere costituiti da più componenti non connesse ed i cicli possono essere contenuti uno nell'altro e produrre buchi nel poligono.
Ora dividiamo i lati di un poligono in tre gruppi dierenti. De nizione C.4 (Segno dei Lati):
Dato un poligono P de nito da un insieme di lati E diciamo che un lato e ∈ E è positivo se:
∀t, 0 < t < 1 : ∃ > 0 : ∀δ, 0 < δ < : e(t) + (δ, 0) ∈ P. (C.1) In modo simile diciamo che e è negativo se C.1è vera con i punti e(t) − (δ, 0). In ne diciamo che eè neutro se e non è né positivo né negativo.
73 L'insieme dei lati positivi e quello dei lati negativi si denotano rispettivamente con E+ e E−.
Osserviamo che queste de nizioni ricalcano le de nizioni date in modo più generale in Nielsen and Odgaard (2003). A partire da queste basi Egeblad et al. (2007) riescono a derivare un analogo del teorema B.0.1per i poligoni (anzichè le forme) e gli insiemi di lati (anzichè gli insiemi di segmenti di frontiera):
Teorema C.0.1 (Teorema dell'intersezione (poligoni)):
Dati due poligoni P e Q de niti da due insiemi di lati E ed F rispettivamente, l'area della loro intersezione (che denotiamo con α) è:
α =A(E+, F−) +A(E−, F+) −A(E+, F+) −A(E−, F−)
Come abbiamo visto, l'idea che sta dietro l'algoritmo fast neighborhood search è di esprimere l'in- tersezione di un poligono P con tutit gli altri poligoni come funzione della posizione orizzontale di P . L'elemento chiave di questo approccio è quello di considerare il valore dell'area della regione tra due lati A(e, f) e vedere come cambia quando uno dei due lati viene traslato.
Per calcolare l'area della regione tra due lati e ed f bisogna considerare solamente tre casi: • Il lato e è completamente alla sinistra del lato f.
• Il lato e interseca il lato f.
• Il lato e è completamente alla destra del lato f.
Nel primo caso la regione tra i due lati è l'insieme vuoto, nel secondo caso è un triangolo e nel terzo caso è l'unione di un triangolo ed un parallelogramma (Nielsen and Odgaard (2003) consideravano invece quest'ultimo caso come unione di un triangolo ed un trapezio).
Sia etla traslazione orizzontale del lato e di t unità e de niamo la funzione a(t) = A(et, f ). Assumiamo
che et intersechi f solo in un intervallo [t4, t] per appropriati t4 e t e vediamo come varia l'area
dell'intersezione quando si trasla e.
• Chiaramente per t < t4 si ha a(t) = 0.
• E' facile vedere che per t ∈ [t4, t]l'intersezione di due lati avviene in un punto che è linearmente dipendente da t, quindi l'altezza del triangolo è linearmente dipendente da t. La stessa cosa succede per la larghezza del triangolo, perciò a(t) dovrà essere una funzione quadratica di t. • In ne, per t > t, a(t) è l'area del triangolo per t = t, che è a(t) a cui si somma l'area di un
parallelogramma. Poichè l'altezza del parallelogramma è costante e la larghezza è t − t, a(t)
per t > t è una funzione lineare.
Quindi a(t) è una funzione quadratica a tratti.
Il passo successivo è quello di estendere il teorema dell'intersezione agli insiemi di lati Et ed F dove Et
è composto dai lati di E traslati di t unità, cioè vogliamo de nire la funzione α(t) = A(Et, F ). Per ogni
coppia di lati et∈ Et ed f ∈ F la regione di intersezione è determinata e la funzione aet,f =A(et, f )
è formulata come descritto in precedenza. Tutte le funzioni ae,f(t)sono quadratiche a tratti ed hanno
la forma: ae,f(t) = 0 per t < t4e,f, Ae,f4 t2+ Be,f4 t + Ce,f4 per t ∈ [t4e,f, te,f],
Be,ft + Ce,f per t > te,f. Denotiamo le costanti t4
e,f e te,f i breakpoint della coppia di lati e ed f, i valori A 4 e,f, B 4 e,f, C 4 e,f i
coe cienti relativi al triangolo di ae,f(t), ed i valori Be,f , Ce,f i coe cienti relativi al parallelogramma
L'area totale dell'intersezione tra due poligoni come funzione della traslazione orizzontale di un poligono può ora essere espressa così:
α(t) =A(Et+, F−) +A(Et−, F+) −A(Et+, F+) −A(Et−, F−). (C.2) L'equazioneC.2 è quadratica poichè somma di funzioni quadratiche.
Veniamo ora all'algoritmo iterativo per la traslazione orizzontale costruito daEgeblad et al.(2007), che non è altro che una variante dell'algoritmo 2. L'algoritmo fa le seguenti cose: per ogni coppia di lati (e, f ) ∈ E × F usa i segni dei lati per valutare se ae,f(t) contribuisce positivamente o negativamente
alla somma inC.2. Determina i breakpoint per e ed f e calcola i coe cienti relativamente al triangolo ed al parallelogramma di ae,f(t). Attraversa in ne i breakpoint di tutte le coppie di lati da sinistra a
destra e ad ogni breakpoint mantieni aggiornata la funzione: α(t) = ˜At2+ ˜Bt + ˜C,
dove tutti i coe cienti sono inizialmente posti a zero. Ogni breakpoint corrisponde ad un cambiamento per una delle funzioni ae,f(t): o entreremo nella fase relativa al triangolo al tempo t
4
e,f oppure entrere-
mo nella fase relativa al parallelogramma al tempo t
e,f di ae,f(t). Una volta entrati nella fase relativa
al triangolo in t4
e,f aggiungiamo i coe cienti del triangolo ai coe cienti di α(t). Una volta entrati nella
fase relativa al parallelogramma in t
e,f sottraiamo i coe cienti del triangolo ed aggiungiamo quelli del
parallelogramma ai coe cienti di α(t).
Per trovare il valore minimo di α(t) consideriamo il valore di α(t) in ogni intervallo tra breakpoint successivi. Poichè α(t) in un tale intervallo è quadratica determinarne il minimo è triviale utilizzando calcoli del secondo ordine. Il minimo totale può essere calcolato facilmente considerando tutti i minimi negli intervalli.
Il tempo di calcolo dell'algoritmo è dominato dall'ordinamento dei breakpoint poichè la restante par- te dell'algoritmo gira in un tempo O(|E| · |F |). Quindi l'algoritmo ha un caso peggiore che gira in O(|E| · |F | · log(|E| · |F |)), che nella pratica può essere ridotto considerando solo i poligoni in S che si intersecano orizzontalmente con P .
Teoricamente ogni coppia di lati in E × F può creare un nuovo lato in P ∩ Q. Quindi un lower- bound per il tempo di esecuzione di un algoritmo che calcola una tale intersezione è Ω(|E| · |F |) (è il tempo di esecuzione minimo). Quindi l'algoritmo che abbiamo descritto è lento solamente per un fattore logaritmico rispetto al lowerbound.
Ecco l'algoritmo:
Algorithm 3 Traslazione orizzontale di poligoni con intersezione minima Dati un insieme S di poligoni ed un poligono P /∈ S
for ogni lato e dei poligoni S − {P } do for ogni lato f di P do
Crea breakpoint per la coppia di lati (e, f). end for
end for
Sia B = breakpoint ordinati.
De nisci la funzione-area α(t) = ˜At2+ ˜Bt + ˜C. Poni ˜A = ˜B = ˜C = 0.
for ogni breakpoint b ∈ B do Modi ca α(t) cambiando ˜A, ˜B, ˜C.
Calcola il minimo al prossimo intervallo di α(t). end for