Сплайн по набору точек

Здравствуйте

Дан набор точек (пара значение + время), требуется прибить как можно большее их кол-во заменив сплайном на выбор

- линейный (т.е. вообще без сплайна)
- B-Spline (он же Natural Cubic)
- Hermite (он же TCB)
- Безье "просто"
- Безье с полиномом Бернштейна (Семена Натаныча)

Все сплайны должны сохраняют значения в оставшихся точках. Все имеют опцию "hold" (постоянное значение до следующей). Начиная с Hermite также есть опция "linear in/out" - линейный сегмент (весь или начало/конец). Допустимая погрешность задается юзером.

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

Понимаю что шансов мало (нужны академические знания), ну а вдруг...

0

Сообщение от Igor3D - Безье "просто" - Безье с полиномом Бернштейна (Семена Натаныча)

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

Добавлено через 23 минуты
Да, вспомнил, в описываемом случае количество контрольных точек должно совпадать с количеством исходных, очевидно, чтобы СЛАУ имела решение.
Если требуется намного снизить количество контрольных точек, то требуется применить не интерполяцию, а аппроксимацию, т.е. минимизировать сумму квадратов расстояний точек кривой (с назначенными парметрами) до исходных точек. Там тоже линейная система уравнений получается. Но кривая в этом случае точно через точки проходить не будет.

0

Сообщение от woldemas И чем они отличаются? По-моему, базовые функции кривой Безье всегда представляют из себя полиномы Бернштейна соответствующей степени.

В первом случае используется стандартная "эрмитная матрица". Степени сплайна - все кубические (2 контрольных точки). Про "вектор узлов" впервые слышу.
Обычный ход мысли примерно такой (еще называется "умывать руки")

Ага... Безье, Бернштейн, TCB - да откуда же я могу все это знать? Не-не-не, вот пусть математики этим и занимаются, а я - программист. Каждый должен заниматься своим делом! и.т.п.

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

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

0

Сообщение от Igor3D Про "вектор узлов" впервые слышу.

Это NURBS-терминология, В-сплайн, кривая Безье - это частный случай NURBS-кривых. Вектор узлов определяет степень "гладкости" соединения сегментов сплайна. Но это вряд ли понадобится.

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

0

Сообщение от woldemas Вообще какая проблема-то?

Рассмотрим собсно сплайн (аттач). Каждый сегмент сплайна определяется 2 точками самой кривой (ромбики) + 2 "контрольные" точки (синие квадратики, их часто называют handle(s)), их юзер тоже может менять настраивая кривизну. Таким образом имея небольшое кол-во точек сплайна можно получать разнообразные кривые.

Сообщение от woldemas Провести сплайн (Безье или Б-сплайн) через все точки - получится только, если число контрольных точек равно числу точек для интерполяции.

Допустимая погрешность задается (стартовый пост)

Сообщение от woldemas Используйте аппроксимацию: задайте нужное вам количество контрольных точек (например для составной Безье) и вычисляйте их, по условию минимизации суммы квадратов расстояний (там система линейных уравнений относительно координат контрольных точек).

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

Ну и главное - не видно алгоритма. Пришли исходные точки (часто 2-3 тысячи). Мои действия? Ну может это всего лишь прямая и 2 точек сплайна достаточно. Хорошо, попробовал аппроксимировать все одним сегментом - не вышло. Дальше что? Взять исходную точку с макс отклонением и добавить ее в сплайн? Есть мысли ?

Миниатюры

 

0

Разбить ломанную на участки двух видов:
-отрезки
-кривые 2 степени.

1)отрезки
берем 3 точки подряд, отрезок по первой и последней удовлетворяет точность?
да, берем еще точку и снова проверяем отрезок
нет, вызов “поиск участка кривой”


2) “поиск участка кривой”
В цикле находим:
Vec1=вектор по N и N+1 точкам
Vec2=вектор по N+1 и N+2 точкам
DiffAngle=угол между Vec1 и Vec2
SumAngle=SumAngle+DiffAngle
N++

Продолжаем цикл пока DiffAngle<Порог1 и SumAngle<Порог2

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

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

3)Аппроксимация.
Аппроксимировать будем кривой Безье 3 ст. искать средние точки 2 и 3.
Способ аппроксимации зависит от наличия касательных от соседних участков.

Похоже тут 4 случая:
1)прошлого участка нет, текущий кривая, следущий отрезок.
2)нет, кривая, кривая.
3)отрезок, кривая,отрезок
4)отрезок, кривая,кривая
вроде все...


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

