Cours SIG , Dr.

Fatma Trabelsi

Chapitre 3 : L’information spatiale

1. Structure de l’information spatiale en géomatique

1.1. L'espace en géomatique
1.1.1. La notion d'espace : l'espace euclidien et l’espace cartésien

[Link]. Les objets dans l'espace Euclidien

Dans le plan euclidien le SIG va classiquement utiliser les objets élémentaires :
a. Les objets points
Ils sont définis par leurs coordonnés dans le plan (X, Y)

b. Les objets lignes

Les lignes sont des segments de droite définies par deux points : (X1, Y1) (X2, Y2)

c. Les objets polylignes

C'est un ensemble fini de segments de ligne, tel que le point final d'un segment soit le point de
départ du segment suivant.

1
Cours SIG , [Link] Trabelsi

Reprenant la terminologie des graphes, on parle parfois de noeuds ou de sommets pour les
points et d'arcs pour les lignes.
Une polyligne dont aucun arc ne se coupe est une polyligne simple.
Une polyligne dont le sommet de départ est le même que le sommet d'arrivé est une polyligne
fermée.
d. Les objets polygones
Un polygone est l'espace compris à l'intérieur d'une polyligne fermée

Un polygone convexe est tel que tous les angles intérieurs formés par ces arcs sont inférieurs
à 180 degré.
Une chaîne est un ensemble de points ordonnés. Une chaîne est dite monotone s’il existe une
droite telle que la projection des points de la chaîne sur cette droite préserve l'ordre des points.
Un polygone est dit monotone s’il peut être décomposé en deux chaînes monotones.
L'enveloppe convexe d'un ensemble est le plus petit polygone convexe englobant cet
ensemble.

2
Cours SIG , [Link] Trabelsi

Enveloppe convexe d'un ensemble de points

Un point d'observation est un point d'où on peut voir tous les autres points du polygone.

Un polygone est convexe si n’importe quel point P du polygone c'est un point d'observation.
Un polygone est semi-convexe s’il existe au moins un point d'observation dans le polygone.
Un polygone n'est pas convexe s’il n'existe aucun point d'observation dans le polygone.

e. Les grilles ou matrices

Des matrices sont utilisées pour réaliser une partition régulière de l'espace.
Ce peut être une image, un MNT (Modèle Numérique de Terrain)...

f. Tessellations régulières
La tessellation d'une surface est une couverture de cette surface par un arrangement de
polygones réguliers non recouvrant:

g. Tessellations irrégulières : TIN

Le Triangulated Irregular Network est le plus connue des tessellations irrégulières, basée sur
une couverture de triangles irréguliers, elle est utilisée pour modéliser des MNT.

3
Cours SIG , [Link] Trabelsi

h. Triangulation de Delaunay et Diagramme de Voronoi

Il s'agit d'une triangulation avec des triangles les plus équilatéraux possibles.
Diagramme de Voronoi ou polygones de Thiessen
Diagramme Voronoi = polygones de Thiessen Triangulation de Delaunay

i. Les graphes
Un graphe G est défini comme un ensemble fini de noeuds et d'un ensemble d'arcs reliant les
noeuds deux à deux.

 graphe orienté
Un graphe orienté est un graphe pour lequel on assigne une direction aux arcs.

 graphe labelisé
Un graphe labélisé est un graphe pour lequel à chaque arc est associé une valeur

 chemin dans un graphe

Un chemin dans un graphe entre deux noeuds, est une liste d'arcs connectés entre ces noeuds.

 graphe connecté
Un graphe G, est dit connecté, quand quel que soit na et nb appartiennent à G 2 noeuds
quelconques, il existe un chemin entre na et nb.

 Graphe cyclique
Un chemin partant d'un noeud na, est dit cyclique, s’il repasse par na.

 arbre
Un arbre est un graphe connecté et acyclique.
4
Cours SIG , [Link] Trabelsi

j. Courbes fractales

Courbe de Peano, Courbe de Hilbert

1.2. Opérations géométriques sur les ensembles d'objets du plan

Les propriétés classiques de la théorie des ensembles s'appliquent à nos objets :
Egalité
Sous-ensemble
Ensemble vide
Cardinalité
Intersection
Union
Complément

2. La topologie
2.1. La notion de topologie
La topologie est une description des relations spatiales des objets entre eux, telles que : "est à
côté de", "inclus", "intersecte" … Dans certain système elle est stockée explicitement, dans
d'autre elle est calculée dynamiquement, selon les besoins de telle ou telle fonction.

