Abstract
Given a Digital Straight Line (DSL) of known characteristics (a,b,μ), 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 \(\mathcal{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 [15,14] for “short” segments.
Chapter PDF
Similar content being viewed by others
References
DGtal: Digital Geometry Tools and Algorithms Library, http://libdgtal.org
Berenstein, C., Lavine, D.: On the number of digital straight line segments. IEEE Trans. on Pattern Anal. and Mach. Intell. 10(6), 880–887 (1988)
Charrier, E., Buzer, L.: Approximating a real number by a rational number with a limited denominator: A geometric approach. Discrete Applied Mathematics 157(16), 3473–3484 (2009)
Coeurjolly, D., Sivignon, I., Dupont, F., Feschet, F., Chassery, J.-M.: On digital plane preimage structure. Discrete Applied Mathematics 151(1-3), 78–92 (2005)
Debled-Rennesson, I., Reveillès, J.-P.: A linear algorithm for segmentation of digital curves. Inter. Jour. of Pattern Recog. and Art. Intell. 9(6), 635–662 (1995)
Dorst, L., Smeulders, A.N.M.: Discrete representation of straight lines. IEEE Trans. on Pattern Anal. and Mach. Intell. 6(4), 450–463 (1984)
Dorst, L., Smeulders, A.W.: Discrete straight line segments: Parameters, primitives and properties. In: Vision Geometry. Contemporary Mathematics, pp. 45–62. Am. Math. Soc. (1991)
Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers. Oxford Society (1989)
Klette, R., Rosenfeld, A.: Digital geometry - geometric methods for digital picture analysis. Morgan Kaufmann (2004)
Koplowitz, J., Lindenbaum, M., Bruckstein, A.: The number of digital straight lines on an n ×n grid. IEEE Trans. on Info. Theory 36(1), 192–197 (1990)
Kovalevsky, V.: New definition and fast recognition of digital straight segments and arcs. In: Inter. Conf. on Patt. Anal. and Mach. Intell., vol. 2, pp. 31–34 (1990)
McIlroy, M.D.: A Note on Discrete Representation of Lines. AT&T Technical Journal 64(2), 481–490 (1985)
Wein, R., Fogel, E., Zukerman, B., Halperin, D.: CGAL - 2D Arrangements, http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Arrangement_2/Chapter_main.html
Said, M., Lachaud, J.-O., Feschet, F.: Multiscale Discrete Geometry. In: Brlek, S., Reutenauer, C., Provençal, X. (eds.) DGCI 2009. LNCS, vol. 5810, pp. 118–131. Springer, Heidelberg (2009)
Said, M., Lachaud, J.-O.: Computing the Characteristics of a SubSegment of a Digital Straight Line in Logarithmic Time. In: Debled-Rennesson, I., Domenjoud, E., Kerautret, B., Even, P. (eds.) DGCI 2011. LNCS, vol. 6607, pp. 320–332. Springer, Heidelberg (2011)
Sivignon, I., Dupont, F., Chassery, J.M.: Digital intersections: minimal carrier, connectiviy and periodicity properties. Graphical Models 66(4), 226–244 (2004)
Troesch, A.: Interprétation géométrique de l’algorithme d’euclide et reconnaissance de segments. Theor. Comput. Sci. 115(2), 291–319 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sivignon, I. (2013). Walking in the Farey Fan to Compute the Characteristics of a Discrete Straight Line Subsegment. In: Gonzalez-Diaz, R., Jimenez, MJ., Medrano, B. (eds) Discrete Geometry for Computer Imagery. DGCI 2013. Lecture Notes in Computer Science, vol 7749. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-37067-0_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-37067-0_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-37066-3
Online ISBN: 978-3-642-37067-0
eBook Packages: Computer ScienceComputer Science (R0)