Конструирование кривых. 
Компьютерная графика

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

Основные принципы конструирования кривых:

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

В описании кривых в КГ возможны два подхода:

а) задание кривой уравнением;

б) описание приближенными методами: интерполяции и аппроксимации.

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

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

Пусть (x1,y1), (x2,y2), …, (xn, yn) — последовательность точек, заданных на плоскости, причём xi xj при ij. Формулу интерполяционного полинома (n-1) степени можно представить в виде.

. (8).

Основным недостатком интерполирования с помощью полиномов является значительное отклонение кривой между точками — узлами интерполирования.

Пример 1. Заданы пять точек: (0, 0), (1, 3), (2, 0), (3, 0), (4, 0).

Соответствующий интерполяционный полином может быть записан.

Этот полином имеет три экстремума вблизи точек (0,67; 3,46), (2,46; -0,47), (3,5; 0,66) (рис. 1).

Уравнение (8) представляет интерполяционную формулу Лагранжа. Для решения задач КГ более подходит параметрическая формула.

. (9).

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

(10).

где h — шаг интерполяции; yi = yi+1 — yi (i=0, 1, 2,…) — конечная разность.

Например,.

y0 =y1 — y0,.

y1 =y2 — y1,.

y2 =y3 — y2.

и т.д.

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

Пример 2. Построить интерполяционный полином Ньютона для точек (0;5,2); (1,8), (2;10,4), (3;12,4), (4,14), (5;15,2). Определим шаг интерполяции h=1.

Составим таблицу разностей.

Из табл. 1 видно, что y0=5,2, y1=2,8, 2y = 0,4.

Подставив указанные значения в (10), получим.

или Таблица 1.

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

(11).

где — полином Лагранжа.

Рис. 1. Интерполяционный полином

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

Рис. 2. Исходные данные для конструирования кривой Фергюсона