2.2. Voisinage

5
Cours SIG , [Link] Trabelsi

2.3. Connexité

2.3.1. Formule d'Euler

Un arrangement de 0objets dans le plan avec a arcs et n noeuds :

2.3.2. Simplexe et complexe

6
Cours SIG , [Link] Trabelsi

3. Représentations informatiques des données spatiales

3.1. Introduction
Après avoir présenté une modélisation conceptuelle de l'information dans les SIG, nous nous
intéressons maintenant à l'organisation de bas niveau de cette information. Cela concerne les
structures de données informatiques utilisées pour coder l'information présente dans les SIG.
Les choix qui sont fait dans les différents systèmes à ce niveau d'organisation ont des
répercutions très importante en termes de performances d'accès aux données et de taille de
stockage des bases.

3.2. Information graphique et information sémantique

On distingue habituellement deux types d'informations pour les données des SIG: L'aspect
sémantique donne une description dans différents champs ou attributs, comme dans un
SGBD classique. L'aspect graphique qui est le contour de l'objet localisé géographiquement.

3.3. Information objet / information champ

L’information élémentaire correspond à un objet ou à 1 champ (d’une table) décrivant cet
objet.
3.4. Organisation des systèmes de fichiers et méthodes d'accès
3.4.1. Introduction
L'organisation élémentaire d'une base de données, est une collection de fichiers composés
d'enregistrement, stockés sur un disque informatique. Des techniques plus sophistiquées de
structurations des bases de données, sur les disques, ont été imaginées afin d'accélérer les
algorithmes (programmes) de recherche.

3.4.2. Organisation simple des fichiers et recherches linéaires

C'est la méthode d'organisation la plus élémentaire, il n'y a pas de structuration particulière
des informations sur le disque, imposée par le SIG.
C'est le système d'exploitation de la machine qui alloue les positions sur le disque pour les
fichiers. Le type de recherche qui est utilisé avec ce type de structure est qualifié de linéaire.
En effet les données ne sont pas triées en fonction de l'information, pour rechercher une

7
Cours SIG , [Link] Trabelsi

