Интерполяция кривой натурально параметризованными сплайнами

[balodja]

Постановка задачи проста: по заданным точкам $\bar{r}_0, \bar{r}_1, \bar{r}_2 \dots$ ($\bar{r}_i \in \mathbb{R}^n$) построить кривую $\bar{r}(s)$ ($s$ -- длина дуги от начала) с непрерывной второй производной. Первая мысль -- воспользоваться кубическими сплайнами.

Гугление по интернетам показывает, что типичный подход к этой проблеме следующий:

1. строим по точкам $\bar{r}_i$ ломаную $\bar{P}_0$ и определяем её соответсвующие кумулятивные длины $s_{0i}$;
2. конструируем сплайн $\bar{P}_1(s_0)$ по тем же $\bar{r}_i$, используя найденные $s_{0i}$ в качестве параметра;
3. разбиваем весь сплайн $\bar{P}_1(s_0)$ на $m$ равнодлинных отрезков $s_{1i} = \frac {S_1} m i$ и находим соответствующие точки $\tilde{r}_i$ на сплайне $\bar{P}_1(s_0)$;
4. используя найденные точки $\tilde{r}_i$ в качестве новых узлов и длину дуги $s_{1i}$ в качестве параметра, делаем итоговый сплайн $\bar{P}_2(s_1)$.

Этот метод мне лично совсем не нравится по ряду причин, а именно:

• он не относится к "точным" методам, ибо параметром итоговой кривой является длина дуги другой кривой, близкой к итоговой;
• есть дополнительный параметр $m$, который нужно каждый раз выбирать;
• полученный сплайн узлами имеет не исходные точки.

Поэтому хочу оставить этот метод в качестве запасного, а найти другой метод, который:

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

В данный момент застрял на совершенно тривиальной мысли: никакая кривая не может быть параметризована на каком-либо заданном отрезке полиномом степени выше первой. Аргумент (весьма примитивный) состоит в следующем:

Возьмём полином $\bar{r}(s) = \bar{a} s^n + \bar{b} s^{n-1} + \dots + \bar{c}s + \bar{d}. И наложим на него условие того, что $s$ -- длина дуги, а именно $|\frac{d \bar{r}}{d s}| = 1$. Или, что проще, $(\bar{r}'(s), \bar{r}'(s)) = 1$.

Дифференцируем $\bar{r}'(s) = n \bar{a} s^{n-1} + (n-1) \bar{b} s^{n-2} + \dots + \bar{c}$, получаем $(\bar{r}'(s), \bar{r}'(s)) = n^2 (\bar a, \bar a) s^{2n - 2} + \dots + (\bar c, \bar c) = 1$.

Слева стоит полином и справа полином. Поскольку они должны быть равны на отрезке, то у них одинаковые коэффициенты. Следовательно либо $(\bar a, \bar a) = 0, \dots (\bar c, \bar c) = 1$ при $n > 1$, либо $(\bar a, \bar a) = 1$ при $n = 1$. Откуда следует $\bar a = 0$ при любом $n > 1$.

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

Посему прошу уважаемую аудиторию помощи в разрешении этого вопроса. Либо указать мне косяк в рассуждении, либо посоветовать что-нибудь неполиномиальное в качестве базы для построения сплайна. Наиболее круто было бы, конечно, указать сразу на уже готовый алкоритм для построения сплайна.

Заранее спасибо.

[profrotter]

Недавно похожая тема была topic73692.html . С картинками.

А вообще не плохо бы заглянуть в:

1. Методы сплайн-функций. Завьялов Ю.С., Квасов М.И., Мирошниченко В.Л. - М.: Наука. Главная редакция физико-математической литературы, 1980, глава VII.

2. Шикин Е.В., Плис Л.И. Кривые и поверхности на экране компьютера. Руководство по сплайнам для пользователей. - М.: ДИАЛОГ-МИФИ, 1996, глава 3.

[iifat]

balodja в сообщении #741493 писал(а):

