|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Kanilo 2:5020/400 27 Oct 2001 19:35:40
To : Michael Savin
Subject : Re: Spline with tension
--------------------------------------------------------------------------------
"Michael Savin" <Michael.Savin@f269.n5070.z2.fidonet.org> wrote in message
news:1004211650@f269.n5070.z2.ftn...
> >> А все-таки, где достать сабж. Поискал на google.com, замучился по
ссылкам
> >> лазить, но один сырец достал. А вот описания... Подскажите точных
> >> ссылочек, или может у кого доки по этому делу есть? А-то у нас
интернет
> >> дорогой... :-(
> SK> А что конкретно имеется в виду?
> Поясняю конкретно: имеется массив из точек, фиксирующих положение объекта
> (x,y), по ним нужно построить некую кривую, характеризующую траекторию
объекта.
> Желателен простой вид функции (так, чтоб можно было найти скорость,
ускорение,
> etc). Естественно, координаты объекта имеют некую погрешность, поэтому
нужно
> брать сглаживающие функции.
Ага, а где здесь "tension"?
Я могу еще предположить, что известны времена прохождения этих точек.
Для апроксимации ускорений я применял сплайны, и все достаточно просто
если не придираться к произволительности :)
1) Отрезок времени от начала до конца движения разбивается на равномерные
кусочки, между кусочками находятся узлы к которых будем искать значение
функции и ее производной). Будем считать N узлов по две неизвестных в
каждом.
2) Hа каждом кусочке искомая функция задантся сплайном (кубическая
парабола определенная значениями функции и ее производной в узлах)
Если не лень и очень нужно, то можно исаользовать и пятый и седьмой
порядок полинома.
3) Для каждой точки ищем, во-первых, на какой кусок времени она попадает,
и затем отклонение, от искомой траектории, вид которого
c1*f_(i-1)+c2*f'_(i-1)+c3*f_i+c4*f'_i
где c1,c2,c3,c4 - коэффициенты зависящие от положения точки на временном
куске.
4) Все отклонения возводим в квадрат, суммируем и получаем квадратичный
функционал для минимизации.
Если есть какие-то идеи о том, что какие-то точки более приоритетные, а
какие-то
менее - то ставим при квадратах соответствующие веса.
5) Терерь по-вкусу, добавляем ограничения на саму функцию и ее производные.
Я например минимизировал разрывы по второй производной в узлах. Опять же,
вычислял ранзицу между вторыми производными в узле, брал квадрат, умножал
на эмпирически подобранный коэффициуни и добавлял к функционалу. (не это ли
подразумевалось под "tension"?)
Обычно еще добавляют условия для граничных точек.
6) Берем производные от функционала по каждой из незизестных и приравниваем
их нулю. И получается трехдиагоныльная или ленточная система из 2*N
уравнений,
которая достаточно легко и эффективно решается.
Все здесь - для одной функции, но для материальной точки перемещения
по x и y независимы, так что можно из считать отдельно.
Поскольку время у них одинаково, то можно совместить поиск положения
точки.
Hу и в крацнем случае добавить ограничения на кривизну траектории в
пространстве. Hо тогда уже будет связь между x и у, и вместо двух систем
2N уравнений, прийдется решать одну из 4N и с более широкой лентой.
Hу пока все,
Cheers,
Serge
--- ifmail v.2.15dev5
* Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
