Institute of Computer Science III
University of Bonn
Databases * Information Systems * Software Engineering *
Pattern Recognition * Image Processing * Artificial Intelligence * Robotics
Best Approximate General Ellipses on Integer Grids
The definition of a best approximation for circles introduced by McIlroy [7] is generalized for general ellipses (i.e. ellipses not aligned with the coordinate axes) on integer grids. For any given ellipse this definition yields a unique set of grid points, which is connected, thin, and does not contain sharp corners except at octant changes. The definition is octant independent and solves the problems of ambiguity and octant changes. The best approximation of an elliptical arc is equal to the union of the best approximations of its subarcs. For circles it is equivalent to the definition of McIlroy.
An incremental and robust algorithm is given which efficiently computes the best approximation of general ellipses according to this definition. Hardware implementations of this algorithm will be able to compete with all ellipse-rendering algorithms known so far.
Click here to obtain the full paper (PS, gzip, 49469 bytes, 13 pages)
webmaster@www.informatik.uni-bonn.de -
16.12.05