Réseau triangulaire irrégulier (RTI)

Question 1

Quelles sont les caractéristique d’un Réseau Triangulaire Irrégulier (RTI) ?

Answer 1

• Triangulated Irregular Network (TIN)
• Représentations d’images (2D) utilisant un modèle de points (Pixel)
• Réseau de triangles connectés
• Nœuds irrégulièrement espacés
• Les nœuds représentent les points d’observation par des coordonnées x et y (2D) et les valeurs z (0.5D)
• Chaque triangle peut avoir plusieurs attributs

Question 2

Description générale des RTI.

Answer 2

• Alternative intéressante à la matrice régulière d’un MNT.
• Adopté par de nombreux logiciels de SIG et de cartographie numérique.
• Développer au début des années 70.
• À l’origine, il s’agissait simplement de construire une surface à partir d’un ensemble de points répartis dans l’espace de façon irrégulière.

Question 3

Définition d’un RTI (TIN) selon Office québécois de la langue française.

Answer 3

Structure (triangulaire) vectorielle permettant la représentation et le stockage de données à l’aide de cellules triangulaires de forme et de taille variables.

Question 4

Definition d’un RTI (TIN) selon ESRI.

Answer 4

• Structure de données vectorielles qui divise l’espace géographique en triangles contigus et non superposés.
• Les sommets de chaque triangle sont des points de données d’échantillonnage de valeurs x, y et z.
• Ces points d’échantillonnage sont reliés par des lignes pour former des triangles de Delaunay.
• Pour stocker et d’afficher des modèles de surface.

Question 5

Quelles sont les composantes d’un RTI ?

Answer 5

• Noeuds (Node)
• Arrêts de triangle (Edge)
• Triangles

Question 6

Quels sont les avantages d’un RTI ?

Answer 6

• La taille des triangles (maille) peut être ajustée localement à la finesse des détails du terrain.
• La densité des points peut varier selon la pente.
• La possibilité de générer plus d’informations dans les zones de relief complexe.
• Éviter le problème de la collecte de données redondantes dans les zones de relief simple.

Question 7

Quels sont les inconvénients d’un RTI ?

Answer 7

• Structure plus complexe
• Manipulation plus complexe
• Topologie explicite et complexe

Question 8

Quels sont les trois méthodes de sélection des points d’une grille matricielle pour un TIN ?

Answer 8

• L’algorithme de Fowler et Little
• L’algorithme des points très importants
• L’algorithme des points peu significatifs

Question 9

Comment fonctionne les méthodes de sélection des points ?

Answer 9

• Cherche à sélectionner les points situés sur les ruptures des pentes les plus significatives de la surface.
• De telles ruptures de pente sont courantes pour la représentation du relief.

Question 10

Décrire l’algorithme de Fowler et Little.

Answer 10

• Fondée sur le concept de points spécifiques de surface jouant un rôle particulier pour définir la surface.
• Représente les éléments tels que les sommets et les creux.
• S’applique à une matrice régulière des points d’altitudes connus.
• Examine la surface à l’aide d’une fenêtre 3×3, en considérant à chaque fois une petite matrice de 9 points.
• À partir du point central, on code des (+) s’ils sont situés plus haut, ou (-) s’ils sont situés plus bas.

Question 11

Quels sont les choix importants à faire lors de la réalisation d’u TIN ?

Answer 11

• Comment retenir les points ? (Sélection des points)
• Comment connecter les points afin de former des triangles ? (Triangulation)
• Comment modéliser la surface à l’intérieur de chaque triangle ? (Interpolation)

Question 12

Expliquer le principe de codage derrière l’algorithme de Fowler et Little ?

Answer 12

• Un point est un sommet si chacun de ses 8 autres points voisins est situé au-dessous (8 -).
• Un point est un creux si chacun de ses 8 autres points voisins est situé au-dessus (8 +).
• Un point est une passe si les (+) et les (-) alternent autour de ce point pour au moins deux cycles complets.
  
  • Deux cycles: 2 fois alternance entre (+) et (-)
  • Quatre cycles: 4 fois alternance entre (+) et (-)

