Алгоритм построения окружности методом средней точки (Glikjnmb hkvmjkyunx ktjr'ukvmn bymk;kb vjy;uyw mkctn)
![]() | Эту статью предлагается удалить. |
![]() | Необходимо проверить качество перевода, исправить содержательные и стилистические ошибки. |
Алгоритм построения окружности методом средней точки (англ. 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)
Для каждой точки выполняется равенство:
x2n + y2n = r2
Уравнение можно преобразовать к виду:
x2n = r2 - y2n
И также уравнение для следующей точки:
x2n+1 = r2 - y2n+1
Поскольку в первой полчетверти первая точка всегда будет как минимум на 1 пиксель выше последней, будет верно следующее утверждение:
y2n+1 = (yn + 1)²
= y2n + 2yn + 1
X2n+1 = r2 - y2n - 2yn - 1
Зная что r² = x² + y² преобразовываем уравнение к виду:
X2n+1 = x2n - 2yn - 1
Из-за непрерывности окружности и того, что максимумы по обеим осям одинаковы, ясно, что алгоритм не будет пропускать x точек по мере движения по последовательности. Обычно он остается на той же координате x , а иногда и сдвигается на единицу.
Вариант с целочисленной арифметикой
Так же, как и линейный алгоритм Брезенхэма , этот алгоритм может быть оптимизирован для вычислений на основе целых чисел. Из-за симметрии, если можно найти алгоритм, который вычисляет пиксели только одной полчетверти, пиксели можно отразить, чтобы получить весь круг.
Начнем с определения ошибки радиуса как разницы между точным представлением окружности и центральной точкой каждого пикселя (или любой другой произвольной математической точкой на пикселе, если она одинакова для всех пикселей). Для любого пикселя с центром в (xi ; yi) ошибка радиуса определяется как:
RE(xi ; yi) = | x2i + y2i - r2|
Эту формулу можно применить для любой точки кривой. Лучше начать с точки на положительной части оси X. Поскольку радиус будет представлять собой целое число пикселей, очевидно, что ошибка радиуса будет равна нулю:
RE(xi ; yi) = | x2i + 02 - r2| = 0
Рисование дуг окружности
[править | править код]Приведённый выше алгоритм всегда рисует только полные окружности или дýги (равные 1/8 от длины окружности). Чтобы нарисовать произвольную дугу с углом α необходимо сначала найти координаты точек этой дуги. Для поиска координат точек нужно прибегнуть к тригонометрическим вычислениям. Затем алгоритм Брезенхэма обрабатывает полную дугу и закрашивает только те точки что попали в заданый интервал. После завершения дуги алгоритм завершается досрочно.
Обобщения
[править | править код]Похожие методы можно использовать для растеризации парабол, эллипсов или других двухмерных кривых.
Источники
[править | править код]Оригинал - https://en.m.wikipedia.org/wiki/Midpoint_circle_algorithm
Для улучшения этой статьи желательно:
|