کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419136 | 681745 | 2013 | 23 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Two efficient algorithms for computing the characteristics of a subsegment of a digital straight line Two efficient algorithms for computing the characteristics of a subsegment of a digital straight line](/preview/png/419136.png)
We address the problem of computing the exact characteristics of any subsegment of a Digital Straight Line (DSL) with known characteristics (a slope ab, a shift to origin μμ). We present here two new algorithms that solve this problem, whose correctnesses are fully proved. Their principle is to descend/climb the Stern–Brocot tree of fractions in a top-down/bottom-up way. The top-down algorithm SmartDSS has a time complexity which depends on the sum of the quotients of the continued fraction of the output slope and on the number of pattern repetitions. As a corollary, its time complexity is bounded by the sum of the quotients of the continued fraction of the input slope, Said and Lachaud (2009) [18]. The bottom-up algorithm ReversedSmartDSS has a time complexity proportional to the difference of depth of the input slope and the slope of the output segment, Said and Lachaud (2011) [17]. As a corollary, its complexity is thus logarithmic in the coefficients of the input slope. These algorithms are also efficient in practice, as shown by a series of experiments comparing these new algorithms with standard arithmetic digital straight segment recognition.
Journal: Discrete Applied Mathematics - Volume 161, Issue 15, October 2013, Pages 2293–2315