Prof Goze B. Bénié, Ph.D. · 04/02/08 4 Visions de l'espace Introduction Il s'agit de...

NOTIONS DE TOPOLOGIE

Prof Goze B. Bénié, Ph.D.

04/02/08 2

Plan

► Visions de l'espace

► Théorie des graphes

► Topologie

04/02/08 3

Visions de l'espace► Vision euclidienne

► Vision cartésienne

► Vision fractale

► Vision péanienne

► Vision tessérale

► Vision topologique

04/02/08 4

Visions de l'espace► Introduction

● Il s'agit de définir la façon de voir la structure et l'organisation des objets dans l'espace de manière à :✔ Analyser et comprendre le monde;✔ Concevoir les objets et le territoire.

● Ces visions réfèrent à l'observation et à la mesure de la terre.

04/02/08 5

Visions de l'espace► Vision euclidienne

● Objet planaire limité par des segments de droite ou presque (nécessité d'un référentiel).

● La caractéristique principale de cette vision met en relation les sommets du polygone et ses côtés.

04/02/08 6

Visions de l'espace► Vision cartésienne

● Représentation par un système d’axes conduisant à doter tout point de l'espace d'un ensemble de coordonnées (x, y, z, ...).

● On peut ainsi se localiser dans l'espace (points géodésiques, GPS, etc.).

04/02/08 7

Visions de l'espace► Vision fractale

● Limite d’un objet définie par une suite infinie de petits segments appelés « éléments structurants ».

● Vision récursive et stochastique.

04/02/08 8

Visions de l'espace► Vision péanienne

● Un objet peut être formé d’un ensemble de petits carrés dont le côté tends 0 (point) : exemple de l'image de télédétection dont la limite de résolution spatiale peut varier selon l'instrument de prise de vue.

04/02/08 9

Visions de l'espace► Vision tessérale

● Répétition itérative d'une même forme (carré, hexagone, carroyage, nid d'abeilles, image de télédétection…).

04/02/08 10

Visions de l'espace► Vision topologique

● La relation de voisinage spatial (positionnement relatif) des objets demeure la clé de la topologie. Exemple : inclusion, voisinage, connexité, etc.

● Par extension, la topologie temporelle a trait à la relation de voisinage des objets dans le temps (étude de la détection des changements).

● La topologie constitue la base de l'analyse spatiale.

04/02/08 11

Visions de l'espace► Vision topologique

04/02/08 12

Visions de l'espace► Conclusion partielle

● Ces méthodes de vision offrent de puissants outils d'analyse spatiale.

● Elles réfèrent à la géométrie algorithmique axée sur le format vectoriel ainsi qu'à la géométrie discrète basée sur le format matriciel ou raster.

04/02/08 13

Théorie des graphes (1 de 10)(Référence : J.-P. Rodrigue : Théorie des graphes : définition et propriétés)

► Définition● Un graphe est une représentation symbolique d’un

réseau, une abstraction de la réalité de sorte à permettre sa modélisation.

● En géographie des transports, la plupart des réseaux ont un fondement spatial, mais ceci n’est pas vrai pour tous les réseaux de transport. ✔ Par exemple, il est possible de représenter un système de

télécommunication sous forme de réseau bien que son expression spatiale a une importance limitée et serait difficile à transposer sur un territoire.

✔ Les exemples d’un réseau de téléphones mobiles ou l’Internet incarnent des cas de réseaux à structure spatiale limitée. Toutefois, la majorité des réseaux de transport peuvent être représentés par le biais de la théorie des graphes.

04/02/08 14

Théorie des graphes

► Définition● Graphe : un réseau de transport, comme tout réseau, peut

être représenté sous forme de graphe. Un graphe G consiste en un ensemble de noeuds ν et d’arcs α. écrit : G=(ν ,α).

Noeuds ν : (1, 2, 3, 4, 5)

Arcs α : (1,2), (1,3), (2,2), (2,5), (4,2), (4,3), (4,5)

1

5

43

2

04/02/08 15

Théorie des graphes

► Définition● Noeud : Un noeud ou sommet n est un point d’extrémité

ou un point d’intersection d’un graphe. ✔ Il s’agit d’une abstraction d’un lieu tel que une ville, une division

administrative, une intersection routière ou une infrastructure de transfert (stations, terminus, ports et aéroports).

✔ Un graphe connexe exige l'existence d'un chemin entre deux noeuds,

1

543

2

Noeuds ν : (1, 2, 3, 4, 5)

04/02/08 16

Théorie des graphes

► Définition● Arc : un arc α est un lien entre deux sommets initial i et

terminal j. ✔ C'est un segment de droite orienté et représenté par les

coordonnées de ses deux extrémités. Un arc est une représentation abstraite d’infrastructures de support des déplacements entre deux noeuds.

● Boucle : un arc fait correspondre un même sommet.

04/02/08 17

Théorie des graphes

► Définition● Arc et Boucle Arcs α : (1,2), (1,3), (2,2), 4,2), (4,3), 4,5)

Boucle (2,2)

1

543

2

04/02/08 18

Théorie des graphes

► Définition● Arête : un groupe de deux sommets tels que chaque

sommet fait partie de l’ensemble des correspondants de l’autre sommet (arêtes : (3-4) et (4-5))✔ Une arête incarne toute possibilité de mouvement entre deux

noeuds, nonobstant la direction. Un arc est arête orientée.✔ Les arêtes permettent par conséquent de savoir si un endroit peut

être atteint.

5

43

04/02/08 19

Théorie des graphes

► Définition● Chemin : séquence d’arcs tous parcourus dans le même

sens. Pour qu’un chemin relie deux sommets, un déplacement continu suivant une séquence d’arcs doit être possible. ✔ L’établissement de chemins est une étape fondamentale dans la

mesure d’accessibilité et de flux de trafic au sein d’un réseau.

3

21

6

54

Chemin entre 1 et 3

Pas de chemin entre 4 et 6

04/02/08 20

Théorie des graphes

► Définition● Longueur d'un arc, d'une arête ou d'un chemin :

nombre associé à un arc, une arête ou un chemin, signifiant une distance, un flot, ou tout autre attribut relié à ces éléments. ✔ La longueur d’un chemin est fonction du nombre d’arcs constituant

ce chemin. La longueur de l'arc (2,3) est 4 m.

4 m

1

63

4

2

5

2 m

7,.5 m

3 m

2 m5 m

7 m

6 m

04/02/08 21

Théorie des graphes

► Définition● Chaîne : une suite d’arcs telle que chaque arc de la suite a

une extrémité en commun avec l’arc précédent. La direction n’a pas d’importance.✔ La séquence d'arcs reliant les sommets 1,2,3 et 6 est une chaîne.

1

63

4

2

5

2 m

7,.5 m

3 m

2 m5 m

7 m

6 m

04/02/08 22

Théorie des graphes

► Définition● Cycle : une chaîne dont le sommet initial et terminal

coïncident et qui n’emprunte pas le même arc constitue un cycle.

● Circuit : un chemin fini et fermé dont l’extrémité terminale du dernier arc coïncide avec l’extrémité initiale du premier. C’est un cycle dont tous les arcs sont parcourus dans le même sens. Les cycles revêtent une importance capitale en transport car maints systèmes de distribution utilisent des cycles afin de couvrir le plus de territoire possible en une seule direction.

● Ce sont des chemins fermés.

04/02/08 23

Théorie des graphes

► Définition● Cycle et Circuit

✔ (1, 2, 3, 6, 5, 4) est un cycle et non un circuit.✔ [(1,2), (2,4), (4,1)] est à la fois un cycle et un circuit.

1

63

4

2

5

04/02/08 24

Application de la théorie des graphes

► Exemples de questions qui font appel à la théorie des graphes● Quel est le niveau d'accessibilité de différentes villes par

voie aérienne?● Comment le transport peut être affecté par un nouveau

pont?● Quel est le chemin le plus court (en temps) pour aller d'un

point A à un point B pendant les heures de pointe dans une ville comme Montréal?

04/02/08 25

Graphes et surfaces

A

A

A

A

La surface A est une unité spatiale polygonale

La surface sert de fond à des objets linéaires

A

D

C

B

La surface A sert de fond pour les objets zonaux B, C et D

04/02/08 26

Identification d'erreurs

► Erreurs géométriques potentielles● Noeud manquant ou mal localisé● Contour manquant ou mal localisé● Contour de forme imprécise ● Noeud localisé à plusieurs endroits● Coordonnées de points manquantes

04/02/08 27

Rôle de la topologie

► Définir les relations entre des formes.

► Forme : ensemble caractérisé par un intérieur, un extérieur et une frontière.

► Forme connexe : une forme est dite connexe si entre deux points quelconques (p et q) de cette forme, il existe toujours un chemin entre p et q, tel que tous les points du chemin soient à l'intérieur de la forme.