1)прошлого участка нет, текущий кривая, следующий отрезок.
Прошлой касательной нет, значит для точки 2 будет поиск двух переменных x2,y2.
Следующий участок касательная есть, значит поиск одной неизвестной точки 3 лежащей на касательной.
Поиск трех неизвестных.

2)нет, кривая, кривая.
Поиск четырех неизвестных.

3)отрезок, кривая,отрезок
Самый простой случай, точки 2 и 3 лежат на касательных к соседним участкам.
Поиск двух неизвестных.

4)отрезок, кривая,кривая
Поиск трех неизвестных.

0

Excalibur921, излагаете довольно сумбурно , но все равно спасибо за желание помочь.

Копнем немного сплайны (не так уж страшен черт как его малюют). Для каждого сегмента имеем

y0 - значение в начальной точке сплайна (левый ромбик на рисунке)
y1 - значение в первой контрольной точке (правый синий квадратик левой "ручки")
y2 - значение во второй контрольной точке (левый синий квадратик правой "ручки")
y3 - значение в конечной точке сплайна (правый ромбик)

Требуется рассчитать значение y в точке с заданным временем t которое лежит в интервале 2 точек сплайна. "В принципе" это делается просто

y = y0 * k0(t) + y1 * k1(t) + y2 * k2(t) + y3 * k3(t);

Где k(t) - коэффициенты сплайна которые вычисляются всяко-разно (по Бернштейну, Эрмиту и др), но в данной задаче эти детали нас совершенно не волнуют - для любого сегмента мы можем взять 2 точки внутри него и получить y1 и у2. Отсюда кстати следует что выделять "прямую" в отдельный случай совсем необязательно - если синие точки лежат на прямой соединяющей 2 точки сплайна - то он сам даст прямую.

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

0

Сообщение от Igor3D излагаете довольно сумбурно

Разве? А по-моему 95% алгоритма.
Разбиваете ломанную на интервалы и определяете их тип.
Берете каждый интервал и классифицируете какой из 4 случаев аппроксимации.
Делаете нелинейную оптимизацию находите точки 2 и 3.

Сообщение от Igor3D y = y0 * k0(t) + y1 * k1(t) + y2 * k2(t) + y3 * k3(t);

Это уравнение я не знаю.

Сообщение от Igor3D "В принципе" это делается просто

Для кривой Безье 3 ст. просто так f(x) не взять, находят так:
Берем нужный X, опорные точки кривой, находим какую из 4 формул использовать.
Формулы есть на вики.
Находим t.
Подставляем в формулу f(t) для Y получаем в итоге f(x).

Сообщение от Igor3D выделять "прямую" в отдельный случай совсем необязательно

Обязательно, это проще и быстрей, нет ненужных расчетов оптимизации.

Сообщение от Igor3D y0 - значение в начальной точке сплайна (левый ромбик на рисунке)

На вики кривая Безье 3 ст. нумерация опорных векторов 1,2,3,4.
Рекомендую не употреблять названия типа “правый синий квадратик левой "ручки". От вас убегут не только немного математики но и немного программисты.

Тут единственно сложность в поиске вектора когда для точки 2 неизвестных.
Можно считать сеткой значений локализовать корень, уменьшить размер сетки и уточнить. Методов оптимизации вагон и тележка.


Давайте я переведу как я понял ТЗ.

Сообщение от Igor3D Дан набор точек (пара значение + время), т

Есть ломанная.

Сообщение от Igor3D требуется прибить как можно большее их кол-во

Аппроксимировать ломанную.

Сообщение от Igor3D сплайном на выбор

Используя например кривую Безье любой степени.

Сообщение от Igor3D Все сплайны должны сохраняют значения в оставшихся точках.

На ломанной есть N точек которые нельзя двигать.

Так? Вот это описано выше+будет непрерывная гладкая кривая.

Сообщение от Igor3D как выбирать точки для сплайна из исходных.

Как отобрать точки которые похоже на кривую второй степени?
Ну вот:

Сообщение от Excalibur921 2) “поиск участка кривой”

Если не нужна непрерывная гладкость всей кривой(непрерывность производной или как там ее называют) то алгоритм намного упрощается. Можно взять Безье 2 ст.
будет всегда поиск двух неизвестных и ненужно классифицировать участки.

0

Сообщение от Excalibur921 Рекомендую не употреблять названия типа “правый синий квадратик левой "ручки". От вас убегут не только немного математики но и немного программисты.

Та было бы кому убегать , пока Вы единственный кто проявляет интерес.

Сообщение от Excalibur921 Давайте я переведу как я понял ТЗ.

В принципе все верно, уточним пару моментов.