information il faut donc balayer tous les enregistrements jusqu'à trouver l'information
recherchée.
Pour n enregistrements on va en moyenne faire n/2 recherche avant de trouver. (On parle de
complexité de l'algorithme)
Cette méthode est particulièrement lente pour de grosses bases de données.
Elle a l'avantage, comme elle n'est pas structurée de permettre des modifications faciles des
enregistrements (suppression, insertion ...)

3.4.3. Organisation séquentiel des fichiers et recherches binaires

Contrairement au cas précédent, les données sont ici organisées dans le fichier, en fonction de
la valeur de un ou de plusieurs champs. Une recherche de type binaire peut être appliquée sur
ces fichiers. Pour cette recherche on se place au milieu du fichier, on lit dans l'enregistrement
le champ qui a servi à organiser le fichier. Si la valeur recherchée est inférieur au champ lu,
on recherche alors dans la première moitié du fichier, de la même manière, sinon on recherche
dans la seconde moitié du fichier.
Pour n enregistrement la complexité est cette fois de l'ordre de log2(n)
Par exemple pour 1000 enregistrements, un traitement linéaire nécessite en moyenne 500
accès contre seulement log2(1000) = 10 accès pour une recherche binaire.
Par contre les modifications de la base (insertion, délétions ...) sont très couteuses en temps,
car la modification de la place d'un enregistrement se répercute sur la place des autres.

3.4.4. Tables de hachages

Une table de hachage utilise une fonction de hachage. Sur un ou plusieurs champs, la fonction
de hachage transformait la valeur en une adresse physique sur le disque. L'adresse peut donc
être entièrement calculée et ne nécessite alors seulement un accès disque pour retrouver
l'enregistrement.
Soit un bloque de 1000 emplacements sur le disque, numéroté de 0 à 999.
Soit des enregistrements avec un champ numérique variant de 0 à 1999.
Une fonction de hachage très simple: diviser par deux, peut être utilisé.
valeur du champ = 400 ----> Fonction Hachage(400) = 200 -------> adresse sur le disque
C'est une technique très optimale, mais qui pose des problèmes pour la gestion de bloques
disques (recouvrement, taille élémentaire des bloques ...), elle ne peut s'appliquer que sur des
champs numériques ou pouvant se transformer en valeur numérique.

3.4.5. Tables d'index notion d'identifiant

Cette technique utilise des tables d'index à la manière de l'index d'un livre.
Le fichier de données lui même n'est pas organisé, mais un second fichier index est créé, qui
lui est ordonné et qui contient un des champs des enregistrements, que l'on nome l'indexe,
ainsi que l'adresse ou pointeur de l'enregistrement correspondent dans le premier fichier.

8
Cours SIG , [Link] Trabelsi

Une recherche binaire peut alors être entreprise, sur le fichier indexe.
Pour de très grosses bases de données le fichier index peut lui aussi devenir très gros et
ralentir la recherche. On peut alors créer une table d'index du fichier index. On parle alors
d'index multi-niveaux. Le B-tree (balanced tree) est un exemple d'indexe multi-niveaux.
Dans la plupart des SIG un champ particulier, que l'on nome identifiant, sert à construire une
table d'index, pour manipuler rapidement les enregistrements de la base.

3.4.6. Indexations spatiales notion de localisant

Les méthodes de codage et d'accès précédentes faisaient surtout référence aux données
sémantiques. Le problème se pose de la même façon pour des accès à la base par l'information
spatiale. Pour cela des méthodes d'indexations spatiales ont été imaginées, il s'agit de
rapprocher physiquement sur le disque des enregistrements qui sont proche dans l'espace
géographique.

Par exemple :

Par analogie avec la notion d'identifiant pour les données sémantique, on parle parfois de
localisant pour la façon d'accéder à l'information par le spatial.

9
Cours SIG , [Link] Trabelsi

3.5. Format de l'information graphique : Raster ou Vecteur

- Le format raster utilise une description matricielle de l'espace géographique.

La matrice est une image, chaque élément de l'image ou pixel (picture element) contient un
niveau donné qui représente une thématique. Ces images sont généralement issues de scanners
ou d'images aériennes ou satellitaires.

10
Cours SIG , [Link] Trabelsi

- Dans le format vectoriel, les objets sont représentés par des primitives graphiques
(point, ligne, polyligne etc ...).

11
Cours SIG , [Link] Trabelsi

3.5.1. Format raster

 Définitions des images numériques
Un signal s, est le support physique d'une information [Kunt, 1981].
Mathématiquement, le signal est représenté par une fonction d'une ou plusieurs variables (x et
y pour une image). Selon la nature de ces variables,
On distingue :
- un signal analogique pour des variables continues;
- un signal discret ou échantillonné pour des variables discrètes.
En outre, l'amplitude du signal (niveau de gris pour une image), peut également être continue
ou discrète.
Un signal analogique, dont l'amplitude est discrète, est un signal quantifié.
Un signal discret dont l'amplitude est discrète est un signal numérique.
Une image numérique I, ou image digitale, est un exemple de signal numérique
bidimensionnel, elle résulte de deux étapes :
- l'échantillonnage qui est la discrétisation spatiale sur x et y;
- la quantification qui est la discrétisation de l'amplitude du signal, donnant le niveau de gris.
Une image digitale est donc représentée par une zone discrète et finie, d'amplitude discrète.
Elle constitue la représentation spatiale d'un objet, d'une scène bidimensionnelle ou
tridimensionnelle ou d'une autre image [Haralick, 1991].
Soit I une fonction image bidimensionnelle : I : N2 -> N
I : (x,y) -> I(x,y) où I(x,y) un élément d'image aux coordonnées (x,y) est appelé pixel
(picture element). La valeur de I(x,y) peut être un niveau de gris ou une valeur de couleur
pour les images couleurs, qui comportent généralement trois composantes, Rouge, Vert, Bleu
dans le système RVB par exemple.

12
Cours SIG , [Link] Trabelsi

Image digitale en niveaux de gris et en couleur

 Voisinage et connexité
Le voisinage est défini par un ensemble de points connexes qui constituent une forme pré
définie entourant le point considéré. On distingue classiquement :
- un voisinage en connexité 4 dans le cas où les quatre pixels voisins sont utilisés;
- un voisinage en connexité 8 dans le cas où les huit pixels adjacents sont pris en compte.

 Structure de données informatique du raster

Il existe de nombreuses techniques issues du traitement d'images pour coder des données sous
forme raster.
 Matrice raster
