Алгоритм вывода эллипса.

Данный алгоритм является модификацией алгоритма генерации окружности, предложенного Джеком Брезенхемом

Уравнение эллипса имеет вид . Перепишем его следующим образом: b²x²+a²y²=a²b²

Рассмотрим точку с абсциссой . Касательная к эллипсу в этой точке будет составлять угол 45º. Тогда эллипс в первой четверти можно построить в два этапа: сперва при изменении абсциссы от 0 до x_m, затем от a до x_m.

Алгоритм Брезенхема пошагово генерирует очередные точки эллипса, выбирая на каждом шаге для занесения пикселя точку растра P_i(x_i,y_i), ближайшую к истинному эллипсу, так чтобы ошибка ε(P_i) =b²x_i²+a²y_i²-a²b² была минимальной.

Рассмотрим генерацию части эллипса, лежащей в первой четверти, по часовой стрелке при изменении абсциссы от 0 до x_m.

Проанализируем возможные варианты занесения i -й точки, после занесения i –1 -й.

При генерации эллипса в рассматриваемой области после занесения
точки P(x_i-1,y_i-1) следующая точка может быть (см. рис) либо S(x_i-1+1,y_i-1) - перемещение по горизонтали, либо T(x_i-1+ 1, y_i-1- 1) - перемещение по диагонали. Для этих возможных точек вычислим и сравним абсолютные значения разностей квадратов расстояний от центра эллипса до точки и эллипса:

|S_i| = |(x_i-1+1)²b²+ y_i-1²a²– a²b²|

|T_i| = |(x_i-1+1)²b²+ (y_i-1- 1)²a²– a²b²|

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

d_i = |S_i| - |T_i|= |(x_i-1+1)²b²+ y_i-1²a²– a²b²| - |(x_i-1+1)²b²+ (y_i-1- 1)²a²– a²b²|

И будем выбирать T_i если d_i> 0 и S_i если d_i≤ 0.

Попробуем избавиться от модулей. Возможны 3 случая:

1. S_i> 0, а T_i< 0. Тогда d_i=S_i+T_i.

2. S_i> 0, а T_i >0. Тогда надо будет выбрать точку T_i. Если рассмотрим d_i=S_i+T_i, то оно, очевидно, будет положительным, что соответствует точке T_i

3. S_i< 0, а T_i< 0. Тогда надо будет выбрать точку S_i. Если рассмотрим d_i=S_i+T_i, то оно, очевидно, будет отрицательным, что соответствует точке S_i

Одним словом, знак выражения d_i=S_i+T_i определяет следующую точку однозначно. Преобразуем его следующим образом:

d_i= S_i+ T_i= 2 (x_i-1+1)²b²+ 2 y_i-1²a²+a²- 2 y_i-1a²- 2 a²b²=

= 2 x_i-1²b²+ 4 x_i-1b²+ 2 b²+ 2 y_i-1²a²+ a²- 2 y_i-1a²- 2 a²b² (*)

Выведем рекуррентную формулу для d_i. Для этого рассмотрим разность d_i+1-d_i.

d_i+1- d_i =2 x_i²b²+ 4 x_ib²+ 2 b²+ 2 y_i²a²+ a²- 2 y_ia²- 2 a²b²– ( 2 x_i-1²b²+ 4 x_i-1b²+ 2 b²+ 2 y_i-1²a²+ a²- 2 y_i-1a²- 2 a²b²)

Так как x_i=x_i-1 + 1, то d_i+1-d_i = 4 b²x_i-1 + 6 b²+ 2 a²(y_i-y_i-1)(y_i+y_i-1+ 1 )

Если на i-ом шаге выбрана точка S, то y_i=y_i-1 и d_i+1=d_i + 4 b²x_i-1 + 6 b²; а если точка P, то y_i=y_i-1 – 1 и d_i+1=d_i + 4 b²x_i-1 + 6 b²- 4 a²y_i-1

Подставляя в формулу (*) начальные значения x= 0 и у =b, получаем, что d₁ = 2 b²+a²- 2 ba²

Таким образом, дуга эллипса при изменении абсциссы от 0 до x_m построена. Построение оставшейся части эллипса в первой четверти ведётся аналогично, только меняется направление просмотра и все х заменяются на у.

