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

Какой алгоритм можно применить в данном случае?

y'[i] = (y[i - 1] + y[i] + y[i + 1]) / 3

если задача состоит не в получении плавной кривой, то можно попробовать алгоритм Дугласа-Пекера
http://www.simdesign.nl/Components/DouglasPeucker.html

Спасибо всем ответившим. Покажу на рисунке, что нужно.

http://84.19.182.224/makhaon/Untitled-2.jpg

Есть кривая линия 2. Состоящая из отрезков, соединяющих около 40 точек.
Есть прямая линия 1. Она приблизительно усредненная из всех точек.

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

Еще самый главный нюанс. Это показан частный случай. Линия 1, к которой нужно приближаться - не обязательно прямая. Она может быть немного изогнута в одном-двух местах.

хм...
Тогда строим прямую по МНК, затем точки к ней нетрудно приблизить.
Если одна прямая слишком большую погрешность дает, то несколько кусков обсчитываем (можно рекурсивно пополам делить, например, только надо придумать, как быть с согласованием отрезков)
А откуда такая задача?

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

Так может, сглаживающий сплайн подойдет?

Кривизну кривой линии желательно частично сохранить. Хотя, видимо, придётся сглаживать полнолстью до плавной линии.

А алгоритм Xprogera разве не дает нужного эффекта? Там все правильно, можно только попробовать расширить диапазон, если сглаживание недостаточное.  (-3, -2, -1, ... +2, +3) / 7.
И все данные сохранять в новый массив, чтобы уже обсчитаные точки не влиали на последующие точки.

Следует применить алгоритм сглаживания. Ломаную линию надо представить массивом дискретной  функции. Очевидно, что  вторые  разности этой функции определяет ее 'ломаность' . Чем меньше значения вторых разностей,  тем более гладкой является функция. Значения сглаженной функции должны, во-первых, не сильно отличаться от  значений исходной функции, во-вторых, иметь  малые значения вторых разностей.
Пусть   f[i] – исходная функция,  g[i] – искомая сглаженная функция, i=1…n .
r[i]=f[i]-g[i],q[i]=g[i+2]-2g[i+1]+g[i] .
Следует определить такую функцию g[i], которая минимизирует функционал
F=k∑_1^n▒〖r[i]〗^2 +∑_1^(n-2)▒〖〖q[i]〗^2.〗          k - коэффициент сглаживания, чем он меньше, тем меньше «ломаность»  сглаженной функции.  Произведя обычные выкладки способа наименьших квадратов, можно получить  значения элементов сглаженной функции как линейную комбинацию элеменов исходной функции.  Например, при k = 1
g[i]=-0.01f[i-4]+0.01f[i-3]+0.09f[i-2]+0.24f[i-1]+0.39f[i]+0.24f[i+1]+0.09f[i+2]+0.01f[i+3]-0.01f[i+4].
Глухов Г.Н. Алгоритм цифрового сглаживания. Научно - технический и рекламно -коммерческий периодический журнал ФГУП ННИПИ "Кварц" Нижний Новгород. 2004.- С.43-46.

>Глухов Г.Н.   (30.07.11 10:27) [9]
чем плох обыкновенный кубический сплайн(если необходимо, итеративно сглаженный по длине дуги) по сравнению с продемонстрированным "велосипедом"?

Так некромагию же вроде б как запретили?

Кщд "велосипед" проще. С помощью коэфициента k можно выбирать величину сглаживания.

>Глухов Г.Н.   (26.08.11 16:41) [12]
>Кщд "велосипед" проще.
пока ф-лы нечитаемы, утверждение спорно.

Кщд "велосипед" проще. Формулы на https://sites.google.com/site/glyhovgn/test

>Глухов Г.Н.   (04.09.11 17:39) [14]
прочитал, спасибо
трехдиагональная матрица у сплайна против пяти - у Вас
сглаживание у Вас вместо интерполяции у сплайна
на основании чего сделан вывод о том, что сплайн - "сложнее", - из статьи не ясно - ни оценок по погрешности, ни сравнения сложности вычислений(в терминах О)

