MODELLI DI DATI GEOGRAFICI
MODELLIZZAZIONE DEI DATI
100
80
60
40
20
0
modellizzazione
esterna
modellizzazione
concettuale
modellizzazione
logica
modellizzazione
interna
1
MODELLI DI DATI GEOGRAFICI
STANDARDIZZAZIONE
DELL'INFORMAZIONE GEOGRAFICA
ENTI PRINCIPALI
•
ISO/IEC JTC1/SC32 – ISO/IEC Comitato Tecnico
Congiunto per le Informazioni Tecnologiche.
SC32 è il sottocomitato di JTC1 che si occupa dei
servizi di gestione dei dati, inclusi gli standard
legati alle unità di misura.
•
ISO/IEC JTC1/SC33 --SC33 è il sottocomitato di
JTC1 che si occupa dello standard ISO 8211
usato come standard di base per lo scambio di
dati geografici.
• ISO/IEC TC211– Comitato Tecnico per le
Informazioni
Geografiche e la Geomatica; è
formato da 33 paesi membri partecipanti e 16
paesi osservatori.
Ha 5 gruppi di lavoro:
WG1 – Sistemi di riferimento
WG2 – Modelli e operatori di dati geospaziali.
WG3 - Amministrazione di dati geospaziali.
WG4 - Servizi geospaziali.
WG5 - Profili e funzionali standard.
2
MODELLI DI DATI GEOGRAFICI
Chairman TC211:
Olaf Østensen
Statens kartverk
Norwegian Mapping Authority
Kartverksveien
N-3500 Hønefoss Norway
e-mail: [email protected]
Riferimento Italiano:
Ente Nazionale Italiano di Unificazione (UNI)
UNINFO
Corso Galileo Ferraris 93
I-10128 Torino (TO)
Italia
TP: + 39 011 591 964
TF: + 39 011 501 837
[email protected]
3
MODELLI DI DATI GEOGRAFICI
•
CEN TC287 – Organizzazione Europea
di standardizzazione per l’informazione
Geografica. TC287 ha 4 gruppi di
lavoro:
WG1 – Ambiti di standardizzazione.
WG2 – Modelli e applicazioni
WG3 – Trasferimento dei dati.
WG4 – Posizione dei sistemi di riferimento.
MATERIALE PRODOTTO:
CEN Report CR 13436:1998 Geog. Inf. - Vocabulary :
terminologia di riferimento adottata dal CEN/TC 287;
CEN Report CR 13425:1998 Geog. Inf. - Overview
ENV 12009:1997 Geog. Inf. - Reference model
ENV 12160:1997 Geog. Inf. - Data Description - Spatial
Schema
ENV 12656:1998 Geog. Inf. - Data Description - Quality
ENV 12657:1998 Geog. Inf. - Data Description - Metadata
ENV 12658:1998 Geog. Inf. - Data Description - Transfer
ENV 12661:1998 Geog. Inf. - Referencing - Geographic
identifiers
ENV 12762:1998 Geog. Inf. - Referencing - Direct Position
prENV 13376:1998 Geog. Inf. - Data Description - Rules
for Application Schemas
CEN Report CR12660:1998 Geog. Inf . - Processing Query and Update: spatial aspects.
4
MODELLI DI DATI GEOGRAFICI
DEFINIZIONE DI CARTA
SAN
FIREN
ZE
48.3
DELLA
SIGNORIA
50.1
50.6
VIA
DE'
50.0
GONDI
?
FILIPP
INA
PIAZZA
50.1
VIA
49.8
VIA
48.3
DE'
DE
I
VI
A
RU
ST
IC
I
RNO
VIA
DE'
VIA
VIN
EG
IA
VIA
DE
L
NE
RI
DE
'
VIA
DE
I
DE
LLA
VIA
VIA
VIA
REM
IGIO
M
OS
CA
46.8
VIA
SAN
VIA
D48.3
EI
VIA
S DI
REM AN
IGIO
GU
AN
TO
D'A
LTA
FRO
NTE
CA
STE
LLO
CA
STE
LLA
NI
DE
L
DE
'
PIAZ
ZALE
47.5
PIAZ
ZA
S
REM AN
IG IO
47.1
46.8
OS
TER
IA
DEG
LI
45.0
49.4
PIAZZA
LUIS
A
DE
'
DE'
47.8
GIUDICI
VIA
VIA
MAR
IA49.6
43.6
47.8
VIA
47.1
49.5
VIA
UFFIZ
I
DEL
CO
NIN
NA
PA
RL
AS
CIO
48.6 IA
DELL
A
GRECI
MAG
ALO
TTI
V
49.9
VIA
DEL
BAR
ON
CEL
LI
LEO
NI
VIA
BORG
O
DEI
VIA
DEI
SAPONA
I
Una carta è un insieme di punti, linee e aree definite:
♦ dalla posizione nello spazio
♦ da attributi non spaziali
Generalmente si considerano separate planimetria e
altimetria.
La LEGENDA della carta è la chiave di
connessione degli attributi non spaziali alle
entità spaziali.
Gli attributi non spaziali possono essere indicati
visivamente con COLORI, SIMBOLI, SFUMATURE il
cui significato è deducibile dalla legenda.
5
MODELLI DI DATI GEOGRAFICI
RELAZIONI SPAZIALI TRA ENTITA’
GEOGRAFICHE
L'analisi di una carta consente di:
•
dare una conoscenza del territorio sia
puntuale (basata sull'osservazione di ogni
singolo oggetto) che generale (visione
d'insieme);
•
di sviluppare processi logici di tipo
deduttivo e induttivo in funzione di relazioni di
concomitanza, vicinanza, frequenza,...;
Le relazioni spaziali tra entità geografiche
rintracciabili su una carta possono essere
classificate in vari modi.
Una distinzione è quella tra le relazioni che
sono indipendenti dall’orientamento, dette
RELAZIONI TOPOLOGICHE, e quelle che ne
dipendono, dette RELAZIONI DIREZIONALI.
Le relazioni topologiche tra entità geografiche
sono del tipo:
equivalenza (si sovrappone completamente);
equivalenza parziale (si sovrappone parzialmente,
attraversa);
contenimento (è interna);
adiacenza (è connessa o incontra);
separatezza (è disgiunta)
6
MODELLI DI DATI GEOGRAFICI
Le relazioni direzionali includono le seguenti
relazioni tra entità:
•
•
•
•
di fronte a
dall’altra parte di
sopra
sotto
• descrizioni metriche di angoli azimutali
•
•
•
•
a nord
a sud
a est
a ovest
e loro combinazioni
Si hanno poi relazioni di vicinanza che descrivono
la distanza tra entità geografiche sia in termini
metrici quantitativi (misura della distanza) che in
termini qualitativi, mediante termini quali
• vicino
• lontano
• in prossimità di
Relazioni topologiche, direzionali e di vicinanza
sono spesso utilizzate combinate tra loro
7
Modelli di dati geografici
ESEMPIO DI RELAZIONI SPAZIALI TRA ENTITA’
e
h
f
d
c
b
g
a
• Topologiche
b è interno a c
a è connesso a c
d è disgiunto da a
f è sovrapposto a e
• Vicinanza
a vicino a b
f lontano da a
• Direzionali
g a est di b
d a nord di g
8
Modelli di dati geografici
CARTOGRAFIA NUMERICA
• coordinate che descrivono gli schemi
spaziali che rappresentano gli oggetti del
territorio o le entità geografiche (features);
• relazioni tra gli elementi di tale
rappresentazione;
• attributi che ne individuano la tipologia.
La cartografia numerica è un’immagine
speculare della cartografia tradizionale
(Galetto, Spalla):
• l’elemento base della cartografia tradizionale è
un disegno che contiene in forma implicita le
coordinate dei punti
• nella cartografia numerica l’elemento base è
l’insieme delle coordinate che contiene in
forma implicita la sua visualizzazione sotto
forma di disegno.
La cartografia numerica ha tutti i contenuti e
almeno tutte le stesse funzioni di base della
cartografia tradizionale.
9
Modelli di dati geografici
ENTITA' E CAMPI
Astraendo dal loro contenuto, i dati georeferenziati
possono essere ripartiti nelle categorie principali di
campi o di entità.
I campi sono rappresentativi di fenomeni continui
quasi ovunque nel dominio di definizione, quali ad
esempio il rumore ambientale piuttosto che l’altimetria
del territorio; i campi vengono usualmente
discretizzati, e rappresentati mediante matrici regolari
di attributi (modello matrix o raster georeferenziato)
Alla seconda categoria (entità) appartengono
viceversa
gli
oggetti
discontinui,
delimitati
spazialmente
da
confini
ben
precisi
ed,
eventualmente, caratterizzati da specifici attributi: un
esempio di entità sono la ripartizione del territorio in
aree normative piuttosto che il grafo descrittivo di una
rete di infrastrutture di trasporto; in ambito GIS le
entità vengono usualmente rappresentate mediante
modelli vettoriali, eventualmente topologici, cui
vengono associate opportune tabelle di attributi.
10
Modelli di dati geografici
FENOMENI GEOGRAFICI MODELLIZZABILI
A CAMPI
MODELLO DIGITALE DEL TERRENO
FENOMENO
SPAZIALE
?
GRIGLIA - RASTER
IMMAGINE TELERILEVATA
11
Modelli di dati geografici
PER UN MODELLO DIGITALE E' POSSIBILE ANCHE UNA
RAPPRESENTAZIONE A CURVE DI LIVELLO
Predictions (Km)
5150
-15
-19
5100
-23
-27
5050
-31
North (Km)
-35
5000
-39
-43
4950
-47
-51
-55
Differences (Km)
4900
From -25 to -15
From -15 to -10
From -10 to -5
From -5 to 5
From 5 to 10
From 10 to 15
From 15 to 25
4850
4800
1300
1350
1400
1450
1500
1550
1600
East (Km)
O
UNA
RAPPRESENTAZIONE
IRREGOLARI (TIN)
FENOMENO
SPAZIALE
?
PUNTI - CURVE
SUPERFICI
12
A
TRIANGOLI
Modelli di dati geografici
FENOMENI GEOGRAFICI MODELLIZZABILI
A ENTITA'
MODELLO A ENTITA'
FENOMENO SPAZIALE
?
GEOMETRIA: PUNTO - CURVA - SUPERFICIE
TOPOLOGIA: NODO - SPIGOLO - FACCIA
13
Modelli di dati geografici
MA LA CARTA POTREBBE ESSERE DERIVATA DA UNA
IMMAGINE DIGITALE
?
0 1 0 0
0 1 0 3
0 1 0 0
0 0 2
0 0 2
0 0 0
2
2
0
2
2
0
0 1 0 0
0 0 4
4
0
0 1 0 0
0 1 0 0
0 0 0
0 0 0
0
0
0
0
Inoltre:
in molti casi può essere più comodo trattare dati grigliati
(ad esempio si possono usare algoritmi di algebra
matriciale)
non ci sono più, come nel passato, problemi legati
all'occupazione di memoria di massa.
→ I FENOMENI GEOGRAFICI POSSONO
ESSERE MODELLIZZATI SECONDO UN
MODELLO IBRIDO
14
Modelli di dati geografici
→ PROBLEMA DELLA RASTERIZZAZIONE E
VETTORIALIZZAZIONE
⇒DIVERSI CRITERI DI RASTERIZZAZIONE
• DEL CENTRO
• DI IMPORTANZA
• DI DOMINANZA
⇒DIVERSI ALGORITMI UTILIZZATI PER LA
VETTORIALIZZAZIONE (AD ESEMPIO IN GRASS SI
UTILIZZA IL METODO DETTO DI BRESHENAM)
ATTENZIONE:
IL
RISULTATO
DI
RASTERIZZAZIONE
E
VETTORIALIZZAZIONE
DIPENDE DAL PACCHETTO GIS UTILIZZATO
(OLTRE CHE OVVIAMENTE DAL PASSO DI
RISOLUZIONE E DAL METODO ADOTTATO)!
15
Modelli di dati geografici
MODELLIZZAZIONE DI DATI GEOGRAFICI
I dati appartenenti a una base di dati geografici sono
sostanzialmente composti da tre componenti:
aspetto spaziale
geometria/topologia
aspetto semantico:
attributi statistici e/o
testuali
aspetto di qualità
La geometria di un fenomeno, descritta per
mezzo di coordinate di punti e funzioni
matematiche, usa come elementi standard di
base le primitive geometriche e dipende dal
sistema geodetico di riferimento adottato e dalla
scala di rappresentazione (la scala definisce il
dettaglio e le approssimazioni rispetto alla
"realtà").
La componente geometrica può essere
• vettoriale (coordinate dei punti che descrivono
la forma geometrica)
• raster (insieme di
particolare oggetto)
pixel
16
corrispondenti
al
Modelli di dati geografici
La componente vettoriale può contenere o meno
la descrizione della topologia associata alle entità
geografiche considerate.
La topologia (relazioni topologiche: adiacenza,
connessione e contenimento) è invariante per
deformazioni elastiche e continue (ad esempio
trasformazioni di datum o di sistema di coordinate)
ed è descritta a partire da primitive topologiche.
Una volta definito un oggetto come fenomeno
singolo del mondo reale lo schema spaziale
fornisce la descrizione della sua geometria e
topologia.
La componente semantica è data dall’insieme
degli attributi di vario dominio (numerico,
stringa,…) associati alla parte geometrica del
dato.
L'aspetto di qualità è descritto mediante le
categorie
di
accuratezza,
completezza
ed
aggiornamento.
17
Modelli di dati geografici
TOPOLOGIA
L'aspetto geometrico delle entità geografiche è
descritto in ultima analisi da coordinate di punti
relativamente ad un sistema geodetico di riferimento
(posizionamento diretto).
La geometria che descrive le entità di un territorio può
variare in funzione di molti fattori, ad esempio al
variare della scala nominale della rappresentazione
digitale.
regione A
regione B
carta 1
carta 2
inconsistenza
Per garantire quindi la consistenza della
rappresentazione si devono introdurre dei vincoli
e delle relazioni di tipo non metrico.
18
Modelli di dati geografici
⇒ linea nera = confine svizzero misure ETH
⇒ linea verde = confine CTR lombardia 1:10000
⇒ linea rossa = confine svizzero carta svizzera
1:200000 digitalizzata
19
Modelli di dati geografici
La topologia è la disciplina matematica che si occupa
di connessione e adiacenza di punti e linee e che
permette quindi di analizzare le relazioni spaziali tra
dati geografici.
Una struttura dati topologica determina
esattamente come e dove sono connessi
punti e linee su una carta numerica per mezzo
di congiunzioni topologiche, dette nodi.
La teoria dei grafi è lo strumento utilizzabile per
rendere consistente una carta numerica descritta per
mezzo di primitive geometriche.
Un qualsiasi aggiornamento della carta dovrà
rispettare i vincoli topologici imposti alle varie
entità geografiche coinvolte.
20
Modelli di dati geografici
DESCRIZIONE DELL'ASPETTO SPAZIALE
DI DATI GEOGRAFICI
Per descrivere gli aspetti spaziali dei dati geografici
abbiamo seguito le indicazioni riportate nel
prestandard europeo (ENV 12160, 1997) del CEN1
ratificate dal UNI2.
Le primitive geometriche descrivono, parzialmente o
totalmente, la rappresentazione spaziale di un oggetto
mediante coordinate e funzioni matematiche: tutte
le posizioni che concorrono alla descrizione di una
primitiva devono essere riferite allo stesso sistema
geodetico di riferimento.
Le entità geometriche utilizzate per la descrizione di
fenomeni spaziali nel dominio bidimensionale sono:
campi
entità vettoriali
griglia
pixel
banda raster
voxel
blocco raster
punto
curva
superficie
1
Comité Européen de Normalisation.
Ente Nazionale Italiano di Unificazione.
2
21
Modelli di dati geografici
PRIMITIVE GEOMETRICHE
⇒ Punto: è una primitiva geometrica 0-dimensionale,
la cui posizione spaziale è descritta da coordinate
(posizionamento diretto: insieme ordinato di numeri
in un sistema di riferimento di posizioni).
⇒ Curva: è una primitiva geometrica limitata,
continua, monodimensionale e può essere chiusa
o aperta.
Una curva è descritta da un metodo di
interpolazione3 applicato ad una lista di due o più
posizioni dirette.
Una curva può intersecare se stessa
esplicitamente (nella lista delle coordinate ci sono
uno o più valori ripetuti)
• implicitamente (il metodo di interpolazione
applicato alla lista di coordinate dà luogo al
passaggio della curva due o più volte dalla stessa
posizione spaziale).
•
curva intrecciata
esplicitamente
curva intrecciata
implicitamente
3
metodi di interpolazione: cammino minimo, arco, Bspline, clotoide.
22
Modelli di dati geografici
⇒ Bordo: è un elemento chiuso monodimensionale
non
intrecciato
(né
esplicitamente,
né
implicitamente); può essere composto da una o più
curve.
⇒ Superficie: è una primitiva geometrica limitata,
continua, bidimensionale, delimitata da un bordo
esterno e da zero o più bordi (o confini) interni non
annidati e non intrecciati.
superficie
possibile
superficie
non
possibile
23
superficie
non
possibile
Modelli di dati geografici
⇒ Struttura (frame): è una primitiva basata su una
partizione con areole dello spazio considerato: tali
areole sono l'elemento base della struttura. La
forma e dimensione delle areole lungo ogni asse
del sistema di riferimento scelto per la struttura
sono costanti e caratterizzano la struttura stessa.
Si considerano strutture bi o tridimensionali:
nell’ultimo caso la struttura è una partizione
costituita da uno o più piani contigui di righe e
colonne contigue, di unità regolari che riempiono
una parte limitata dello spazio.
Dato un ordine di numerazione lungo i tre assi, ogni
elemento unitario nella struttura è univocamente
definito da tre numeri interi: numero di riga, numero
di colonna, numero di piano.
Deve inoltre essere definita la posizione diretta
dell'origine (0, 0, 0) della struttura in uno specifico
sistema geodetico di riferimento e secondo un
determinato sistema di coordinate.
24
Modelli di dati geografici
In un sistema piano si può definire un angolo di
rotazione tra gli assi del sistema di coordinate e gli
assi della struttura.
Struttura in un sistema di riferimento geografico
Struttura in un sistema di riferimento piano
25
Modelli di dati geografici
⇒ Griglia: è una distribuzione regolare di punti,
derivabile dagli angoli di tassellatura, determinati
da una struttura. Una griglia è definita in accordo
con la specifica struttura che fornisce la posizione
spaziale di ogni punto della griglia stessa.
⇒ Pixel: è una primitiva geometrica bidimensionale,
elemento base (o unità) di una specifica struttura
bidimensionale. La sua posizione spaziale è
definita dal numero di riga e di colonna.
P(i,j)
j
i
⇒ Banda raster: è una primitiva geometrica
bidimensionale costituita da una porzione limitata
e rettangolare di una specifica struttura
rettangolare bidimensionale.
26
Modelli di dati geografici
⇒ Voxel:
è
una
primitiva
geometrica
tridimensionale, elemento base per una specifica
struttura a tre dimensioni.
⇒ Blocco raster: è una primitiva geometrica
corrispondente ad una parte limitata di una
struttura a tre dimensioni.
27
Modelli di dati geografici
PRIMITIVE TOPOLOGICHE
Le primitive topologiche descrivono gli aspetti
topologici delle entità geografiche stabilendo delle
relazioni che le connettono.
Gli aspetti topologici di un oggetto possono essere
descritti da una o più primitive topologiche.
Le entità topologiche per una descrizione nel
dominio bidimensionale sono:
nodo
spigolo
anello
faccia
28
Modelli di dati geografici
⇒ Nodo: è una primitiva topologica 0-dimensionale.
Si può distinguere tra due tipi di nodi.
•
Nodo connesso. Si tratta di un nodo connesso
ad uno o più spigoli. In questo caso si può
ulteriormente distinguere tra nodo che è iniziale o
finale di uno spigolo, detto nodo terminale, e
nodo che è solo intersezione di lati, in questo
caso si parla di nodo intermedio.
•
Nodo isolato: nodo che non è connesso con
nessuno spigolo.
Si può osservare che quello che può essere
considerato nodo intermedio se riferito ad un
determinato spigolo può anche essere terminale
rispetto ad un altro spigolo.
⇒ Spigolo:
è
una
primitiva
topologica
monodimensionale
che
rappresenta
una
connessione orientata tra due nodi terminali; i due
nodi possono essere coincidenti.
⇒ Anello: è un insieme ordinato di spigoli connessi
che formano un elemento monodimensionale non
intersecantesi né implicitamente né esplicitamente.
I punti estremanti di un anello convergono allo
stesso nodo.
⇒ Faccia: è una primitiva topologica descritta da un
anello esterno e da zero a molti anelli interni.
29
Modelli di dati geografici
LE PRIMITIVE TOPOLOGICHE DEFINITE SONO
LEGATE TRA LORO DA UN INSIEME DI
RELAZIONI:
1. Un nodo terminale è:
⇒ punto iniziale di 0-m spigoli
⇒ punto finale di 0-m spigoli.
2. Un nodo intermedio giace su 1-m spigoli.
3. Un nodo isolato appartiene a 0-m facce.
4. Uno spigolo
⇒ può contenere da 0 a m nodi intermedi;
⇒ ha da 0 a 1 spigoli precedenti;
⇒ ha da 0 a 1 spigoli seguenti;
⇒ ha da 0 a m facce a destra;
⇒ ha da 0 a m facce a sinistra;
⇒ è un componente di 0-m anelli.
5. Un anello
⇒ è composto da 1-m spigoli;
⇒ è anello esterno di 0-1 faccia;
⇒ è interno di 0-1 faccia.
6. Una faccia
⇒ ha un solo anello esterno;
⇒ ha 0-m anelli interni;
⇒ può contenere 0-m nodi isolati.
30
Modelli di dati geografici
MODELLI SPAZIALI
I modelli spaziali considerati si rifanno alla teoria dei
Grafo.
La definizione di grafo si basa semplicemente
⇒ sull'esistenza di due insiemi disgiunti V e S
(insieme dei vertici e degli spigoli)
⇒ sui rapporti di incidenza di vertici e spigoli mediante
un'applicazione.
I rapporti di incidenza possono essere descritti da
coppie ordinate.
Se i vertici vi e vf incidono con lo spigolo s questo può
essere descritto associando allo spigolo s la coppia
(vi, vf) o (vf, vi).
Le due coppie (vi, vf) e (vf, vi) sono del tutto
equivalenti (vale una relazione d'equivalenza E).
Allora se VxV è l'insieme di tutte le coppie ordinate di
vertici, allora VxV/E è l'insieme delle classi di coppie
[(vi, vf)]=[ (vi, vf), (vf, vi)].
Le relazioni di incidenza si possono descrivere
attraverso applicazioni da S a VxV/E.
Siano V e S due insiemi disgiunti,
g :S→VxV/E un'applicazione.
Allora la terna G = (V,S,g) si dice grafo con insieme
di vertici V e insieme di spigoli S.
31
Modelli di dati geografici
Definizione: se s ∈ S e g(s) = [(vi, vf)], allora vi e vf
sono collegati attraverso s.
vi
s
vf
Definizione: se vi = vf lo spigolo è detto cappio o
circuito.
vi = vf
g(s1) = g(s2)
s1, s2 ∈ S
s1 ≠ s2
si ha un biangolo.
Definizione: se
vi
s1
vf
s2
32
Modelli di dati geografici
Definizione: un grafo si dice planare (o piano) se è
rappresentabile nel piano.
Definizione: un grafo è detto orientato se per ogni
spigolo si indica il punto di origine. In un grafo
orientato ad ogni spigolo si assegna un verso di
percorrenza rappresentato con una freccia.
Definizione: un grafo è detto completo se i vertici a
due a due sono collegati esattamente con uno
spigolo.
33
Modelli di dati geografici
Definizione: il grado di un vertice v è la cardinalità
dell'insieme di tutti gli spigoli che incidono con il
vertice v stesso.
Se si considerano grafi finiti (cioè con un numero
finito di vertici) senza cappi e biangoli, il grado del
vertice fornisce anche il numero dei vertici che sono
collegati al vertice attraverso gli spigoli.
Il numero degli spigoli è dato da:
1
ns = ∑ grado (v)
2 v∈V
In un grafo finito con nv vertici, il grado di ogni
vertice è
grado (v) = nv- 1
Il numero degli spigoli è quindi
ns =
1
2
nv(nv- 1)
Definizione: un grafo in cui tutti i vertici hanno lo
stesso grado si dice regolare.
34
Modelli di dati geografici
Definizione: una successione finita di vertici vx
collegati da spigoli sx (vi, s1, v1, s2 , …, vf) si dice
catena con origine nel punto vi e termine nel punto vf.
Vertici e spigoli possono ripetersi.
vi
s2
s1
s7
s4
s5
s3
vf
s6
Definizione: una catena è chiusa se vi = vf.
vi
s2
s1
s5
s7
s4
s6
s3
vf
Definizione: una catena è semplice se nessuno
spigolo è ripetuto.
Definizione: una catena con vertici a due a due
disgiunti è detta cammino.
vi
s2
s1
s5
s4
s3
s6
35
vf
Modelli di dati geografici
GRAFI E STRUTTURA TOPOLOGICA
⇒ I modelli basati sui grafi sono quei modelli
geometrici con struttura topologica che
collegano tramite puntatori i dati relativi a facce,
spigoli e nodi associati a entità spaziali.
⇒ Ci sono quindi due tipi di informazioni:
⇒ puntatori: definiscono le connessioni tra le
primitive topologiche
⇒ dati numerici, che possono essere
coordinate di punti o parametri di equazioni di
curve e superfici e descrivono quindi le
primitive geometriche.
36
Modelli di dati geografici
SCHEMI SPAZIALI CEN 287
Vediamo ora gli schemi spaziali, cioè gli schemi
secondo i quali le primitive precedenti possono essere
aggregate per definire e descrivere gli aspetti spaziali
dei dati geografici.
Un qualsiasi dato geografico
può essere descritto facendo
riferimento ad un qualsiasi
schema spaziale definito dal
proprietario dei dati; in tal caso il
produttore e/o proprietario della
cartografia specifica quali sono
le primitive che partecipano alla
descrizione del dato spaziale.
CEN TC 287
SCHEMA G1
In alternativa alla creazione
di
un
proprio
schema
spaziale personalizzato si
può fare riferimento agli
schemi
predefiniti
nel
prestandard europeo ENV
12160.
37
Modelli di dati geografici
Schema di base G0
Lo schema G0 è uno schema completo di tutte le
primitive geometriche e topologiche descritte
precedentemente, utile come base per definire uno
schema spaziale personalizzato. Tutti gli schemi
predefiniti che seguono sono stati progettati facendo
riferimento a questo schema di base. Un set di dati
geografici definito facendo riferimento a questo
schema sarà composto da un insieme di primitive
topologiche e geometriche.
Primitive
geometriche
punto
curva
superficie
struttura
griglia
pixel
banda raster
voxel
blocco raster
Primitive
topologiche:
nodo:
intermedio
terminale
isolato
spigolo
anello
faccia
Vincoli sulle primitive: non sono previsti vincoli
aggiuntivi a quelli dati nelle definizioni.
38
Modelli di dati geografici
ESEMPIO DI DIFFERENTI DESCRIZIONI
DELLO STESSO FENOMENO SECONDO
DIVERSI SCHEMI SPAZIALI.
STRADA 3
B
STRADA 4
D
G
STRADA 2
STRADA 1
A
STRADA 2
• 5 strade (strada1, strada2, , strada5)
• 6 incroci reali di strade
• 1 pseudo-incrocio (una strada è sopraelevata
rispetto alla seconda)
• 9 particelle catastali
E
C
STRADA 4
F
STRADA 5
H
I
STRADA 1
?
39
Modelli di dati geografici
SCHEMA SPAZIALE G0:
DESCRIZIONE GEOMETRICA
STRADA 4
D
G
STRADA 2
STRADA 1
STRADA 3
B
A
E
C
STRADA 4
F
STRADA 5
H
I
STRADA 1
Primitive geometriche utilizzate:
• curve: in questo caso sono segmenti di retta
• punti: i punti sono vertici di segmenti ( )
oppure sono punti il cui attributo è un elemento
di toponomastica ( )
• superfici: le particelle sono rappresentate da
superfici, le strade da insiemi di superfici
(corrispondenti a tronchi e incroci)
40
Modelli di dati geografici
SCHEMA SPAZIALE G0:
DESCRIZIONE TOPOLOGICA
Primitive topologiche utilizzate (esempio):
• nodo (ad ogni intersezione di curve introduco
un nodo)
• spigolo
• faccia (le facce corrispondono alle particelle, a
tronchi di strada e a incroci di strade)
41
Modelli di dati geografici
Grafo topologico planare completo G1
Primitive
topologiche:
nodo:
terminale
isolato
spigolo
faccia
Primitive
geometriche
punto
curva
Vincoli sulle primitive:
⇒ Due punti distinti non possono avere la stessa posizione;
⇒ Le facce devono riempire completamente il piano senza
mai sovrapporsi;
⇒ Le curve descriventi uno spigolo devono essere
connesse; in tutti gli altri casi non possono né
autointersecarsi né intersecare altre curve, sia
implicitamente che esplicitamente.
⇒ Il posizionamento diretto del nodo iniziale di uno spigolo
deve essere uguale al posizionamento diretto della prima
curva che descrive lo spigolo;
⇒ il posizionamento diretto del nodo finale deve essere
uguale al posizionamento diretto dell’ultima curva che
descrive lo spigolo;
⇒ un nodo isolato deve necessariamente appartenere ad
una determinata faccia.
(esempio Arc/Info)
42
Modelli di dati geografici
Grafo planare rete lineare G2
Primitive
topologiche:
nodo:
terminale
isolato
spigolo
Primitive
geometriche
punto
curva
STRADA 3
B
STRADA 4
D
G
STRADA 2
STRADA 1
A
STRADA 2
Vincoli sulle primitive: valgono gli stessi vincoli
definiti per lo schema G1.
E
C
STRADA 4
F
STRADA 5
H
I
STRADA 1
Grafo planare delle strade
N.B.: non si riescono a descrivere fenomeni non
planari, come ad esempio la sovrapposizione di
strade
43
Modelli di dati geografici
Grafo non planare rete lineare G3
Primitive
topologiche:
nodo:
terminale
isolato
spigolo
Primitive
geometriche
punto
curva
Vincoli sulle primitive:
⇒ due punti
posizione;
distinti
non
possono
avere
medesima
⇒ il posizionamento diretto del nodo iniziale di uno spigolo
deve essere uguale al posizionamento diretto della prima
curva che descrive lo spigolo;
⇒ il posizionamento diretto del nodo finale deve essere
uguale al posizionamento diretto dell’ultima curva che
descrive lo spigolo.
Sono consentite intersezioni tra curve e tra spigoli
senza che queste creino necessariamente nodi.
44
STRADA 3
B
STRADA 4
D
G
STRADA 2
STRADA 1
A
STRADA 2
Modelli di dati geografici
E
C
STRADA 4
F
STRADA 5
H
I
STRADA 1
Grafo non planare delle strade
45
Modelli di dati geografici
Grafo non planare rete lineare con superfici
G4
Primitive
topologiche:
nodo:
terminale
isolato
spigolo
Primitive
geometriche
punto
curva
superficie
Vincoli sulle primitive:
STRADA 3
B
STRADA 4
D
G
STRADA 2
STRADA 1
A
STRADA 2
le superfici non devono necessariamente riempire tutto lo
spazio e possono anche sovrapporsi fra loro; per il resto
delle primitive restano definiti i vincoli già citati nello schema
G3
E
C
STRADA 4
F
STRADA 5
H
I
STRADA 1
Descrizione geometrica mediante curve e superfici (le
superfici si riferiscono alle strade che hanno larghezza
maggiore di un certo valore prefissato).
46
Modelli di dati geografici
Spaghetti G5
Primitive
geometriche
punto
curva
Vincoli sulle primitive:
nessuno
A
C
B
D
E
G
H
F
I
Strato informativo particelle: si noti che la curva che
separa H ed I è ripetuta (ad es. cartografia tecnica
comunale con modellizzazione solo geometrica).
47
B
STRADA 4
D
G
STRADA 2
STRADA 1
A
E
STRADA 3
Modelli di dati geografici
C
STRADA 4
F
STRADA 5
H
I
STRADA 1
Descrizione della geometria mediante le primitive:
• curve: in questo caso sono segmenti di retta
• punti: i punti sono vertici di segmenti ( ) oppure
sono punti il cui attributo è un elemento di
toponomastica ( )
N.B.: una descrizione geometrica di questo tipo è
quella di dati catastali del Dipartimento del Territorio
trasferiti tramite il formato di trasferimento NTF del
Catasto Geometrico.
48
Modelli di dati geografici
Rete irregolare di figure triangolari G6
Primitive
topologiche:
nodo:
terminale
spigolo
faccia
Primitive
geometriche
punto
Vincoli sulle primitive:
⇒ punti distinti non possono avere la stessa posizione;
⇒ non è ammessa la sovrapposizione tra facce;
⇒ si hanno solo facce triangolari descritte da tre spigoli.
49
Modelli di dati geografici
Immagine raster G7
Primitive
geometriche
struttura
banda raster
Vincoli sulle primitive:
nessuno.
Immagine raster
50
Modelli di dati geografici
Griglia spaziale G8
Primitive
geometriche
struttura
griglia
Vincoli sulle primitive:
la forma delle areole che compongono la struttura
deve essere rettangolare.
51
Modelli di dati geografici
MODELLO VETTORIALE TOPOLOGICO
B
l6
a
l1
l5
l4
C
b
l7
c
A
D
E
l9
l8
d l
3
l2
e
F
ESERCIZIO: Descrivere geometria e topologia della
carta riportata nell'esempio (nodi, spigoli e facce)
GEOMETRIA DEI NODI
NODO
A
B
C
D
E
F
X
0.0
1.5
1.5
4.0
7.0
7.0
Y
0.0
4.0
3.0
1.5
3.2
0.0
GEOMETRIA DEGLI SPIGOLI
SPIGOLO
l1
l2
l3
l4
l5
l6
l7
l8
l9
1.5, 4.0
0.0, 0.0
7.0, 0.0
7.0, 3.2
0.0, 0.0
1.5, 3.0
1.5, 3.0
7.0, 3.2
4.0, 1.5
COORDINATE
0.0, 4.0
0.0, 0.0
7.0, 0.0
7.0, 3.2
7.0, 4.0
1.5, 4.0
1.5, 3.0
1.5, 4.0
4.0, 1.5
4.0, 1.5
7.0, 3.2
52
Modelli di dati geografici
TOPOLOGIA DELLE FACCE
(considerata la rotazione
in senso antiorario, se lo
spigolo è orientato in
senso
opposto,
si
aggiunge il segno -)
FACCIA
a
b
c
d
e
SPIGOLO
l1,-l5,l6
l4,-l6,l7,l9
l2,l8,-l7,l9
l3,-l8,-l9
l1,l2,l3,l4
NODO
A
B
C
D
E
F
SPIGOLI
l2,-l5,-l1
-l4,-l6,l1
l5,l6,l7
-l7,-l8,l9
-l9,-l3,l4
-l2,l3,-l8
TOPOLOGIA DEI NODI
(se lo spigolo è entrante
si aggiunge il segno -)
TOPOLOGIA DEGLI SPIGOLI
SPIGOLO NODO
INIZIALE
l1
B
l2
A
l3
F
l4
E
l5
C
l6
C
l7
C
l8
F
l9
D
NODO
FINALE
A
F
E
B
A
B
D
D
E
FACCIA
DESTRA
e
e
e
e
a
b
c
d
d
53
FACCIA
SINISTRA
a
c
d
b
c
a
b
c
b
Modelli di dati geografici
CREAZIONE DELLA TOPOLOGIA COMPLETA
Fi
F1
nodo
faccia di
inviluppo
F2
F3
1. Connessione delle curve per formare i bordi.
Le curve sono ordinate in funzione dell’estensione
(coordinate X,Y minime e massime) cosicché curve
topologicamente vicine risultino vicine anche nel
datafile (risparmio di tempo nella ricerca di curve
adiacenti).
Le curve vengono poi esaminate per valutare le
intersezioni: punti di congiunzione sono costruiti per
tutte le curve che si uniscono e i record contenenti le
coordinate dei punti della curva sono estesi in modo
tale da contenere anche i puntatori alle altre curve
e gli angoli tra curve intersecantisi.
Le curve che si intersecano in punti diversi da quelli
finali sono automaticamente spezzate in nuove curve.
54
Modelli di dati geografici
2. Test sulla chiusura delle facce.
Il grafo risultante può essere facilmente controllato per
quanto riguarda la chiusura controllando i record che
descrivono le curve per verificare se ogni curva ha
dei puntatori da e verso almeno un'altra curva.
Un' ”altra curva” potrebbe essere la curva stessa nel
caso di poligono semplice (costituito da una sola
faccia, eventualmente con superfici di esclusione
all’interno) o nel caso di una superficie di esclusione
semplice (definita da una singola curva).
A tutte le curve che non passano il test deve essere
associato un flag in modo tale che siano visibili con
simboli particolari in fase di visualizzazione.
3. Connessione delle curve per formare le facce.
Come primo passo si crea la faccia di “inviluppo” del
contorno esterno della mappa.
Questa entità consiste di record contenenti:
• un identificatore unico;
• un codice che identifica che si tratta di una faccia di
inviluppo;
• un puntatore ad anello;
• una lista di puntatori alle curve di contorno;
• l’area corrispondente alla faccia;
• la sua estensione (valori minimi e massimi delle
coordinate dei vertici del rettangolo che la contiene).
55
Modelli di dati geografici
La faccia di inviluppo non è vista dall’utente e il scopo
è solo quello di permettere la costruzione della
struttura topologica della rete.
La faccia di inviluppo è creata seguendo le curve
attorno al bordo esterno procedendo in senso orario e
scegliendo ad ogni nodo la curva più a sinistra.
L’identificatore di ogni curva è registrato e archiviato
insieme agli altri dati e un flag è settato per indicare
che ogni curva è stata attraversata una volta.
Una volta che è stato creata la faccia esterna, o di
inviluppo, vengono create quelli interne.
Si riparte dal punto precedente ma in questo caso,
procedendo in senso orario, viene scelta ad ogni
punto di giunzione la curva più a destra.
Deve essere tenuto conto del numero di volte che la
curva viene attraversata: se viene attraversata per la
seconda volta si finisce la ricerca.
Quando si ritorna al punto di partenza sono state
identificate tutte le curve componenti la faccia.
56
Modelli di dati geografici
Nello stesso tempo viene fatto il controllo sull’angolo
di rotazione cumulato ad ogni nodo (se alla fine non è
uguale a 360°, per il teorema del cammino chiuso,
l'anello che contorna la faccia è intrecciato).
Come per la faccia di inviluppo, così la prima entità
faccia è caratterizzata da un insieme di informazioni:
• identificatore;
• codice della faccia;
• puntatore ad anello dalla faccia di inviluppo (nello
stesso tempo l’identificatore di questa faccia è scritto
nel puntatore ad anello della faccia di inviluppo);
• una lista di tutte le curve di contorno (allo stesso
tempo, l’identificatore della faccia è scritto nel record
della curva);
• un puntatore ad anello alla faccia "seguente" nel
grafo;
• la sua estensione (MBR = minimum bounding
rectangle).
La ricerca procede alla faccia seguente nello stesso
modo. In questo caso il puntatore ad anello contiene
l'identificatore della faccia precedente (e di quella
seguente).
57
Modelli di dati geografici
Una qualsiasi faccia è quindi caratterizzata da:
• identificatore;
• codice della faccia;
• puntatore ad anello dalla faccia "precedente" (nello
stesso tempo l’identificatore di questa faccia è scritto
nel puntatore ad anello della "precedente");
• una lista di tutte le curve di contorno (allo stesso
tempo, l’identificatore della faccia è scritto nel record
della curva);
• un puntatore ad anello alla faccia "seguente" nel
grafo;
• la sua estensione (MBR = minimum bounding
rectangle).
Quando l’ultima faccia nel grafo è stata costruita, il
suo puntatore ad anello è settato per puntare indietro
alla faccia di inviluppo.
In questo modo tutte le curve di contorno sono
associate a due facce.
58
Modelli di dati geografici
Lo stesso procedimento è seguito per le superfici di
esclusione: quando tutte le curve sono connesse a
formare le facce, le superfici di esclusione (ad
esempio isole) sono trattate nel modo seguente:
• sono ordinate in aree crescenti;
• si verifica in quale inviluppo cadono (confronto
estensioni);
• vengono posizionate nella faccia in cui cadono;
• si verifica che la superficie di esclusione cada
totalmente all’interno della faccia;
Se i passi precedenti non hanno dato luogo a
problemi viene settato un puntatore che punta dalla
faccia del grafo in cui cade la superficie di esclusione
alla faccia di inviluppo della superficie di esclusione
stessa.
Si noti che la struttura puntatore ad anello
faccia di inviluppo faccia del grafo faccia di
inviluppo della superficie di esclusione faccia
della superficie di esclusione
consente un numero infinito di annidamenti.
59
Modelli di dati geografici
APPROCCIO ENTITA'- RELAZIONI
Gli schemi spaziali visti fino ad ora sono stati descritti
in linguaggio naturale, senza far ricorso a linguaggi
più formali.
Nella pratica invece, solitamente, si preferisce
arrivare, dopo l'analisi dei requisiti, alla sintesi dei vari
modelli esterni e alla descrizione del modello
concettuale utilizzando un linguaggio formale.
Un metodo tra i più utilizzati è l'approccio entità relazione: linguaggio formale basato sui concetti
fondamentali di entità, relazioni, domini, attributi.
fiume
modellizzato
con
60
curva
Modelli di dati geografici
ENTITA'
• Sono
insiemi
di
oggetti
concettualmente
appartenenti ad una stessa classe, aventi proprietà
comuni ed esistenza autonoma rispetto agli
elementi di altre entità;
• sono caratterizzate da attributi, e da una chiave.
Un'entità viene indicata graficamente con un
rettangolo; all'entità sono associati i suoi attributi. Ad
esempio nel diagramma seguente gli attributi sono
elencati sotto l’entità; l'attributo o gli attributi
sottolineati indicano l'attributo o l'insieme di attributi
che costituiscono la chiave dell'entità.
• Sono
PERSONA
caratterizzatePERSONA
da attributi, e danome
una
dell'entità
chiave
Codice
Fiscale
Cognome
Nome
Indirizzo
Data di Nascita
Comune di
Nascita
Cognome
Nome
Indirizzo
Attributo 1
Attributo 2
….
Gli insiemi di entità rappresentano i generici insiemi di
fenomeni che devono essere modellizzati nel
database specifico da progettare. Ad esempio
un’entità può essere una città, una particella
catastale, una strada, …
Ogni attributo ha un range di possibili valori; tale
range è il dominio o l’insieme di valori.
61
Modelli di dati geografici
RELAZIONE
E' un legame concettuale tra due o più entità;
formalmente una relazione è definita come
sottoinsieme di prodotti cartesiani di due o più insiemi
di entità.
Una relazione gode delle proprietà:
• può avere attributi;
• può essere ricorsiva;
• per ogni entità che partecipa alla relazione viene
indicata la cardinalità, cioè il numero (minimo e
massimo) di legami che un elemento di quell’entità
può formare.
PERSONA
Cod. fiscale
Nome
Cognome
CITTA'
residenza
1-1
0-N
Esempio di relazione binaria
62
Nome
Provincia
….
Modelli di dati geografici
Corso
Studente
Matricola
Data di Nascita
Cognome
Nome
Indirizzo
Data Iscrizione
Codice
Nome
esame
data
aula
1-N
1-N
1-N
Docente
Matricola
Cognome
Nome
Esempio di relazione ternaria
Attributi
nome
dell'entità
nome
dell'entità
Attributo 1
Attributo 2
….
Attributo 1
Attributo 2
….
Cardinalità
minima
0-N
0-1
Cardinalità
massima
Relazione
Simbologia adottata nel diagramma entità - relazione
63
Modelli di dati geografici
ESEMPIO DI DIAGRAMMA ENTITA' RELAZIONE
STRADA 4
D
G
STRADA 2
STRADA 1
STRADA 3
B
A
E
C
STRADA 4
F
STRADA 5
H
I
STRADA 1
Consideriamo la modellizzazione solo geometrica
dell'aspetto spaziale della carta; come primitive
geometriche supponiamo di considerare:
• punti
• segmenti (curve caratterizzate solo
da 2 vertici e dal metodo di
interpolazione del cammino minimo)
Supponiamo inoltre di avere informazioni relative al
nome e tipologia delle strade; all'identificativo e
all'indirizzo delle particelle catastali e dati anagrafici
relativi ai proprietari delle particelle stesse (Codice
Fiscale, Nome, Cognome, Data di Nascita, Luogo di
Nascita, Indirizzo).
64
Modelli di dati geografici
ESEMPIO DI DIAGRAMMA ENTITA' RELAZIONE
ENTITA':
Strada
Particella
Catastale
Codice Particella
Indirizzo
Nome Strada
Lunghezza
Tipologia
Proprietario
Codice Fiscale
Data di Nascita
Comune di Nascita
Cognome
Nome
Segmento
Punto
Numero
Lunghezza
Numero
Coordinate x, y
65
Modelli di dati geografici
RELAZIONI:
Ha Bordo
strada - segmento
Ha Bordo
particella - segmento
Ha Proprietario
particella - proprietario
Ha Estremo
segmento - punto
66
Modelli di dati geografici
DIAGRAMMA ENTITA' - RELAZIONE:
Proprietario
Particella
Catastale
Ha
Proprietario
Codice Particella
Indirizzo
1 -N
1 -N
3 -N
Data di Nascita
Comune di Nascita
Cognome
Nome
Indirizzo
Ha
Bordo
0 -2
Segmento
1 -N
2 -2
Ha
Estremo
Numero
Lunghezza
0 -2
Ha
Bordo
2 -N
Strada
Nome Strada
Lunghezza
Tipologia
67
Punto
Numero
Coordinate x, y