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

[Dmitriy40]

ewert, спасибо, стало понятнее.

[arseniiv]

А чем плохи сплайны из кривых Корню? Интегральными синусами-косинусами?

[rockclimber]

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

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

А, вот в чем проблема, я сразу не сказал. У меня нет совершенно никаких систематических познаний в той части математики, которая "заведует" сплайнами. Я знаю только общие понятия - что такое функция, производная и т. п., а дальше занимаюсь чистым велосипедостроительством, благо при наличии гугла это не очень сложно. Когда-то услышал про эволюту, и решил использовать ее здесь. То, что существует аналитическое выражение для вычисления радиуса кривизны, я тоже не знал. Хотя если бы догадался поискать, то нашел бы, и эволюта действительно была бы не нужна.

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

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

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

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

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

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

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

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

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

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

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

Понятно, спасибо. А что например?

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

Сплайн с дефектом 1, т.е. с непрерывной второй производной, грубо говоря, единственен. Т.е. он единственен с точностью до задания двух дополнительных граничных условий.

А можно чуть подробнее осветить этот вопрос? Или подскажите литературу, что почитать в качестве простого введения в тему сплайнов.

[iifat]

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

У меня нет совершенно никаких систематических познаний в той части математики, которая "заведует" сплайнами

Не самое ли время таки их приобрести? Либо выбрать другой инструмент...

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

Я не до конца понял ваш вопрос

Взаимно: я не до конца понял ваш ответ

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

Сейчас проблема в том, что я хочу сделать некое подобие ИИ, который будет управлять машиной

Это не проблема. Это задача.

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

По имеющейся информации о траектории он должен решать, когда разгоняться, когда тормозить

По информации о траектории — и прочей информации! Иначе вообще не потребовалось бы тормозить!

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

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

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

[amon]

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

А что например?

Это зависит от того, как у Вас задача поставлена. В любом случае узловые точки в наших руках, и их можно попытаться расставить так, чтобы минимизировать патологию сплайновой интерполяции. То, что мне (дилетанту в этой области) приходит в голову:
1. Прописать заведомо избыточное число узлов
2. Сгладить кривую сплайном нужного порядка (третьего, для простоты)
3. Выбрать новые узлы так, что бы они лежали как можно ближе к полученной кривой
4. Проинтерполировать по полученным узлам кривую кубическими сплайнами с сшиванием двух производных
Подозреваю, что не любую трассу можно так проинтерполировать.

[svv]

rockclimber
Посмотрите в книге Гарднера «Математические новеллы» в главе 33 описание игры «Гонки» (страница 402). Там полторы странички, не считая картинки. Вам, наверное, понравится, и могут прийти какие-то идеи.

[ewert]

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

А можно чуть подробнее осветить этот вопрос?

Каждый кусочек кубического сплайна (т.е. для каждого отрезка) определяется четырьмя параметрами. Раз уж он кубический.

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

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

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

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

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

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

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

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

Ну, есть известная такая книжка: К. де Бор, "Практическое руководство по сплайнам", если не ошибаюсь. В своё время именно она привлекла меня к этой тематике. Но прочитать её я не смог -- слишком уж безобразно она отформатирована.

Или есть ещё Богачёв, "Практикум на ЭВМ. Методы приближения функций". Её я не смог прочитать по другой причине -- только сегодня на неё наткнулся. Но изложение навскидку выглядит вполне разумным. В частности, алгоритм Акимы там изложен, причём достаточно лаконично (страницы две-три) и, если судить по первым фразам изложения -- грамотно.

[rockclimber]

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

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

Алгоритм есть. Выглядит вкратце так:
1. Разбиваем траекторию на отрезки (так проще считать), например, по 10 - 20 промежуточных точек между опорными точками.
2. Для каждой точки считаем максимальную мгновенную скорость, с которой можно находиться в этой точке и не улететь в занос.
3. У нас фактически есть на руках функция зависимости радиуса кривизны от позиции на трассе. Находим точки - локальные минимумы. Каждая такая точка - это точка, в которой скорость будет минимальной. Соответственно, до этой точки надо тормозить, в этой точке тормозить уже не нужно, а дальше можно разгоняться.
4. От каждой такой точки двигаемся назад. Например, точка с номером $N$ является локальным минимумом. Используя значение максимально возможного ускорения торможения, считаем, какую максимальную скорость можно иметь в точке $N - 1$, чтобы успеть затормозить до скорости $v_N$ к моменту достижения точки $N$. Сравниваем эту скорость и скорость, полученную на шаге 2. Берем меньшую из них. Переходим к расчету скорости в точке $N - 2$.
5. В процессе гонки все просто: скорость меньше допустимой - разгоняемся, больше - тормозим больше быть не должно, потому что если больше - то уже 100% вылетишь с трассы.

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

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