Дифференцируем $\bar{r}'(s) = n \bar{a} s^{n-1} + (n-1) \bar{b} s^{n-2} + \dots + \bar{c}$, получаем $(\bar{r}'(s), \bar{r}'(s)) = n^2 (\bar a, \bar a) s^{2n - 2} + \dots + (\bar c, \bar c) = 1$

Вы полагаете $\vec a, \vec b, \dots$ попарно ортогональными. Почему? (Это не наводящий вопрос, поскольку в теме я понимаю слишком мало. Просто интересно)

[balodja]

Не-не-не, я не полагаю их попарно ортогональными, конечно же. Просто не написал в том выражении члены, содержащие $\bar{b}$, например $n(n-1)(\bar{a}, \bar{b}) s^{2 n - 3}$. Они для рассуждения не принципиальны, поскольку важен лишь старший член степени $2 n - 2$.

[balodja]

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

[_Ivana]

А их там никто и не обещал. Было сказано "вообще не плохо бы заглянуть в". А также приведена ссылка на тему, где в подробностях и с картинками приведено то, что вы запрашивали

balodja в сообщении #741493 писал(а):

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

[ewert]

balodja в сообщении #741981 писал(а):

но в обеих книжках нет сплайнов с натуральным параметром.

А зачем они нужны?... Точность, во всяком случае, при любом наобум выбранном способе параметризации будет примерно одинаковой. И натуральная имеет по сравнению с прочими лишь одно достоинство -- что она крайне неудобна.

[balodja]

Листая литературу по сплайнам, обнаружил прекрасную вещь.

Всем известно об "экстремальных свойствах кубических сплайнов". Кубические сплайны являются решением вариационной задачи о минимизации функционала $J(f) = \int \limits _ a ^ b \left| f''(t) \right| ^2 dt$ при условии, что узловые значения $f$ прибиты гвоздями.

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

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

-- 30.06.2013, 23:00 --

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

А зачем они нужны?... Точность, во всяком случае, при любом наобум выбранном способе параметризации будет примерно одинаковой. И натуральная имеет по сравнению с прочими лишь одно достоинство -- что она крайне неудобна.

Секундочку, а какой ещё вид параметризации может быть, если просто задана последовательность точек? Номера этих точек? По-моему, в топике, на который ссылается уважаемый profrotter, убедительно показано, что это глупость.

-- 30.06.2013, 23:08 --

_Ivana в сообщении #741983 писал(а):

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

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

[iifat]

Не просветите слегка? Вроде и про сплайны слегка слышал, но вот в проблему никак не въеду. Возьмём кривую $y=x^3$. Это сплайн? Ну, в смысле — при некоторых граничных условиях может получиться такой сплайн? Посчитаем длину дуги от нулевой точки: $s(x)=\int_0^x\sqrt{1+9x^4}dx=\frac16(3\sqrt{9 x^2+1} x+sinh^{-1}3 x)$ (Вольфрам, конечно). Как понимаю, надо выразить $x, y$ через $s$, нет? Какой уж тут многочлен, понятное дело! И ведь случай-то из простейших...

[profrotter]

balodja в сообщении #741987 писал(а):

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

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

balodja в сообщении #741981 писал(а):

profrotter, спасибо, но в обеих книжках нет сплайнов с натуральным параметром.

Теперь к книжкам. В Шикин Е.В., Плис Л.И. Кривые и поверхности на экране компьютера. Руководство по сплайнам для пользователей. - М.: ДИАЛОГ-МИФИ, 1996, глава 3 написано, что параметризация при которой используются номера точек является простейшим видом параметризации. То есть вполне себе рассматривается и основания, на которых Вы имели неосторожность назвать это глупостью мне непонятны. Посмотрим также на скрин из книжки Методы сплайн-функций. Завьялов Ю.С., Квасов М.И., Мирошниченко В.Л. - М.: Наука. Главная редакция физико-математической литературы, 1980, глава VII, параграф 2, стр 209:

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

[_Ivana]

balodja в сообщении #741987 писал(а):

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

