Помогите разобраться со сплайном и его кривизной

[rockclimber]

Предыстория.
У меня давно была идея попробовать написать одну игру, имеющую отношение к гонкам. Сейчас в очередной раз решил попробовать.
Задача такая: гоночный автомобиль едет по некой траектории, которая задается сплайном (*). Каждой точке сплайна соответствует некоторая величина кривизны траектории. Кривизна участка траектории ограничивает скорость, с которой автомобиль может двигаться по этому участку. Для того, чтобы автомобиль проехал трассу с максимальной скоростью, я придумал примерно такой алгоритм (*):
- рассчитать максимальную скорость для каждого участка траектории
- затем для каждого участка рассчитать максимальную скорость с учетом того, что возможное торможение автомобиля ограничено техническими параметрами автомобиля, поэтому тормозить надо начинать заранее (и рассчитать, когда именно)
- затем рассчитать фактическую скорость каждого участка с учетом мощности двигателя

Теперь к сути вопроса. Для задания траектории я выбрал сплайн Акимы (где-то попалась статья со сравнением разных типов сплайнов, этот показался самым привлекательным). Код (он у меня на java) не привожу, во-первых, потому что его много, и вряд ли кто-то захочет в нем разбираться, а во-вторых, мне кажется, что проблема в математической части решения. Но если кто-то захочет - могу выложить. Дальше порядок такой:
- задаю опорные точки
- массив опорных точек с координатами $(x_i, y_i)$ преобразую в два массива $(t_i, x_i)$ и $(t_i, y_i)$, где $t_0 = 0$, $t_i$ равно расстоянию от точки $i-1$ до $i$
- для каждого участка дуги рассчитываю коэффициенты функций $x(t)$ и $y(t)$
- затем сплайн (для упрощения расчетов вывода на экран) аппроксимируется ломаной линией: для каждой дуги я беру параметр $t$, изменяю его от $t_i$ до $t_{i+1}$ c шагом $(t_{i+1} - t_i)/n$, где $n$ - некоторое произвольное число (10, 20 или 30 обычно). Для каждого такого значения $t_j$ вычисляю $x_j$ и $y_j$, по получившимся точкам $(x_j, y_j)$ строится ломаная. Выглядит она как-то так:



(Цветом показана кривизна, чем краснее цвет, тем меньше радиус кривизны)
- далее беру уравнение эволюты (взял в Википедии):
$X = x-y' \dfrac{x'^2 + y'^2}{x'y'' - y'x''}$
$Y = y+x' \dfrac{x'^2 + y'^2}{x'y'' - y'x''}$
По этим уравнениям для каждой точки $t_j$ рассчитываю координаты соответствующей точки эволюты. Вообще я считал, что если взять некоторое значение параметра $t$ и найти координаты соответствующей точки сплайна ($A_t$), затем по формуле выше рассчитать координаты точки эволюты ($A_e$) при том же значении $t$, то найденная точка $A_e$ будет центром касательной окружности, а точкой касания будет $A_t$. Но сейчас подумал, что у меня нет оснований так считать. Правильное ли это предположение?
- далее для каждой пары точек (точка сплайна + точка эволюты) я рассчитываю расстояние между ними, беру (пока с потолка) некоторое значение предельной силы трения и рассчитываю максимальную скорость в данной точке. Но дальше возникает проблема. На рисунке выше представлен кусок сплайна. Вот так для него выглядит распределение максимальной скорости вдоль траектории:



По оси абсцисс отложен номер промежуточной точки. Участок кривой между двумя опорными точками делится на 30 частей, соответственно каждая 30-я точка на графике соответствует опорной точке, все остальные точки - промежуточные. Тут видно два пика в районе второй и четвертой опорных точек - то есть в этих местах происходит небольшой излом. Для расчета оптимальной скорости автомобиля надо убрать по возможности такие скачки скорости. Буду рад любым советам...

(Наверное, может возникнуть вопрос, а с чего я вообще решил, что построенная таким образом кривая будет удовлетворять моим требованиям? Да, собственно, ни с чего. Просто не задумывался над этим. Я так понимаю, придется все сначала переделывать с другим типом сплайнов.)
_________
Знаком (*) обозначены вопросы, которые формально являются оффтопиком, но их тоже можно обсудить.

