Browse Prior Art Database

Algorithm for Generating Circles or Arcs

IP.com Disclosure Number: IPCOM000084280D
Original Publication Date: 1975-Oct-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 2 page(s) / 42K

Publishing Venue

IBM

Related People

Eubanks, RS: AUTHOR [+2]

Abstract

The algorithm, represented in flow diagram form in the drawing, generates the discrete X-Y raster positions that define the best fit for arcs and circles in a graphic display device. The algorithm provides a simple, recursive relationship which is used to determine the most accurate X and Y coordinates which will approximate an arc of 45 degrees, or a multiple thereof on a matrix grid point by point. The algorithm is simple to implement in digital logic because it is recursive and only requires addition, subtraction and multiplication by binary 2 or 4, the latter of which is accomplished by shifting one or two positions to the left.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 68% of the total text.

Page 1 of 2

Algorithm for Generating Circles or Arcs

The algorithm, represented in flow diagram form in the drawing, generates the discrete X-Y raster positions that define the best fit for arcs and circles in a graphic display device. The algorithm provides a simple, recursive relationship which is used to determine the most accurate X and Y coordinates which will approximate an arc of 45 degrees, or a multiple thereof on a matrix grid point by point. The algorithm is simple to implement in digital logic because it is recursive and only requires addition, subtraction and multiplication by binary 2 or 4, the latter of which is accomplished by shifting one or two positions to the left.

Referring to the drawing, data for the arc to be drawn is entered from 20 labeled Circle Data where X(p),Y(p) define the coordinate reference point of the arc and R is the radius. The algorithm is initialized in block 21, where i defines the step count through the algorithm, j keeps count of changes in X and delta i is an internal variable equal to -2R + 3.

The initialized output is applied to block 22, which increments the step count by 1. This output is applied to decision block 23 which checks the sign of the delta of the previous step. When the sign is positive, the output is applied to block 24; when the sign is negative, the output is applied to block 25.

The sign of the output from block 24 and 25 is checked again at decision block 26. When the sign is positive, the output is applied to...