Progetto CASD
A.A. 2009/2010
Triangulation PR kd-tree: un indice spaziale
per la modellazione di terreni

Introduzione

L’indice spaziale PR kd-tree

L’indice spaziale Triangulation PR kd-tree

Costruzione di un indice spaziale Triangulation PR kd-tree

Localizzazione di un punto (Point location query)
NOTA: questi lucidi sono stati usati per la presentazione in aula del
progetto. La descrizione precisa del progetto a cui fare riferimento verrà
messa a disposizione su Aulaweb.
1
Introduzione

Obiettivo del progetto
Sviluppo di un prototipo di un sistema informativo geografico per eseguire
interrogazioni su modelli di terreno.

Modello di terreno
Dato un insieme V di punti nel piano xy ed un insieme di valori di quota nei punti di
V, un modello di terreno consiste in una funzione interpolante lineare a pezzi
definita su una mesh M nel piano xy che connette i punti di V.
p
Griglia M che
connette i punti
di V
P’
2
Introduzione (2)

Le operazioni di interrogazione su un modello di terreno corrispondono a
interrogazioni su una griglia di triangoli nel piano xy, più semplici da trattare.

Nel progetto, consideriamo operazioni su una griglia di triangoli nel piano xy,
detta modello del terreno proiettato.

Per effettuare le operazioni di interrogazione e di aggiornamento in maniera
efficiente, dobbiamo sovraimporre un indice spaziale sulla griglia di triangoli
p
P’
Griglia M nel piano xy
3
Griglie di triangoli

Una griglia di triangoli (detta anche triangles mesh) è un insieme di triangoli tali che
per ogni coppia di triangoli t1 e t2 vale una delle seguenti condizioni:

t1 e t2 non si intersecano;

se t1 e t2 si intersecano, l’intersezione deve avvenire esclusivamente in uno spigolo
comune o in un vertice comune.
Insiemi di triangoli che non formano una griglia
Una griglia di triangoli
4
Griglie di triangoli manifold

Nel progetto useremo griglie di triangoli manifold.

Una griglia di triangoli si dice manifold se per ogni vertice p i triangoli ivi incidenti sono
adiacenti a coppie e formano un unico ventaglio di triangoli.
Griglia di triangoli manifold
Griglia di triangoli non manifold
5
Il Progetto

Si richiede di sviluppare l'indice spaziale Triangulation Point-Region kd-tree (spesso
abbreviato in Triangulation PR kd-tree), un indice da sovrapporre a triangolazioni.

L'indice spaziale Triangulation PR kd-tree è basato su quello Point-Region kd-tree
(spesso abbreviato in PR kd-tree), un indice spaziale gerarchico per insiemi di punti
nel piano.

Il progetto consiste nel progettare ed implementare:

una struttura dati per l'indice spaziale Triangulation PR kd-tree

un algoritmo per costruire un indice spaziale Triangulation PR kd-tree

un algoritmo per localizzare un punto in una triangolazione (point location query)

Su Aulaweb troverete:

le specifiche formali e complete del Progetto

materiale aggiuntivo per lo svolgimento del Progetto
6
La Prima Parte del Progetto

Nella prima parte del Progetto si dovrà costruire l'indice spaziale Triangulation PR
kd-tree a partire da una griglia di triangoli fornita in input.

Input: una griglia di triangoli specificata dall'insieme dei suoi vertici e dei suoi
triangoli descritto in forma indicizzata:

lista delle coordinate di ogni vertice (in virgola mobile - float)

lista dei triangoli, visti come triple di indici dei vertici

I vertici ed i triangoli in input costituiscono una triangolazione manifold corretta.

Il dominio della triangolazione verrà fornito nel file di input.

Output: una rappresentazione delle foglie dell'indice Triangulation PR kd-tree.

Su Aulaweb troverete:

le specifiche complete per i file di input e di output per quanto riguarda questa
prima parte del Progetto

il codice C del programma visPart1 per poter visualizzare l’output di questa
prima parte del Progetto
7
La Seconda Parte del Progetto

Nella seconda parte del Progetto si dovrà progettare ed implementare l’interrogazione
di localizzazione di un punto (detta anche point-location query).
POINT LOCATION QUERY
 Input:




una griglia di triangoli specificata come per la prima parte del Progetto;
le coordinate del punto p da localizzare (in virgola mobile – float)
Output: la lista dei nodi visitati ed un solo triangolo contenente p (se esiste).
Su Aulaweb troverete:

le specifiche complete dei file di input e di output per quanto riguarda questa
seconda parte del Progetto

il codice C del programma visPart2 per poter visualizzare l’output di questa
seconda parte del Progetto

Il codice C per la primitiva di localizzazione di un punto in un triangolo.
8
Dettagli Organizzativi

La consegna del progetto sarà UNICA e a fine corso – 30 GIUGNO 2010

Il voto conseguito sarà valido fino a FEBBRAIO 2011

Si può svolgere a gruppi (max 3 persone), previa iscrizione su Aulaweb o inviando un
messaggio al dott. Canino ([email protected])

I linguaggi accettati sono C, C++ e Java
9
L'indice spaziale PR kd-tree

Fornisce una rappresentazione gerarchica di un
insieme di punti nel piano.

Dato un insieme finito di punti S, distribuiti in un
dominio D nel piano, un PR kd-tree suddivide D in
regioni rettangolari annidate, dette blocchi.

Ogni blocco nella partizione risultante del dominio
D è vuoto oppure contiene esattamente un punto di
S (condizione di suddivisione).

Il processo di suddivisione si applica fino a quando
non si verifica la condizione di suddivisione per ogni
blocco.

La suddivisione di un blocco b viene eseguita
dividendolo alternativamente in senso verticale
oppure orizzontale rispetto al punto centrale (detto
anche centroide) del blocco b.

Quindi si creano due nuovi sottoblocchi: la loro
definizione deve garantire che un punto appartenga
ad un solo blocco della suddivisione.
A
B C
10
Suddivisione di un blocco

Sia C = ( xc , yc ) il centroide del blocco b allora:

il blocco LEFT (L) contiene tutti i punti P = ( xp , yp ) del blocco b tali che xp < xc

il blocco RIGHT (R) contiene tutti i punti P = ( xp , yp ) del blocco b tali the xp ≥ xc

il blocco BELOW (B) contiene tutti i punti P = ( xp , yp ) del blocco b tali che yp < yc

il blocco ABOVE (A) contiene tutti i punti P = ( xp , yp ) del blocco b tali che yp ≥ yc

Per convenzione il blocco LEFT (oppure BELOW) viene memorizzato come primo sottoblocco,
mentre quello RIGHT( oppure ABOVE) come secondo sottoblocco.

Questo schema di suddivisione impone che un blocco deve contenere solo il suo bordo
inferiore e quello sinistro, tranne quando il blocco si trova lungo il contorno del dominio D:
in questo caso i bordi dovranno essere chiusi, cioè appartenere al blocco stesso.
11
Rappresentazione ad albero di
un PR kd-tree

Un indice PR kd-tree è rappresentato da un albero binario in
cui ogni nodo descrive un blocco della suddivisione.

La radice dell'albero descrive l'intero dominio D.

I nodi interni (nodi INTERNAL) rappresentano blocchi che non
appartengono alla suddivisione finale di D: ogni nodo interno
ha due figli che non contengono punti di S.

I nodi interni di livello pari rappresentano suddivisioni del
blocco corrispondente in senso verticale, mentre quelli di
livello dispari suddivisioni in senso orizzontale.

Le foglie rappresentano blocchi che contengono un punto
(foglie di tipo FULL) o che sono vuoti (foglie di tipo EMPTY).
Nodo FULL
Nodo INTERNAL
Nodo EMPTY
B C
A
L
R
A
A
B
L
R
B
C
12
Inserimento di un punto in
un PR kd-tree (1)
L’inserimento di un punto P=(xp,yp) in un PR kd-tree deve essere eseguito in due fasi.
Fase 1

Bisogna individuare la foglia b che contiene il punto P, visitando l’albero a partire dalla
radice (a livello 0) in maniera analoga agli alberi binari di ricerca.

Se il nodo corrente n è di tipo INTERNAL ed il centroide del blocco interno è C=(xc,yc),
allora:



se n è a livello pari (cioè la suddivisione del blocco interno è verticale) allora:

si prosegue la ricerca nel figlo LEFT, se xp< xc

si prosegue la ricerca nel figlio RIGHT, altrimenti
se n è a livello dispari (cioè la suddivisione del blocco interno è orizzontale) allora:

si prosegue la ricerca nel figlio BELOW, se yp< yc

si prosegue la ricerca nel figlio ABOVE, altrimenti
Se il nodo corrente n è una foglia, allora possiamo eseguire la Fase 2 .
13
Inserimento di un punto in
un PR kd-tree (2)
Fase 2

Una volta individuata la foglia b che contiene il punto P, bisogna proseguire in base al
tipo di foglia trovata:



se la foglia b è di tipo EMPTY si inserisce direttamente P nella foglia b, che diventa
una foglia di tipo FULL
se la foglia b è di tipo FULL e contiene già il punto P allora l'inserimento termina
altrimenti bisogna creare un nuovo livello nell'albero, inserendo in maniera ricorsiva
nell'indice il punto P ed il contenuto della foglia b, che diventa un nodo interno
(cioè di tipo INTERNAL) .
P
P
ok
no
ok
14
PR kd-tree: un esempio
Toronto
Chicago
Denver
Mobile
15
Osservazioni sull'indice PR kd-tree

Le foglie FULL o EMPTY possono trovarsi a qualunque
livello di un indice spaziale PR kd-tree.

La forma di un PR kd-tree è indipendente dall'ordine in
cui punti di S sono inseriti, poiché il processo di
suddivisione è effettuato sul centroide del blocco e non
sulle coordinate dei punti.

L'altezza di un PR kd-tree costruito su un insieme di
punti S è inversamente proporzionale alla distanza
minima fra due punti dell'insieme S.

Ulteriori riferimenti per l'indice spaziale PR kd-tree:


libro di testo H. Samet - Design and Analyisis of
Spatial Data Structures
applets per indici spaziali disponibili presso
http://donar.umiacs.umd.edu/quadtree/index.html
B C
A
L
R
A
A
B
L
R
B
C
16
L'indice spaziale
Triangulation PR kd-tree (1)

L’indice PR kd-tree gestisce insiemi di punti e quindi NON è adatto alle triangolazioni.

Tuttavia possiamo ridurre una triangolazione ad un insieme di punti associando ad ogni
triangolo un punto rappresentativo, che lo identifica univocamente.

La scelta più comunemente adottata è quella di considerare il centroide di un triangolo.
Dato un triangolo avente rispettivamente (x1,y1), (x2,y2) e (x3,y3) come vertici, allora il
suo centroide (o anche baricentro) avrà coordinate ( Cx ,Cy ) dove:
Cx = ( x1 + x2 + x3)/3 e Cy = (y1 + y2 + y3)/3

In questo modo, possiamo costruire una particolare versione dell’indice PR kd-tree sui
centroidi dei triangoli, detta Triangulation PR kd-tree.

Analogamente a quanto avviene per l'indice PR kd-tree, il dominio della triangolazione
viene ricorsivamente suddiviso in regioni rettangolari annidate, dette blocchi.

In un Triangulation PR kd-tree, la regola di suddivisione di un blocco si applica solo ai
centroidi dei triangoli ed è la stessa regola usata nel PR kd-tree.

Ad ogni blocco b della suddivisione finale che contiene il centroide di un triangolo t, è
associato anche il triangolo t.
17
L'indice spaziale
Triangulation PR kd-tree (2)

La suddivisione del dominio dipende dai centroidi dei triangoli ed è la stessa che si
ottiene costruendo un PR kd-tree con i soli centroidi.
18
Rappresentazione ad albero di un indice
spaziale Triangulation PR kd-tree
Un Triangulation PR kd-tree è rappresentato da un
albero binario nel quale ogni nodo descrive un
blocco della suddivisione.
 Il nodo radice rappresenta il dominio della griglia.
 I nodi interni (nodi INTERNAL) corrispondono a
blocchi ulteriormente suddivisi che non contengono
centroidi dei triangoli della griglia di partenza.


Un nodo foglia può essere di tipo:

EMPTY se non contiene alcun centroide;