Эллипс целиком можно получить отображением части, лежащей в первой четверти, относительно осей координат и начала координат.

Кривы́е Безье́

Кривы́е Безье́ или Бернште́йна-Безье́ – типы кривых, предложенные в 60-х годах XX века независимо друг от друга Пьером Безье из автомобилестроительной компании «Рено» и Полем де Кастельжо из компании «Ситроен », где применялись для проектирования кузовов автомобилей.

Несмотря на то, что открытие де Кастельжо было сделано несколько ранее Безье (1959), его исследования не публиковались и скрывались компанией как производственная тайна до конца 1960-х.

Благодаря простоте задания и манипуляции, кривые Безье нашли широкое применение в компьютерной графике для моделирования гладких линий. Кривая целиком лежит в выпуклой оболочке своих опорных точек. Это свойство кривых Безье с одной стороны значительно облегчает задачу нахождения точек пересечения кривых (если не пересекаются выпуклые оболочки опорных точек, то не пересекаются и сами кривые), а с другой стороны позволяет осуществлять интуитивно понятное управление параметрами кривой в графическом интерфейсе с помощью её опорных точек.

Наибольшее значение имеют кривые Безье второй и третьей степеней (квадратичные и кубические). Кривые высших степеней при обработке требуют большего объёма вычислений и для практических целей используются реже. В программах векторной графики, например AdobeIllustrator, подобные фрагменты известны под названием «путей» (path), а в 3DS Max и подобных программах 3D-моделирования кривые Безье имеют название «сплайны».

Свойства кривой Безье

1. непрерывность заполнения сегмента между начальной и конечной точками;
2. кривая всегда располагается внутри фигуры, образованной линиями, соединяющими контрольные точки;
3. при наличии только двух контрольных точек сегмент представляет собой прямую линию;
4. прямая линия образуется при коллинеарном (на одной прямой) размещении управляющих точек;
5. кривая Безье симметрична, то есть обмен местами между начальной и конечной точками (изменение направления траектории) не влияет на форму кривой;
6. масштабирование и изменение пропорций кривой Безье не нарушает её стабильности, так как она с математической точки зрения «аффинно инвариантна»;
7. изменение координат хотя бы одной из точек ведет к изменению формы всей кривой Безье;
8. любой частичный отрезок кривой Безье также является кривой Безье;
9. степень кривой всегда на одну ступень ниже числа контрольных точек. Например, при трех контрольных точках форма кривой — парабола;
10. окружность не может быть описана параметрическим уравнением кривой Безье;
11. невозможно создать параллельные кривые Безье, за исключением тривиальных случаев (прямые линии и совпадающие кривые), хотя существуют алгоритмы, строящие приближённую параллельную кривую Безье с приемлемой для практики точностью.

Кривая Безье— параметрическаякривая, задаваемая выражением

гдеP_i— функция компонент векторов опорных вершин, аb_i,n(t)— базисные функции кривой Безье, называемые такжеполиномами Бернштейна.

Координаты кривой описываются в зависимости от параметра t ⋲[0,1]

· Для двух точек:

P = (1-t)P₁ + tP₂

· Для трёх точек:

P =(1−t)²P₁ + 2(1−t)tP₂ + t²P₃

· Для четырёх точек:

P = (1−t)³P₁ + 3(1−t)²tP₂ +3(1−t)t²P₃ + t³P₄

Вместо P_i нужно подставить координаты i-й опорной точки (x_i, y_i).
Эти уравнения векторные, то есть для каждой из координат:

· x = (1−t)²x₁ + 2(1−t)tx₂ + t²x₃

· y = (1−t)²y₁ + 2(1−t)ty₂ + t²y₃

Вместо x₁, y₁,x₂, y₂, x₃, y₃ подставляются координаты трёх опорных точек, и в то время как t пробегает множество от 0 до 1, соответствующие значения (x, y) как раз и образуют кривую.
Впрочем, это чересчур наукообразно, не очень понятно, почему кривые именно такие, и как зависят от опорных точек. С этим нам поможет разобраться другой, более наглядный алгоритм.