Un raster est par définition une matrice de points (pixels). On défini aussi les voxels par
analogie au pixel dans un espace à trois dimensions. Le stockage sous cette forme peut être
très coûteux en taille, de nombreuses méthodes de codage permettant une compression des
données sont utilisées :
 Chain codes
C'est un codage utilisé pour représenter les contours dans une image, il est basé sur le codage
directionnel de Freeman :

13
Cours SIG , [Link] Trabelsi

Les directions élémentaires d, codent pour le passage d'un pixel de contour à un autre, un
contour est alors entièrement codé par une suite de d.

 Run Length code

Ce type de compression tire partie de la répétitivité de certaine image. En effet une carte raster
peut contenir de larges plages de pixels ayant la même valeur. Par exemple une ligne de 20
pixels contigus tous à la valeur 6 pourra être codée :
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 En codage raster classique ou 20 6 en codage run length.
On code ici sur 2 octets le nombre de pixels de la plage et la valeur de la plage, soit un taux de
compression de 20 / 2 = 10.

 Block code
Il s'agit d'une généralisation du cas précédent au cas bidimensionnel.

 Quadtree
On découpe une image de façon récursive en quadrant jusqu'à obtenir des régions
élémentaires homogènes (de même classe).
Pour une image binaire (2 niveaux : et )

est un nœud hétérogène sont les nœuds homogènes

3.5.2. Format vecteur

Dans le cas d’un codage vectoriel l’espace de représentation est supposé continu,
contrairement au codage raster où l’espace est quantifié et la précision géométrique est donc
limitée. En fait la supposition d’un espace continu ne peut être réellement satisfaite sur les
systèmes informatiques, car les systèmes numériques supposent un codage avec une précision
finie des valeurs numériques. La taille des « mots machines » sur les ordinateurs fixe la
précision des valeurs numériques codées selon leur type mathématique (entier, réel ...).

 Codage par primitives graphiques

 Cas du codage des polygones
Soient deux polygones connexes POLY1 et POLY2, soient pi les points de contour :

Deux techniques sont utilisées concernant le codage graphique des polygones :

Codage par couverture d’arcs / codage par couverture de polygones

14
Cours SIG , [Link] Trabelsi

Dans le premier cas chaque polygone contient tous les points de son contour, en conséquence
les points communs aux deux polygones connexes sont dupliqués dans P1 et P2.
Dans le second cas les arcs individuels sont codés en tant que tel, on parle de couverture
d'arcs, et les polygones ne contiennent que la liste des arcs les constituant.

 Structure de données informatique des vecteurs

Les problèmes d'indexation se posent de la même manière que pour les données raster.
Points
grille régulière
quad-tree de points
PM quadtree
Polygones objets complexes
Segment tree
rectangle englobant

Le R-tree est une extension du B-tree en utilisant les rectangles englobants.

Passage raster -> vecteur : vectorisation

15
Cours SIG , [Link] Trabelsi

Passage vecteur -> raster : rasterisation

La cohabitation raster / vecteur dans les SIG modernes

3.6. Organisation relative du sémantique et du graphique

3.6.1. Modèle par table : par couche (couverture)

16
Cours SIG , [Link] Trabelsi

Le codage par couches (layers) est naturel pour la représentation raster. En effet chaque
cellule d’une matrice raster ne peut contenir qu’une seule valeur, différents attributs
géographiques doivent alors être représentés dans différentes matrices raster géométriquement
superposables appelées couches ou couvertures.

De nombreux systèmes vecteurs utilisent aussi une description par couverture des données.

3.6.2. Modèle objet

Certains systèmes proposent, parfois artificiellement, de s’affranchir de la représentation par
couverture des données géographiques. Des modèles inspirés des représentations
informatiques orientés objets sont implémentées dans certains SIG. Il faut noter que la
terminologie objet est le plus souvent un peu abusivement utilisée. En effet elle est le plus
souvent utilisée pour souligner un codage différent de celui par couverture, sans reprendre
réellement le formalisme orienté objet.

3.7. Représentation de la topologie dans les SIG

On trouve deux catégories de systèmes quant au codage de la topologie :

 Codage explicite de la topologie

Dans ce cas lors de la création, suppression ou modification des objets, la topologie est
calculée ou recalculée et conservée dans la base. Les fonctions utilisant l'information
topologique peuvent alors y avoir accès à tout moment.

 Calcul dynamique de la topologie

La topologie n'est pas codée explicitement dans la base. Quand une fonction a besoin
d'information topologique, elle la calcule dynamiquement.

17