Rappresentazion e vettoriale Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. 1/27 GIS di tipo vettoriale • La primitiva fondamentale è il punto, definito da una coppia di coordinate. • Gli oggetti sono creati connettendo punti con linee rette, dette segmenti o archi: ogni arco ha due vertici. • Una linea (polilinea) è una spezzata costituita da segmenti: gli estremi della linea sono chiamati nodi. • Le aree sono rappresentate da linee chiuse, cioè da poligoni. Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. 2/27 Rappresentazione vettoriale dei dati: concetti generali Con rappresentazioni vettoriali, ogni elemento territoriale può essere rappresentato come: •punto (nodo): alberi, pali, aeroporti, città •linea (arco): fiumi, strade, fogne, •area (poligono): proprietà, città, comuni, foreste Quale tipo è usato dipende dalla scala: aeroporti o città possono essere punti o poligoni Dato che la rappresentazione dipende dalla forma, ArcView chiama i file contenenti dati territoriali shapefiles (che sono utilizzati sia per vettoriale che per raster) Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. 3/27 Rappresentazione Vettoriale: implementazione Y 1 • Elementi dello stesso tema (coverage) hanno identificatori unici - point ID, polygon ID, arc ID, ecc. • Identificatori comuni collegano : – tabelle di coordinate (il dove) – tabelle tematiche (il cosa) 5 4 2 3 X Coordinate Point ID x 1 1 2 2 3 4 4 1 5 3 y 3 1 1 2 2 Point ID 1 2 3 4 5 Attributi modello a b b a c anno 90 90 80 70 70 • Si utilizza una rappresentazione tipo DBMS relazionale Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. 4/27 Oggetti geometrici 1 3 2 4 1 2 Num. punto 1 2 3 4 Coordinate x,y 2,4 3,2 5,3 6,2 Num. Linea 1 2 Coordinate x,y 1,3 3,4 5,3 7,4 1,1 3,1 5,1 7,2 Num.poligono 1 2 1 Coordinate x,y 2,5 2,6 3,7 4,6 4,5 2,5 3,2 4,3 5,4 7,3 6,1 5,1 4,2 3,2 2 Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. 5/27 Legame fra oggetti e attributi • L’identificatore degli oggetti geometrici, FeatureId, da un lato compare nei file della geometria, dall’altro nella relazione con gli attributi. • La relazione in cui compare il FeatureId costituisce il collegamento fra il sistema di gestione della geometria e il sistema relazionale: è l’unica relazione gestita direttamente dal software GIS. • Un’operazione di join, realizzata sul campo FeatureId, permette di legare la geometria alle relazioni. Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. 6/27 Legame geometria-attributi 4 6 1 2 3 5 Featureid 1 2 3 4 5 6 Coordinate XY 1,5 5,5 5,5 8,5 8,5 10,5 5,9 4,8 3,7 4,6 5,5 5,5 4,6 3,5 2,4 1,3 8,5 8,7 FeatureId TipoStrada Pavimentaz. Larghezza Lunghezza Corsie Nome 1 1 asfalto 12 300 4 SS3 2 1 asfalto 12 300 4 SS3 3 1 asfalto 12 200 4 SS3 4 3 asfalto 10 400 2 SP24 5 3 asfalto 10 450 2 SP24 6 4 sterrato 4 100 1 Vicinale S.mauro Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. 7/27 Layer • Diversi tipi di informazione possono essere memorizzati si diversi layer (o temi). • Alcuni GIS non permettono di memorizzare nello stesso layer oggetti geometricamente diversi (es. punti e linee). • Il numero di layer in genere è inferiore a quello dei GIS raster. Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. 8/27 Precisione in un sistema vettoriale La precisione numerica finita associata ad ogni coordinata fa cadere i punti sugli angoli di una griglia. Conseguenze: la creazione di un nodo intersezione di due rette spezza le rette in segmenti non allineati. La griglia è comunque molto fine: con numeri a 32 bit si rappresentano più di 4.000.000.000 di interi 9/27 un millimetro su 4000- A.S.E. Km. Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione Precisione ed errori L’elevata precisione dei GIS vettoriali trasforma la normale imprecisione dei dati in veri e propri errori topologici, che possono essere osservati solo applicando forti ingrandimenti (zoom). Overshoot Linea mancante Undershoot Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. 10/27 Eliminazione degli errori I GIS forniscono strumenti per ripulire i dati dal tipo di errori appena visto. Si basano sulla definizine di opportune tolleranze che dovranno essere scelte sulla base della qualità dei dati. Esempio: CLEAN in ARC/INFO • Fuzzy tolerance: distanza minima tra coordinate • Dangle length: lunghezza min. per dangling arc • Node match tolerance: min. distanza tra nodi • Weed tolerance: min. distanza fra due vertici. Prima del CLEAN Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. Dopo il CLEAN 11/27 Sliver e loro eliminazione Si chiamano sliver poligons i piccoli poligoni dovuti alla imperfetta coincidenza nella digitazione multipla di unalinea (es. digitando separatamente due poligoni confinanti). Anche gli sliver si osservano con forti ingrandimenti. Il comando ELIMINATE di ARC/INFO permette di individuare sliver secondo diversi criteri (es. area minima) Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. 12/27 ELIMINATE Esempio di sliver poligons Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. 13/27 Strutture dati topologiche Servono per rappresentare le proprietà di adiacenza fra poligoni e connessione fra linee. E’ necessario gestire strutture dati specifiche. ESEMPIO: strutture dati topologiche in ARC/INFO • un poligono è costituito da una sequenza di linee (arcs) e non da un’unica linea; • le linee sono rappresentate una sola volta, anche se appartengono a due Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. 14/27 Topologia lineare in ARC/INFO Topologia arconodo 1 1 2 3 4 2 5 3 4 6 10 5 8 6 7 9 7 11 12 Lista archi-nodi # arco nodo DA nodo A 1 2 1 2 1 4 3 1 3 4 2 3 5 4 3 6 3 6 7 4 7 8 5 6 9 6 7 10 2 8 11 6 8 12 8 7 8 1 numero del nodo 1 numero dell’arco Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. Lista coordinate archi # arco coordinate XY 1 5,5 5,7 8,7 2 8,7 11,7 11,5 3 8,7 ... 9,5 4 5,5 9,5 5 11,5 9,5 6 ... 7 8 9 10 11 12 15/27 Topologia poligonale in ARC/INFO Contiguità 1 2 5 1 5 7 6 9 3 6 8 4 10 2 3 Lista sx-dx # arco Lpoly Rpoly 1 1 5 2 1 4 3 1 3 4 1 2 5 5 4 6 2 5 7 2 4 8 2 6 9 4 3 10 3 2 4 1 numero dell’arco 1 numero del poligono Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. Lista coordinate archi # linea Coord. XY 1 5,3 5,5 2 8,5 20,5 3 20,4 20,1 4 18,1 5,1 5 7,4 8,5 6 7,4 6,3 7 ... 8 9 10 8,5 ... ... 5,3 ... 16/27 Topologia poligonale in ARC/INFO Definizione aree Lista poligono-archi # poligono # linea 2 4, 6, 7, 10, 0, 8 3 3, 10, 9 4 7, 5, 2, 9 5 1, 5, 6 6 8 1 2 5 1 5 7 6 9 3 6 8 4 10 3 2 4 1 numero dell’arco 1 numero del poligono Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. Lista coordinate archi # linea Coord. XY 1 5,3 5,5 2 8,5 20,5 3 20,4 20,1 4 18,1 5,1 5 7,4 8,5 6 7,4 6,3 7 ... 8 9 10 8,5 ... ... 5,3 ... 17/27 QUADTREE come indici vettoriali • L’idea di base (come nel caso raster) è la decomposizione gerarchica dello spazio e la rappresentazione ad albero di tale gerarchia. • Nei sistemi vettoriali il Quadtree è usato come indice per individuare più rapidamente gli elementi geometrici presenti in una certa zona. • Il criterio alla base della suddivisione di un’area in sottoaree è dato dal numero massimo di elementi che possono appartenere ad una singola area Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. 18/27 QUADTREE come indici vettoriali Esempio Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. 19/27 Generalizzazione Consiste nel semplificare la rappresentazione eliminando dettagli, fondendo elementi molto vicini, ecc. Necessaria nella riduzione di scala. • Riduzione della quantità dei dati. • Riduzione del tempo di plotting. • Maggiore velocità nella conversione da vettoriale a raster e nella elaborazione vettoriale. Alcuni problemi derivanti da generalizzazioni non sono risolvibili automaticamente. Problema tipico: semplificazione di linee Algoritmo: Douglas Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. 20/27 Algoritmo di Douglas Douglas, Peucker, 1973 1) Costruisci una linea di trend fra i punti estremi 2) Trova il punto più lontano dalla linea di trend e confrontane la distanza con una soglia (parametrica). 3) Se sopra soglia, accetta il punto e identifica due nuove linee di trend. Torna al passo 2 su ogni linea. Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. 21/27 Vettoriale: vantaggi • I dati possono essere rappresentati nella loro forma e risoluzione originale, senza modifiche. • L’output grafico é di solito migliore (più vicino alla rappresentazione cartografica tradizionale). • La maggior parte dei dati é in formato vettoriale e non viene richiesta nessuna conversione. • Viene mantenuta una localizzazione geografica accurata delle località. • Permette una codifica più efficiente della topologia e rende quindi più efficienti le operazioni che richiedono informazioni topologiche, es. prossimità e elaborazioni su grafo. 22/27 Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. Vettoriale: svantaggi • La localizzazione di ogni vertice deve essere memorizzata esplicitamente. • Per molti tipi di analisi, i dati devono venire convertiti in strutture topologiche. Questo richiede elaborazioni pesanti e ripuliture dei dati. Inoltre la topologia é statica, e ogni aggiornamento dei dati vettoriali richiede di ricostruire la topologia. • Gli algoritmi di supporto alla manipolazione e analisi dei dati sono spesso complessi e computazionalmente pesanti. Questo limita intrinsecamente le funzionalità so grosse basi dati. • I dati continui, ad es. l’elevazione, non é rappresentata efficacemente in formato vettoriale. Spesso, é richiesta una generalizzazione e interpolazione dei dati per questo tipo di layers. • L’analisi spaziale e il filtraggio all’interno dei poligoni é impossibile. 23/27 Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. Confronto raster/vector • • • Nessuno dei due modelli è migliore in tutte le situazioni. Molti GIS, anche se più orientati a gestire l’uno o l’altro tipo, permettono la conversione (però vector raster facile, il contrario difficile). Un confronto può essere basato su 4 aspetti: 1) 2) 3) 4) Precisione Velocità di elaborazione Occupazione di memoria Caratteristiche rappresentate Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. 24/27 Precisione • La precisione vettoriale è superiore. Se un vettoriale ha precisione P (coordinate con precisione di 10 cifre e oltre), un raster per garantire lo stesso livello di dettaglio dovrebbe gestire P^2 celle. • Sul raster non esistono oggetti puntiformi, tutto ha almeno la dimensione di una cella. Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. 25/27 Velocità di elaborazione • L’elaborazione necessaria per risolvere problemi che coinvolgono overlay o analisi di prossimità è più veloce sul raster. • I sistemi vettoriali richiedono macchine più potenti e quindi supportano un numero minore di utenti simultanei. Occupazione di memoria • Il vettoriale è molto più compatto • L’occupazione è molto influenzata dalle strutture dati utilizzate, dalla compressione, ecc. Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. 26/27 Caratteristiche rappresentate • La rappresentazione vettoriale è più flessibile e si adatta meglio a situazioni di variabilità della densità di informazione. • La rappresentazione e identificazione di “oggetti” (strade, case, ecc.) e relazioni topologiche è molto più difficile in raster • Alcuni tipi di dati (es. foto satellitari) sono intrinsecamente raster. Vittorio Maniezzo - Algoritmi e Sistemi di Elaborazione - A.S.E. 27/27