То, что мне (дилетанту в этой области) приходит в голову:
1. Прописать заведомо избыточное число узлов
2. Сгладить кривую сплайном нужного порядка (третьего, для простоты)
3. Выбрать новые узлы так, что бы они лежали как можно ближе к полученной кривой
4. Проинтерполировать по полученным узлам кривую кубическими сплайнами с сшиванием двух производных

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

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

Посмотрите в книге Гарднера «Математические новеллы» в главе 33 описание игры «Гонки» (страница 402). Там полторы странички, не считая картинки. Вам, наверное, понравится, и могут прийти какие-то идеи.

Да, такую игру я знаю (хотя и слышал в варианте с более слабыми правилами). У меня концептуально то же самое, только чуть усложнено.

ewert
Спасибо! Пойду читать.

[iifat]

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

Алгоритм есть

Прекрасно. Вот и представьте себе: построил некий редкостный чудак трассу с разрывом радиуса кривизны. Сначала большой, потом маленький. Ваш алгоритм предписывает тормозить на прямом участке, проходя его медленнее, чем допускают прочие условия — и это совершенно правильно! Иначе автомобиль вылетит на крутом повороте.
Теперь представим себе практически такую же трассу, но без разрыва. Большой радиус кривизны переходит в малый не мгновенно, но очень резко. Что это изменит? Ничего.
Как по мне, проблема, скорее — радиусы кривизны. Известно, что погрешность функции при интерполяции — это одно, а вот погрешность первой, паче того второй производной — это совсем другое...

[iifat]

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

Находим точки - локальные минимумы

Кстати, подозрительно мне вот это место. Каждая точка накладывает ограничения на предыдущую скорость, и, смутно подозреваю, минимумами тут не ограничитесь.

[Dmitriy40]

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

минимумами тут не ограничитесь.

Да, не обойтись. Будет много лишней работы, а некоторые "горбы" скорости можно и пропустить, если они попадут целиком на интервал между расчётными точками.

Надо искать не минимумы $v(t)$, а $\begin{cases} v'(t)=-\lvert a_\text{торможения} \rvert \\ v''(t)>0 \end{cases}$ (в этих точках скорость дальше меньше максимально допустимой) и восстанавливать максимально допустимую скорость назад с наклоном $-\lvert a_\text{торможения} \rvert$ до пересечения с исходной $v(t)$. Грубо говоря срезать прямой максимального торможения слишком выпуклые горбы на спадах $v(t)$ с выравниванием на конечную точку.

Кстати, имея сплайны, можно задачу поиска таких точек решить заранее аналитически, первая и вторая производные кубического сплайна тривиальны.
Вот аналитически в одно действие найти точку начала срезания горба проблематично - она может попасть (и обязательно попадёт!) на другой кусок сплайна, с другими коэффициентами. Думаю проще итерационно идти назад по кусочкам вычисляя или точку начала срезания горба, или условия (фактически лишь одно число $v(t)-v_{max}(t)$) на границе кусочка (для продолжения поиска назад). Как только эта невязка станет отрицательной - искомая точка пересечения лежит внутри кусочка (или точно на границе если равно нулю). Проход по кусочкам тоже несложен: если $v_{max}(t_2)$ - максимальная скорость на правом конце, то максимальная скорость на левом конце будет всего лишь $v_{max}(t_1)=v_{max}(t_2)+ \lvert a_\text{торможения} \rvert \cdot (t_2-t_1)$.

PS. Ускорение везде под модулем на всякий случай, чтобы не возникало путаницы со знаком ускорения при торможении. При аккуратности определений модуль не нужен, но знаки могут и поменяться.
PPS. $t$ выше - это не время, это лишь аргумент функции вдоль траектории (например длина от начала).

[iifat]

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

срезать прямой максимального торможения слишком выпуклые горбы

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

[Dmitriy40]

iifat
Очень возможно повторяю. Тут вопрос к автору, он про полное ускорение пока не упоминал.

-- 13.06.2016, 18:38 --

Ну тогда вместо константы $a_\text{торможения}$ берём функцию $a_\text{т}(t)$ (с учётом полного ускорения), она однозначно определена сплайном и коэффициентом трения. В системе уравнений для нахождения точки конца ограничения всё остальное остаётся в силе. А назад ищём снова точку $a_\text{т}(t)=v'(t)$ (что тоже можно аналитически) - это и будет точкой начала ограничения.

[Утундрий]

Не хотите трассу задать в виде полосы, как она и задаётся в природе?

[rockclimber]

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