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

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

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

Уравнение эллипса для рассматриваемого случая можно записать в следующем виде:

В случае окружности можно упростить построение: достаточно определить координаты 1/8 окружности и дальше отразить на все остальные. Название связано с тем, что на каждом шаге работы алгоритм выбирает ближайший к эллипсу пиксел из двух возможных, анализируя, находится ли средняя точка между этими пикселами внутри или вне эллипса. Приведенное уравнение эллипса можно использовать в качестве пробной функции (примечание: пробная функция - функция вида f(x,y), равная 0 в случае, если точка принадлежит к описываемой этой функцией фигуре).
Точка, лежащая на эллипсе, при подстановке ее координат в пробную функцию даст нулевое значение. Если точка лежит внутри эллипса, то значение пробной функции будет отрицательно, а при расположении точки вне эллипса получим положительный результат. Анализируя знак пробной функции для средней точки, расположенной между двумя альтернативными пикселами, выбираем один ближайший к эллипсу пиксел. Выбор очередного пиксела может осуществляться из пары пикселов, расположенных либо на одной вертикальной либо на одной горизонтальной линии . Анализ вертикальной или горизонтальной пары пикселов зависит от угла наклона касательной к эллипсу, т.е. от значения производной dY/dX.При dY/dX > -1 выбор должен осуществляться между двумя вертикальными пикселами, а при dY/dX < -1 – между двумя горизонтальными пикселами.

Рассмотрим интервал 1:

Пусть пиксел, выбранный на предыдущем шаге, имеет координаты (X i-1 ,Y i-1 ) Средняя точка М будет иметь координаты (X i-1 +1, Y i-1 –0,5). Значение пробной функции для средней точки будет иметь следующее значение:

Полученное значение можно использовать для принятия решения, однако непосредственно использовать это выражение нецелесообразно, так как его вычисление требует выполнения большого количества операций. Уменьшить количество проводимых вычислений можно, если использовать итерационную схему вычислений, предполагающую определение значения пробной функции на текущем шаге на основе ранее вычисленного значения пробной функции для предыдущего шага. Координаты средней точки на предыдущем шаге вычислений имеют вид (X i-1 ,Y 1 –1 +0,5). Разность значений пробной функции для двух соседних шагов вычисляется из следующего выражения:

.

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

;

,

где .

Значения b2, bd вычисляются один раз в начале работы алгоритма.

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

Рассмотрим интервал 2:

A и B в отличие от первого случая расположены на одной горизонтальной линии. Для выбора пиксела анализируется расположение средней между A и B точки М. Если точка М расположена вне эллипса, то точка А расположена ближе к эллипсу (эллипс проходит между точками М и А). Если точка М расположена внутри эллипса, то точка В расположена ближе к эллипсу (эллипс проходит между точками В и М).

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

;

,

где .

Переход от первого случая выбора пикселов ко второму случаю:

Искомая точка удовлетворяет равенству dY/dX = -1.Дифференцируем выражение b^2X^2 + a^2Y^2 - a^2*b^2 и получаем:

Вычисление пробной функции для граничной точки, удовлетворяющей условию dY/dX= -1.

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

Вычисление начального значения fпр:

Алгоритм(Взят: https://github.com/Panda-Lewandowski/Computer-graphics):