Составные кривые Безье

[Алексей К.]

artful7 писал(а):

Вот тут и возникает вопрос: как получить значение Y при заданной координате Х ?

Решить кубическое уравнение (для данного участка $x_i\le X \le x_{i+1}$, описываемого ф-циями $x_i(t),\:y_i(t)$) $x_i(t_0)=X_i$, корень --- единственный --- должен найтись в пределах $0\le t_0 \le 1$ (альтернатива --- ошибка в программах) и вычислить $y(t_0)$.

Добавлено спустя 2 минуты 33 секунды:

ewert писал(а):

Это неверно. Если строить обычный сплайн, то однозначность обеспечивается просто по определению.

Знаки производных тут вообще не при чём.

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

Добавлено спустя 2 минуты 36 секунд:

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

[ewert]

Алексей К. писал(а):

Да и "обычный сплайн, мы, видимо понимаем по-разному. По мне, в "обычном сплайне" однозначность не требуется и не возникнет. Любого типа кривую "обычно сплайнуем".

Это (если я правильно Вас понял) совершенно разные неоднозначности. Сплайны строятся неоднозначно, если не заданы некие дополнительные условия, кроме сшивания. Но уж коли они построены, то они уже суть вполне однозначные функции.

[Алексей К.]

Да, согласен. (Просто не додумываю до конца --- гости уже на букву сц обозвали). Беру себя в руки, выключаю ЭВМ.

[artful7]

Спасибо за полезные рассуждения. Продолжим позднее.

Добавлено спустя 42 минуты 52 секунды:

Особенно заинтересовало следующее:

Алексей К. писал(а):

Решить кубическое уравнение (для данного участка $x_i\le X \le x_{i+1}$, описываемого ф-циями $x_i(t),\:y_i(t)$) $x_i(t_0)=X_i$, корень --- единственный --- должен найтись в пределах $0\le t_0 \le 1$ (альтернатива --- ошибка в программах) и вычислить $y(t_0)$.

[Алексей К.]

А что здесь интересного/непонятного? Пишите, не стесняйтесь... Может, Вы чего-то не понимаете (в известных вещах), может, мы (в постановке задачи), может, я где-то ракообразно выразился...

[artful7]

Цитата:

Может, Вы чего-то не понимаете (в известных вещах)

С данной темой только начал разбираться.

Добавлено спустя 1 минуту 33 секунды:

Цитата:

(альтернатива --- ошибка в программах)

Это к чему относилось?

[Алексей К.]

Ну, Ваша задача (в создавшемся у меня представлении) сильно напоминает программистскую деятельность (тянущую за собой относительно простую математику). Если описание кривой $y(x)$ (сплайнами ли, не-сплайнами ли) спрограммировано правильно, то упомянутый корень $0\le t_0 \le 1$ должен (а) быть и (б) быть в этом диапазоне единственным. Альтернатива --- ошибка в программах

[artful7]

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

[Алексей К.]