Question 13

Nommer un inconvénient de l’algorithme de Fowler et Little ?

Answer 13

• Il ne peut pas être utiliser en milieu urbain
• Nécessite la présence de plusieurs ruptures de pentes (milieu montagneux)

Question 14

Comment sont définit les crêtes et les talweg avec l’algorithme de Fowler et Little ?

Answer 14

• La surface est examiner en utilisant une fenêtre 2x2.
• Mise à part des limites du MNT, chacun des points
  apparaît à quatre positions dans la fenêtre.
• Un point est potentiellement un point de crête s’il n’est jamais le plus bas des quatre positions de la fenêtre.
• Un point est potentiellement un point de talweg s’il n’est jamais le plus haut des quatre positions de la fenêtre.
• Il faut parfois élargir la fenêtre d’analyse (ex.: creux de quatre pixels).

Question 15

Qu’est-ce que l’algorithme des points très importants ?

Answer 15

• Fonctionne avec une matrice de points connus.
• Fonctionne en analysant la surface en détail à l’aide d’une fenêtre locale de 3x3.

Question 16

Quels sont les avantages de l’algorithme des points importants ?

Answer 16

• Adapté au milieu urbain.
• Plus conviviable !

Question 17

Quelles sont les principales étapes de l’algorithme des points très importants ?

Answer 17

0) Création préalable d’une grille
1) Sélection de 8 points voisins formant 4 paires diamétralement opposées.
2) Examine à tour de rôle les paires de voisin pour chaque point.
3) Sur un diagramme représentant des altitudes, on relie les deux voisins par une ligne droite puis on calcule la distance othogonale du point central à cette ligne.
4) Moyenne des quatre distances = mesure de signification globale du point (poids).
5) Élimineles points par odre de signification croissante.
6) Continue jusqu’à l’une des conditions suivantes soit satisfaite : 1. Nb de points retenus 2. Degré de signification

Question 18

Commentaire sur l’algorithme des points très importants.

Answer 18

• En raison de sa nature locale: optimale lorsque la
  proportion de points à éliminer est faible.
• Emphase mise sur les lignes droites et le TIN utilisant des surfaces planes : peu satisfaisante pour le traitement des surfaces courbes.

Question 19

Qu’est-ce que l’algorithme des points peu significatifs ?

Answer 19

• Aborde le problème sous son aspect d’optimisation.
• Représente la surface en sélecitionnant un nb définit de points à partir d’un modèle d’altitude matriciel dense.
• Sélectionné de manière à construire un réseau de triangle approximant le mieux la surface originale.

Question 20

Quelles sont les étates de l’algorithme des points peu significatifs ?

Answer 20

1) TIN préliminaire
2) Élimine temporairement ch. point et ajuste les triangles voisins
3) Trouve le triangle contenant le point éliminé
4) Mesure la différence entre l’alt. réelle du point et celle de la surface.
5) Continue le processus en éliminant ch. point à tour de rôle.
6) Une fois tous les points examinés : supprime définitivement celui avec la différence la +faible
7) Reprend le processus de puis le début pour l’ensemble de la matrice

Question 21

Nommer un critère déterminant lors de la triangulation et expliquer pourquoi.

Answer 21

• Les triangles doivent être le plus homogènes possible (fat triangle).
• Chaque point situé dans le triangle est aussi proche que possible des trois sommets.
• La représentation de la surface est plus précise au voisinage des sommets !

Question 22

Nommer deux méthodes de construction des triangles.

Answer 22

• Le classement selon la distance
• La triangulation Delaunay

Question 23

En quoi consiste la triangulation par classement selon la distance ?

Answer 23

1) Calcule la distance entre toutes les paires de points
2) Trie les distance en ordre croissant
3) Relie la seconde paire de points les +proches à condition qu’aucune ligne ne se croisent
4) Continue jusqu’à ce que ce ne soit plus possible de tracer une ligne sans qu’elle n’en coise un autre
5) Les lignes retenues sont utilisées pour formers des triangles

Question 24

Quel est l’inconvénient principal de la triangulation par classement selon la distance ?

Answer 24

