Informatique

INTRODUCTION

Depuis le milieu des années 60, la technologie a fait un bond considérable, dans le domaine de la géographie : satellites chargés d'observer la terre, photos aériennes... Ces innovations ont conduit à la création de systèmes informatiques gérant l'information géographique récupérée par les satellites, les photos aériennes ou les levés topographiques de terrain. Les Systèmes d'Information Géographique (ou SIG) sont, selon la Société Française de Photogrammétrie et de Télédétection, des "systèmes informatiques permettant, à partir de diverses sources, de rassembler et organiser, de gérer, d'analyser et de combiner, d'élaborer et de présenter des informations localisées géographiquement, contribuant notamment à la gestion de l'espace" [24]. Les SIG ont pour but de gérer une information correspondant à une localisation géographique précise. Cette information possède deux particularités principales : une localisation spatiale souvent représentée par des coordonnées cartésiennes, et des propriétés alphanumériques (non spatiales).

Les domaines d'application des SIG sont de nature très diverses. Quatre domaines principaux peuvent toutefois être dégagés [49] :

- Les applications de gestion des données urbaines sont principalement dédiées à la gestion du cadastre, des réseaux, du patrimoine et du mobilier urbain (e.g., les applications développées pour la ville de Nîmes, Marseille, Colombes [24]...). Les utilisateurs de ce type d'application sont essentiellement les services techniques des collectivités locales. Ces applications se caractérisent par des données à grande et très grande échelle (de l'ordre du 1/500 et du 1/200), de gros volumes de données, des traitements fréquents mais de courte durée, des sorties sous forme textuelle et sous forme cartographique.

