Введение

Алгоритм заливки окружности – это важный инструмент в компьютерной графике и обработке изображений. Он используется для закрашивания внутренней области окружности определенным цветом.

Применяется в:

• Рендеринге 2D-графики.
• Построении шрифтов.
• Компьютерных играх.
• Геометрических моделях.

Основные понятия

Окружность в двумерной плоскости задаётся следующим уравнением:

\[
x^2 + y^2 = R^2,
\]
где \( (x, y) \) — координаты точек окружности, а \( R \) — радиус окружности.

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

Алгоритм растеризации окружности

Алгоритм растеризации окружности, например, алгоритм средней точки (Midpoint Circle Algorithm), применяется для точного и быстрого вычисления всех точек окружности.

Этот алгоритм основывается на использовании симметрии окружности. Вместо вычисления всех точек по всей окружности, мы рассчитываем точки только в одной восьмой части (например, от \(0^\circ\) до \(45^\circ\)), а остальные получаем с помощью симметрии.

Инициализация

1. Задаём радиус окружности \( R \).
2. Начинаем с точки \( (x_0, y_0) = (0, R) \).
3. Определяем начальное значение для параметра принятия решения:
   \[
   d = 1 - R.
   \]

Итерации алгоритма

На каждом шаге алгоритм определяет, куда будет перемещаться следующая точка: либо прямо вправо (\(E\)), либо по диагонали вправо и вниз (\(SE\)). Условие выбора:

• Если \(d < 0\), выбираем пиксель \(E\), и параметр обновляется:
  \[
  d_{\text{нов}} = d_{\text{стар}} + 2x + 3.
  \]
• Если \(d \geq 0\), выбираем пиксель \(SE\), и параметр обновляется:
  \[
  d_{\text{нов}} = d_{\text{стар}} + 2x - 2y + 5.
  \]

В обоих случаях обновляем координаты:
\[
x_{\text{нов}} = x_{\text{стар}} + 1,
\]
\[
y_{\text{нов}} = y_{\text{стар}} - 1 \quad \text{(если выбрано \(SE\))}.
\]

Использование симметрии

Для оптимизации алгоритма достаточно вычислить одну восьмую часть окружности, так как остальные точки можно получить с помощью отражений относительно осей и диагоналей. Например:

Если вычислена точка \( (x, y) \), то следующие точки также принадлежат окружности:
\[
(y, x), \, (-x, y), \, (-y, x), \, (-x, -y), \, (-y, -x), \, (x, -y), \, (y, -x).
\]

Заполнение окружности

После вычисления точек окружности, чтобы закрасить её, нужно заполнить все пиксели внутри. Это делается путём отрисовки горизонтальных линий (сканов):

Для каждой координаты \( y \) от центра до границы окружности вычисляем интервал от \( -x \) до \( x \), где \( x \) — текущая граница окружности на данной строке.

Итоговый алгоритм

1. Вычисляем точки окружности с помощью алгоритма средней точки.
2. Используем симметрию для получения всех точек.
3. Заполняем окружность линиями, перебирая точки от верхней границы к нижней.

Пример кода

def fill_circle(center_x, center_y, radius):
    x, y = 0, radius
    d = 1 - radius
 
    while x <= y:
        # Рисуем линии заполнения
        draw_scanline(center_x, center_y, x, y)
 
        if d < 0:
            d = d + 2 * x + 3
        else:
            d = d + 2 * (x - y) + 5
            y -= 1
        x += 1

Заключение

Алгоритм заполнения окружности является базовым и важным инструментом для работы с графическими объектами. Его реализация основывается на эффективных вычислениях и использовании симметрии, что делает его незаменимым в компьютерной графике.