Best approximate circles on integer grids

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Best approximate circles on integer grids

Full text

Pdf (1.34 MB)

Source

ACM Transactions on Graphics (TOG) archive
Volume 2 , Issue 4 (October 1983) table of contents

Pages: 237 - 263

Year of Publication: 1983

ISSN:0730-0301

Author

M. D. McIlroy

AT&T Bell Laboratories

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 52, Citation Count: 14

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/245.246 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BADLER, N.I. Disk generation for a raster display device. Comput. Gr. Image Process. 6, 4 (Aug. 1977), 589-593.
	2	Jack Bresenham, A linear algorithm for incremental digital display of circular arcs, Communications of the ACM, v.20 n.2, p.100-106, Feb. 1977 [doi>10.1145/359423.359432]
	3	DOROS, M. Algorithms for generation of discrete circles, rings, and disks, Comput. Gr. Image Process. 10, 4 (Aug. 1979), 366-371.
	4	Herbert Freeman, Computer Processing of Line-Drawing Images, ACM Computing Surveys (CSUR), v.6 n.1, p.57-97, March 1974 [doi>10.1145/356625.356627]
	5	HARDY, G. H., AND WRIGHT, E.M. An Introduction to the Theory of Numbers. Oxford Univ. Press, London (1971), Theorem 244.
	6	HORN, B. K.P. Circle generators for display devices. Comput. Gr. Image Process. 5, 2 (June 1976), 280-288.
	7	JORDAN, B. W., LENNON, W. J. AND HOLM, B.D. An improved algorithm for the generation of nonparametric curves, IEEE Trans. Comput. C-22, 12 (Dec. 1973), 1052-1060.
	8	KAMAE, T., KOSUGI, M. AND HOSHINO, T. Dot display of simple grapics. Trans. IECE Japan 56-A, 7 (1973), 401-408, (in Japanese, quoted in {13}).
	9	KULPA, Z. On the properties of discrete circles, rings, and disks. Comput. Gr. Image Process. 10, 4 (Aug. 1979), 348-365.
	10	KULPA, Z., AND DOROS, M. Freeman digitization of integer circles minimizes the radial error. Comput. Gr. Image Process. 17, 2 (Oct. 1981), 181-184.
	11	LANE, M. More Needlepoint by Design. Scribners, New York (1972).
	12	PITTEWAY, M. L.V. Algorithms for drawing ellipses or hyperbolae with a digital plotter. Comput. J. 10, (1967), 282-289.
	13	SUENAGA, Y., KAMAE, T. AND KOBAYASHI, T. High-speed algorithm for the generation of straight lines and circular arcs. IEEE Trans. Comput. C-28, 10 (Oct. 1979), 728-736.
	14	Sutherland, I.E. SKETCHPAD--A man-machine graphical communication system. In Proceedings of the Joint Computer Conference (Detroit, Mich., May, 1963), pp. 335-352.

CITED BY 14

	Roger D. Hersch, Character generation under grid constraints, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.243-252, July 1987
	Dieter W. Fellner , Christoph Helmberg, Robust rendering of general ellipses and elliptical arcs, ACM Transactions on Graphics (TOG), v.12 n.3, p.251-276, July 1993
	Jerry Van Aken , Mark Novak, Curve-drawing algorithms for Raster displays, ACM Transactions on Graphics (TOG), v.4 n.2, p.147-169, April 1985
	Chengfu Yao , Jon G. Rokne, Hybrid Scan-Conversion of Circles, IEEE Transactions on Visualization and Computer Graphics, v.1 n.4, p.311-318, December 1995
	Arie Kaufman , Eyal Shimony, 3D scan-conversion algorithms for voxel-based graphics, Proceedings of the 1986 workshop on Interactive 3D graphics, p.45-75, January 1987, Chapel Hill, North Carolina, United States
	K. C. Posch , W. D. Fellner, The circle-brush algorithm, ACM Transactions on Graphics (TOG), v.8 n.1, p.1-24, Jan. 1989
	Daniel Cohen-Or , Arie Kaufman, 3D Line Voxelization and Connectivity Control, IEEE Computer Graphics and Applications, v.17 n.6, p.80-87, November 1997
	William E. Wright, Rendering: Parallelization of Bresenham's Line and Circle Algorithms, IEEE Computer Graphics and Applications, v.10 n.5, p.60-67, September 1990
	M. Douglas McIlroy, Getting raster ellipses right, ACM Transactions on Graphics (TOG), v.11 n.3, p.259-275, July 1992
	Eric Andres , Marie-Andrée Jacob, The Discrete Analytical Hyperspheres, IEEE Transactions on Visualization and Computer Graphics, v.3 n.1, p.75-86, January 1997
	Benedek Nagy, Characterization of digital circles in triangular grid, Pattern Recognition Letters, v.25 n.11, p.1231-1242, August 2004
	Henry G. Baker, Complex Gaussian integers for “Gaussian graphics”, ACM SIGPLAN Notices, v.28 n.11, p.22-27, Nov. 1993
	Partha Bhowmick , Bhargab B. Bhattacharya, Number-theoretic interpretation and construction of a digital circle, Discrete Applied Mathematics, v.156 n.12, p.2381-2399, June, 2008
	Partha Bhowmick , Bhargab B. Bhattacharya, Real Polygonal Covers of Digital Discs - Some Theories and Experiments, Fundamenta Informaticae, v.91 n.3-4, p.487-505, August 2009

INDEX TERMS

Primary Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Geometrical problems and computations

Additional Classification:
I. Computing Methodologies
I.3 COMPUTER GRAPHICS

General Terms:
Algorithms, Design, Theory, Verification

REVIEW

"Varol Akman : Reviewer"

This is an extremely well-written paper which will probably be the major reference when it comes to the grid-following algorithms for drawing circles. However, here is my criticism: Is this really a very important problem? Who needs 26 pages on more...

Collaborative Colleagues:

M. D. McIlroy: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player