Item – Theses Canada

​
OCLC number
947284274
Link(s) to full text
LAC copy
Author
Weber, Romaine Ariane,1990-
Title
Un algorithme linéaire pour le calcul de l'enveloppe externe d'un chemin discret
Degree
Mémoire (M. en informatique)--Université du Québec à Montréal, 2015.
Publisher
Montréal : Université du Québec à Montréal, 2015.
Description
1 online resource (vi, 53 feuillets) :illustrations (certaines en couleur)
Notes
En tête du titre : Université du Québec à Montréal.
Comprend des références bibliographiques (feuillets 51-53).
Abstract
Ce mémoire concerne le problème du calcul de l'enveloppe externe d'une figure et se situe dans le domaine de la géométrie digitale, une branche importante de la géométrie discrète et algorithmique. Le point de vue adopté est intimement lié à la combinatoire des mots puisque toute figure discrète est codée par son contour, c'est-à-dire un mot sur l'alphabet de Freeman constitué de quatre lettres identifiant les quatre directions élémentaires sur le réseau carré Z x Z, qui représente notre plan discret. Ainsi le problème se réduit à étudier les mots de contour. On présente donc un algorithme permettant de calculer l'enveloppe externe d'un chemin discret. On utilise une structure d'arbre quaternaire pour représenter les points du plan discret Z x Z, enrichie par des liens de voisinages. En assimilant notre chemin discret à un labyrinthe, l'algorithme de calcul de l'enveloppe externe se base sur la méthode bien connue dite "de la main droite" permettant de sortir d'un labyrinthe efficacement. De plus, grâce à la structure d'arbre quaternaire, notre algorithme est linéaire en temps et en espace.
Other link(s)
Disponible par Archipel
www.archipel.uqam.ca
Subject
Envelopes (Geometry)
Discrete geometry.
Convex geometry.
Enveloppes (Géométrie)
Algorithmes.
Géométrie discrète.
Géométrie algorithmique.
Géométrie convexe.
Combinatoire des mots.