Russian Qt Forum

Добрый день

Есть N точек на пути, для каждой известно пройденное (от начала пути) расстояние. Также известно

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

Требуется: для всех точек рассчитать время и скорость (т.е. то что дано для первой и последней)

Спасибо

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

Нет, в общем случае нельзя.
У этой задачи существует бесконечное число решений, однако, также существует универсальный алгорит решения (одного из множества решений).

Рассмотрим простейший частный случай, когда мы задаём скорость как квадратичную функцию времени (см. fig1). Такая функция имеет три пераметра: a, b, c.
Для их определения нам нужно три уравнения. Первые два - очевидны: они задают начальную и конечную скорости в начале и конце пути (см. fig2).
Третье уравнение согласует среднюю скорость на всём пути (см. fig2).
Из этих трёх уравнений мы вытаскиваем три неизвестных константы a,b,c.

Теперь легко получить значения соответствующих скоростей и времён в каждой точке на пути (см. fig3).   

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

v0, v1 - скорости в начальной и конечной точках
S - длина всего пути
T - время прохождения всего пути

Нужно вывести такое уравнение(я) что подставляя в него s(i) - длина пути i-й точки, получить v(i) и t(I) - время и скорость i-й точки. Ну ясно что свести дело к равноускоренному движению не удастся (к равномерному тем более). Поэтому моей фантазии хватило лишь на утверждение "Пусть скорость меняется квадратично"  :)

v(t) = a * t * t + b * t + v0;

Мы знаем что v(T) = v1, отсюда ур-е 1
Путь - интеграл от скорости,

s(t) = a / 3 * t * t * t + b / 2 * t * t + v0 * t
 
Мы знаем что s(T) = S, отсюда ур-е 2
В итоге имеем сопливую СЛАУ 2x2. решая ее находим a и b

Теперь сам расчет.

1) Решаем кубическое ур-е s(i) - путь i-й точки. находим t
s(i) = a / 3 * t * t * t + b / 2 * t * t + v0 * t

2) Подставляя найденное t в ур-е скорости находим скорость i-й точки
v(i) = a * t * t + b * t + v0;

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

Спасибо

Чего там тижаловатого в трёх картинках со школьными выкладками?


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

Задача для теслы, только электродвигатель/реактивный двигатель способен выдавать примерно одинаковое максимальное ускорение на любой посильной ему скорости.
потом может получиться вначале скорость 60-120-240-300(что не совсем реально для автомобиля). вместо того чтоб всю дорогу 120 ехать, а в крайних точках резко разогнаться.

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

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

Конечно учитывается. Учитывается и скорость в начальной, конечной да и ещё средняя скорость полностью согласована)

Нет, ничего подобного. Вот квадратичная функция в общем случае: v(t) = v0 + a*t + b*t*t.
v0 - скорость в начальный момент времени (t=0). Остаётся ещё два параметра. Для их определения нужно два уравнения. Одно из них как раз определяет скорость в конечный момент времени
t = T: v2 = v0 + a*T + b*T*T. Второе уравнение определяет среднюю скорость: S/T = v0 + (a/2)*T + (b/3)*T*T
В итоге у нас СЛАУ 2x2:

v2 = v0 + a*T + b*T*T,
S/T = v0 + (a/2)*T + (b/3)*T*T.

из которых мы однозначно найдём a и b.  

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

Мне кажется интуитивнее домножить обе части на T и мы получим ур-е пути. А так неясно почему средняя должна быть такой. Ну это не принципиально

В общем случае нет, не даст расстояние (в точках). Если a = 0 то получится равноускоренное движение. А если и b = 0 то выйдет движение с постоянной скоростью.

Ну вообще-то парабола задается 3 точками, а здесь только 2 (начальная и конечная). Не пойму каким образом я (неявно) задал третью?  :)

Хорошо, а как удобно (гибко) варьировать "форму" графика скоростей? Напр при v0 = v1 = 0.0 он выглядит как школьная парабола
у = -x^2
Как сместить максимум влево/вправо по желанию юзверя (пусть примитивно но с минимумом опций и не влезая в обильную математику)?

Спасибо

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

интеграл от скорости даст путь.

Ну и возвращаясь к задаче, при отрицательных скоростях ему придестя заехать за старт/финиш. При слишком большой начальной скорости ему придется уехать за финиш, вернуться уехав за старт, и потом финишировать.

Ну и сам алгоритм(допустим мы едем в тесла), есть начальная скорость и начальное нахатие на педаль ускорения, в течении всего времени педаль равномерно движеться.
Вобщем есть много краевых моментов и не факт что алгоритм оптимальный. Смотря какие дополнительные условия? можно ли пересекать старт/финиш, ограничения на скорость/ускорение...

Это принципиально! Это условие фактически фиксирует третью точку. Поскольку с одной стороны суммарный путь по условию это S, а с другой стороны - это интеграл от скорости от начального момента времени до конечного!

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

Хотите дать юзеру свободу вырьировать параметры: апроксимируйте скорость полиномом выше второй степени. Например, для кубической функции и юзера появится один свободный параметр.


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

Как его "дать"? Какие ручки / контролы? Рассказывать ему о полиномах (любой степени) бесполезно. Нужно примитивное упр-е, типа:

- если значение = 1, то как сейчас
- если < 1, то скорости нараствют/убывают  сначала быстро, потом медленно
- если > 1, то наоборот

И о себе подумать. На ур-е 4-й степени либа еще найдется, а дальше что?

------------------------

Ну вот, только подумал "на этот раз удачно проскочил" - и на тебе  :'( Хирак - выдает 3 корня.
И шо делать ???? (паника)

Юзер вообще не будет знать о ваших полиномах и т.д.. Вы ему дадите N-ное колличество "бубочек", которые он может крутить-вертеть. Число "бубочек" определяет число свободных параметров. Число свободных параметров N задаётся условием: N = n-2, где n - степень полинома (n >= 2).


Если на пути нет точек останова (т.е. точек, где скорость меняет направление) то корень на интервале t [0, T] будет только один.

Уже сообразил (да, путь неубывающий), но все равно спасибо,

Насчет бубочек - давайте через денек-другой, а то сейчас обсуждение слишком бурное (а значит быстро выдохнется) :)

Я извиняюсь, но вот "квадратичность" зависимости скорости от времени - это 100% заданное начальное условие или просто взято как иллюстрация (а движение может быть неравномерным)?

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

Вот для меня как для не-специалиста ни в полиномах и их степенях, ни в физике вообще, есть (не)много непонятно, как же собственно произошел переход от интеграла от t1 до t2 (я так понимаю, "путь" там строится из кусочков) в выражения на рис.2 ?

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

Да и загадкой остается, откуда же функция то на свет явилась, если ее нет в начальных условиях? То есть какая задача в итоге решается? Исходная или мнимая?

Строго говоря - мнимая :) Пожуем простой пример: известны расстояния (от начала пути) которые проходит объект (их менять нельзя)

s = { 0, 10, 40, 100 };  // 4 точки, длина пути 100

Теперь юзверь говорит: хочу чтобы весь путь был пройден напр за 10 сек, начальная скорость ноль, конечная напр 50. Рассчитайте время и скорости в двух средних точках (в первой и последней они заданы)

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

v = v0 + a * t;     // v = 50, v0 = 0, t = 10, отсюда ускорение  a = 5
S = a * t * t / 2;  // S = 100, t = 10, отсюда ускорение  a = 2

Т.е. скорости первых 3 точек мы-то выстроим по прямой, но до последней или не дотянемся или она вообще окажется сзади.

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

v = a * t * t + b * t + v0;

Где a - второе ускорение, b - первое. Ну и дальше песня как эти коэффициенты найти

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

Да, и я наконец понял с "третьей точкой". Надо сформулировать так

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

Поэтому 3-я точка здесь наоборот, НЕ нужна

Макс прав, решений тут может быть бесконечное множество, но имхо тут уже пошел отход от сути в дебри матанов :)
А почему бы не разбить задачу на конечные отрезки (например, на 2 - от 0 до 40 и от 40 до 100), и выполнять расчет ускорений отдельно? Получим 2 решения, но ведь в условии и не сказано, насколько "гладким" должно быть движение?

В смысле легко или сложно?

скорость и координаты от времени:
v(t) = a * t * t + b * t + v0
x(t) = a * t^3 / 3 + b * t^2 / 2 + v0 * t

b =( v2 - a*t² - v0 ) / t
S/t = a*t² / 3 + b * t / 2 + v0 * t
S/t = a*t² / 3 + ( v2 - a*t² - v0 ) / t * t / 2 + v0 * t
S/t = a*t² / 3 + ( v2 - a*t² - v0 ) / 2 + v0 * t
S/t = - a*t² / 6 + v2/2 -v0/2 + v0 * t
a = ( -S / t + v2 / 2 - v0 / 2 + v0 * t ) * 6 / t²

p.s. Вообще если брать более практичный вариант, мне кажется машина должна ехать с учетом ограничений скорости и множеством других ограничений... График ускорения будет разрывная функция - точнее множество разных функций на разных участках, длинна которых будет определяться начальными условиями.

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

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

Конечно прав, но никто и не утверждал обратное :) И то не дебри еще, а так, "3 сосны"

Ну получим ту же задачу только с меньшим числом точек. А если речь о подстройке 2-3 точек - то есть редактор где можно это делать интерактивно.

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

Update: прочитал свой же пост выше и подумал - а что тут военного? Ну возьмем третье ускорение, вот у него коэффициент свободен и может задаваться юзером. СЛАУ остается 2х2. Вот только как этот коэффициент втихаря подстроить (от юзеровского ввода) чтобы график не "вилял"?

А откуда такая привязка конкретно к случаю движения машины? Может igors решает проблему полёта пьяного Карлсона? :) Кто его знает, что у него в голове)

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

Есть 3D объект, настройка траектории его движения (в пр-ве) - своя песня (сплайны и все такое). Термин "velocity" (control) означает упр-е скоростью НЕ меняя траектории. А насколько пьян Карлсон - решает юзер, мое дело дать ему тулзы.

Вот не надо умничать, вещь пусть не очень популярная, но совсем не редкая.

Что имеете сказать по этому вопросу? Нужны еще пояснения (может проблема не ясна)?

Так уже всё сказано. Вот алгоритм для кубической зависимости скорости:

v(t) = v0 + a*t + b*t*t + c*t*t*t;

Имеем 2 условия:

v2 = v0 + a*T + b*T*T + c*T*T*T,
S/T = v0 + a*T/2 + b*T*T/3 + c*T*T*T/4.

Находим коэффициенты a и b, которые в данном случае теперь зависят (причём линейно) от параметра c.

a = (6*f2 - 2*f1)/T,
b = (3*f1 - 6*f2)/(T*T),

f1 = v2 - v0 - c*T*T*T,
f2 = S/T - v0 - c*T*T*T/4.

Далее подставляем a и b в уравнение для скорости и ищем условие для параметра c, где скорость на интервале t [0, T] больше или равна нулю:

v0 + a*t + b*t*t + c*t*t*t >= 0

Это, так называемое неравенство с параметром, то, чего так боятся школьники на ЕГЭ.
Решая его, получаете возможный интервал изменения параметра c. Всё. юзеру даёте бубочку с мин и мак. значениями для c.
Пускай крутит туда-сюда)   

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

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

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

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

Если мы сначала "взяли" какое-то значение "с" (т.е. ввод юзера), и на основании его вычислили a и b, потом из них вычисляем допустимый интервал "с" - то боюсь что этот интервал будет зависеть от того "с" что "взяли" :) А значит каких-то конкретных чисел для "пределов" у меня нет. Также условие "скорость положительна" вызывает у меня сомнения, не лучше ли поставить условие "скорость монотонно" (убывает/возрастает)

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

Ничего подобнтго.. Интервал для c, где скорость больше нуля определяется только начальными условиями т.е. начальная и конечная скорости, полный путь и время. И его можно аналитически получить. Юзеру давайте по умолчанию положение бубочки на c=0.

Нет, это монотонное убывание/возростание возможно только лишь в том случае, если окажется, что средняя скорость S/T будет лежать между начальной и конечной скоростями.
Более того, даже для квадратичной зависимости скорости никто не гарантирует, что на интервале [0, T] не будет точек поворота.

Да, верно, с монотонностью не выходит

Может и можно но не так как Вы предложили. Сначала Вы протаскиваете значение "с" "от фонаря"
А потом используете полученные a и b  для расчета пределов. Типа "куда повернул - туда и вышло".