FULL se contiene al più un centroide dei
triangoli della griglia di partenza.
L
B
R
A
B
A
1
L
2
R
3
0
Nodi FULL
Nodi INTERNAL
Nodi EMPTY
19
Costruire un indice Triangulation PR kd-tree

L'algoritmo per costruire un Triangulation PR kd-tree a partire da una triangolazione
inserisce in maniera incrementale i triangoli della griglia di partenza.

L'algoritmo per inserire un triangolo è lo stesso usato per inserire un punto in un PR kdtree (in questo caso il centroide del triangolo).

NOTA: bisogna memorizzare il riferimento ad un triangolo quando si memorizza il suo
centroide in una foglia di tipo FULL.
20
Triangulation PR kd-tree – Proprietà (1)
 Le foglie di tipo FULL ed EMPTY possono trovarsi a
qualunque livello dell’indice.
 La forma di un indice Triangulation PR kd-tree NON
dipende dall’ordine di inserimento dei triangoli,
visto che la suddivisione di un blocco viene eseguita
rispetto al centroide.
 L’altezza di un indice Triangulation PR kd-tree è
inversamente proporzionale alla distanza minima
fra i centroidi.
L
B
R
A
B
A
1
2
In un Triangulation PR kd-tree TUTTAVIA:
L
 un triangolo viene univocamente associato ad un
solo nodo di tipo FULL
 NON è garantito che un triangolo sia interamente
contenuto nel blocco di tipo FULL a cui è associato
 NON è possibile conoscere quali blocchi vengono
intersecati da un triangolo
R
3
0
Nodi FULL
Dunque, nel processo di indicizzazione NON si tiene
conto dell’estensione spaziale di un triangolo, MA
solo della posizione del suo baricentro.
Nodi INTERNAL
Nodi EMPTY
21
Triangulation PR kd-tree – proprietà (2)
Di conseguenza, NON è garantito che:

Una foglia EMPTY sia effettivamente vuota

Una foglia FULL sia intersecata solo dal triangolo t ad
essa associata.
Quindi NON è possibile
analizzare SOLO i centroidi
nelle interrogazioni!
22
Localizzazione di un punto
QUERY
 Dato un punto p=(xp,yp), si vogliono individuare gli eventuali triangoli della griglia
contenenti p al loro interno o sul loro bordo.
NOTA
 Se il punto p sta sul bordo di un triangolo allora potrà essere condiviso fra più triangoli.
23
Localizzazione di un punto (2)
IDEA di BASE
 Possiamo limitare la ricerca dei triangoli nella porzione di dominio “più vicina
possibile” al punto p, scartando parti di dominino non significative con un indice.
Soluzione possibile (con un Triangulation PR kd-tree)
Individuare la foglia che contiene il punto p visitando l’albero a partire dalla radice (a
livello 0) in maniera analoga agli alberi binari di ricerca.

Se il nodo corrente n è di tipo INTERNAL ed il centroide del blocco b descritto da n è
C=(xc,yc), allora:



se n è a livello pari (cioè la suddivisione di b è verticale) allora:

si prosegue la ricerca nel figlio LEFT, se xp< xc

si prosegue la ricerca nel figlio RIGHT, altrimenti
se n è a livello dispari (cioè la suddivisione di b è orizzontale) allora:

si prosegue la ricerca nel figlio BELOW, se yp< yc

si prosegue la ricerca nel figlio ABOVE, altrimenti
Se il nodo corrente n è una foglia FULL oppure EMPTY, allora possiamo cercare gli
eventuali triangoli che contengono il punto p a partire dal blocco descritto da n.
24
Localizzazione di un punto (3)

Tuttavia non è detto che sia possibile individuare tali triangoli: ad esempio, se siamo in
una foglia EMPTY non possiamo fare riferimento ad alcun triangolo oppure una foglia
FULL viene intersecata da triangoli differenti da quello memorizzato (non raggiungibili).
Durante la ricerca sono state scartate porzioni significative del dominio senza
verficarne l’importanza nella localizzazione del punto p in input.
25
Localizzazione di un punto (4)
TUTTAVIA:
 è necessario visitare un nodo FULL per poter accedere al triangolo ad esso associato,
altrimenti non verrà mai preso in considerazione
 è probabile che i triangoli contenenti il punto p siano associati a blocchi FULL il “più