Хорошо, попробую.

balodja в сообщении #741493 писал(а):

Постановка задачи проста: по заданным точкам $\bar{r}_0, \bar{r}_1, \bar{r}_2 \dots$ ($\bar{r}_i \in \mathbb{R}^n$) построить кривую $\bar{r}(s)$ ($s$ -- длина дуги от начала) с непрерывной второй производной. Первая мысль -- воспользоваться кубическими сплайнами.

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

balodja в сообщении #741493 писал(а):

Гугление по интернетам показывает, что типичный подход к этой проблеме следующий:
......
Этот метод мне лично совсем не нравится по ряду причин, а именно:

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

balodja в сообщении #741493 писал(а):

В данный момент застрял на совершенно тривиальной мысли: никакая кривая не может быть параметризована на каком-либо заданном отрезке полиномом степени выше первой.
........
То есть у меня получается, что попытка интерполировать кривые кубическими сплайнами с натуральной параметризацией обречена на провал. Что сомнительно, ибо всякие серьёзные дядьки не гнушаются исследовать эти самые кубические сплайны с натуральной параметризацией.

Не вникал вообще, ибо есть и теоретические и практические примеры существования таких кривых.

balodja в сообщении #741493 писал(а):

Посему прошу уважаемую аудиторию помощи в разрешении этого вопроса. Либо указать мне косяк в рассуждении, либо посоветовать что-нибудь неполиномиальное в качестве базы для построения сплайна. Наиболее круто было бы, конечно, указать сразу на уже готовый алкоритм для построения сплайна.

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

ЗЫ пока набирал, уже ответили.

[balodja]

profrotter в сообщении #742042 писал(а):

Там приведены примеры, когда натуральная параметризация даёт хорошие результаты. Для того, чтобы что-то было показано нужна постановка задачи и соответствующее её решение. При грамотной постановке задачи будут рассматриваться не просто кое-какие кривые, а кривые определённого класса и погрешность их интерполяции или, скажем, величина выбросов. В решении же придётся показать, что натуральная параметризация является оптимальной в смысле минимизации погрешности или величины выбросов. (Примерно так.) Ничего такого мы пока ещё не видели, а посему не будем сотрясать воздух.
Теперь к книжкам. В Шикин Е.В., Плис Л.И. Кривые и поверхности на экране компьютера. Руководство по сплайнам для пользователей. - М.: ДИАЛОГ-МИФИ, 1996, глава 3 написано, что параметризация при которой используются номера точек является простейшим видом параметризации. То есть вполне себе рассматривается и основания, на которых Вы имели неосторожность назвать это глупостью мне непонятны.

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

profrotter в сообщении #742042 писал(а):

Посмотрим также на скрин из книжки Методы сплайн-функций. Завьялов Ю.С., Квасов М.И., Мирошниченко В.Л. - М.: Наука. Главная редакция физико-математической литературы, 1980, глава VII, параграф 2, стр 209. В параграфе 1 также сказано, что параметризация в принципе может быть любой.

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

-- 01.07.2013, 11:37 --

_Ivana в сообщении #742046 писал(а):

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

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

_Ivana в сообщении #742046 писал(а):

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

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

_Ivana в сообщении #742046 писал(а):

Не вникал вообще, ибо есть и теоретические и практические примеры существования таких кривых.

Крайне прошу вникнуть. Если что-то не ясно, постараюсь по мере своих сил пояснить.

_Ivana в сообщении #742046 писал(а):

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

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

_Ivana в сообщении #742046 писал(а):

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

Тут скорее не вопрос, а просьба к аудитории помочь разрешить мою проблему, "помогите решить / разобраться" же. Либо указать на ошибку в моих рассуждениях, если я не прав, либо, если я прав, помочь отыскать сплайноподобные конструкции, которые помогут построить натурально параметризованный сплайн.

-- 01.07.2013, 12:05 --

iifat в сообщении #742018 писал(а):

