СПЛАЙНЫ: вычисление заранее значений t

[kym]

Здравствуйте!
Есть такая задача: сделать аппроксимацию сплайнами, но - максимально жёсткими сплайнами. Попытаюсь объяснить: заранее определяются значения t для группы точек (для первой точки - t=0, для последней - t=1, для промежуточных точек t вычисляются по определённому правилу). Пример правил для вычисления t: 1) использовать расстояния между точками, т.е. длину хорд, и вычислять t как отношение суммы длин хорд текущей и всех предыдущих к сумме длин всех хорд; 2) то же, но использовать не длину хорды, а квадратный корень из длины. В обоих случаях сплайн получается достаточно "гибким", т.е. чутко реагирует на изменение длин хорд. Необходимо, чтобы он реагировал как можно слабее, т.е. был более "жёстким". Какое ещё правило можно применить?

Добавлено спустя 11 минут 27 секунд:

дополнение

имеются в виду параметрические сплайны, т.е. заданные уравнениями x(t) и y(t)

[мат-ламер]

Поясните популярней, что значит "чутко реагирует на изменение длин хорд"?

Добавлено спустя 6 минут 48 секунд:

Мне кажется, что параметризация должна быть как можно более натуральной в том смысле, чтобы определяться длиной кривой. Тогда можно попробовать сделать второе приближение и параметр в нём будет определяться длиной дуги сплайна от первого приближения.

[Алексей К.]

мат-ламер в сообщении #189216 писал(а):

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

Почти полностью согласен с предыдущим оратором. Согласен полностью, если речь идёт о некой кривой, а не о сплайновании графика некой функции вроде $\mbox{маг.поле}=F(\mbox{чего-то-ещё})$, где длина дуги или хорды ничего натурального в себе не несёт. Я уже пел эту арию в сообщении #164828.

мат-ламер в сообщении #189216 писал(а):

Тогда можно попробовать сделать второе приближение и параметр в нём будет определяться длиной дуги сплайна от первого приближения.

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

"Натуральность" параметризации сплайна удобна ещё и с позиций задания граничных условий --- неких не-пойму-откуда-взять производных $x'_t(0),y'_t(0)$ (и в конце). В ряде задач известны или очевидны требуемые углы наклона касательных к сплайну $\tau(0),\:\tau(L)$. В конструкторских задачах, например. Как от них перейти к производным? Да просто, $x'_t(0)=\cos\tau(0)$, $y'_t(0)=\sin\tau(0)$. Ибо каждый кусочек кубического сплайна мы можем приближённо считать (или с высокой степенью точности считать? ) четырьмя членами тейлоровского разложения некой натурально-параметризованной кривой.

А вот стоит Вам перейти от накопленной длины хорды $l$ к относительной накопленной длине хорды $l/L$, и этот номер не проходит (проходит, но не забыть множитель-поправку!).

Вводить же какие-то корни из длины... То ли эвристика, то ли эмпирика, то ли мудрствование, в общем --- полная денатурализация!

Добавлено спустя 17 минут 47 секунд:

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

[kym]

согласен, что второе приближение практически не изменит ситуации. сам пробовал применить.
Алексей, а какой множитель-поправку Вы имеете в виду, когда говорите о переходе от накопленной длины хорды к относительной накопленной длине?
и ещё вопрос повисает в воздухе: параметризация не может изменяться длиной кривой, т.к. та заранее неизвестна. Ситуация даже ещё хуже - один из результатов параметризации - получение длины сплайна!
P.S. Под "чутким реагированием на изменение длины хорды" я понимаю изменение длины отрезка сплайна, приходящееся на изменение длины соответствующей и/или соседних хорд.

[Алексей К.]

kym в сообщении #189326 писал(а):

а какой множитель-поправку Вы имеете в виду, когда говорите...

Всего-навсего, если $t=l/L$, то

$$\dfrac{dx}{dt}=\dfrac{dx}{d(l/L)}=\fbox{L}\dfrac{dx}{dl}\quad[=L\cos\tau].$$

