Перевод Algorithm to draw circles and ellipses, c сайта Math Open Reference

Алгоритм основан на параметрической форме уравнения окружности. Более подробно смотрите Параметрическое уравнение окружности.

Напомним, это уравнение выглядит так:

x = h + r cosθ

y = k + r sinθ

где r – радиус окружности, а h, k – координаты центра.

Это уравнение точки с координатами x, y находящейся на окружности на заданном углу θ. Алгоритм в цикле увеличивает theta от 0 до 360, рисуя прямые линии между двумя соседними точками окружности. Окружность таким образом состоит из серии отрезков. При небольших значениях угла, результат будет представляться окружностью, хотя с точки зрения математики это не совсем верно.

Алгоритм

Алгоритм в виде псевдокода демонстрирует основную идею:

theta = 0;  // угол, который должен увеличиваться в цикле
h = 12      // Координата x центра окружности
k = 10      // Координата y центра окружности
step = 15;  // Приращение угла на проход цикла (в градусах)

повторять до theta >= 360
{
    x = h + r*cos(theta)
    y = k + r*sin(theta)
    рисовать линию x, y
    прибавить step к theta
}

Решение о том, насколько большим должен быть угол между точками (step) – это всегда компромисс. Если он будет очень маленьким, то окружность получится гладкой, но это потребует больше компьютерных вычислений. Если будет большим, то окружность будет не гладкой.

Пример

Ниже приведена реализация алгоритма на JavaScript с использованием HTML5 canvas.

var ctx = canvas.getContext("2d");
var step = 2 * Math.PI / 20; // примечание 2
var h = 150; 
var k = 150;
var r = 50;

ctx.beginPath();

for(var theta = 0; theta < 2 * Math.PI; theta += step) {
    var x = h + r * Math.cos(theta);
    var y = k - r * Math.sin(theta); // примечание 1
    ctx.lineTo(x, y);
}

ctx.closePath();
ctx.stroke();

(Пример в jsfiddle – прим. пер.)

Как и многие графические системы, canvas имеет, отличную от математической, координатную плоскость:

1. Начало координат располагается в верхнем левом углу. Код выше предполагает, что значения h и k берутся относительно верхнего левого угла.
2. Ось y инвертирована. Положительная ось y направлена вниз, а не наверх. Чтобы алгоритм работал, переменная k (координата y центра окружности) должна быть положительной, чтобы центр располагался в области видимости. Также при вычислении координаты y необходимо sin(theta) вычитать, а не прибавлять. Отмечено в коде, как примечание 1.

Примечание 2. Размер шага (step) вычисляется делением 2π на коэффициент для предотвращения появления пробелов в окружности. Код делит окружность на 20 сегментов. Также заметим, что в большинстве языков программирования, трибометрические функции работают с радианами, а не с углами.

Эллипс

Окружность превращается в эллипс простым “сплющиванием” одной из сторон. Для создания эллипса, сплющенного по высоте, нужно разделить координату y (здесь на 2) для уменьшения высоты. Вычисления выглядели бы таким образом:

var x = h + r * Math.cos(theta);

var y = k - 0.5 * r * Math.sin(theta);

Меняя коэффициент 0.5 можно менять степень “сплющенности” по высоте.