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.
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 |
Éditer le document (administrateurs uniquement)
Altmetric
Altmetric