Продолжаем про сплайны и кривые безье

здесь написано http://alglib.sources.ru/interpolation/beziercurve.php что не обязана проходить через все точки.
Пусть Die-Hard напряжется, и таки вспомнить что читать надо по вопросу. Хотя б математику этого дела приведет, или ссылку даст. Тогда можно будет покумекать

http://www.moshplant.com/direct-or/bezier/math.html

Суть в том, что контрольные точки задают касательные в начальных точках. Лучше кривую Безье строить по соседним точкам, а касательные выбирать так, чтобы на соседних участках кривая была гладкой.

Например для построения кривой между x_n и x_{n+1} для точек x_{n-1} x_{n} x_{n+1} x_{n+2}

можно выбрать следующие значения

x_{n} - начальная точка x_{n+1} - конечная x_n + (x_n - x_{n-1}) - первая контрольная x_n - вторая контрольная

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

Либо я чего-то непонимаю, либо одно из двух. "Промоделировал" твое предложение в inkscape - получилась, мягко говоря, херня. http://dfo.antex.ru/files/pics/bayesian.png

welkam :

> В этом случае касательная всегда будет направлена на предыдущую точку.

Да, да, я с этого начал когда-то!

Картинка получилась удручающей...

Прямо сейчас некогда, может, попозже сегодня (мне все равно вскоре понадобится самому). Пока что нагуглилось:

http://www.ibiblio.org/e-notes/Splines/Bint.htm

Вот, кстати:

http://www.ibiblio.org/e-notes/Splines/Cardinal.htm

Там все прозрачно по ссылке; кривые Безье проходят через опорные точки P_i и P_{i+1}, а производная в P_i определяется как (P_{i-1} + P_{i+1})/a, где a -- некий параметр, обычно равный 2 (понятно, в вышеприведенной формуле P это 2-вектор (P_x,P_y) ). То есть, в качестве производной берется некий аналог первой центральной разности, а длина контрольных векторов остается произвольной и регулируется параметром "a", от нее зависит качество интерполирующего алгоритма.

Взглюкнулось,

(P_{i-1} + P_{i+1})/a => (P_{i+1} - P_{i-1})/a

Не дождусь ответа, спать пора...

Все понял, или формулы в компонентах расписать?

Я говорил, что геометрию не помню? По моему говорил. Если тебе не лень - распиши формулы. Если лень - ну что ж, придется вспоминать, что такое "производные" и "векторы" =)

drF_ckoff

> Если тебе не лень - распиши формулы.

Мне надо уходить, буду часов в 19 по Москве. Если к тому времени не сообразишь, напишу.

Да, векторы-производные -- это опорные точки кривых Безье, через которые они не проходят. Может, дальше сам сообразишь (больше про производные знать ничего не надо)?

