Informatique

THESE

Spécialité

INFORMATIQUE
Présentée par

Bénédicte LANGOU
pour obtenir le grade de DOCTEUR de l'UNIVERSITE PARIS 6

Sujet de la thèse

La Gestion des Chemins dans

les Systèmes d’Information Géographique

Soutenue le 29 janvier 1998

Devant le jury composé de :

M. Bergougnoux, professeur à l’Université Paul Sabatier de Toulouse, rapporteur

Mme Doucet, professeur à l’Université Paris VI

M. Drouet d’Aubigny, professeur à l’Université Pierre Mendès France de Grenoble, rapporteur

M. Jeansoulin, chargé de recherches CNRS

M. Mainguenaud, directeur de thèse

M. Philippe, directeur de la société Ataraxie, invité

M. Scholl, professeur au CNAM

Remerciements

Cette thèse a été réalisée au sein de l'équipe Bases de Données du département Informatique de l'Institut National des Télécommunications à Evry, dans le cadre d'un contrat CIFRE avec la société Ataraxie à Poissy.

Je remercie très vivement :
M. Michel Mainguenaud pour sa patience, son encadrement et son aide tout au long de cette thèse;
M. François Philippe pour m'avoir permis de m'insérer dans la vie professionnelle et pour son aide;
M. Bergougnoux et M. d’Aubigny pour avoir pris le temps de lire cette thèse, pour leurs remarques constructives et pour avoir accepté d’être rapporteur;
M. Scholl, M. Jeansoulin, Mme Doucet pour leurs remarques constructives, ainsi que pour avoir accepté d’être membre du jury de soutenance;
le département Informatique de l'INT, et plus particulièrement M. Bruno Defude, Mme Anne Brossier-Wansek et Mme Claire Carpentier pour leurs conseils, leur accueil, leur aide et leur sympathie;
l'équipe Bases de données de l'Ecole Nationale Supérieure des Télécommunications de Paris pour leurs conseils et leur sympathie;
l'équipe COGIT de l'Institut Géographique National, et plus particulièrement Mlle Anne Ruas pour son amitié et son aide.
Enfin, je remercie vivement tous mes amis et toute ma famille, et plus particulièrement M. Benoît Javet, mes parents, mon frère, mes soeurs et ma grand-mère, ainsi que Mlle Marine Tabourier et Mme Salima Hamma, pour leur disponibilité, leur écoute, leurs conseils, leur patience, leur aide et leur soutien moral tout au long de ce travail.

SOMMAIRE
INTRODUCTION 7

Chapitre I - Etat de l’art 11

Introduction 11

I- Définitions 11

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

I-1.1 L'information géographique 12

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

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

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

I-1.2.2.1 Le modèle raster 16

I-1.2.2.2 Le modèle vecteur 18

I-1.2.2.3 Raster ou vecteur ? 20

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

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

I-1.4 Conclusion 26

I-2. Définitions sur les graphes 27

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

I-3.1 Recherche de chemins 37

I-3.2 Augmentation des détails 40

I-3.3 Requêtes connexes 41

I-3.4 Exemple de référence 43

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

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

II-1.1 Les SIG physiques format raster 45

II-1.2 Les SIG physiques format vecteur 47

II-1.2.1 Les systèmes embarqués 47

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

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

II-1.3 Conclusion 57

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

II-2.1 Le système GraphDB 58

II-2.2 Le modèle GRAM 65

II-2.3 Conclusion 72

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

II-3.1 L'intégration physique 73

II-3.2 L'intégration logique 77

Conclusion 82

Chapitre II - Le modèle de graphe 83

Introduction 83

I- Le modèle de données 83

I-1. Les composants de base 84

I-1.1 Les Noeuds 84

I-1.2 Les Arcs 85

I-1.3 Les Réseaux 86

I-2. Le second niveau d'abstraction 88

I-2.1 Les Réseaux_associés 89

I-2.2 Les Master_noeuds 90

I-2.3 Les Master_arcs 90

I-3. Conclusion 91

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

II-1. La hiérarchie des noeuds 92

II-2. La hiérarchie des arcs 94

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

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

IV- Exemple de référence 102

Conclusion 110

Chapitre III - Les opérateurs 111

Introduction 111

I- Définitions sur les opérateurs 111

I-1. Définitions 112

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

II- Les Opérateurs 114

II-1. Les Opérateurs de Base 114

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

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

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

II-1.1.3 Illustration par un exemple 118

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

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

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

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

II-1.2.3 Illustration par un exemple 128

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

II-1.3 Conclusion 131

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

II-2.1 L'opérateur de SELECTION 131

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

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

II-2.1.3 Illustration par un exemple 140

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

II-2.2.1 Notion de prépondérance 144

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

II-2.2.3 Illustration par un exemple 155

II-2.3 L'opérateur de DIFFERENCE 159

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

II-2.3.2 Illustration par un exemple 165

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

II-3.1 L'opérateur de CHEMINS 169

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

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

II-3.1.3 Illustration par un exemple 182

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

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

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

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

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

II-3.2.5 Illustration par un exemple 196

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

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

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

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

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

II-3.3.5 Illustration par un exemple 212

III- Traduction des requêtes 215

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

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

III-3. Requêtes connexes 221

Conclusion 223

CONCLUSION 225

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