- Les applications de planification et d'aménagement du territoire sont dédiées principalement à l'aménagement urbain ou péri-urbain ainsi qu'à la gestion des ressources naturelles et à la protection de l'environnement (e.g., le SIG développé pour le Service d'Information du Territoire de la ville de Fréjus [24]). Les utilisateurs de ces applications sont essentiellement des décideurs. Elles se caractérisent par des données à échelles moyennes (du 1/10.000 au 1/100.000), des traitements peu fréquents mais de longue durée, des sorties cartographiques concernant un thème d'information particulier (sorties à caractère thématique) ou des sorties analytiques.
- Les applications de cartographie de présentation et de communication sont dédiées aux études thématiques (statistiques principalement). Les utilisateurs en sont principalement des entreprises privées et des collectivités locales. Elles se caractérisent par des données à des échelles petites ou moyennes (inférieures au 1/10000), des traitements typiquement thématiques et peu complexes, des sorties cartographiques thématiques.
- Les applications du domaine scientifique sont mises en place par des instituts de recherche ou de prospective. Elles s'intéressent à des sujets très divers comme les études de modélisation d'écosystèmes complexes, des études d'aménagement au niveau régional ou national, des études d'impact... Elles sont caractérisées par des échelles très diverses, par la possibilité de simulations interactives et par l'absence de prise en compte des problèmes liés au coût des informations spatialisées.
Notre objectif est d'offrir un outil permettant la gestion des réseaux de communication au sens large du terme (réseaux routiers, ferroviaires, fluviaux, aqueux...). Ce type d'étude recouvre à la fois les applications du domaine scientifique et les applications de gestion des données urbaines. Ces applications s'appuient sur des outils informatiques, les SIG.
Les SIG se décomposent en deux classes distinctes [49] : les SIG thématiques et les SIG de type réseau. Cette classification est basée sur la nature spatiale de l'information géographique traitée et sur les différentes fonctions applicables sur cette information géographique.
- Les SIG thématiques manipulent des informations géographiques regroupées selon leur sémantique (valeur des propriétés alphanumériques). Ainsi, un thème correspond aux routes, un autre au réseau ferroviaire (réseau utilisé par les trains), un autre au réseau des bus (réseau utilisé par les bus), un autre aux villes. Une information géographique peut correspondre à plusieurs thèmes différents (une voie de bus peut être aussi une voie routière). Cette information sera alors conservée dans plusieurs "ensembles thématiques" différents. Ces SIG permettent essentiellement de créer des applications de type planification et aménagement de territoire, ainsi que des applications de cartographie de présentation et de communication. Ces applications vont mêler les informations contenues dans des thèmes différents (routes, voies ferroviaires et villes) afin de pouvoir résoudre des requêtes sur la nature de l'information géographique ("Quelles sont les routes passant dans une ville située à côté d'une forêt ?"). Pour résoudre de telles requêtes, des opérations sont appliquées sur ces données : sélection d'objets respectant certains critères, intersection d'objets, inclusion d'objets... Ces opérations sont basées sur la notion de géométrie et/ou de topologie.
Ainsi, pour un SIG thématique, une intersection entre une route et une voie ferrée existe si le segment de droite représentant la route coupe le segment de droite représentant la voie ferrée. La représentation spatiale des différents thèmes ne forme pas obligatoirement une partition de l'espace entre ces thèmes, ni même à l'intérieur d'un thème.

- Les SIG de type réseau modélisent les informations géographiques par un graphe [10]. Ces informations géographiques sont essentiellement de type réseau (réseaux routiers, fluviaux, aériens, aqueux, électrique, gazeux...). Elles sont décomposées en deux classes distinctes : les noeuds (représentant les villes, les embranchements de rivières, les vannes de gaz..) et les arcs (représentant les routes, les voies fluviales...). Ces classes permettent de représenter et de visualiser l'information géographique sous forme d'un graphe. Cette formalisation des informations induit l'existence d'opérateurs, dont le principal est l'opérateur de recherche de chemins. Cet opérateur se ramène au calcul d'une fermeture transitive entre deux noeuds du graphe. D'autres opérations sont également applicables sur ces informations : affichage du réseau, sélection de certaines données dans le graphe, étalement de la couverture spatiale étudiée... Chacun de ces opérateurs s'applique sur un graphe (ou un ensemble de graphes) et renvoie pour résultat un graphe.

Notre objectif est d'étudier la modélisation de données associées à des réseaux de communication quelconques (routier, ferroviaire, gazeux, électrique...). Cette modélisation est réalisée sous la forme de graphes auxquels sont associés des opérateurs permettant la gestion des informations contenues dans ces graphes. Ce type d'étude relève donc du domaine des SIG de type réseau.
Les SIG de type réseau font apparaître une dualité dans la représentation des données : une représentation logique d'un graphe à l'aide de noeuds et d'arcs, et une représentation graphique de ces mêmes noeuds et arcs, à l'aide des coordonnées associées aux informations. Ces SIG peuvent donc se décomposer en deux sous-classes distinctes : les "SIG physiques de type réseau" et les "SIG logiques de type réseau".
- Les SIG physiques de type réseau sont des SIG s'intéressant essentiellement au mode de stockage de l'information géographique. Partant de ce mode de stockage, ils en déduisent certaines opérations possibles sur ces données. Le modèle conceptuel ainsi déduit est fortement corrélé à l'implantation physique des données. Deux modes de stockage sont possibles : le format vecteur et le format raster. Chacun de ces formats induit l'existence ou non d'opérateurs de manipulation de l'information géographique. Les SIG physiques de type réseau sont des SIG "bottom-up" ou "ascendants".
- Les SIG logiques de type réseau modélisent les informations géographiques sous forme d'un graphe, selon les principes de la théorie des graphes. Ils modélisent ces informations de façon conceptuelle, sans s'intéresser au mode de stockage des données. Ils prennent comme point de départ, non l'implantation physique des données, mais l'organisation des données entre elles et les opérateurs à utiliser sur ces données. Ce sont des SIG "top-down" ou "descendants".

La plupart des SIG conçus aujourd'hui sont des SIG physiques. Notre étude s'intègre dans le cadre des SIG logiques de type réseau. Elle consiste à définir un modèle de données et ses opérateurs pour gérer des informations géographiques de type réseau.

Le modèle de données proposé allie les concepts de la théorie des graphes (notion de noeuds et d'arcs) au paradigme orienté objet (notion de classes, d'abstraction). Ce modèle de données comprend différentes classes de bases (les noeuds, les arcs et les réseaux). Chacune de ces classes possèdent des attributs alphanumériques représentant les propriétés alphanumériques des informations géographiques. L'introduction de la notion d'abstraction permet de considérer un noeud et/ou un arc comme représentant une abstraction d'un ou de plusieurs sous-réseaux. Ainsi le noeud France peut représenter l'abstraction de plusieurs réseaux (réseau ferroviaire français, réseau routier français...). Chacun de ces réseaux comporte lui-même des noeuds et des arcs représentant l'abstraction de réseaux. Le réseau routier français comportera par exemple un ensemble de noeuds, dont le noeud Paris. Ce noeud Paris représente à son tour l'abstraction de plusieurs sous-réseaux (réseau des voies de bus parisiens, réseau des routes de Paris). Les éléments de ces classes sont organisés en hiérarchies. Ces hiérarchies permettent de représenter un graphe à différents niveaux d'abstraction (différents niveaux de détails).

Les opérateurs de manipulation définis sur ce modèle prennent en compte la problématique de la recherche d'itinéraires dans une base de données géographiques. Ces opérateurs sont très différents des opérateurs des SIG classiques de type réseau car ils intègrent la notion de hiérarchie à leur recherche d'itinéraires. De plus, cette recherche peut s'effectuer sous contraintes : le chemin résultant doit répondre à des critères concernant les caractéristiques alphanumériques de chacun de ses noeuds et/ou arcs.

Les SIG de type réseau tendent de plus en plus à se développer. Ils présentent néanmoins encore de nombreuses lacunes, tant au niveau de la modélisation qu'au niveau de la résolution de requêtes. Notre proposition n'apporte cependant pas toutes les solutions et de nombreux problèmes restent posés (au niveau des propriétés alphanumériques de l'information géographique en particulier).

Dans un premier chapitre, nous définissons les notions concernant l'information géographique, ainsi que les notions concernant les graphes utiles à cette étude. Ces définitions sont utilisées pour étudier un état de l'art concernant les SIG de type réseau. Cette étude nous permet de montrer leurs forces et faiblesses et de nous positionner vis-à-vis de ces SIG. Le second chapitre présente un modèle de données pour les informations géographiques de type réseau. Le troisième chapitre représente le coeur de cette thèse en définissant les opérateurs applicables sur ce modèle. Enfin, nous concluons sur les travaux effectués et les opportunités s'ouvrant à ces travaux.

Remerciements 2

INTRODUCTION 7

Chapitre I - Etat de l’art 12

Introduction 12

I- Définitions 12

I-1. Définitions sur l'information géographique 13

I-1.1 L'information géographique 13

I-1.2 Acquisition et stockage de l'information géographique 15

I-1.2.1 Acquisition de l'information géographique 15

I-1.2.2 Modèles de stockage de l'information géographique 16

I-1.2.2.1 Le modèle raster 17

I-1.2.2.2 Le modèle vecteur 19

I-1.2.2.3 Raster ou vecteur ? 21

I-1.2.3 Les cartes et bases de données de référence des SIG 23

I-1.3 Les normes sur l'information géographique 27

I-1.4 Conclusion 28

I-2. Définitions sur les graphes 29

I-3. Requêtes pour les SIG de type réseau 39

I-3.1 Recherche de chemins 40

I-3.2 Augmentation des détails 43

I-3.3 Requêtes connexes 44

I-3.4 Exemple de référence 46

II- Les propositions existantes de SIG de type réseau 48

II-1. Les SIG physiques de type réseau 48

II-1.1 Les SIG physiques format raster 48

II-1.2 Les SIG physiques format vecteur 50

II-1.2.1 Les systèmes embarqués 50

II-1.2.2 Les systèmes commerciaux thématiques et réseaux 54

II-1.2.3 Les SIG destinés à un large public 58

II-1.3 Conclusion 61

II-2. Les SIG logiques de type réseau 61

II-2.1 Le système GraphDB 62

II-2.2 Le modèle GRAM 69

II-2.3 Conclusion 77

II-3. L'intégration de niveaux d'échelles 77

II-3.1 L'intégration physique 78

II-3.2 L'intégration logique 82

Conclusion 87

Chapitre II - Le modèle de graphe 89

Introduction 89

I- Le modèle de données 89

I-1. Les composants de base 90

I-1.1 Les Noeuds 90

I-1.2 Les Arcs 91

I-1.3 Les Réseaux 92

I-2. Le second niveau d'abstraction 94

I-2.1 Les Réseaux_associés 95

I-2.2 Les Master_noeuds 96

I-2.3 Les Master_arcs 97

I-3. Conclusion 98

II- La gestion des différents niveaux d'abstraction 98

II-1. La hiérarchie des noeuds 99

II-2. La hiérarchie des arcs 101

II-3. La hiérarchie des réseaux 103

III- Récapitulatif : les différentes classes du modèle 107

IV- Exemple de référence 109

Conclusion 117

Chapitre III - Les opérateurs 119

Introduction 119

I- Définitions sur les opérateurs 120

I-1. Définitions 120

I-2. Les critères et les contraintes 121

II- Les Opérateurs 122

II-1. Les Opérateurs de Base 122

II-1.1 L'opérateur de développement DEVELOP 123

II-1.1.1 Notion de développement et structure de données 123

II-1.1.2 Spécification de l'opérateur DEVELOP 125

II-1.1.3 Illustration par un exemple 127

II-1.1.4 Généralisation de l'opérateur DEVELOP 130

II-1.2 L'opérateur de regroupement UNDEVELOP 133

II-1.2.1 Notion de regroupement et structure de données 133

II-1.2.2 Spécification de l'opérateur UNDEVELOP 135

II-1.2.3 Illustration par un exemple 138

II-1.2.4 Généralisation de l'opérateur UNDEVELOP 139

II-1.3 Conclusion 141

II-2. Les Opérateurs Elémentaires 142

II-2.1 L'opérateur de SELECTION 142

II-2.1.1 Notion d'invalidation et structure de données 143

II-2.1.2 Spécification de l'opérateur de SELECTION 144

II-2.1.3 Illustration par un exemple 151

II-2.2 L'opérateur d'UNION 155

II-2.2.1 Notion de prépondérance 156

II-2.2.2 Spécification de l'opérateur d'UNION 156

II-2.2.3 Illustration par un exemple 168

II-2.3 L'opérateur de DIFFERENCE 172

II-2.3.1 Spécification de l'opérateur de DIFFERENCE 173

II-2.3.2 Illustration par un exemple 179

II-3. Les Opérateurs de Haut Niveau 183

II-3.1 L'opérateur de CHEMINS 183

II-3.1.1 Notion d'approximation et structure de données 187

II-3.1.2 Spécification de l'opérateur de CHEMINS 188

II-3.1.3 Illustration par un exemple 198

II-3.2 L'opérateur d'INCLUSION 206

II-3.2.1 Propriétés des opérateurs d'INCLUSION 206

II-3.2.2 L'opérateur d'INCLUSION de noeuds 207

II-3.2.3 L'opérateur d'INCLUSION d'arcs 209

II-3.2.4 L'opérateur d'INCLUSION de noeuds et d'arcs 211

II-3.2.5 Illustration par un exemple 213

II-3.3 L'opérateur d'INTERSECTION 215

II-3.3.1 Propriétés des opérateurs d'INTERSECTION 216

II-3.3.2 L'opérateur d'INTERSECTION de noeuds 217

II-3.3.3 L'opérateur d'INTERSECTION d'arcs 221

II-3.3.4 L'opérateur d'INTERSECTION de noeuds et d'arcs 226

II-3.3.5 Illustration par un exemple 232

III- Traduction des requêtes 234

III-1. Requêtes de recherche de chemins 235

III-2. Requêtes d'augmentation de détails 238

III-3. Requêtes connexes 240

Conclusion 243

CONCLUSION 245

Bibliographie 248