• Elle peut produire des triangles aigus !
• Cette méthode n’est donc pas utilisée en pratique…

Question 25

Qu’est-ce qu’un triangle de Delaunay ?

Answer 25

Trois points forment un triangle Delaunay si et seulement si le cercle passant par ces trois points (cercle circonscrit) n’en contient aucun autre.

Question 26

Quelles sont les composantes principales de la triangulation de Delaunay ?

Answer 26

• Partition de l’espace : polygones de Voronoi
• Connecte le centre de cellules Voronoi -> maillage triangulaire respecant Delaunay
• Polygone convexe (Convex Hall) : +petit polygone contenant tous les sommets

Question 27

Quelles sont les trois méthodes principales de construction des triangles Delaunay ?

Answer 27

• Convex Hall
• Distance la plus courte
• Dynamique

Question 28

Expliquer la triangulation de Delaunay avec le Convex Hall.

Answer 28

• Le Convex Hall est un polygone convexe faisant
  partie de la triangulation Delaunay.
• On part de ses côtés et on progresse vers l’intérieur jusqu’à ce que le réseau soit complété.

Question 29

Expliquer la triangulation de Delaunay par distance la plus courte.

Answer 29

1) Relie la paire la plus proche (côté de Delaunay)
2) Cherche le 3e point tel qu’il n’existe aucun autre point compris dans le cercle
3) Continue vers l’extérieur àpartir de ces côtés en direction du point suivant le plus proche

Question 30

Expliquer la triangulation de Delauny dynamique (construction par incrément).

Answer 30

1) Commence par un triangle qui contient tous les points observés (triangle universel)
2) Prend 1er point sur la liste des points observés
3) Recherche pour trouver le triangle qui contient le point sélectionné
4) Insérer le points dans le triangles trouvé en le divisant en 3 nouveau triangles
5) Vérifier si les nouveaux triangles sont Delaunay
6) Si non, optimiser avec changement topologique
7) Utiliser cette procédure pour insérer les autres points de la liste

Question 31

Quelles sont les méthodes principales pour modéliser la surface à l’intérieur de chaque triangle (interpolation) ?

Answer 31

• Linéaire
• Coordonnées locales
• 2nd exacte fit surface
• Quintique

Question 32

En quoi consiste l’interpolation linéaire ?

Answer 32

• Créer une surface continue, mais cette surface n’est pas lisse.
• Contrainte (𝑏3 ≠ 0) pour que le plan ne soit pas vertical.
• Équation : Z (X, Y) = 𝑎0 + 𝑎1X + 𝑎2Y
• En ayant les sommets d’un triangle, on peut déterminer les paramètres 𝑎0, 𝑎1 et 𝑎2
• Faiblesse : la direction du vecteur normal à la surface change de façon abrupte lorsqu’on traverse d’un triangle à l’autre.

Question 33

En quoi consiste l’interpolation par des coordonnées locales ?

Answer 33

• Définition des coordonnées locales: en ayant les coordonnées des sommets d’un triangle on peut calculer les coordonnés locales d’un point p.
• Équation : Zp = r1Z1+ r2Z2 + r3*Z3
  
  • r1 = a1 / a (a = aire totale)
• Faiblesse : la direction du vecteur normal à la surface change de façon abrupte lorsqu’on traverse d’un triangle à l’autre.

Question 34

En quoi consiste l’interpolation par “2nd exacte fit surface” ?

Answer 34

• Pour définir cette surface, on utilise non seulement les sommets du triangle, mais aussi les sommets des triangles voisins de ce triangle.
• La surface d’un triangle est définie par une surface courbe passant par tous les points = surface plus lisse !
• Le calcul nécessite au minimum 6 points
• L’équation d’un polynôme peut être utilisée pour la
  détermination de la valeur z d’un point quelconque.
  Faiblesse : La direction du vecteur normal à la surface change de façon abrupte lorsqu’on traverse d’un triangle à l’autre.

Question 35

En quoi consiste l’interpolation Quintique ?

Answer 35

