Walking in the Farey fan to Compute the Characteristics of a Discrete Straight Line Subsegment - AGPIG Accéder directement au contenu
Communication Dans Un Congrès Lecture Notes in Computer Science Année : 2013

Walking in the Farey fan to Compute the Characteristics of a Discrete Straight Line Subsegment

Résumé

Given a Digital Straight Line (DSL) of known characteristics (a,b,\mu), we address the problem of computing the characteristics of any of its subsegments. We propose a new algorithm as a smart walk in the so called Farey Fan. We take profit of the fact that the Farey Fan of order n represents in a certain way all the digital segments of length n. The computation of the characteristics of a DSL subsegment is then equivalent to the localization of a point in the Farey Fan. Using fine arithmetical properties of the fan, we design a fast algorithm of theoretical complexity O(log(n)) where n is the length of the subsegment. Experiments show that our algorithm is faster than the one previously proposed by Said and Lachaud in [14,15].
Fichier principal
Vignette du fichier
article_final.pdf (380.71 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00765981 , version 1 (17-12-2012)

Identifiants

  • HAL Id : hal-00765981 , version 1

Citer

Isabelle Sivignon. Walking in the Farey fan to Compute the Characteristics of a Discrete Straight Line Subsegment. DGCI 2013 - 17th IAPR International Conference on Discrete Geometry for Computer Imagery, Mar 2013, Séville, Spain. pp.23-34. ⟨hal-00765981⟩
184 Consultations
112 Téléchargements

Partager

Gmail Facebook X LinkedIn More