Нашли опечатку? Выделите ее мышкой и нажмите Ctrl+Enter
Название: Best approximate circles on integer grids
Автор: McIlroy M.D.
Аннотация:
The problem of drawing an approximate circle on an integer x — у grid has a unique best solution in practical cases. If the center is (0, 0) and the square of the radius (r^2) is integral, then each grid line that intersects the circle contains near each intersection a unique grid point that simultaneously minimizes (1) the residual x^2 + y^2 - r^2, (2) Euclidean distance to the circle, and (3) displacement along the grid line from the intersection. Thus the set of such minimizing points is the "best" approximation to the circle in several natural senses. Criteria (l)-(3) collectively, but not severally, define unique approximate circles when half-integer center coordinates and integer squared diameters (4r^2) are admitted. In other cases the criteria may disagree. Simple, efficient, all-integer algorithms for drawing circles and arcs with approximately known endpoints follow from the analysis. Diophantine problems arise in connection with the occasional appearance of sharp (90*) corners in the resulting approximations.