03. Построение плоских кривых. Выбор шага изменения аргумента. Алгоритм построения эллипса и окружности по методу средней точки.

Окружность можно описать:

(x - x0)^2 + (y - y0)^2 = R^2
x^2 + y^2 = R^2
y = sqrt(R^2 - x^2)

Параметрически:

x = x0 + R*cost
y = y0 + R*sint

t ∈ [0, 2pi)

Можно построить и окружность, и эллипс используя эти уравнения. При этом, шаг изменения аргумента t = 1 / R. (можно добавить вывод 1 / R, но мне лень - ниже).

При генерации окружности достаточно построить 1/8 окружность (от (0, R) по часовой стрелке) и отразить получившеюся дугу.
При генерации эллипса так не получится, придется строить 1/4 окружности.

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

Уравнение эллипса можно записать в виде:

b^2 x^2 + a^2 y^2 - a^2 b^2 = 0

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

Пробная функция - функция вида f(x, y). Равна 0, если точка принадлежит описываемой фигуре. В данном случае в качестве пробной функции возьмем уравнение (эллипса), указанное выше.

• f(x, y) < 0 - точка внутри эллипса.
• f(x, y) > 0 - точка вне эллипса.

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

• Пока dy/dx > -1 выбор идет между двумя вертикальными пикселями.
• Пока dy/dx < -1 выбор идет между двумя горизонтальными пикселями.

Первый интервал

Значение пробной функции для средней точки:

Полученое значение требует затратных вычислений, поэтому можно свести его получение к рекурентному процессу. Координаты предыдущей средней точки: (Xi-1, Yi–1 + 0,5).

Второй интервал

• Если М расположена вне эллипса, то А расположена ближе к эллипсу.
• Если М расположена внутри эллипса, то В расположена ближе к эллипсу.

Переход от первого случая ко второму

Переход происходит, когда dy/dx = -1. Продифференцировав b^2 x^2 + a^2 y^2 - a^2 b^2, получим:

использовать для определения точки, в которой выполняется равенство dy/dx = -1.

Получение пробной функции для граничного случая

Вычисление пробной функции для начальной точки

Псевдокод

Вход: a, b, xc, yc

b2 = b * b
bd = 2 * b2
a2 = a * a
ad = 2 * a2

x = 0, y = b, f = b2 - a2 * b + 0,25 * a2

while b2 * x > a2 * y do
    if f > 0 then
        x = x + 1
        y = y - 1
        f = f + bd * x + b2 - ad * y
    else
        x = x + 1
        f = f + bd * x + b2

f = f + 3 / 4 * (a2 + b2) - (a2 * y + b2 * x)

while y >= 0 do
    if f > 0 then
        y = y - 1
        x = x + 1
        f = f + ad * y + a2 - bd * x
    else
        y = y - 1
        f = f + ad * y + a2

Из Курова (стр. 3-4)

Следующий вопрос: 04. Требования, предъявляемые к алгоритмам вычерчивания отрезков. Пошаговый алгоритм разложения отрезка в растр. Разложение в растр по методу цифрового дифференциального анализатора.

Предыдущий вопрос: 02. Преобразования на плоскости. Вывод расчетных соотношений. Матрицы преобразований.