Интерполяция/аппроксимация алгоритмы

← →
Unknown user © (2006-09-19 18:31) [0]

подскажите где найти рабочие алгоритмы интерполяции/аппроксимации гладких кривых, заданных набором точек. спасибо

← →
Loginov Dmitry © (2006-09-19 18:37) [1]

Попробуй поискать их в Интернете.

← →
Unknown user © (2006-09-19 18:47) [2]

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

← →
Leonid Troyanovsky © (2006-09-19 19:08) [3]

> Unknown user © (19.09.06 18:47) [2]

> не разбивающий кривую на участки, не учитывающий, что приращение
> по Х может быть 0 и т.п. короче теория в голом виде. мне

А почему это вдруг ее надо разбивать на участки?

Впрочем, есть такая книга:
Катковник В.Я. Непараметрическая идентификация и сглаживание данных. Метод локальной аппроксимации. -М: Наука, 1985

--
Regards, LVT.

← →
Германн © (2006-09-20 01:18) [4]

> пробовал. находил. но все они не окончены, не готовы для
> исползования в программе. просто математический алгоритм,
> не разбивающий кривую на участки, не учитывающий, что приращение
> по Х может быть 0 и т.п.

Ну ты просишь слишком много. Типа общего аналитического решения "задачи трёх тел", которого не существует. Обратись тогда к Перельману.
Или сформулируй свою задачу по-реальнее.

← →
atruhin © (2006-09-20 12:50) [5]

> Или сформулируй свою задачу по-реальнее.

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

← →
Chort © (2006-09-20 18:44) [6]

Посмотри снимок при работе в среде MathCad. Если это то что нужно тебе - напишу полный алгоритм. http://softvok.narod.ru/Mathcad.JPG

← →
Desdechado © (2006-09-20 19:04) [7]

http://ilib.mccme.ru/
http://www.allmath.ru/
может, есть там?

← →
Unknown user © (2006-09-24 17:00) [8]

большое спасибо всем за помощь. не ожидал такого участия :)

to Chort

то что MathCad успешно с такой задачей справляется, это я знаю :) то что нужно мне это такие вот функции:

function Interpolate(const Pnts:T2DPointsArray; Step:Single):T2DPointsArray;
-интерполяция масссива точек Pnts, Step-шаг точек выходного массива

function Approximate(const Pnts:T2DPointsArray; Step:Single):T2DPointsArray;
-аппроксимация массива точек

type T2DPointsArray=array of T2DPoint; T2DPoint=record X,Y:Double; end;

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

ну вот, в принципе, и сформулировал :)

← →
Chort © (2006-09-24 18:03) [9]

попоробуй поищи в гугле http://www.google.ru/search?hl=ru&q=function+Interpolate&btnG=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA&lr=
и так далее по всем словам

← →
Сало (2006-09-24 21:34) [10]