Возьмём кривую $y=x^3$. Это сплайн? Ну, в смысле — при некоторых граничных условиях может получиться такой сплайн? Посчитаем длину дуги от нулевой точки: $s(x)=\int_0^x\sqrt{1+9x^4}dx=\frac16(3\sqrt{9 x^2+1} x+sinh^{-1}3 x)$ (Вольфрам, конечно).

Ну да, это вполне может быть куском какого-то сплайна. Да и почему "Вольфрам, конечно"? Это достаточно простой интеграл :)

iifat в сообщении #742018 писал(а):

Как понимаю, надо выразить $x, y$ через $s$, нет? Какой уж тут многочлен, понятное дело! И ведь случай-то из простейших...

При переходе от одной параметризации к другой наверняка итоговый вид сплайна будет далеко не самым удобным для аналитики. В исходном посте речь не про переход от одной параметризации к другой, а про прямое построение натурально параметризованного сплайна. То есть при таком подходе ожидается в качестве кусков сплайна увидеть что-нибудь в стиле $\bar r(s) = (3 s^3 - s, s^2, s^3 + 2)$ -- три координаты кривой в зависимости от длины дуги. Конкретно этот пример, не удовлетворяет, конечно же, условию того что $s$ -- длина дуги. Собственно, именно утверждение о том, что не существует таким образом параметризованных кривых, и является важнейшей частью моей проблемы.

[_Ivana]

balodja в сообщении #742066 писал(а):

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

Локальный сплайн, основанный на Лагранжевой интерполяции 3 порядка имеет вторую производную с устранимыми точками разрыва в узлах. Первая производная имеет при этом неустранимые точки разрыва в узлах.

balodja в сообщении #742066 писал(а):

На этот подход я в самом первом сообщении уже ссылался и объяснил, почему именно он мне не нравится и почему ищу другой подход.

Две из трех ваших претензий к "этому подходу" необоснованы, ибо предложенный в теме (а не в вашем первом сообщении) подход от них свободен. Если почитаете описание метода, можете в этом убедиться. Третья же претензия основана на

balodja в сообщении #742066 писал(а):

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

Имхо, это может быть с любой желаемой точностью "совсем она", как и значение иррационального числа. Значит, получается, что это "совсем она".

[balodja]

_Ivana в сообщении #742119 писал(а):

Локальный сплайн, основанный на Лагранжевой интерполяции 3 порядка имеет вторую производную с устранимыми точками разрыва в узлах. Первая производная имеет при этом неустранимые точки разрыва в узлах.

И тут выскакивает кроликом из шапки устранимость производных. Это не непрерывная вторая производная. Таких и без полиномов Лагранжа можно напридумывать.

_Ivana в сообщении #742119 писал(а):

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

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

_Ivana в сообщении #742119 писал(а):

Имхо, это может быть с любой желаемой точностью "совсем она", как и значение иррационального числа. Значит, получается, что это "совсем она".

В одной из работ, на которую я ссылаюсь в первом сообщении, как раз разбиением кривой на $m$ равнодлинных кусков и взятием их в качестве новых узлов пытаются максимально приблизить параметризацию к натуральной. Меня не интересует "она с желаемой точностью", такие методы уже есть и в достатке, интересует "точно она".

-- 01.07.2013, 17:43 --

_Ivana в сообщении #742119 писал(а):

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

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

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

Таким образом, надеюсь, я смогу Вас убедить, что не игнорирую сообщений других участников. Тащемта тот тред я читал ещё до того, как начать эту тему.

[_Ivana]

Хорошо, уговорили - вам надо все: и шашечки и ехать без дополнительных узлов, и единственный параметрический полином третьей степени между узлами, и непрерывные производные, и натуральная параметризация во всех точках по всей длине кривой, и чтоб все это точно, а не в каком-то приближении, и все это можно без хлеба... И вы предполагаете, что такое сочетание невозможно. Чтож, вполне вероятно. Возьму таймаут на подумать, но без гарантии выдачи каких-либо конструктивных методов построения такого счастья...