Informatique

Conclusion

Les modèles de SIG de type réseau existant ne gèrent pas l'intégralité des requêtes susceptibles d'être posées par un utilisateur à un tel système. Le but de cette thèse est de présenter et de développer sur un modèle de graphe des opérateurs permettant d'étendre le pouvoir d'expression des langages de manipulation de réseaux.

Le modèle de graphe présenté intègre la notion d'abstraction à une modélisation de données géographiques sous forme de noeuds et d'arcs. Cette modélisation s'appuie sur les notions classiques de la théorie des graphes. Ces notions sont enrichies pour permettre à un noeud (resp. arc) de représenter l'abstraction d'un ensemble de noeuds et d'arcs. Cette intégration permet de représenter les données à différents niveaux d'échelles. Ceci permet de simplifier la présentation d'un graphe et les recherches qui vont être effectuées sur ce graphe, sans pour autant nuire à la quantité d'informations contenues dans la base de données. Cette modélisation permet également de s'affranchir de l'échelle de représentation, en privilégiant la perception logique (connectivité des noeuds et arcs) plutôt que physique. Ainsi, l'exemple considéré est tiré de cartes au 1/1.000.000 et au 1/10.000, sans que cela soit perceptible.
Sur cette modélisation nous allons définir des opérateurs qui vont permettre de poser les requêtes définies dans le chapitre I. Ces opérateurs intègrent la notion d'abstraction du modèle. Chacun de ces opérateurs est illustré par des requêtes posées sur l'exemple défini précédemment.

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