• Consiste à définir la surface d’un triangle de sorte que la variation du vecteur normal à la surface soit continue à l’intérieur du triangle ainsi que sur ses frontières.
• Avantage : la surface obtenue est continue et plus lisse (smooth) et donc la direction du vecteur normal à la surface ne change pas de façon abrupte !
• Équation polynomiale d’ordre 5
• 21 coefficients à déterminer (21 points) !

Question 36

Présentation historique et applications du diagramme Voronoi.

Answer 36

• Structure géométrique permettant de résoudre des questions à caractère spatial, telles que la proximité et la contiguité.
• Dirichlet (1850) : propose le concept pour la 1e fois
• Voronoi (1908) : approfondi le concept de la structure
• Différents noms : polygone Dirichlet, diagramme Voronoi ou polygone Thiessen

Question 37

Donner une définition du diagramme Voronoi.

Answer 37

• Considérons un ensemble de n points (appelé sites) dans l’espace E2 (euclédient 2D). Pour chaque point p, une cellule Voronoi Vor(p) est l’ensemble des points de E2 qui sont plus proches de p que tous les autres points de S.
• Deux sommets sont voisins si leurs cellules Voronoi sont contiguës.

Question 38

Pourquoi dit-on que le diagramme Voronoi est le graphe dual de la triangulation de Delaunay ?

Answer 38

• Pour chaque vertex Voronoi correspond un triangle Delaunay.
• Pour chaque cellule Voronoi correspond un sommet d’un triangle Delaunay.
• Pour chaque segment d’une cellule Voronoi, on peut associer un côté d’un triangle Delaunay.

Question 39

Nommer des extensions pour le diaramme Voronoi.

Answer 39

• Diagramme Voronoi pondéré
• Diagramme Voronoi des éléments linéaires
• Diagramme Voronoi pour des points, des lignes et des polygones
• Diagramme Voronoi sur la sphère

Question 40

Expliquer la méthode de construction du diagramme Voronoi par incrément.

Answer 40

Étapes :
1) Construit la triangulation de Delaunay
2) Calcule le centre circonscrit des tous les triangles
3) Fait une connexion entre les centres des cercles circonscrits des triangles adjacents
4) Le diagramme résultant est le diagramme Voronoi

• Avantages : simple et efficace !

Question 41

Expliquer la méthode de construction du diagramme Voronoi par le test de “incircle”.

Answer 41

???

Question 42

Donner un exemple d’application du diagramme Voronoi pour les MNT.

Answer 42

• Sélection des points voisins à des fins d’interpolation
• Il n’est pas nécessaire d’établir une distance ou une nombre de points (variable)
• Méthode plus naturelle et performante !
• Permet une navigation facile dans le maillage pour la sélection des voisins.

Question 43

Expliquer l’interpolation par la méthode d’aire volée.

Answer 43

• Exploite la contiguité spatiale offerte par le diagramme Voronoi pour deux objectifs :
  1) La recherche des points voisins
  2) Le calcul des poids (pondération)

Question 44

Qu’est-ce que le problème du triangle plat ?

Answer 44

• Triangle dont les sommets ont la même altitude…
• Plus fréquent dans les triangulations utilisant les courbes de niveau
• Sommet du triangle plat sont situés sur la même courbe de niveau

Question 45

Qu’est-ce que la triangulation Delaunay par contraintes ?

Answer 45

• Pour augmenter la précision d’un MNT, il faut considérer des éléments importants du relief (sommets, creux, lignes de crête et de talweg).
• Dans un TIN, les côtés des triangles ne doivent pas traverser ces lignes !
• La triangulation résultante est optimisée pour être la plus proche d’une triangulation Delaunay.

Question 46

Quelles sont les deux méthodes de triangulation de Delaunay par contraintes ?

Answer 46

1) Méthode par augmentation de la densité des points sur des lignes de contrainte
- Triangulation résultante respecte Delaunay
2) Méthode par triangulation avec contraintes
- 1. Triangulation avec tous les points y compris les points des lignes de contrainte
- 2. Changement des côtés traversant les lignes de contraintes
- Permet d’éliminer le problème des triangles plats !
- La triangulation résultante n’est plus une triangulation Delaunay…