TPRQuadTree — un indice spaziale per la modellazione dei terreni

Per questo progetto viene richiesta l’implementazione di un prototipo di un sistema informativo geografico per effettuare interrogazioni spaziali su triangolazioni che rappresentano terreni. Dato un insieme V di punti nel piano ed un insieme di valori di elevazione per i punti di V, un modello di terreno consiste di una funzione di interpolazione lineare definita sulla triangolazione M con vertici sui punti di V nel piano xy.

Le operazioni di interrogazione sui modelli di terreno triangolati corrispondono a interrogazioni sulla triangolazione M proiettata sul piano. Nel nostro progetto considereremo quindi interrogazioni sulla triangolazione M. Per effettuare efficientemente delle interrogazioni su di una triangolazione, è necessario sovrapporre ad essa un indice spaziale.

In questo progetto useremo il Triangle-PR-quadtree, o brevemente TPR-quadtree.

Il TPR-quadtree è basato sul PR-quadtree visto a lezioni. Nel TPR-quadtree si utilizzano le medesime regole di suddivisione proprie del PR-quadtree, utilizzando come punti del dominio I vertici della triangolazione.

Il progetto consiste nel design e nell’implementazione di:

✔ la struttura dati per il TPR-quadtree
✔ un algoritmo per la costruzione di un TPR-quadtree per una triangolazione data
✔ alcune operazioni di interrogazione sulla triangolazione utilizzando il TPR-quadtree come indice spaziale.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *