Interested Article - Алгоритм построения окружности методом средней точки

Алгоритм построения окружности методом средней точки ( англ. Midpoint circle algorithm, Bresenham's circle algorithm ) — алгоритм, используемый для определения точек, необходимых для растеризации круга, разработанный Джеком Брезенхэмом .

Кратко об алгоритме

Суть алгоритма зачключается в том чтобы найти координаты точек для растеризации окружности. Для начала необходимо обозначить центр и радиус окружности. Алгоритм расчитвываеть лишь полчетверть всей окружности.

Алгоритм

Задача алгоритма - аппроксимировать кривую x² + y² = r² используя пиксели. Каждый пиксель должен находится примерно на одном расстоянии от центра. Каждый шаг алгоритм расширяет кривую в сторону соседних пикселей удовлетворяющих неравенству x² + y² <= r², округляя x² + y² в большую сторону.

Алгоритм начинается с уравнения окружности. Для примера предположим что центр окружности находится в точке (0;0). Рассмотрим для начала только первую полчетверть и нарисуем кривую, начинающуюся в точке (r;0) и идущую против часовой стрелки, пока не достигнет угла 45°.

Быстрым направлением выступает ось y ( базисный вектор с бóльшим приростом значения) Алгоритм всегда делает шаг в положительную сторону оси y (вверх) и иногда делает шаг в медленном направлении (отрицательный X).

Из уравнения окружности выводится формула x² + y² - r² = 0 , где r² вычисляется единожды при инициализации.

Пусть точки на окружности представляют собой последовательность координат вектора к точке (в обычном базисе). Точки нумеруются в соответствии с очередью растеризации, где первый номер n = 1 присвоен точке (r;0)

Для каждой точки выполняется равенство:

x ² _n + y ² _n = r ²

Уравнение можно преобразовать к виду:

x ² _n = r ² - y ² _n

И также уравнение для следующей точки:

x ² _n+1 = r ² - y ² _n+1

Поскольку в первой полчетверти первая точка всегда будет как минимум на 1 пиксель выше последней, будет верно следующее утверждение:

y ² _n+1 = (y _n + 1)²

= y ² _n + 2y _n + 1

X ² _n+1 = r ² - y ² _n + 2y _n + 1

Зная что r² = x² + y² преобразовываем уравнение к виду:

X ² _n+1 = x ² _n - 2y _n - 1

Из-за непрерывности окружности и того, что максимумы по обеим осям одинаковы, ясно, что алгоритм не будет пропускать x точек по мере движения по последовательности. Обычно он остается на той же координате x , а иногда и сдвигается на единицу.

Вариант с целочисленной арифметикой

Так же, как и линейный алгоритм Брезенхэма , этот алгоритм может быть оптимизирован для вычислений на основе целых чисел. Из-за симметрии, если можно найти алгоритм, который вычисляет пиксели только одной полчетверти, пиксели можно отразить, чтобы получить весь круг.

Начнем с определения ошибки радиуса как разницы между точным представлением окружности и центральной точкой каждого пикселя (или любой другой произвольной математической точкой на пикселе, если она одинакова для всех пикселей). Для любого пикселя с центром в (x _i ; y _i ) ошибка радиуса определяется как:

RE(x _i ; y _i ) = | x ² _i + y ² _i - r ² |

Эту формулу можно применить для любой точки кривой. Лучше начать с точки на положительной части оси X. Поскольку радиус будет представлять собой целое число пикселей, очевидно, что ошибка радиуса будет равна нулю:

RE(x _i ; y _i ) = | x ² _i + 0 ² - r ² | = 0

Рисование дуг окружности

Приведённый выше алгоритм всегда рисует только полные окружности или дýги (равные 1/8 от длины окружности). Чтобы нарисовать произвольную дугу с углом α необходимо сначала найти координаты точек этой дуги. Для поиска координат точек нужно прибегнуть к тригонометрическим вычислениям. Затем алгоритм Брезенхэма обрабатывает полную дугу и закрашивает только те точки что попали в заданый интервал. После завершения дуги алгоритм завершается досрочно.