Corso di Interfacce Utente - A.A. 2005-2006

PROGETTO DI LABORATORIO - DOCUMENTO 1 DI 3

Vedere la pagina principale del progetto per gli altri due documenti.

Descrizione dell'applicazione "Diagramma di Voronoi"

Teoria

Il diagramma di Voronoi e' una struttura geometrica nel piano costruita a partire da un insieme di punti.

Sia S un insieme di punti nel piano, che chiamiamo siti.
Ad ogni sito P e' associata una regione di Voronoi R, definita come la parte di piano che e' piu' vicina a P che a qualsiasi altro punto di S.
L'insieme dei siti e delle loro regioni costituisce il diagramma di Voronoi.

Alcune proprieta':

• Per ogni sito P, la corrispondente regione di Voronoi e' un poligono contenente P al suo interno.
• Il lato di confine fra due regioni di Voronoi, associate a due siti P1 e P2, e' un tratto dell'asse del segmento P1-P2 (l'asse e' la retta perpendicolare al segmento nel punto medio di questo).
• Le regioni del diagramma di Voronoi ricoprono tutto il piano senza intersecarsi fra loro e senza lasciare "buchi".

Esempio di diagramma di Voronoi:

Semplificazioni nel nostro caso:

• Tutti i siti dell'insieme S sono contenuti in un rettangolo di riferimento, per esempio il quadrato di diagonale (-10,-10) - (10,10).
• L'insieme S contiene sempre come siti almeno i quattro angoli del suddetto quadrato.
• In questa situazione, il diagramma di Voronoi coincide con la ripartizione del piano nei quattro quadranti.

Diagramma di Voronoi dei quattro angoli del quadrato:

Pratica

L'applicazione permette di:

• rappresentare un diagramma di Voronoi con i suoi vertici, le sue regioni e tutte le informazioni relative
• modificare il diagramma aggiungendo o eliminando un sito