vicino possibile” rispetto a p.
Soluzione proposta
 Individuare i blocchi della suddivisione in base alla loro distanza dal punto p, a partire
da quelli “più vicini” al punto p in input.
E’ possibile risolvere questo problema, proponendo una opportuna variante della
Nearest Neighbor Query.
Dati un insieme S di punti ed un punto Q si vuole
trovare il punto in S avente distanza minima dal
punto Q.
26
Incremental Nearest Neighbor Query
OBIETTIVO

Costruire in maniera incrementale l’insieme dei nodi dell’indice Triangulation PR kd-tree
ordinato in senso crescente rispetto alla distanza dei nodi dal punto p in input (punto da
localizzare).
INCREMENTAL NEAREST NEIGHBOR QUERY

In questo Progetto si userà l’algoritmo per la Ricerca Incrementale degli Elementi più
Vicini (in inglese Incremental Nearest Neighbor Query) in un PR quadtree, proposto in
G. Hjaltason e H. Samet, 1995

Questa tecnica può essere adattata facilmente all’indice Triangulation PR kd-tree.

Sfrutta la struttura dati coda con priorità per memorizzare i nodi da visitare.

In una coda con priorità gli elementi sono associati ad un valore numerico (priorità), che
determina l’ordine con cui essi vengono acceduti.

Due primitive fondamentali:

DELETE_MAX: rimuove l’elemento con priorità massima dalla coda

INSERT: inserisce un nuovo elemento nella coda in base alla sua priorità
Dovete fornire una implementazione della coda con priorità!
27
Distanza di un blocco da un punto

Dato un blocco b ed un punto p allora diremo che la distanza del blocco b dal punto p
sarà nulla se e soltanto se il punto p appartiene al blocco b.

In caso contrario, dobbiamo capire a quale quadrante appartiene il punto p (rispetto al
blocco b) e proseguire come mostrato in figura.

IMPORTANTE: la priorità di un blocco b (e quindi del nodo n che lo descrive) è definita
come l’inverso della distanza di b dal punto p.
28
Incremental Nearest Neighbor Query Algoritmo

Nella coda con priorità verranno memorizzati i nodi di un Triangulation PR kd-tree in
base alla loro priorità.

Dati un punto p da localizzare e T un indice spaziale Triangulation PR kd-tree, allora:
Passo 1: si inserisce in una coda con priorità Q (inizialmente vuota) il nodo radice di T.
Passo 2: se la coda Q non è vuota, si estrae dalla coda il nodo n con priorità massima e si
prosegue in base a n:

se n è di tipo EMPTY, allora non si esegue alcuna operazione;

se n è di tipo INTERNAL, allora si inseriscono i due figli di n nella coda Q;

se n è di tipo FULL, allora si controlla se il triangolo t memorizzato in n
contiene il punto p al suo interno: in caso affermativo si memorizza t.
Passo 3: si ripete nuovamente il passo 2.

L’algoritmo viene ripetuto fino a quando la coda con priorità Q non diventa vuota.
29
Incremental Nearest Neighbor Query –
Esempio 1

Nell’algoritmo appena proposto si visitano i nodi dell’indice Triangulation PR kd-tree a
partire da quelli più vicini al punto p da localizzare.

Solitamente, NON richiede la visita di un numero elevato di nodi, se il punto p appartiene
ad un triangolo.
30
Incremental Nearest Neighbor Query –
Esempio 2

Nel caso peggiore (quando il punto p da localizzare è esterno alla triangolazione),
dobbiamo visitare tutti i nodi dell’indice prima di concludere.
31
Approfondimenti

G. Hjaltason e H. Samet, Ranking in Spatial Databases, In Proceedings of the 4°
Symposium on Spatial Databases, volume 951 of Lecture Notes in Computer Science,
pagine 83-95, Portland, Maine, USA, Agosto 1995, Springer-Verlag

G. Hjaltason e H. Samet, Distance Browsing in Spatial Databases, ACM Transactions on
Database Systems, Volume 24, numero 2, pagine 265-318, 1999

H. Samet, Foundations of Multidimensional and Metric Data Structures, Morgan
Kaufmann Publisher, Agosto 2006
32