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

[_Ivana]

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

[balodja]

_Ivana, да-да-да. В одном извращённом алкоритме так делалось. После построения кривой-сплайна с параметром в виде кумулятивной длины ломаной строился ещё один одномерный сплайн для связывания длины ломаной и длины построенной кривой-сплайна. Ехал сплайн через сплайн, короче :)

[Алексей К.]

[off=". ." ]

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

Изначальная идея сплайна --- в заданные точки забили гвоздики...

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

при условии, что узловые значения $f$ прибиты гвоздями.

[/off]

[iifat]

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

[Алексей К.]

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

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

Почему-то мне кажется, что это не "сомнительно", а естественно. Вы полагате, что существуют полиномы $x(s),y(s)$ степени выше первой, такие, что ${x'}_s^2+{y'}_s^2\equiv 1\,?$ Вы же сами доказали (или почти доказали) обратное! Вроде доказано, что и рациональных таких функций нет. Известная древняя статья об этом присутствует в списке литературы из Вашей ссылки в первом сообщении:

Цитата:

Real rational curves are not ’unit speed’. Computer Aided Geometric Design - Farouki, Sakkalis - 1991

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

-- 02 июл 2013, 01:44:12 --

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

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

Присоединяюсь к вопросу.
Клотоидальные сплайны (из кусков спиралей Корню) когда-то обсуждались в журналах типа CAGD и CAD (Comp.-Aided [Geom.] Design). И даже на этом форуме. Они, должно быть, разрывны по кривизне, но удовлетворяют требованию натуральной параметризации. Или их можно сделать таковыми. Но (мне) трудно придумать ситуацию, где такой геморрой был бы оправдан.

[balodja]

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

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

Ну, пока весь тред -- это лишь обсуждение постановки проблемы, а не попытки её решить.

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

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

Да, похоже, что да.

-- 02.07.2013, 08:01 --

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

Вроде доказано, что и рациональных таких функций нет.

Да-да-да, это доказывается чуть-чуть посложнее. Но я решил не усложнять доказательство ради охвата рациональных функций.

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

Известная древняя статья об этом присутствует в списке литературы из Вашей ссылки в первом сообщении:

Цитата:

Real rational curves are not ’unit speed’. Computer Aided Geometric Design - Farouki, Sakkalis - 1991

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

Вы совершенно правильно всё поняли. Честно говоря, не заметил ссылки на эту статью.

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

Клотоидальные сплайны (из кусков спиралей Корню) когда-то обсуждались в журналах типа CAGD и CAD (Comp.-Aided [Geom.] Design). И даже на этом форуме. Они, должно быть, разрывны по кривизне, но удовлетворяют требованию натуральной параметризации. Или их можно сделать таковыми. Но (мне) трудно придумать ситуацию, где такой геморрой был бы оправдан.

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

[Алексей К.]

С чисто болтологической точки зрения оно мне представляется так.
Вот если так уж приспичил натурализм, так выбирать модель надо не для $x(s), y(s)$, а для $k(s)$ (кривизны) или её первого интеграла, $\tau(s)$, угла наклона касательной. Типа имеем $n$ отрезков, т.е. $n+1$ узлов, из которых $n-1$ --- внутренние, в которых надо что-то там сшивать. Берём модель

$$\tau_i(s)=a_i+b_is+c_is^2, \quad 0\le s\le s_i,\quad i=1,\ldots, n$$

(или, может что-то похитрее, чтобы $\cos[\sin]\tau(s)$ легко интегрировалось). Имеем $3n+n$ неизвестных, если включить туда длины $s_i$; надо будет --- возьмём их какими-то фиксированными.
Щитаем уравнения и неизвестные. Типа гладкость: $\tau_i(s_i)=\tau_{i+1}(0)=a_{i+1}$, $n-1$ уравнений. Непрерывность кривизны ${}\to{}$ аналогичные уравнения для $\tau'(s)$. Далее, условия

$$\int\limits_{s_i}^{s_{i+1}}\cos\tau_i(s)=x_{i+1}-x_i$$

дают $n$ уравнений; и так же для $\Delta y_i$. Нарисовалось $4n-2$ уравнений. Тогда углы наклона касательных в концевых точках зафиксируем. Ну и решаем...