И тогда перепараметризация не повлияет на итоговый сплайн.

Цитата:

параметризация не может изменяться длиной кривой, т.к. та заранее неизвестна.

Длина кривой МОЖЕТ служить параметром. Поскольку заранее она неизвестна, то в качестве первого приближения длины кривой берётся суммарная длина хорд. Всё это с определённой условностью говорится, ибо в промежуточных точках можно ожидать только приближённого совпадения параметра и длины кривой.

Цитата:

Ситуация даже ещё хуже - один из результатов параметризации - получение длины сплайна!

Ну и чего там страшного? Тем более, что Вы вроде как умеете её считать ("согласен, что ... сам пробовал применить"). Проделайте несколько итераций, увидьте, как эта длина сходится к пределу. И объявляйте результат.

Цитата:

P.S. Под "чутким реагированием на изменение длины хорды" я понимаю изменение длины отрезка сплайна, приходящееся на изменение длины соответствующей и/или соседних хорд.

Это мне непонятно. У Вас что, не фиксированное множество точек, Вы их зачем-то как-то ещё дёргаете? Кстати, мои ноги тоже устают сильнее, если конечную точку пути подальше отодвинуть от начальной, но я это "чутким реагированием" не считаю. :)

[kym]

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

[Алексей К.]

kym в сообщении #189379 писал(а):

ведь длина сплайна пропорциональна длине соответствующей хорды.

Вы неясно выражаетесь.
Утверждается, что длина $l_i$ $i$-го участка сплайна пропорциональна длине хорды $h_i$? Т.е. что $l_1/h_1=l_2/h_2=\ldots=l_n/h_n$? Если это имеется в виду, то не верю.

kym в сообщении #189379 писал(а):

сплайн ищется путём решения системы линейных уравнений

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

[kym]

сейчас речь идёт о том, что значения t (или l - кому как нравится) заранее неизвестны?

[ewert]

Алексей К. в сообщении #189382 писал(а):

Есть, в том числе, способы скрыть проблему граничных условий (кажется, понижением порядка первого и последнего участка сплайна).

Это просто граничные условия на старшие производные.

[мат-ламер]

Посколько, как я понял, поставленная задача не решена, у меня тут такое предложение.Может вообще исходную задачу аппроксимации ставить по-другому. Что такое вообще сплайн? Это кривая, имеющая минимум потенциальной энергии. Заметим, что тут никакая параметризация не используется. Под решением задачи понимать кривую, имеющую минимум потенциальной энергии, и проходящую вблизи точек аппроксимации. Под словом "вблизи" можно понимать разнообразные метрики. Также потенциальную энергию можно будет понимать в некотором упрощённом смысле, удобном для вычислений. Типа, интеграл от квадрата кривизны. Возможно в литературе найдёте какие-нибудь альтернативные постановки.

[ewert]

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

[Алексей К.]

Какой второй производной? $\mathbf{r}''_{ss}$?

[ewert]

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

[Алексей К.]

ewert в сообщении #189789 писал(а):

А при минимизации точной энергии изгиба этого не будет

Этот фактик я помню, не помню, чем её приближали.
А, наверняка, так: поскольку значения $t$ тем или иным образом приписаны, то для плоской кривой получаются две одинаковые одномерные задачки с минимизацией ${q''}^2$, где $q$ --- координата.
Далее обсуждалась некая логика приписывания $t$.
мат-ламер, видимо, хочет от этого искусственного $t$ избавиться. Тогда от полиномов отказаться прийдётся.

Интересно будет посмотреть простейшие случаи, например, равномерной расстановки точек по окружности. Задачка сводится к паре соседних точек, нормали на концах, очевидно, --- радиальные векторы. Кривая $y(x)$, никаких $t$ не надо. Ответ, наверное --- дуга окружности при честной минимизации энергии. И некая ближайшая Безьюха при нечестной.

Добавлено спустя 1 минуту 37 секунд:

слегка offtopic, однако...

[ewert]

Алексей К. в сообщении #189798 писал(а):

Ответ, наверное --- дуга окружности при честной минимизации энергии.

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