%0 Journal Article %T A Comparison of Standard One-Step DDA Circular Interpolators with a New Cheap Two-Step Algorithm %A Leonid Moroz %A Jan L. Cie£żli¨½ski %A Marta Stakhiv %A Volodymyr Maksymovych %J Modelling and Simulation in Engineering %D 2014 %I Hindawi Publishing Corporation %R 10.1155/2014/916539 %X We present and study existing digital differential analyzer (DDA) algorithms for circle generation, including an improved two-step DDA algorithm which can be implemented solely in terms of elementary shifts, addition, and subtraction. 1. Introduction Digital interpolation algorithms are widely used in machine tools with numerical control, graphics displays and plotters, and manipulation robots. Circles and circular arcs frequently appear in computer graphics, computer-controlled printing, and automated control; see [1]. One of most popular methods for generation of circles and arcs is known as digital differential analyzer (DDA). Digital circular interpolators (or angular sweep generators) based on DDA approach are widely used [2¨C6]. There are many papers where characteristics research results of such interpolators are systematized [7, 8]. In this paper a new improved two-step algorithm for DDA circle generation is presented. In paper [9] the idea of applying a Nystrom two-step scheme to circle generation appeared for the first time. Our next paper [10] developed theoretical and geometric aspects of this method. In the present paper we focus on practical and experimental issues. Moreover, here we consider circles of arbitrary radius , while in [9, 10] we assumed . The accuracy of this method is higher than the accuracy of other known algorithms. Because of its simplicity (it uses only elementary shift, addition, and subtraction); this method can also be used in numerical control, planning mechanisms, and so forth. 2. DDA Algorithms The general class of DDA algorithms for circles generation is based on obvious trigonometric transformations describing rotation of vector in the coordinate plane - (Figure 1); Advantages of DDA algorithms include simplicity and high speed in generating circle point coordinate , . Figure 1: Rotation of vector in the coordinate plane - . Substituting , where is an integer (usually ), we rewrite (1) as which, obviously, can be expressed by a rotation matrix : To avoid expensive computation of trigonometric functions DDA algorithms use simpler (cheaper) expressions instead of and . For example, by replacing trigonometric functions by truncated Taylor series one gets so-called simultaneous DDA algorithms [3]. The determinant of the rotation matrix is 1. Matrices of DDA algorithms have different determinants and only approximately. The closer it equals 1 the more accurate is the corresponding circular interpolator [2]. Approximating and , we obtain the simplest (and least accurate) DDA algorithm [2, 11]: Much more accurate %U http://www.hindawi.com/journals/mse/2014/916539/