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

Алгоритм построения окружности методом средней точки (англ. 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^2_n + y^2_n = r^2

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

x^2_n = r^2 — y^2_n

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

x^2_n+1 = r^2 — y^2_n+1

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

y^2_n+1 = (y_n + 1)²

= y^2_n + 2y_n + 1

X^2_n+1 = r^2 — y^2_n — 2y_n — 1

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

X^2_n+1 = x^2_n — 2y_n — 1

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

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

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

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

RE(x_i ; y_i) = | x^2_i + y^2_i — r^2|

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

RE(x_i ; y_i) = | x^2_i + 0^2 — r^2| = 0

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

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

Обобщения

Похожие методы можно использовать для растеризации парабол, эллипсов или других двухмерных кривых.

Источники

Оригинал — https://en.m.wikipedia.org/wiki/Midpoint_circle_algorithm

Категория:Алгоритмы компьютерной графики