Abstract
In this paper, we arithmetically describe the convex hull of a digital straight segment by three recurrence relations. This characterization gives new insights into the combinatorial structure of digital straight segments of arbitrary length and intercept. It also leads to two on-line algorithms that computes a part of the convex hull of a given digital straight segment. They both run in constant space and constant time per vertex. Due to symmetries, they are enough to reconstruct the whole convex hull. Moreover, these two algorithms provide efficient solutions to the subsegment problem, which consists in computing the minimal parameters of a segment of a digital straight line of known parameters.
This work has been mainly funded by DigitalSnow ANR-11-BS02-009 research grants.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
DGtal: Digital geometry tools and algorithms library, http://libdgtal.org
Anderson, T.A., Kim, C.E.: Representation of digital line segments and their preimages. Computer Vision, Graphics, and Image Processing 30(3), 279–288 (1985)
Balza-Gomez, H., Moreau, J.-M., Michelucci, D.: Convex hull of grid points below a line or a convex curve. In: Bertrand, G., Couprie, M., Perroton, L. (eds.) DGCI 1999. LNCS, vol. 1568, pp. 361–374. Springer, Heidelberg (1999)
Brons, R.: Linguistic Methods for the Description of a Straight Line on a Grid. Computer Graphics and Image Processing 3(1), 48–62 (1974)
Bruckstein, A.M.: Self-Similarity Properties of Digitized Straight Lines. Contemporary Mathematics 119, 1–20 (1991)
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)
Davenport, H.: The Higher Arithmetic: Introduction to the Theory of Numbers. Oxford University Press, Oxford (1983)
Debled-Rennesson, I., Reveillès, J.P.: A linear algorithm for segmentation of digital curves. International Journal of Pattern Recognition and Artificial Intelligence 9(4), 635–662 (1995)
Har-Peled, S.: An output sensitive algorithm for discrete convex hulls. Computational Geometry 10(2), 125–138 (1998)
Harvey, W.: Computing Two-Dimensional Integer Hulls. SIAM Journal on Computing 28(6), 2285–2299 (1999)
Klette, R., Rosenfeld, A.: Digital straitghness – a review. Discrete Applied Mathematics 139(1-3), 197–230 (2004)
Lachaud, J.O., Said, M.: Two efficient algorithms for computing the characteristics of a subsegment of a digital straight line. Discrete Applied Mathematics 161(15), 2293–2315 (2013)
Lindenbaum, M., Bruckstein, A.: On recursive, o(n) partitioning of a digitized curve into digital straight segments. IEEE Transactions on Pattern Analysis and Machine Intelligence 15(9), 949–953 (1993)
Ouattara, J.S.D., Andres, E., Largeteau-Skapin, G., Zrour, R., Tapsob, T.M.Y.: Remainder Approach for the Computation of Digital Straight Line Subsegment Characteristics. Submitted to Discrete Applied Mathematics (2014), doi:10.1016/j.dam.2014.06.006
Reveillès, J.P.: Géométrie Discrète, calculs en nombres entiers et algorithmique. Thèse d’etat, Université Louis Pasteur (1991)
Reveillès, J.P., Yaacoub, G.: A sublinear 3D convex hull algorithm for lattices. In: DGCI 1995, pp. 219–230 (1995)
Sivignon, I.: Walking in the Farey Fan to Compute the Characteristics of a Discrete Straight Line Subsegment. In: Gonzalez-Diaz, R., Jimenez, M.-J., Medrano, B. (eds.) DGCI 2013. LNCS, vol. 7749, pp. 23–34. Springer, Heidelberg (2013)
Voss, K.: Coding of digital straight lines by continued fractions. Computers and Artificial Intelligence 10(1), 75–80 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Roussillon, T. (2014). An Arithmetical Characterization of the Convex Hull of Digital Straight Segments. In: Barcucci, E., Frosini, A., Rinaldi, S. (eds) Discrete Geometry for Computer Imagery. DGCI 2014. Lecture Notes in Computer Science, vol 8668. Springer, Cham. https://doi.org/10.1007/978-3-319-09955-2_13
Download citation
DOI: https://doi.org/10.1007/978-3-319-09955-2_13
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09954-5
Online ISBN: 978-3-319-09955-2
eBook Packages: Computer ScienceComputer Science (R0)