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

Эллипс с центром в начале координат описывается уравнением:

$\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1$

где $a$ - горизонтальный радиус, $b$ - вертикальный радиус.

Умножим обе части уравнения на $a^2b^2$, чтобы избавиться от дробей:

$b^2x^2 + a^2y^2 = a^2b^2$

Определим функцию ошибки для точки $P(x_i, y_i)$:

$EllipseError(x_i, y_i) = b^2x_i^2 + a^2y_i^2 - a^2b^2$

Значение этой функции показывает, насколько точка $P$ отклоняется от идеального эллипса:

Если $EllipseError(x_i, y_i) = 0$, точка лежит точно на эллипсе

Если $EllipseError(x_i, y_i) > 0$, точка находится вне эллипса

Если $EllipseError(x_i, y_i) < 0$, точка находится внутри эллипса

В отличие от окружности, эллипс в первом квадранте строится в двух областях, разделенных точкой, где наклон касательной равен $-1$. Остальные квадранты эллипса могут быть получены последовательными отражениями.

Рассмотрим процесс построения в первой области.

Первая область начинается от точки $(a, 0)$. Движение против часовой стрелки. На каждом шаге $y$ увеличивается на 1, а $x$ может уменьшиться на 1 или остаться прежним. Движение заканчивается, когда наклон касательной достигает $-1$.

Пусть мы находимся в точке $(x, y)$. На следующем шаге мы перейдем к $y+1$, и нам нужно выбрать между точками:

- $P_g = (x, y+1)$ - движение по вертикали

- $P_d = (x-1, y+1)$ - движение по диагонали

Для выбора между этими точками сравниваем их ошибки:

$EllipseError(x, y+1) = |b^2x^2 + a^2(y+1)^2 - a^2b^2|$

$EllipseError(x-1, y+1) = |b^2(x-1)^2 + a^2(y+1)^2 - a^2b^2|$

Выбираем точку с меньшей ошибкой. Нам не нужно заново вычислять $EllipseError$ для каждой следующей точки, если мы просто отслеживаем, как меняется значение при изменении аргументов.

$EllipseError(x-1, y+1) = |EllipseError(x, y) + b^2(1 - 2x) + a^2(2y + 1)|$

$EllipseError(x, y+1) = |EllipseError(x, y) + a^2(2y + 1)|$

$$EllipseError(x-1, y+1) < EllipseError(x, y+1)$$
эквивалетно условию:
$$2 \cdot [b^2 \cdot x^2 + a^2 \cdot y^2 - b^2 \cdot a^2 + a^2 \cdot (2y + 1)] + b^2 \cdot (1 - 2x) > 0$$

Определим:

- $XChange = b^2(1 - 2x)$

- $YChange = a^2(2y + 1)$

- $EllipseError = b^2x^2 + a^2y^2 - a^2b^2$ (без модуля)

Подставляя эти определения, получаем следующее условие:

$2 \cdot EllipseError + XChange > 0$

Значения $YChange$ и $XChange$ можно быстро пересчитывать, введя константы $TwoASquare = 2a^2$ и $TwoBSquare = 2b^2$

После увеличения $y$ на 1:

$YChange_{new} = a^2(2(y+1) + 1) = a^2(2y + 2 + 1) = a^2(2y + 1) + 2a^2$

$a^2(2y + 1)$ - это текущее значение $YChange$, поэтому:

$YChange_{new} = YChange + TwoASquare$

Аналогично, после уменьшения $x$ на 1:

$XChange_{new} = XChange + TwoBSquare$

Таким образом, условие выбора точки $P_d$ (диагональной) вместо $P_g$ (вертикальной) в первой области сводится к проверке:

$2 \cdot EllipseError + XChange > 0$

Если условие истинно, то выбираем $P_d$ и уменьшаем $x$ на 1, иначе выбираем $P_g$ и оставляем $x$ без изменения.

Чтобы определить, когда заканчивается первая область и начинается вторая, используем условие наклона касательной. Наклон касательной к эллипсу:

$y' = \frac{-b^2 x}{a^2 y}$

Условие $y' = -1$ приводит к:

$b^2 x = a^2 y$

Умножаем обе части на 2:

$2 b^2 x = 2 a^2 y$

Вводим переменные:

- $StoppingX = 2 b^2 x$

- $StoppingY = 2 a^2 y$

Тогда условие продолжения в первой области:

$StoppingX \geq StoppingY$

Во второй области мы начинаем от точки $(0, b)$ и движемся по часовой стрелке. На каждом шаге мы увеличиваем $x$ на 1 и решаем, нужно ли уменьшать $y$ на 1.

Пусть мы находимся в точке $(x, y)$. На следующем шаге мы перейдем к $x+1$, и нам нужно выбрать между точками:

- $P_g = (x+1, y)$ - движение по горизонтали

- $P_d = (x+1, y-1)$ - движение по диагонали

Аналогично первой области, мы можем выразить изменение ошибки через текущие значения.

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

$2 \cdot EllipseError + YChange > 0$

Если условие истинно, то выбираем $P_d$ и уменьшаем $y$ на 1, иначе выбираем $P_g$ и оставляем $y$ без изменения.

Для второй области используются те же константы:

- $TwoASquare = 2a^2$

- $TwoBSquare = 2b^2$

Обновление переменных во второй области:

- При увеличении $x$ на 1 (что мы делаем на каждом шаге):
$EllipseError = EllipseError + XChange$
$XChange = XChange + TwoBSquare$

- При уменьшении $y$ на 1 (если условие выше истинно):
$EllipseError = EllipseError + YChange$
$YChange = YChange + TwoASquare$

Условие окончания второй области - это когда наклон касательной снова становится равным $-1$, что эквивалентно условию:

$StoppingX \leq StoppingY$

где $StoppingX = 2 b^2 x$ и $StoppingY = 2 a^2 y$ (как и в первой области).