Кшд. спасибо.
демо-прогамма алгоритма сглаживания FLATIRON.EXE можно запустить с файлообменника http://www.fayloobmennik.net/942383

Кшд. спасибо.
демо-прогамма алгоритма сглаживания FLATIRON.EXE можно запустить с файлообменника http://www.fayloobmennik.net/942383

>Глухов Г.Н.   (05.09.11 09:14) [17]
1. опять: ни погрешности, ни сложности вычислений;
2. что будет при неравномерном разбиении сетки?

PS Программа выглядит странно. Исходники покажете?

Кщд
Имея исходную и сглаженную линии, вычислить отклонения их друг от друга - погрешность не проблема.
Сглаженная линия считается как средне взвешенное значение (см сообщение от(30.07.11 10:27)), поэтому сложность вычислений линейна относительно количества данных, числа значений исходной функции.
При неравномерной сетке алгоритм не работает.
Если бужет проявлен значительный интерес, исходники будут доработаны и опубликованы.

Я недаво тоже задавался этим вопросом, поискав в нете нашел вот эту статейку с обзором дополнительного графического модуля, надеюсь поможет - http://www.cross-kpk.ru/forum.dll/topic?id=20

>Глухов Г.Н.   (06.09.11 10:48) [19]
1. меня интересовало сравнение погрешностей сплайна и Вашего алгоритма;
2. сложность вычисления кубического сплайна также возрастает линейно по кол-ву точек.

Т.о. преимущества Вашего алгоритма неочевидны, тогда как недостатки существенны. Равномерность шага сетки - серьезное ограничение.

И ещё раз: мне не ясно, каким образом Ваш метод может быть альтернативой сплайну, если сплайн - это интерполяция, а Ваш метод - усреднение.

>piople ©   (06.09.11 13:33) [20]
Вы топик читали?

Кщд
Интеполяция и усреднение - разные задачи.

>Кщд   (06.09.11 13:44) [22]
Отлично. Тогда почему(и на основании) чего делаете вывод, что Ваш алгориитм "не хуже" кубического сплайна?

>Кщд   (07.09.11 12:25) [24]
ой-ой.
Тогда почему(и на основании чего) делаете вывод, что Ваш алгориитм "не хуже" кубического сплайна?)

Кщд
Не хуже для решения задачи   Белькевич   (20.02.08 02:34)

>Глухов Г.Н.   (08.09.11 10:23) [26]
к сожалению, ссылка с примером автора нерабочая.
ему требовалось равномерное разбиение сетки?

Кщд
Спасибо за интересное общение. Вы мне очень помогли.

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

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

Ну это если в лоб. Возможно есть какие-то более оптимальные решения.

Заниматься алгоритмом лень, если честно. Написанный работает нормально.

Дмитрий Белькевич  
На плоскости помещен массив точек с координатами  x,y . Если соединить подряд все точки, то получится некая ломаная линия. Нужно уменьшить её 'ломаность'. То есть сгладить.
Следует перенумеровать все точки. Построить два графика:  график функции X(k) и график функции Y(k), приняв за аргумент k номер точки.  Для каждой из функций произвести сглаживание. Можно, например, использовать программу  FLATIRON.EXE с файлообменника http://www.fayloobmennik.net/942383. Полученные координаты Xc(k) и Yc(k) поместить на график исходной плоскости. Построив несколько сглаженных ломаных линий,   изменяя коэффициент сглаживания , возможно удастся получить результат, близкий к желаемому.

В соответствии с рекомендациями (15.09.11 16.11) написана программа «Сглалин.exe».

и всего-то четыре года )

Демо версию программы «Сглалин.exe» можно скачать с файлообмуенника http://www.fayloobmennik.net/942383.

> «Сглалин.exe»


Чет я прочитал, как "Сталин" -к чему бы ? :)