Constellation, le dépôt institutionnel de l'Université du Québec à Chicoutimi

Efficient computation of the outer hull of a discrete path

Brlek Srecko, Tremblay Hugo, Tremblay Jérôme et Weber Romaine. (2014). Efficient computation of the outer hull of a discrete path. Dans Elena Barcucci, Andrea Frosini et Simone Rinaldi (dir.), Discrete geometry for computer imagery. (7908, p. 122-133). Lecture Notes in Computer Science. Cham, Switzerland : Springer.

[thumbnail of outerhull.pdf]
Prévisualisation
PDF - Version acceptée
290kB

URL officielle: http://dx.doi.org/doi:10.1007/978-3-319-09955-2_11

Résumé

We present here a linear time and space algorithm for computing the outer hull of any discrete path encoded by its Freeman chain code. The basic data structure uses an enriched version of the data structure introduced by Brlek, Koskas and Provençal: using quadtrees for representing points in the discrete plane ℤ×ℤ with neighborhood links, deciding path intersection is achievable in linear time and space. By combining the well-known wall follower algorithm for traversing mazes, we obtain the desired result with two passes resulting in a global linear time and space algorithm. As a byproduct, the convex hull is obtained as well.

Type de document:Chapitre de livre
Date:2014
Lieu de publication:Cham, Switzerland
Identifiant unique:10.1007/978-3-319-09955-2_11
Sujets:Sciences naturelles et génie > Sciences mathématiques
Département, module, service et unité de recherche:Départements et modules > Département d'informatique et de mathématique
Éditeurs:Barcucci, Elena
Frosini, Andrea
Rinaldi, Simone
Mots-clés:freeman code, lattice paths, radix tree, discrete sets, outer hull, convex hull, informatique
Déposé le:15 déc. 2020 00:28
Dernière modification:15 déc. 2020 22:58
Afficher les statistiques de telechargements

Éditer le document (administrateurs uniquement)

Creative Commons LicenseSauf indication contraire, les documents archivés dans Constellation sont rendus disponibles selon les termes de la licence Creative Commons "Paternité, pas d'utilisation commerciale, pas de modification" 2.5 Canada.

Bibliothèque Paul-Émile-Boulet, UQAC
555, boulevard de l'Université
Chicoutimi (Québec)  CANADA G7H 2B1
418 545-5011, poste 5630