1) Говорят просто "кубический сплайн", и это значит используются (юзер может настраивать) ДВЕ контрольные точки. Это может быть Безье второй степени или что-то еще. Напр при обмене данными c помощью популярного FBX тип сплайна просто "cubic" - никак не уточняется Безье или что еще

2) y = y0 * k0(t) + y1 * k1(t) + y2 * k2(t) + y3 * k3(t);
Это просто-напросто "взвешивание", разумеется сумма всех "k" = 1. Таким образом имея 2 точки сплайна и взяв 2 (исходные) точки между ними легко находятся y1 и y2. Ну конечно это еще ничего не значит - найденная кривая может быть далеко от др (исходных) точек сегмента.

Также условие "гладкости" может и не выполняться, изломы в точках сплайна допустимы (иногда говорят "Bezier Knee").

Сообщение от Excalibur921 Разве? А по-моему 95% алгоритма. Разбиваете ломанную на интервалы и определяете их тип. Берете каждый интервал и классифицируете какой из 4 случаев аппроксимации. Делаете нелинейную оптимизацию находите точки 2 и 3.

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

0

Для начала нужно сделать алгоритмы 1 и 2

Сообщение от Excalibur921 1)отрезки

Сообщение от Excalibur921 2) “поиск участка кривой”

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

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

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

Сообщение от Igor3D условие "гладкости" может и не выполняться,

Лучше чтобы не выполнялось, меньше матана. Если нет гладкости, то лучше взять какой то интерполяционный сплайн через 3 точки, наверно его оптимизация будет быстрей сходиться чем для Безье.
Может даже парабола по 3 точкам. Формулы есть на вики.

В общем такой велик:
Есть ломанная. Аппроксимируем Безье 2 ст. опорные точки A,C заданы, ищем B.

Проводим прямую AC. Ищем максимум расстояния от каждой точки на ломанной до прямой это будет точка B. Это и будет грубый корень.

Именно поэтому удобней брать интерполяционный сплайн через 3 точки а не Безье.
Считаем точность аппроксимации, если не подходит делаем целевую функцию:
сумма расстояний по Y от N точек на кривой до точек на ломанной.
Минимизируем целевую функцию и выполняем нелинейную оптимизацию поиск двух неизвестных (xB,yB) градиентным спуском или другим. Наверно тут очень гладкая поверхность и корень один.

Может хватит даже и без матерых методов оптимизации, но корень искать намного дольше. Зато матан проще. Например берем хоть сетку точек (или рандом от генератора в неком радиусе) вокруг грубого корня B.

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

Если настроить классификатор на мелкие куски похожие на параболу то зачем брать что то сложней параболы?
Если искать Безье 3 степени, то будет поиск 4 неизвестных, но зачем усложнять матан?
Проще найти две параболы\ Безье 2 ст где будет 2 неизвестных чем искать 4.

0

Сообщение от Excalibur921 -сделать генератор ломанной.

Кстати - именно этим сейчас и занимаюсь.

Сообщение от Excalibur921 В общем такой велик:

Понимаю что охаять чужой велик - ума много не надо, гораздо труднее предложить (хоть что-то). Но все же.. вот после нашего обмена неск постами у меня сложилось стойкое впечатление - не хватает теории. Др словами гуглить надо. Я конечно пробовал, но пока нашел только неск статей с обильными формулами с которыми хз что делать. На тему "interpolation" (сплайнов) - море ссылок, а вот "approximation" - мало.

0

Сообщение от Igor3D именно этим сейчас и занимаюсь.

Что там его делать?
Несколько синусоид основная форма кривой + тоже меньшей амплитуды мелкий шум.
Или тоже от рандом генератора и\или их смесь.
Или подмешивать шум в любой сплайн контрольные точки которого задаем.
Нужна рандом ломанная по шероховатости примерно похожая на ваши данные.

Сообщение от Igor3D с которыми хз что делать.

Как это хз?
Вникать и повторять на С++. Вводить данные по примеру и смотреть результат…а как еще? Хотите научный подход? Может искать квадратичная аппроксимация.
http://dit.isuct.ru/IVT/sitano... Glava3.htm

0

Igor3D, Есть сдвиги? Бросили?
Мой мощный алгоритм классификатора работает? =)).

0

Сообщение от Excalibur921 Есть сдвиги? Бросили?

Пока занимаюсь "рандомайзером" - он нужен и сам по себе. Потом может тоже отложу. Это не значит "поматросил и бросил" Должно созреть, пока этого нет. А так лезть что-то "кодить" - ну будет вариант может чуть лучший чем нынешний, но который в будущем опять переделывать. А хотелось бы "закрыть вопрос". Ну и нужно капитальное гугление, штука скорее всего известная, накатанные решения должны быть

0

0