Либо 3 действительных, из которых один и только один будет, по Вашей задаче, в $t\in[0,1]$,
либо 1 действительный, который будет, по Вашей задаче, в $t\in[0,1]$.
По дискриминанту и коэффициентам количество действительный корней определяется сразу.
Вариант: убеждаетесь, что $x(t)$ монотонна на отрезке $[0,1]$ $(x'\ge 0)$, и ищете этот корешок сколь угодно точными приближёнными методами. Или по Кардано.

В суть эталонов и каркасов пока не проник, но Ваше акцентирование полиномов Бернштейна кажется излишним. По ewertу, аберрацией.

А подзадачка про определение ординаты --- вроде как совсем простая. Вас пугает кубическое уравнение?

[artful7]

Цитата:

Вас пугает кубическое уравнение?

Пугает не задачка, а усложнения, возникающие при ее решении. Вот если, например, решать ее по методу Кардано (сделал выкладки решения вчера ночью), то в итоге получается нехилая формула, причем, что особенно неприятно, необходимо делать сравнение дискриминантов Q^3 и R^2, что покажет количество корней и их тип (действ./компл.)!

Цитата:

и ищете этот корешок сколь угодно точными приближёнными методами.

Это дополнительные затраты времени. А значение координаты Y на кривой Безье мне нужно будет определить не один раз, а многократно, т.к. вычисление координат точки на кривой Безье предполагается использовать в составе итерационной процедуры оптимизации, следовательно, приближенные методы определения координат сильно затормозят работу всего алгоритма в целом!

Я тут на досуге рассудил (но еще не успел проверить) следующим образом. Если известно, что параметр $t$ в уравнениях параметрической кривой отвечает за пропорциональное положение (в долях от нуля до единицы) точек вычисления соответствующих значений $x$ параметрической кривой, то не лучше ли будет сразу найти такое значение $t_0$, лежащее в интервале $t\in[0,1]$, которое точно будет соответствовать положению заданной абсциссы $x_0$ (для которой требуется вычислить значение $y_0$) - об этом Вы уже говорили выше, но предлагали для этого решить кубическое уравнение $x_i(t_0)=X_i$.
Мне подумалось, что определение значения $t_0$, совпадающего с положением абсциссы $x_0$ можно осуществить исходя из пропорции:
$t_0 = \frac{{x_0 - a }}{{b - a }}$,
где $a$ и $b$ - соответственно начало и конец интервала (сегмента), на котором построена кривая (элементарная).

Таким образом, если $x_0$ совпадет с началом сегмента, то значение параметра $t_0=0$, а если $x_0$ совпадет с концом сегмента, то параметр $t_0=1$. Любое другое возможное значение абсциссы $x_0$ НА ДАННОМ ИНТЕРВАЛЕ(!) будет иметь соответствующее значение $t_0$, $t_0\in[0,1]$, пропорциональное длине интервала. В этом случае, получив величину $t_0$ найдем $y_0$.
Конечно же, перед вычислением значения $t_0$, необходимо будет очевидным способом определить, а на какой же именно сегмент составной кривой приходится значение заданной абсциссы $x_0$, иначе мы ошибочно попадем на "чужой" интервал (сегмент составной кривой) и, соответственно, на "чужие" параметрические уравнения соседнего сегмента.
Таким мне видится решение. Каково Ваше мнение?

[Алексей К.]

Удалил свои наезды (хотя и лёгкие, всё равно извиняюсь). Да, Вы правы, если сплайн строится как функция $y(x)$, то $x$ играет роль традиционного $t$, в смысле $t_0 = \frac{{x_0 - a }}{{b - a }}$, кубические уравнения отменяются (осознание этого случилось в очереди в магазине; сам слишком привык к кривым, описываемым парой $x(t),y(t)$...)

[artful7]

Значит, метОда имеет место быть?

[ewert]

Господи, сколько ж можно этот несчастный сплайн мурыжить.

Ну берём набор узлов ("сетку"): $x_0<x_1<x_2<\dots<x_n$ и соответствующие значения $y_0,\;y_1,\;y_2,\;\dots,\;y_n$ (произвольные). Рассматриваем один из отрезков $[x_{i-1};\;x_i]$, $i=1,2,\dots,n$ и обозначаем для него:

$h_i\equiv x_i-x_{i-1}$ -- длина отрезка;

$\widetilde v_i\equiv{y_i-y_{i-1}\over h_i}$ -- "средний наклон" на этом отрезке (т.е. наклон прямой, соединяющей эти две точки);

$S_i(x)$ -- кубический многочлен, представляющий сплайн на этом отрезке.

Кроме того, обозначим через $v_0,\;v_1,\;v_2,\;\dots,\;v_n$ "наклоны" сплайна, т.е. значения первой производной сплайна в соответствующих узлах. Тогда выражение для $S_i(x)$ на указанном участке будет вполне явным и довольно простым:

$$ S_i(x)=y_i + \widetilde v_i\;(x-x_i)+ $$

$$ + (v_{i-1}-\widetilde v_i){(x-x_{i-1})(x-x_{i})^2 \over h_i^2} + $$

$$ + (v_{i}-\widetilde v_i){(x-x_{i-1})^2(x-x_i) \over h_i^2}\;. $$

Здесь первая строчка задаёт линейную функцию, график которой проходит через узловые точки (т.е. интерполяционный многочлен первой степени). Если только эту строку и оставить, то получится кусочно-линейная аппроксимация, график которой -- это ломаная линия. Две последних строки -- это многочлены 3-й степени, устроенные так, чтобы значения производной в узлах оказались бы правильными: $S_i'(x_{i-1})=v_{i-i}$ и $S_i'(x_{i})=v_{i}$ для каждого $i$.

График того, что получилось, представляет собой гладкую кривую (один раз гладкую, т.е. гарантирована непрерывность только первой производной). При любом расположении узлов $\{x_i\}$ вид кривой однозначно определяется наборами узловых значений $\{y_i\}$ и наклонов $\{v_i\}$, которые тоже могут задаваться произвольно.

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

[Алексей К.]

В терминах контрольных точек желанная линейность $x(t)$ означает, что две контрольные точки с абсциссами $p_{1,2}$, $(a<p_1<p_2<b)$, разбивают Ваш отрезок $[a,b]$ на три равные части: $p_1=\frac{2a+b}{3},\;p_2=\frac{a+2b}{3}$. Играться можно только с ординатами.

[artful7]

Можно вопросик насчет NURBS?
В такого рода кривых (плоских) есть особые параметры, позволяющие существенно изменять форму отдельных участков кривой и, следовательно, всей кривой в целом. Но в плоских кривых NURBS требуются два отдельных параметрических уравнения (от параметра t), что иногда не совсем удобно. Так вот, хочу узнать, возможно ли построить кривую, которая будет описана в виде $y=f(x)$ и при этом иметь широкие возможности настройки, как у кривых NURBS.