Не, не хочу соображать. afair я _так_ уже соображал. На "реальных данных" получалось не то, что должно было бы получиться.
(btw, если интересно - это я http://metromap.antex.ru/ на cairo перевожу)

Кубическая кривая Безье (а именно такие кривые Безье чаше всего рассматриваются) -- параметрическая кривая 3 порядка:

P(t)=P0*(1 - t)^3 + 3*P1*t(1 - t)^2 + 3*P2*t^2*(1 - t) + P3*t^3 Тут "P" это 2-вектор (пара X,Y), а параметр t пробегает от 0 до 1, 0<=t<=1.

То есть, формула для P это две формулы на X и Y:

X(t)=X0*(1 - t)^3 + 3*X1*t(1 - t)^2 + 3*X2*t^2*(1 - t) + X3*t^3

Y(t)=Y0*(1 - t)^3 + 3*Y1*t(1 - t)^2 + 3*Y2*t^2*(1 - t) + Y3*t^3

Как видим, P(0)=P0, P(1)= P3, то есть кривая начинается в точке (X0,Y0) и заканчивается в точке (X3,Y3).

Через точки P1 P2 кривая не проходит, но ее концы "прилипают" к отрезкам [P0,P1] [P3,P2], то есть касательная в начале определяется отрезком [P0,P1], а в конце -- [P3,P2]. Чем длиннее отрезки, тем больше кривая к ним "прилипает".

Пусть есть точки Q1, Q2, Q3, ... Qn (каждый Q -- 2-вектор). Сплайн стоим так:

Забудем на минутку про Q1 и Qn.

Через каждую пару Qi,Qi+1 проводим кривую Безье так, чтобы касательная в точке Qi+1 была параллельна отрезку [Qi,Qi+2]. То есть, вектор касательной получаем как (-/+)(Qi+2 - Qi)/a-+, где "a-+" -- некое число, обычно равное 2. То есть, для кривой, которая заканчивается в Qi+1, берется вектор -(Qi+2 - Qi)/a-, а для для кривой, которая начинается в Qi+1, берется вектор (Qi+2 - Qi)/a+, и обычно кладется a+ = a- = 2. Для вычисления опорных точек кривых надо к Qi+1 прибавить найденные векторы.

Пример: Qi = (10,10); Qi+1 = (20,20); Qi+2 = (10,20);

-(Qi+2 - Qi)/a- = (0,-5); (Qi+2 - Qi)/a+ = (0,5);

Первая кривая: Qi ? (20,15) Qi+1 (знак вопроса вычислен на пред. шаге; (20,15) = (20,20) + (0,-5) )

Вторая кривая: Qi+1 (20,25) ? Qi+2 (знак вопроса будет вычислен на след. шаге, (20,25)= (20,20) + (0,5) )

Про концевые точки по ссылке почитай сам.

> На "реальных данных" получалось не то, что должно было бы получиться.

Проверил, работает. Код на Математике:

x0 = 10; x1 = 15; x2 = 20; x3 = 20;

y0 = 10; y1 = 5; y2 = 15; y3 = 20;

x10 = 20; x11 = 20; x12 = 15; x13 = 10;

y10 = 20; y11 = 25; y12 = 25; y13 = 20;

fx[t_] := x0*(1 - t)^3 + 3*x1*t(1 - t)^2 + 3*x2*t^2*(1 - t) + x3*t^3

fy[t_] := y0*(1 - t)^3 + 3*y1*t(1 - t)^2 + 3*y2*t^2*(1 - t) + y3*t^3

fx1[t_] := x10*(1 - t)^3 + 3*x11*t(1 - t)^2 + 3*x12*t^2*(1 - t) + x13*t^3

fy1[t_] := y10*(1 - t)^3 + 3*y11*t(1 - t)^2 + 3*y12*t^2*(1 - t) + y13*t^3

ParametricPlot[{{fx[t], fy[t]}, {fx1[t], fy1[t]}}, {t, 0, 1}]

Вдогонку:

В приведенной ссылке для концевых точек рекомендовалось в качестве касательных векторов брать просто последний отрезок ( [Q1 Q2] и [Qn Qn-1] ). У меня получалось лучше, если я брал что-то более хитрое, типа среднего между последним отрезком и касательной, вычесленной на следующем (для Q1) / предыдущем (для Qn) шаге.

Достаточно было фразы "чтобы касательная в точке Qi+1 была параллельна отрезку [Qi,Qi+2].". afair, я уже пробовал строить их исходя из этого допущения и, afair, "визуально" получалось "не то". То есть похоже, что в исходных данных точки выбраны так, что их надо апроксимировать исходя из какого-то другого допущения. Но, блин, склероз. Не помню. Постараюсь завтра себя построить реализовать это дело... И вечером доложиться.

> ..."визуально" получалось "не то".

У меня именно так все хорошо получалось.

Попробуй поиграть с параметром "a".

Если взять параметр "a" очень большим (100), то получится просто ломаная (кстати, проверка запрограммированного алгоритма на кривые руки). Возьми a=20 и потихоньку уменьшай, пока ломаная не сгладится достаточно.

Утверждается, что подобный сплайны всегда хороши, пока не требуется гладкости больше C^1. Поскольку ты ничего не дифференцируешь, единственное место, где сплайн может сглючить, будет крайне неравномерное распределение точек интерполяции. Тогда тебе придется параметр "a" сделать адаптивным.