(P. S.)

На случай, если кому-то вдруг покажется, что что-то подобное я спрашивал ранее. Да, спрашивал: «Построение кривых линий по заданным точкам».

[Dmitriy40]

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

-- 11.06.2016, 23:58 --

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

[rockclimber]

Dmitriy40 в сообщении #1130920 писал(а):

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

Так я про это и говорю. Вот как-то построил, взяв метод построения с потолка, и получилась ерунда. А как правильно - не знаю.

Dmitriy40 в сообщении #1130920 писал(а):

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

Ну, логика была такая: эволюта - это множество центров кривизны. Берем точку кривой и центр окружности, высчитываем радиус. А как он "уже заложен в сплайне"? Я что-то не понимаю. У меня еще была идея просто по каждым трем последовательным точкам искать радиус описанной окружности, но если проблема именно в сплайне, это тоже не поможет.

[Dmitriy40]

Может я что-то недопонял? Ведь сплайн - это некоторая кривая $y(x)$, заданная аналитическим выражением, коэффициенты в котором и подбираются (вычисляются) по опорным точкам. А для любой аналитической функции (ну за малым исключением) определён радиус кривизны в точке, $r=\dfrac{\sqrt{1+y'^2}}{\left\lvert y''\right\rvert}$ (в параметрической форме сложнее, но тоже есть, хоть в вики). Взять обе производные для сплайнов вроде бы можно аналитически (на бумажке), потом в программе просто подставляете свои коэффициенты в готовую формулу и получаете радиусы кривизны в любых точках.
Чтобы получить равенство кривизны на краях сплайнов достаточно потребовать равенства первых и вторых производных там же.
И главное это всё не слишком зависит от выбора типа конкретного сплайна - можно потренироваться хоть на параболах, а потом сменить на Акимы.

[svv]

Имеет смысл сразу получить выражение для кривизны, хоть из уравнения эволюты, хоть найти готовое:
$k=\dfrac{x'y''-y'x''}{(x'^2+y'^2)^{\frac{3}{2}}}$
Кривизна положительная — автомобиль поворачивает влево, минус — вправо.

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

[amon]

rockclimber в сообщении #1130917 писал(а):

я выбрал сплайн Акимы

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

[svv]

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

[iifat]

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

-- 12.06.2016, 11:35 --

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

[Dmitriy40]

(Ошибся в формуле)

При наборе формулы радиуса кривизны забыл добавить возведение корня в числителе в куб.

-- 12.06.2016, 05:26 --

Без сплайнов никак, ведь нет кривой через опорные токи, как считать радиус кривизны? Через окружности по трём точкам не пойдёт. Потому и надо сплайнами (не менее чем кубическими для стыковки с прямыми участками и непрерывности второй производной) получить ход кривой через опорные точки, причём на краях сплайнов и первые и вторые производные должны быть равны (для равенства кривизны), получить кривизну вдоль всей кривой $k(t)$ (она будет непрерывной), по ней допустимую скорость $v(t)$, а уже потом её сгладить с учётом ограничений величин ускорений и торможений до $v_m(t)$. Наверное можно ограничения на ускорения/торможения преобразовать в ограничения на производные для сплайна, но тогда и траектория получится другой, черезчур сглаженной.

[iifat]

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

[amon]

svv в сообщении #1130946 писал(а):

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

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

[Dmitriy40]

amon в сообщении #1130988 писал(а):

у сплайна Акимы вторая производная разрывна

Хм, получается эти разрывы и видим? И от них не избавиться без смены сплайна на другой? Какая засада.

[ewert]

Dmitriy40 в сообщении #1130993 писал(а):

И от них не избавиться без смены сплайна на другой?

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

[Dmitriy40]

Даже поднятием степени полинома? Ведь тогда можно наложить дополнительные условия - потребовать непрерывность второй производной (или сразу кривизны если это не эквивалентно ). Или даже третьей чтобы исключить изломы второй.

(Почему достаточно кубического сплайна)

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

[ewert]

Dmitriy40 в сообщении #1131009 писал(а):

Даже поднятием степени полинома?

Поднятием степени -- естественно, можно.

Dmitriy40 в сообщении #1131009 писал(а):

Просто вспоминаю про использование в железнодорожном транспорте именно кубических кривых

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