Есть массив координат точек размерности 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)), поэтому сложность вычислений линейна относительно количества данных, числа значений исходной функции.
При неравномерной сетке алгоритм не работает.
Если бужет проявлен значительный интерес, исходники будут доработаны и опубликованы.