04/02/08 28

Rôle de la topologie

► Exemple de forme connexe● Un graphe est dit connexe si pour toute paire de sommets

distincts il existe une chaîne les reliant. La direction n’a pas d’importance pour qu’un graphe soit connexe.

5

4

3

5

5

5

04/02/08 29

Opérateurs topologiques

► Exemple de relation entre deux formes● Inclusion : Une forme B est incluse dans une forme A si

tous les éléments de B appartiennent à A.

A

B

04/02/08 30

Opérateurs topologiques

► Exemple de relation entre deux formes● Intersection : deux formes A et B s'intersectent si certains

éléments de l'une appartiennent aussi à l'autre.

AB

A ∩ Β = C

04/02/08 31

Opérateurs topologiques

► Exemple de relation entre deux formes● Union : l'union (C) de deux formes A et B contient tous les

éléments des deux formes. Leur intersection apparaît une seule fois.

AB

A ∪ Β = C

04/02/08 32

Opérateurs topologiques

► Exemple de relation entre deux formes● Recouvrement total : si tous les points de la forme A

appartiennent à la forme B et vice versa, alors les deux formes se recouvrent totalement.

A ⊂ B et B ⊂ A Donc A = B

Forme A en jauneForme B hachurée

04/02/08 33

Opérateurs topologiques

► Exemple de relation entre deux formes● Voisinage ou adjacence : deux formes A et B sont dites

voisines ou adjacentes si elles ont une frontière commune. Leur intersection est vide.

A ∩ B = ∅

AB

04/02/08 34

Identification d'erreurs

► Erreurs topologiques potentielles● Contours non connectés● Un polygone possède plus d'un ou pas de point de

référence qui est est associé● Présence d'arcs dupliqués● Un polygone possède un trou (non fermé) entre deux

contours● Un noeud a seulement un ou deux contours au lieu de trois● Un polygone, un point ou une ligne manquants

04/02/08 35

Exemples d'erreurs

04/02/08 36

Topologie

► Conclusion● La topologie décrit les caractéristiques géométriques des

objets, invariantes par des transformations tel l'étirement.● Ces caractéristiques sont indépendantes de tout système

de coordonnées et de l'échelle.● La topologie comprend trois éléments fondamentaux :

l'adjacence (objets à frontières communes), l'inclusion (objet inclus dans un autre) et la connexité (lien entre des objets linéaires pour former par exemple un réseau).

04/02/08 37

Topologie

► Conclusion● La prise en compte des relations géométriques entre les

entités spatiales est très importante pour l'analyse spatiale et l'intégration des données dans les SIG.

● Par exemple, l'ignorance des relations géométriques entre les entités ne permet pas de répondre à des questions telles que : « quel est le plus court chemin entre deux points? Combien de maisons se trouvent dans le secteur inondé d'une ville? ».

04/02/08 38

Gestion des données attributairesRappel

► Donnée● Représentation d'une information, codée dans un format

permettant son traitement par ordinateur.

► Donnée attributaire ou descriptive● Donnée relative à l'un des attributs d'une entité ou d'une

relation, à l'exclusion de sa position et de sa forme. ✔ Cette donnée constitue un élément distinctif qui permet de

reconnaître un objet géographique parmi une série de même nature.

✔ La donnée descriptive est textuelle, numérique ou alphanumérique.

04/02/08 39

Gestion des données attributairesRappel

► Métadonnée● Elle renseigne sur la nature de certaines autres données et

permet ainsi leur utilisation pertinente. Le type de projection est un exemple de métadonnée. ✔ Dans la perspective des entrepôts de données, les métadonnées

sont un élément primordial et sont destinées à diverses catégories d'utilisateurs. Elles permettent notamment de connaître l'origine et la nature des données stockées dans l'entrepôt, de comprendre comment elles sont structurées, de savoir comment y avoir accès et comment les interpréter, de connaître les différents modèles de données en présence et les règles de gestion de ces données.

04/02/08 40

Gestion des données attributairesRappel

► Donnée géographique● Ensemble des données géométriques, des données

descriptives et des métadonnées utilisées dans une application géomatique.

► Géorépertoire● Catalogue répertoriant et décrivant des jeux de données à

référence spatiale. C'est un répertoire géodocumentaire.

04/02/08 41

Prof Goze B. Bénié, Ph.D.

JeJe vous remercieremercie