PDF книги

Поиcк по сайту by Google

Рейтинг@Mail.ru
Rambler's Top100
PDF книги » Информатика. Компьютеры » McIlroy M. D. - Best approximate circles on integer grids

McIlroy M. D. - Best approximate circles on integer grids

Скачать
Название: Best approximate circles on integer grids
Автор: McIlroy M. D.
Категория: Информатика. Компьютеры
Тип: Книга
Дата: 22.02.2009 12:47:43
Скачано: 25
Оценка:
Описание: 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 (r2) is integral, then each grid line that intersects the circle contains near each intersection a unique grid point that simultaneously minimizes (1) the residual x2 + y2 — r2, (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 (4r2) 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. Diophan-tine problems arise in connection with the occasional appearance of sharp (90°) corners in the resulting approximations. Categories and Subject Descriptors: 1.3.3 [Computer Graphics]: Picture/Image Generation; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems— geometric problems and computations General Terms: Algorithms, Theory Additional Key Words and Phrases: Raster graphics, diophantine approximation
Файл: 258.3 КБ
Скачать