Я вот даже задумался: а если бы мне за переход от болтологии к чему-то численно-практическому пообещали домик на берегу реки Вазуза, на участке между Хлепенем и водохранилищем (и, естественно, моторную лодку впридачу) --- взялся бы я за такую задачку? Не уверен.

[Алексей К.]

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

(или, может что-то похитрее, чтобы $\cos[\sin]\tau(s)$ легко интегрировалось)

Например, легко интегрируются штучки вроде

$$ \int{}{}{\cos{% \left(\sqrt[3\,]{ \frac{\sqrt{a^2{+}s^2}+{s}}{a}} {\,}-\sqrt[3\,]{ \frac{\sqrt{a^2{+}s^2}-{s}}{a}}\,\right)} }\,\mathrm{d}s. $$

И синус, естессно, тоже.

[balodja]

Вот, сейчас смотрю на варианты в стиле $\tau(s) = 2 \arctan (a s) + 2\arctan (b s) = 2 \arctan \cfrac {a s + b s} {1 - a b s^2}$, то есть

$$ \int \cos \tau (s) ds = \int \cos \left(2 \arctan \cfrac {a s + b s} {1 - a b s^2}\right) d s = \int \cfrac {(1 - a b s^2)^2 - (a s + b s)^2} {(1 - a b s^2)^2 + (a s + b s)^2} d s =$$

,

$$ = \int \left( 1 - \cfrac {2 (a + b)^2 s^2} {(1 + a^2 s^2) (1 + b^2 s^2)} \right) d s$$

. Что тоже весьма интегрируемо.

[Алексей К.]

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

Вот, сейчас смотрю на варианты в стиле $\tau(s) = 2 \arctg (a s) + 2\arctg (b s) {\color{magenta}{}+ c}$

(искажение цитаты --- моё. //A.K.)
Мне сходу кажется, что константу нельзя игнорировать.
Не только потому что третий свободный параметр вроде просто нужен, но и вообще.

-- 02 июл 2013, 15:26:59 --

Ой, немного ерунду написал, но не много. Она интегрированиям не мешает и не усложняет дело. Чисто поворот. На этом этапе можно и проигнорировать.

[balodja]

После интегрирования (без константы) у меня в итоге получилось:

$$ X(s) = \int \cos (\tau(s)) d s = s + \cfrac {a + b} {a (a - b)} 2 \arctg (a s) + \cfrac {a + b} {b (b - a)} 2 \arctg (b s) + C_1$$

$$ Y(s) = \int \sin (\tau(s)) d s = \cfrac {a + b} {a (a - b)} \ln (1 + a^2 s^2) + \cfrac {a + b} {b (b - a)} \ln (1 + b^2 s^2) + C_2 $$

Если повезёт, с этим даже что-то конструктивное можно сделать. Насчёт константы сейчас пораздумываю.

-- 02.07.2013, 14:36 --

Теперь неплохо бы проверить, что $ X'^2(s) + Y'^2(s) = 1$. Как бы это покороче сделать? :)

[Алексей К.]

Это излишне. Достаточно проверить правильность интегрирования (дифференцированием, например).
Основное тригонометрическое тождество проверять как-то не принято.
Если только втихаря, чтоб никто не видел.

-- 02 июл 2013, 16:13:44 --

Лучше вспомните разность квадратов двух чисел и поупрощайте вышенаписанное.
Кнопка Правка ещё минут 14 будет активна.

-- 02 июл 2013, 16:21:19 --

Двойки в X(s) не перед арктангенсом, а перед дробью должны быть.

[balodja]

Шикарно, теперь уже что-то начинает прослеживаться. Например, похоже, что $X(s)$ задаёт касательную, а арктангенсы с логарифмами друг в друга как-то перетекают при повороте. Не будет ли это всё в комплексных обозначениях выглядеть проще?

-- 02.07.2013, 15:24 --

Ну, я таким образом решил выделить то, что арктангенсы списаны с $\tau(s)$ подчистую.

[Алексей К.]

Должно быть проще. Интегрируем ведь $\exp(\mathrm{i}\tau(s))$. А там у них, в ТФКП, арктангенсы с такими логарифмами вроде как братья.

[balodja]

Да-да-да, именно так. Один -- это другой от мнимого аргумента.