Высшее профессиональное образование

Отрезок прямой получаем в частном случае, когда ломаная линия содержит один участок. Радиус-вектор отрезка, построенного по точкам р₀ и Р|, вычисляют по формуле
г (?) = р₀( 1 - 0 + Pi'-
Кривые, построенные по набору точек и обладающие определенной гладкостью, называют сплайнами. Термин «сплайн» для кривых заим­ствован у названия чертежного инструмента — упругой гибкой линейки, которая может изгибаться так, чтобы проходить через заданные точки.
Интерполяционная формула Лагранжа позволяет построить кривую по заданным точкам в виде
r(t) = ^L,ⁿ(t)p_i, t₀ (1.9)
/=о
где коэффициенты L"(t) равны единице при t = t, и равны нулю в ос­тальных узлах tj,j * i. Коэффициенты L"(t) представляют собой много­члены степени п - 1
L?(t) = - t₀)...(t - /,_,)(* - *_/+1)...(/ - t_n)

.


Из условия Liⁿ(tj) = 1 следует, что — = (/, - - /,_,)(/, - Г,
... (/, - t„) и
п ('-'у)
_Lj4t)₌l^i±L . ₍₁.,0)
П ih-tj)
Итак, радиус-вектор сплайна Лагранжа описывается формулой
П ('-о)
р, (in)
ⁱ⁼⁰ П «i-V j=0,j*i
Сплайн Лагранжа можно записать в виде
«)-£■ ^ р„
где lV₀ „(t) = (t- t₀)(t - /,)...(/ - /„_,)(/ - t„); = (ft ~ 'и)...
^dt ,,
На форму сплайна оказывает влияние не только расположение кон­трольных точек, но и значения узлов. На рис. 1.4 приведен сплайн Ла­гранжа, изменение узловых значений параметра которого пропорцио­нально расстоянию между соседними точками:
fj+\ ~tj _ |Pl'-bl ~ P/| h-h-1 |P/-P/-i|’
Тонкой штриховой линией на рис. 1.4 показан сплайн Лагранжа с од­нородной параметризацией (/, = /).
На рис. 1.4 можно видеть, что на форму кривой влияет не только положение контрольных точек, но и соответствующие им значения па­раметров, т.е. параметризация кривой.
Сплайн Ньютона, проходящий через заданные точки, найдем в форме:
г(г) = а₀ + а,(/ - /₀) + а₂(г - /„)(/ - t\) + - +
+ - t₀)(t /„_,). (1.12)
Векторы а, определим из условия прохождения векторной функции г(?) через точки р, при значениях параметра t_h i = 0, 1, ..., я:
Ро = ^ао>
р, = а₀ + а,(/, - t₀),
р₂ = а₀ + а,(/₂ - t₀) + а₂(?₂ — tg)(h ~~ U)i (1.13)
р„ = а₀ + а,(/„ - /₀) + a₂(r„ - t₀)(t„ - /,) + ... + а„(/„ - t₀)(t_n - /,)...(?„ - /„_,). 14Рис. 1.4
Матрица этой системы уравнений является треугольной, и система решается за один прямой проход. Первое уравнение системы (1.13) дает а₀. Подставляя этот результат во второе уравнение, получим а,. Из третье­го уравнения находим а₂ и так далее до а„. Вставляя дополнительную точку р_л+| в сплайн, увеличиваем систему (1.13) на одно уравнение, а ос­тальные уравнения остаются неизменными. Это является преимуществом сплайна Ньютона по сравнению со сплайном Лагранжа при построении кривых с увеличивающимся числом точек. Формулы (1.9) и (1.12) опи­сывают одну и ту же кривую. Сплайны Лагранжа и Ньютона редко ис­пользуются в геометрическом моделировании из-за их поведения, в том числе и из-за сильной зависимости от значений параметров в контроль­ных точках.
Построим на заданной совокупности контрольных точек кубический сплайн, который бы имел непрерывными первые и вторые производные радиуса-вектора. На каждом участке между соседними контрольными точками будем описывать радиус-вектор кривой кубическим полиномом. Вторые производные радиуса-вектора сплайна в контрольных точках обозначим через s,. Вторая производная радиуса-вектора сплайна на участке /, < / < t_M по определению является линейной функцией пара­метра t
d²г _ -t . _ t-t:
г-s,— + s,_+l .
dt² t_M-t, t_M-t_i
После двукратного интегрирования получим
r(0-s, ^(?,+1 ~^Г)3 + s₎₄, +C|? + C₂.
^W ' 6(/,-₊₁ -/,) '^+l 6(t_M -/,) ¹

²

Выражение (1.14) описывает кубический полином на отрезке /, < / <

• 
  t_M и содержит две неизвестные величины s, и s,₊₁. Для их определения приравняем первую производную сплайна на правом конце отрезка <
  
• 
  t < t, первой производной сплайна на левом конце отрезка t,_M. После дифференцирования (1.14) и подстановки t = получим
  

(7а, + я_м)Ц_м-0 _t р^-р,-

6. 
   ',41
   

После замены в (1.14) / на i - 1, дифференцирования и подстановки t = t, получим
dr _ (2s,-+s_;,,)(/, -/,■.,) _| p, -p,_i dt,, 6 t,-t_t__x
Приравняв правые части последних двух выражений, получим сле­дующее уравнение:
s,_, (t, - /_M) + 2s,. (t_M -1) + s,.₊₁ (/₍₊₁ -1,) = 6^-^ - 6 .
^{м ~*i ^ti~h-1
Такие уравнения можно составить для п - 1 контрольных точек. Под­лежат определению п + 1 неизвестных векторов s,. Два недостающих уравнения для определения всех неизвестных составим исходя из условий на концах кривой. Например, если считать концы кривой свободными, то можно положить s₀ = s„ = 0. В некоторых случаях можно принять s₀ = S], s„ = s_n_j, тогда на концевых участках сплайн будет иметь посто­янную кривизну. Дополнительные условия зависят от геометрических условий в каждом конкретном случае. Если требуется построить замк­нутую кривую, то будем иметь равное число неизвестных и уравнений. Таким образом, неизвестные векторы вторых производных s, в контроль­ных точках найдем из системы линейных уравнений. Матрица этой системы линейных уравнений трехдиагональная, что упрощает решение системы. Выражение (1.14) можно представить в виде





w = — a tj < t < t_i+l. Полученная кривая называется кубическим
U+\ ~ h
сплайном.
На форму сплайна оказывают влияние расположение контрольных точек и значения узлов. Если есть свобода выбора узловых значени

й


Рис. 1.5
параметра, то для избежания петель и необоснованных изгибов сплайнов желательно использовать параметризацию, пропорциональную натураль­ной параметризации сплайна. При натуральной параметризации кривой за параметр принимается длина кривой, отсчитываемая от некоторой начальной точки. Хорошие результаты дает также параметризация, при которой изменение узловых значений параметра пропорционально рас­стоянию между соседними точками
На рис. 1.5 приведен кубический сплайн, изменение узловых значений параметра которого пропорционально расстоянию между соседними контрольными точками; штриховой линией показан кубический сплайн с однородной параметризацией (t, = /). При однородной параметризации изменение формы сплайна будут тем больше, чем менее равномерно расположены контрольные точки.
По аналогии с кубическим сплайном могут быть построены сплайны более высокой степени, когда производные радиуса-вектора третьего и более высокого порядка непрерывны в контрольных точках. В пре­дельном случае, сохраняющем непрерывность производных «-го поряд­ка при п + 1 контрольных точках, мы построим сплайн Лагранжа или сплайн Ньютона.
Если задана последовательность т + 1 точек, через которую должна пройти кривая и производные ее радиуса-вектора в этих точках, то по этим данным можно построить сплайн Эрмита, описываемый полино­мом степени 2т + 1. Рассмотрим частный случай сплайна Эрмита для т = 1.
Ломаную линию можно рассматривать как составную кривую, постро­енную из отрезков прямой линии. По аналогии можно построить состав­ную кубическую кривую, состоящую из сплайнов Эрмита третьей степе­ни, гладко стыкующихся между собой. Построим составной сплайн Эр­мита, проходящий через заданную последовательность точек и имеющий в этих точках заданные производные. Пусть радиусы-векторы этих точек равны р„ векторы производных кривой в этих точках равны q„ а значения параметра в этих точках равны t, (t_t < t_M), где / = 0, 1, 2, ..., п — номера точек. На участке между точками р, и р,₊₁ составной сплайн Эрмита яв­ляется полиномом третьей степени местного параметра w (рис. 1.6)

: