Browse Prior Art Database

Circle Generation and Representation

IP.com Disclosure Number: IPCOM000081806D
Original Publication Date: 1974-Aug-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 3 page(s) / 51K

Publishing Venue

IBM

Related People

Bantz, DF: AUTHOR

Abstract

This programming concept enables circles to be generated by a digital plotter or a vector type display from stored data with considerable saving of time and expense, in those applications where many circles of the same diameter must be generated.

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 53% of the total text.

Page 1 of 3

Circle Generation and Representation

This programming concept enables circles to be generated by a digital plotter or a vector type display from stored data with considerable saving of time and expense, in those applications where many circles of the same diameter must be generated.

In the generation of a circle by digital methods, the arc contained within one octant of the circle can be approximately represented by a series of vectors, each extending in one of two available directions that are 45 degrees apart. Thus, referring to Fig. 1, the arc :AB in the first octant can be represented by a series of small vectors, respectively extending in either of the two directions shown by the horizontal and diagonal arrows M1 and M2, whose included angle is 45 degrees. In the vicinity of point A the horizontal vectors M1 will predominate, and in the vicinity of point B the diagonal vectors M2 will predominate.

In the second octant the arc BC can be represented by vectors extending in the directions indicated by the vertical and diagonal arrows M1 and M2, respectively, with the diagonal vectors M2 predominating in the vicinity of point B, and the vertical vectors M1 predominating in the vicinity of point C; and so on in similar fashion for the remaining octants of the circle.

To store a digital representation of a circle, the set of vectors defining any given octant of that circle is represented by a bit string, in which the 0 and 1 bits, respectively, represent the two available vector directions in that octant. Thus, for the first octant, 0 bits may represent horizontal vectors M1 while 1 bits represent diagonal vectors M2.

The same bit string, read in the reverse direction, also may represent the vectors defining the second octant, with 1 bits again representing the diagonal vectors M2 as in the first octant, but with 0 bits now representing vectors M1 that are vertically oriented. In other words, the vector directions associated, respectively, with the 0 and 1 bits in the stored bit string will change partially from octant to octant, and the direction in which the bit string is read will be reversed each time a new octant is entered. With the appropriate vector generating algorithm, the same bit string can be used to generate all octants of the circle.

The bit pattern in the octant-generating string will depend upon the diameter of...