Fast recognition of a digital straight line subsegment: two algorithms of logarithmic time complexity

DOI10.1016/j.dam.2014.04.017zbMath1307.05036MaRDI QIDQ2255825

Isabelle Sivignon

Publication date: 18 February 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.04.017

zbMATH Keywords

digital geometry; digital straight segment recognition; Farey fan; local convex hull; subsegment

Mathematics Subject Classification ID

05B25: Combinatorial aspects of finite geometries

Uses Software

• 2D Arrangement
• DGtal

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Two efficient algorithms for computing the characteristics of a subsegment of a digital straight line
• Approximating a real number by a rational number with a limited denominator: a geometric approach
• Geometric interpretation of the Euclidean algorithm and recognition of segments
• Digital straightness -- a review
• Classroom examples of robustness problems in geometric computations
• On digital plane preimage structure
• Computing the Characteristics of a SubSegment of a Digital Straight Line in Logarithmic Time
• Discrete Representation of Straight Lines
• The number of digital straight lines on an N*N grid
• Multiscale Discrete Geometry
• On the number of digital straight line segments
• An on-line algorithm for fitting straight lines between data ranges
• Computing Two-Dimensional Integer Hulls
• Digital Intersections: minimal carrier, connectivity, and periodicity properties
• Walking in the Farey Fan to Compute the Characteristics of a Discrete Straight Line Subsegment