Ну ладно, то может я слишком много хочу. И запрос этот всего лишь "вероятный". Ясно что сходу его не решить, да и ур-е 4-й степени надо либку подобрать.

Всем спасибо за обсуждение

Именно так. Вы просто, похоже, не понли..


Опять нет. Мы выражаем параметры a и  b через c. При этом a и b - линейно зависят от c.
Подставляем a и b, как функции c  в неравенство. Получаем линейное неравенство относительно c, где t - параметр. Никаких a  и  b там уже нет!
Решаем его, определяя границы для c, таким образом, чтоб при любых значениях t [0, T] это неравенств выполнялось. 
Этот интервал [c_min, c_max] будет зависеть только лишь от T, S, v0, v2. Всё!

Ааа! Дошло! Спасибо.

Но условие V >= 0 все-таки хиленькое. Оно и на просто квадратичной может не выполняться - ну обрезаю до нуля, лучшего не видно. И да, по условию скорость только положительная, хотя сам объект может двигаться в противоположном напр-и - это учитывается траекторией.

Спасибо

Если ускорение и скорость неограниченны то с - может любое значение приимать вплоть до бесконечности. (чисто физически )

Можно, конешно, любое c вставить, только вот никто не гарантирует вам, что скорость не сменит знак на пути s. Т.е. не будет точек поворота..

Так они и так есть, напр при v0 = v1 = 0

Немного сменим тему. Там есть еще "скорость на сегменте", т.е. 2 точки не так себе "соединяются прямой", а рисуется честная аналитическая кривая. Она вычисляется полиномом 5-й(?) степени, т.е. задаются

1) Длина пути между 2 точками
2) Начальные и конечные скорости
3) Начальные и конечные ускорения

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

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

Это точки остановки. Точки поворота это когда скорость меняет направление движения

уравнение 4 степени тоже решается. Можно сюда и других функций добавить, sin, log... в принципе и решать можно подбором значений(при делении уже точность теряется), ну или математический пакет для решения уравнений заюзать.

Ну да, при v0 = v1 = 0 получим параболу у = -kx^2 в верхней точке скорость перестает нарастать и начинает убывать

Давайте "точнее". Ни о каких синусах и/или логарифмах речь не идет.  Есть 2 точки, дано

S - длина пути
T - время
v0, v1 - скорости (в точках)
a0, a1 - ускорения (в точках)
b0, b1 - вторые ускорения (в точках)

Все перечисленное - конкретные числа. Требуется найти ф-цию (коэффициенты) полинома

общая формула скорости v(t) = a*t4 + b*t3 + c*t2 + d*t + e

v1 = a*t4 + b*t3 + c*t2 + d*t + v0
a1 = 4a*t3 + 3b*t2 + 2c*t + a0
b1 = 12a*t2 + 6b + b0

из формулы:
 e = v0 ( для нулевого времени)
 d = a0
 c = b0/2

осталось a, b найти.

p.s. если не секрет, а зачем это все нужно?

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

А скорость считается так
Похоже каждый параметр добавляет степень. Без ускорения (стартовый пост) 2-я степень. Добавили a0 - 3-я,  еще добавили a1 - 4-я. Со вторым(и) ускорением должна получиться 6-я степень
Что "все это"? :) "Вообще" - упр-е скоростью объекта для которого юзер задал траекторию. Конкретно "для 2 точек" - ну так между точками тоже надо считать, там может быть сколь угодно длинный путь

И вот у меня впечатление, что никакие "книги", вылазки в гуглу, поиски "готовых решений" и.т.п.  здесь совершенно не нужны  :) Просто записать ур-е нужной степени и найти коэффициенты.  Это хорошо  :)

Конечно не нужны. Книги, гугл... Достаточно зайти на prog.org.ru и спросить у m_ax. Все. :)

Исходя из начального условия задачи, ничто не мешает вам добавить к вашему полиному любых других функций(например синусом можно добавить вибрацию...)
можно вообще на одном синусе задачу решить - движемся со средней скоростью(при этом скорость изменяетсмя от 0 до Vmax > v0 и v1 - границы подгоняем чтоб v0 и v1 совпали) - конечно это несколько странное решение, но начальному условию удовлетворяет(S t v0 v1).

А вообще мне ваша задача напоминает построение сплайна.