Corso di Interfacce Utente - A.A. 2003-2004

PROGETTO DI LABORATORIO DI RECUPERO

Descrizione dell'applicazione e requisiti dell'interfaccia

Realizzare un'interfaccia per una applicazione che costruisce una una gerarchia di quadrati annidati (chiamata "QuadTree") per un insieme di punti.
Un QuadTree e' una struttura geometrica nel piano, percio' l'interfaccia avra', oltre alla parte di controllo, una parte di grafica bidimensionale.

L'applicazione viene data gia' fatta. La descrizione dell'applicazione e delle classi che la implementano (punti 2 e 3 di questo documento) sono illustrazione di cosa gia' esistente pronta per essere usata.
Voi dovrete invece prima progettare e poi implementare l'interfaccia per l'applicazione, seguendo le specifiche (punto 4 di questo documento).

Nozioni teoriche

Sono assegnati:

• un insieme S di punti nel piano
• un quadrato chiamato "universo" contenente tutti i punti di S
• un numero intero K > 0 chiamato "capacita'"

• Si parte da un unico quadrato coincidente con l'intero universo
• Se il quadrato contiene piu' di K punti di S, allora viene diviso in 4 quadrati tracciando le due mediane
• Si applica lo stesso procedimento ricorsivamente a ciascuno dei quadrati risultanti
• Alla fine ogni quadrato della partizione contiene non piu' di K punti, che sono memorizzati nel quadrato stesso

La figura mostra un esempio di QuadTree che memorizza un insieme di punti, supponendo capacita' K=2.

Che cosa fa l'applicazione

L'applicazione contiene strutture dati ed algoritmi che permettono di:

• rappresentare un QuadTree con i suoi quadrati, i punti memorizzati in essi e tutte le informazioni relative
• modificare il QuadTree aggiungendo o eliminando un punto

L'aggiunta e l'eliminazione di un punto consistono in due fasi, da eseguire strettamente in sequenza:

1. fase "try": tenta di eseguire la modifica, controlla se si puo' fare.
2. fase "do": se il tentativo ha avuto successo, esegue veramente la modifica sul QuadTree; se invece il tentativo e' fallito non fa nulla.

Vengono date le classi

• QuadTree che implementa un QuadTree.
• QuadNode che, per quanto interessa a noi, implementa un quadrato della partizione (in realta' implementa una struttura piu' complicata che pero' ai fini dell'interfaccia non abbiamo bisogno di sapere).

Classe QuadNode

Per quanto ci riguarda, rappresenta un quadrato della partizione.

Creazione:
Non c'e' modo di creare un quadnode dall'esterno. Vengono creati solo all'interno dell'implementazione del QuadTree.

Informazioni sulla geometria del quadrato:

• double getMinX(), double getMinY() ritornano le coordinate dell'angolo in basso a sinistra.
• double getEdgeLength() ritorna la lunghezza del lato del quadrato.
• boolean containsPoint(double x, double y) ritorna true se il punto (x,y) cade nel quadrato. Cio' non significa che vi sia memorizzato, vi sara' memorizzato solo se appartiene gia' al QuadTree. Questa funzione opera un controllo solo sulla posizione geometrica del punto (x,y) non sulla sua eventuale presenza nel QuadTree. Se il punto cade sul confine tra due quadrati, viene considerato come contenuto in quello dei due che sta in alto / a destra.

Informazioni sui punti memorizzati nel quadrato:

• int numPoints() ritorna il numero di punti memorizzati nel quadrato (non possono eccedere la capacita').
• double getPointX(int i), double getPointY(int i) ritornano le coordinate dell'i-esimo punto fra quelli memorizzati nel quadrato. Il valore di i deve essere tra 0 e numPoints()-1.
• int hasPoint(double x, double y) se il punto e' memorizzato in questo quadrato, ritorna l'indice i tale che getPointX(i)=x e getPointY(i)=y. Altrimenti ritorna -1.
• int hasNearPoint(double x, double y, double toll) come la precedente, ma con una tolleranza toll sulla posizione: se nel quadrato c'e' un punto che dista meno di toll da (x,y) allora ne restituisce l'indice (se sono piu' di uno sceglie il piu' vicino). Altrimenti ritorna -1.
  Utile se dall'interfaccia selezionate il punto col mouse, in quanto e' difficile cliccare esattamente sul pixel giusto.

Classe QuadTree

NOTA: essendo QuadTree sottoclasse di QuadNode, tutte le funzioni presenti in QuadNode sono presenti anche in QuadTree.

Creazione:

• QuadTree (int kk, double x0, double y0, double edgeLength) Crea un QuadTree con capacita' = kk, universo il quadrato con angolo in basso a sinistra (x0,y0) e lato lungo edgeLength. L'insieme di punti e' vuoto. La partizione e' fatta da un solo quadrato coincidente con l'universo.

Informazioni generali sul QuadTree:

• int capacity() ritorna la capacita' del QuadTree.
• Le dimensioni dell'universo si ottengono mediante le funzioni getMinX, getMinY, getEdgeLength ereditate dalla superclasse QuadNode.

Informazioni sulla situazione corrente del QuadTree:

• int numAllPoints() Ritorna il numero totale di punti presenti nell'insieme.
• Invece la funzione numPoints ereditata dalla superclasse QuadNode ritorna sempre zero perche' l'intero QuadTree NON e' un rettangolo della partizione.
• int numSquares() Ritorna il numero di quadrati che formano la partizione.
• QuadNode[] getSquares() Ritorna un array contenente i quadrati della partizione.

Funzione di ricerca:

• QuadNode searchPoint(double x, double y) ritorna il quadrato della partizione in cui cade il punto (x,y). Questo non significa che il punto sia memorizzato in tale quadrato, vi sara' memorizzato solo se appartiene gia' al QuadTree. Questa funzione opera un controllo solo sulla posizione geometrica del punto (x,y) non sulla sua eventuale appartenza al QuadTree.
  Sul quadrato poi si puo' chiamare la funzione hasPoint (o la sua versione con tolleranza hasNearPoint) per controllare se il punto, oltre a cadervi geometricamente, vi si trova anche memorizzato.

Aggiunta di un punto:

• boolean tryAddPoint(double x, double y)
  Tenta di aggiungere il punto (x,y) all'insieme, non modifica la partizione. Ritorna true se e' possibile aggiungerlo cioe' se il punto (x,y) non e' esterno all'universo e non e' gia' presente nell'insieme.
• QuadNode doAddPoint(double x, double y)
  Se preceduta da un tentativo concluso con successo, aggiunge il punto (x,y) all'insieme modificando la partizione. Ritorna il quadrato in cui e' stato memorizzato il punto. Altrimenti non fa nulla e ritorna null.

Eliminazione di un punto:

• boolean tryDeletePoint(double x, double y)
  Tenta di eliminare il punto (x,y), non modifica la partizione. Ritorna true se e' possibile eliminarlo cioe' se (x,y) e' presente nell'insieme.
• QuadNode doDeletePoint(Point v)
  Se preceduta da un tentativo concluso con successo, elimina il punto (x,y) modificando la partizione. Ritorna il quadrato che contiene geometricamente il punto (mentre il punto non vi e' memorizzato). Altrimenti non fa nulla e ritorna null.

Generalita'

In ogni momento sono presenti in memoria:

• un QuadTree che memorizza un insieme S di punti
• un altro insieme E di punti non facenti del QuadTree, che chiameremo punti extra

Il QuadTree si implementa con la classe QuadTree. L'insieme S e' memorizzato nel QuadTree: basta prendere i quadrati della partizione e, per ciascun quadrato, prendere i punti contenuti: questi sono tutti e soli i punti dell'insieme S. Per i punti extra occorre definire una propria implementazione, ricordando che Java fornisce varie classi predefinite per gestire insiemi.

Per default l'interfaccia mostra il QuadTree con i suoi punti e i punti extra. L'utente puo' scegliere di mostrare / nascondere ciascuna di queste due entita'.
A seconda dello stato dell'interfaccia, alcuni elementi possono essere evidenziati, ad esempio durante l'anteprima e l'animazione (ved. dopo).

Accesso alle operazioni applicative

L'utente deve poter fare le seguenti operazioni.

Operazioni sull'insieme dei punti extra:

• Caricare un insieme di punti extra da file
• Salvare l'insieme dei punti extra su file
• Svuotare l'insieme dei punti extra
• Modificare interattivamente l'insieme dei punti extra aggiungendo, cancellando, spostando un punto

Operazioni sul QuadTree:

• Impostare la capacita' K del QuadTree (i valori di K consentiti variano nell'intervallo 1..5)
• Impostare l'universo del QuadTree.
• Aggiungere un punto al QuadTree (vale a dire aggiungerlo all'insieme S), che puo' essere un punto extra oppure un punto nuovo, direttamente immesso dall'utente
• Eliminare un punto dal QuadTree (vale a dire eliminarlo dall'insieme S), conservandolo pero' tra i punti extra
• Aggiungere tutti i punti extra al QuadTree (non importa in che ordine).
• Eliminare tutti i punti dal QuadTree, conservandoli tra i punti extra

Anteprima

L'anteprima puo' essere abilitata e disabilitata dall'utente e riguarda l'aggiunta di un punto al QuadTree e l'eliminazione di un punto dal QuadTree.

Viene eseguita prima la fase "try", viene comunicato come feedback all'utente l'esito dell'operazione e viene mostrato il quadrato della partizione in cui cade il punto da aggiungere / eliminare.

Solo se l'esito era possibile, viene eseguita poi la fase "do" e viene mostrato il quadrato della partizione in cui cade il punto aggiunto / eliminato (Se il punto e' stato appena aggiunto, allora tale quadrato oltre a contenerlo geometricamente lo memorizza anche. Se il punto e' stato appena eliminato, allora tale quadrato lo contiene geometricamente ma non lo memorizza piu').

La figura mostra un esempio di quali quadrati vanno mostrati per l'aggiunta di un punto (capacita' K=2), il punto da aggiungere e' in bianco a sinistra:

La figura mostra un esempio di quali quadrati vanno mostrati per l'eliminazione di un punto (capacita' K=2), il punto eliminato e' in bianco a destra:

Il passaggio dall'una all'altra fase puo' essere comandato dall'utente con una azione (l'utente puo' anche decidere di rinunciare) oppure automatico dopo un certo intervallo di tempo fissato dall'utente (l'interfaccia permette all'utente di scegliere tale intervallo).

Animazione

L'animazione puo' essere abilitata e disabilitata dall'utente e riguarda l'aggiunta di tutti i punti extra al QuadTree e l'eliminazione di tutti i punti dal QuadTree.

Se l'animazione e' attiva, allora dopo ogni passo viene mostrato il nuovo QuadTree, fino al risultato finale. Se l'animazione non e' attiva allora viene mostrato direttamente il risultato finale.

I passi dell'animazione possono essere comandati dall'utente (compiendo un'azione per eseguire il passo successivo) oppure procedere in automatico dopo un certo intervallo di tempo fissato dall'utente (l'interfaccia permette all'utente di scegliere tale intervallo).

L'animazione interagisce con l'anteprima. Se entrambe sono attive, allora per ogni passo eseguito nell'animazione vengono mostrate le due fasi.

In qualsiasi momento l'utente puo' interrompere l'animazione. Dopo averla interrotta puo' riprendere l'esecuzione (per inserire / eliminare i punti rimanenti) oppure abortirla (rinunciando ad inserire / eliminare i punti rimanenti).

Durante la sosta l'utente puo' cambiare lo stato delle abilitazioni e gli intervalli di tempo, sia per l'animazione che per l'anteprima.

Gradi di liberta' e raccomandazioni

Non e' specificato in che modo l'utente deve interagire (es. come si fa a selezionare il punto da inserire nel QuadTree).
E non e' specificato se non in parte il feedback da rendere all'utente (es. come si comunica all'utente l'avvenuta selezione del punto).
E non sono nemmeno specificate le sequenze di azioni necessarie per compiere le varie operazioni (es. per inserire un punto devo prima selezionare il punto e poi dire che lo voglio inserire oppure prima dire che voglio inserire un punto e poi selezionare quale).

Tutto quanto non specificato fa parte della liberta' che avete nel progettare l'interfaccia.

Questa liberta' va gestita tenendo in considerazione i principi generali per la progettazione di interfacce utente (buona presentazione, efficace interazione, facilita' di apprendimento, comodita' d'uso ecc.).

Questo e' un progetto di interfacce utente. Pertanto, sara' tenuto conto non solo del fatto che tutte le funzioni richieste siano presenti nell'interfaccia sviluppata, ma anche e di quanto facile e gradevole risulta l'uso dell'interfaccia stessa per l'utente.