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
Scarica

document