3.2 Cube Analysis
3.2.1 Analisi Statica
L’idea di base del nostro metodo `e quella di dividere il MBB appena creato in tanti cubi di dimensione minima (che chiameremo cubo minimali) e di valutare per ognuno di essi la densit`a.
Le domande che sorgono spontanee in seguito a questa affermazione sono principalmente due:
1. Come viene calcolata la dimensione minima di un cubo?
2. Cosa si intende con “densit`a di un cubo minimale”? Quante traiettorie sono necessarie affinch´e un “cubo minimale” sia considerato denso? e questa densit`a come si calcola?
Ispirandoci agli algoritmi di clustering density-based, di cui abbiamo par- lato nella sezione 2.4.5, abbiamo deciso di utilizzare i parametri MinPts ed per stimare le aree pi`u o meno dense. Ovviamente il significato di questi parametri nel nostro metodo `e un p`o diverso.
DBSCAN effettua l’analisi ponendo l’attenzione su un oggetto, quindi rappresenta l’intorno dell’oggetto, e MinPts rappresenta il numero di oggetti che devono risiedere nell’intorno di affinch´e quel oggetto sia dia un core- object.
Il nostro metodo invece effettua l’analisi ponendo l’attenzione sul cubo correntemente analizzato, quindi `e utilizzato per verificare se la dimensione
2Il MBB creato, in base alle dimensioni dell’area da analizzare, pu`o non essere un
cubo, anzi molto probabilmente la figura ottenuta sar`a un parallelepipedo, nonostante ci`o continueremo ad usare il termine cubo per facilitare la comprensione del metodo.
47 3.2 Cube Analysis
del cubo `e minima o meno, mentre il parametro MinPnts `e la soglia che ci permette di valutare se il cubo corrente `e denso o meno.
All’inizio del processo, la dimensione dell’asse X viene divisa ripetuta- mente a met`a fin tanto che la dimensione che si ottiene non `e compresa tra e 2.
Il numero di cubi minimali che si possono disporre lungo l’asse X sar`a dato da:
N. cubi minimali lungo asse X = 2i con i uguale al numero di suddivisioni effettuate.
Stesso procedimento sar`a effettuato per calcolare il numero di cubi mi- nimali che possono essere disposti lungo l’asse Y. Ovviamente anche l’asse T verr`a suddiviso, ma, a differenza dei precedenti, utilizzeremo il parame- tro MinT al posto di , questo perch´e si `e voluto rendere indipendente la granularit`a dell’asse temporale, rispetto a quella spaziale.
Grazie a queste divisioni siamo stati in grado di recuperare due informa- zioni: il numero di cubi minimali che `e possibile inserire lungo tutti e tre gli assi, e le loro dimensioni effettive; a questo punto non ci resta che iniziare ad effettuare la divisione del cubo.
Partendo dall’angolo in basso a sinistra e procedendo prima lungo l’asse X, poi lungo l’asse Y ed infine lungo l’asse T, andremo ad analizzare la densit`a di ogni cubo minimale.
Dobbiamo ancora stabilire come si calcola la densit`a di questi cubi, anche se prima `e necessario identificare la varie facce che li compongono.
Ogni cubo `e composto da sei facce ognuna identificata da una coppia di tuple < T, X, Y > che rappresentano rispettivamente i due angoli opposti della faccia. In particolare dato un cubo K chiameremo faccia anteriore di K e faccia posteriore di K le due facce le cui tuple hanno lo stesso valore di timestamp. La faccia anteriore sar`a quella che, tra le due, ha il timestamp pi`u basso, mentre l’altra verr`a identificata con il nome di faccia posteriore. Le altre 4 facce del cubo non necessitano di identificazioni particolari pertanto ci riferiremo ad esse con il termine generico di facce laterali di K.
La densit`a di un cubo minimale `e data dal numero di traiettorie che lo attraversano, indipendentemente dal percorso esse seguono al suo interno. Ci`o significa che se una traiettoria attraversa pi`u di una faccia, oppure attra- versa una faccia pi`u volte, tale traiettoria viene considerata una sola volta. L’operazione si esegue quindi `e una sorta di “distinc count” sulle traiettorie che attraversano le varie facce del cubo.
Al fine di quantificare questa densit`a `e necessario identificare le traiettorie che attraversano ogni faccia; la metodologia per l’identificazione di queste
48 3.2 Cube Analysis
traiettorie cambia in base al fatto che la faccia sia quella anteriore/posteriore o una di quelle laterali.
Per individuare le traiettorie che attraversano la faccia anteriore o poste- riore occorre, di ogni traiettoria, ricercare la tupla avente come timestamp lo stesso istante temporale della faccia che si sta analizzando. Una volta indi- viduata tale tupla, si controller`a se le coordinate spaziali della traiettoria in quell’istante rientrano nei confini della faccia o meno (attraverso il confronto con le coordinate delle due tuple della faccia che rappresentano i suoi angoli opposti).
Poich´e non sempre di ogni traiettoria `e disponibile una tupla che abbia lo stesso timestamp della faccia, l’algoritmo, durante la scansione delle tuple, conserver`a per ogni traiettoria le informazioni relative alla tupla avente un valore di timestamp immediatamente precedente a quello della faccia, e quelle relative alla tupla con il timestamp immediatamente successivo. Di seguito ci riferiremo a queste due tuple indicandole rispettivamente con l’identificativo Pa e Pp. Queste due informazioni sono necessarie poich´e, nel caso in cui
la tupla con lo stesso timestamp della faccia non esista, l’algoritmo dovr`a ricorrere ad una approssimazione della posizione della traiettoria nell’istante temporale della faccia.
Per calcolare questa approssimazione si utilizza uno dei metodi pi`u sem- plici e diffusi in letteratura, quello dell’interpolazione lineare tra una coppia di punti, nel nostro caso in tre dimensioni:
Dati Pa= (T1, X1, Y1) e Pp = (T2, X2, Y2) ricerchiamo il punto interpolato
Pf = (T3, X3, Y3),tramite la formula d’interpolazione:
(T1+ λ(T2 − T1), X1+ λ(X2− X1), Y1+ λ(Y2− Y1)) con λ ∈ R
Ma il valore di T3 lo conosciamo, `e il timestamp della faccia analizzata,
per cui: T1+ λ(T2− T1) = T3 quindi λ = TT32−T−T11 T3, X1+TT23−T−T11(X2 − X1), Y1+ T3−T1 T2−T1(Y2− Y1)
Il metodo per individuare le intersezioni con le facce laterali `e `e un p`o pi`u complesso. Innanzitutto `e necessario recuperare le tuple i cui timestamp sono compresi nell’intervallo temporale della faccia laterale che si sta analiz- zando, nonch´e le due tuple che hanno rispettivamente il timestamp imme- diatamente precedente rispetto all’estremo temporale anteriore della faccia ed il timestamp immediatamente successivo rispetto all’estremo temporale posteriore (vedi fig. 3.3)
49 3.2 Cube Analysis
Figura 3.3: Tuple necessarie per l’analisi dell’intersezione con la faccia Per ogni coppia di tuple appartenenti a questo insieme, si controller`a l’eventuale intersezione con la faccia laterale. A partire due tuple della tra- iettoria, P1(tp1, xp1, yp1) e P2(tp2, xp2, yp2), `e possibile ricavare l’equazione
della retta a cui appartiene il segmento che collega P1 a P2. Allo stesso mo- do, dati gli angoli opposti di una faccia A1 (ta1, xa1, ya1) e A2 (ta2, xa2, ya2)
e sapendo che ogni faccia `e parallela ad un piano coordinato XOY, XOT, YOT, `e possibile ricavare l’equazione del piano a cui appartiene la faccia.
Il problema di trovare l’intersezione tra il segmento di retta e la fac- cia del cubo non `e altro che un caso particolare del problema pi`u generale dell’intersezione di una retta con un piano.
Se questo problema restituisce una sola soluzione, allora significa che la retta interseca il piano; se invece vengono individuate infinite soluzioni allora significa che la retta `e adagiata sul piano. Altrimenti, non trovando nessuna soluzione, significa che la retta non interseca mai il piano, ovvero la retta `e parallela al piano.
Se viene trovata una soluzione si procede a controllare che tale punto X individuato appartenga sia al segmento P1-P2, sia alla faccia A1-A2.
Se invece, caso piuttosto raro, vengono trovate infinite soluzioni, occorre fare un’ulteriore controllo, ovvero calcolare le intersezioni della retta P1-P2 con la faccia A1-A2, o meglio con le 4 rette a cui appartengono i segmen- ti che compongono la faccia (xa1, ya1) − (xa1, ya2), (xa1, ya2) − (xa2, ya2),
(xa2, ya2) − (xa2, ya1) e (xa2, ya1) − (xa1, ya1), e, una volta trovato il punto
di intersezione, controllare che appartenga sia a P1-P2, sia al segmento della della faccia.
Abbiamo adesso le informazioni necessarie per poter costruire il cubo iniziale nonch´e quelle necessarie per identificare le coordinate dei cubi di dimensione minima e potersi cos`ı spostare tra di essi. Con i metodi di in-
50 3.2 Cube Analysis
terpolazione appena visti siamo in grado di individuare le traiettorie che intersecano una determinata faccia, non ci rimane che definire una volta per tutte, come viene calcolata la densit`a.