Меня тоже этот вопрос интересует.
Реализаций сплайн-интерполяций я видел много.
Например
unit spline3; (*********************************************************************** This code is generated by the AlgoPascal translator This code is distributed under the ALGLIB license (see http://www.alglib.net/copyrules.php for details) ***********************************************************************) interface uses Math, Ap; procedure Spline3BuildTable(N : Integer; const DiffN : Integer; x : TReal1DArray; y : TReal1DArray; const BoundL : Double; const BoundR : Double; var ctbl : TReal2DArray);forward; function Spline3Interpolate(N : Integer; const c : TReal2DArray; const X : Double):Double;forward; implementation (************************************************************************* Процедура Spline3BuildTable служит для построения таблицы коэффициентов кубического сплайна по заданным точкам и граничным условиям, накладываемым на производные. В дальнейшем постренная таблица используется функцией Spline3Interpolate. Параметры: N - число точек DiffN - тип граничного условия. "1" соответствует граничным условиям накладываемым на первые производные, "2" - на вторые. xs - массив абсцисс опорных точек с номерами от 0 до N-1 ys - массив ординат опорных точек с номерами от 0 до N-1 BoundL - левое граничное условие. Если DiffN равно 1, то первая произ- водная на левой границе равна BoundL, иначе BoundL равна вторая. BoundR - аналогично BoundL Выходные значения: ctbl - в этот массив помещается таблица коэффициентов сплайна. Эта таблица используется функцией Spline3Interpolate. *************************************************************************) procedure Spline3BuildTable(N : Integer; const DiffN : Integer; x : TReal1DArray; y : TReal1DArray; const BoundL : Double; const BoundR : Double; var ctbl : TReal2DArray); var C : Boolean; G : Integer; Tmp : Double; nxm1 : Integer; I : Integer; J : Integer; DX : Double; DXJ : Double; DYJ : Double; DXJP1 : Double; DYJP1 : Double; DXP : Double; YPPA : Double; YPPB : Double; PJ : Double; b1 : Double; b2 : Double; b3 : Double; b4 : Double; begin x := DynamicArrayCopy(x); y := DynamicArrayCopy(y); N := N-1; g := (n+1) div 2; repeat i := g; repeat j := i-g; c := True; repeat if x[j]<=x[j+g] then begin c := False; end else begin Tmp := x[j]; x[j] := x[j+g]; x[j+g] := Tmp; Tmp := y[j]; y[j] := y[j+g]; y[j+g] := Tmp; end; j := j-1; until not ((j>=0) and C); i := i+1; until not (i<=n); g := g div 2; until not (g>0); SetLength(ctbl, 4+1, N+1); N := N+1; if DiffN=1 then begin b1 := 1; b2 := 6/(x[1]-x[0])*((y[1]-y[0])/(x[1]-x[0])-BoundL); b3 := 1; b4 := 6/(x[n-1]-x[n-2])*(BoundR-(y[n-1]-y[n-2])/(x[n-1]-x[n-2])); end else begin b1 := 0; b2 := 2*BoundL; b3 := 0; b4 := 2*BoundR; end; nxm1 := n-1; if n>=2 then begin if n>2 then begin dxj := x[1]-x[0]; dyj := y[1]-y[0]; j := 2; while j<=nxm1 do begin dxjp1 := x[j]-x[j-1]; dyjp1 := y[j]-y[j-1]; dxp := dxj+dxjp1; ctbl[1,j-1] := dxjp1/dxp; ctbl[2,j-1] := 1-ctbl[1,j-1]; ctbl[3,j-1] := 6*(dyjp1/dxjp1-dyj/dxj)/dxp; dxj := dxjp1; dyj := dyjp1; j := j+1; end; end; ctbl[1,0] := -b1/2; ctbl[2,0] := b2/2; if n<>2 then begin j := 2; while j<=nxm1 do begin pj := ctbl[2,j-1]*ctbl[1,j-2]+2; ctbl[1,j-1] := -ctbl[1,j-1]/pj; ctbl[2,j-1] := (ctbl[3,j-1]-ctbl[2,j-1]*ctbl[2,J-2])/pj; j := j+1; end; end; yppb := (b4-b3*ctbl[2,nxm1-1])/(b3*ctbl[1,nxm1-1]+2); i := 1; while i<=nxm1 do begin j := n-i; yppa := ctbl[1,j-1]*yppb+ctbl[2,j-1]; dx := x[j]-x[j-1]; ctbl[3,j-1] := (yppb-yppa)/dx/6; ctbl[2,j-1] := yppa/2; ctbl[1,j-1] := (y[j]-y[j-1])/dx-(ctbl[2,j-1]+ctbl[3,j-1]*dx)*dx; yppb := yppa; i := i+1; end; i:=1; while i<=n do begin ctbl[0,i-1] := y[i-1]; ctbl[4,i-1] := x[i-1]; Inc(i); end; end; end; (************************************************************************* Вычисление значения сплайна в точке по таблице коэффициентов Функция Spline3Interpolate по построенной процедурой Spline3BuildTable таблице коэффициентов вычисляет значение интерполируемой функции в заданной точке. Параметры: N - число точек, переданных в процедуру Spline3BuildTable C - таблица коэффициентов, построенная процедурой Spline3BuildTable X - точка, в которой ведем расчет Результат: значение кубического сплайна, заданного таблицей C, в точке X *************************************************************************) function Spline3Interpolate(N : Integer; const c : TReal2DArray; const X : Double):Double; var I : Integer; L : Integer; Half : Integer; First : Integer; Middle : Integer; begin N := N-1; L := N; First := 0; while L>0 do begin Half := L div 2; Middle := First+Half; if C[4,Middle]<X then begin First := Middle+1; L := L-Half-1; end else begin L := Half; end; end; I := First-1; if I<0 then begin I := 0; end; Result := c[0,I]+(X-c[4,i])*(C[1,I]+(X-c[4,i])*(C[2,I]+C[3,i]*(X-c[4,i]))); end; end.

← →
Unknown user © (2006-09-25 09:35) [11]

to Chort спасибо, буду еще искать. пробовал на SourceForge скачивать исходники, но наверное никто таким вопросом не занимается. не нашел ничего :(

to Сало

Да, я находил тоже этот модуль, испытывал его, но:
1. он не обрабатывает ситуацию, когда приращение по Х равно нулю (вертикальная линия), при этом происходит деление на 0.
2. на границах задаваемой кривой возникают синусоидальные всплески, о чем впрочем упоминалось в описании алгоритма.

такие же проблемы и для других алгоритмов интерполяции/аппроксимации выложенных на этом сайте.

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

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

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

Это особенности данного алгоритма, а не его реализации, кроме конечно,
> при этом происходит деление на 0.

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

> 1. он не обрабатывает ситуацию, когда приращение по Х равно
> нулю (вертикальная линия), при этом происходит деление на
> 0.
> 2. на границах задаваемой кривой возникают синусоидальные
> всплески, о чем впрочем упоминалось в описании алгоритма.
>

параметризуйте по хордовой переменной
далее можно применить итерационное сглаживание по длине дуги

to Кщд

как математик математику? :) спасибо, конечно но мне нужны не краткие и емкие а простые и доходчивые объснения :) я не знаю такого способа параметризации кривых :( какие параметры при этом используются? как строится хорда для кривой? что такое иттерационнное сглаживание?

to atruhin

мне бы уже хоть бы какую реализацию :) лишь бы она устойчиво работала

x=x(t)
y=y(t)
t - хордовая переменная
можно через аську 197-157-721

Тебе несколько раз намекнули, что алгоритм и реализация зависят от данных.
Что бы реально помочь нужен хотя бы образец сырых (необработанных) данных. Для начала выложи график данных, без сглаживания, можно и немного данных, текстовый файл X,Y через табуляцию, что бы excel открывал, посмотрю.
Также опиши характер данных, откуда они беруться хотя бы, периодичность, спектральная плотность (теоретическая, и практическая) и т.д.
Когда то плотно этим занимался, но без информации увы.

Интерполяция/аппроксимация алгоритмы Найти похожие ветки