2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему
 
 Взаимосвязь кубического сплайна и кривой Безье...
Сообщение24.01.2011, 22:32 


23/09/08
8
Взаимосвязь кубического сплайна и кривой Безье... третьего порядка.

Кто-нибудь мог бы объяснить популярно взаимосвязь между этими кривыми?
По сути ведь, кривая Безье является кубическим сплайном, с необычным способом задания.

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

 Профиль  
                  
 
 Re: Взаимосвязь кубического сплайна и кривой Безье...
Сообщение24.02.2011, 00:28 
Модератор
Аватара пользователя


16/02/11
3788
Бурашево
Кривая Безье является параметрической кривой, рассматривается как совокупность своих элементарных фрагментов. Фрагмент кривой Безье порядка $n$ описывается выражением:
$$\overrightarrow{r}_{i}(t)=\sum\limits_{k=0}^nB_{k}^n(t)\overrightarrow{P}_k^{(i)}$$ где $\overrightarrow{r}_{i}(t)$ - радиус-вектор точек фрагмента, $B_{k}^n(t)$ - многочлен Бернштейна; $\overrightarrow{P}_k$ - опорные векторы; $t\in\left[0,1\right]$ - параметр.
В случае кривой третьего порядка $$\overrightarrow{r}_{i}(t)=(((1-t)\overrightarrow{P}_0^{(i)}+3t\overrightarrow{P}_1^{(i)})(1-t)+3t^2\overrightarrow{P}_2^{(i)})(1-t)+t^3\overrightarrow{P}_3^{(i)}$$ Элементраный фрагмент кривой Безье третьего порядка определяется четырмя опорными векторами. При заданной совокупности опорных векторов $\overrightarrow{P}_n,n=0,...,N-1$ кривая Безье формируется так, что первый фрагмент строится на векторах $\overrightarrow{P}_0, \overrightarrow{P}_1, \overrightarrow{P}_2, \overrightarrow{P}_3$, то есть:
$\overrightarrow{P}_0^{(0)}=\overrightarrow{P}_0$,
$\overrightarrow{P}_1^{(0)}=\overrightarrow{P}_1$,
$\overrightarrow{P}_2^{(0)}=\overrightarrow{P}_2$,
$\overrightarrow{P}_3^{(0)}=\overrightarrow{P}_3$.

Следующий фрагмент на $\overrightarrow{P}_3, \overrightarrow{P}_4, \overrightarrow{P}_5, \overrightarrow{P}_6$, то есть
$\overrightarrow{P}_0^{(1)}=\overrightarrow{P}_3$,
$\overrightarrow{P}_1^{(1)}=\overrightarrow{P}_4$,
$\overrightarrow{P}_2^{(1)}=\overrightarrow{P}_5$,
$\overrightarrow{P}_3^{(1)}=\overrightarrow{P}_6$.

И тд.
Кривая Безье является непрерывной, однако её гладкость зависит от расположения опорных векторов:
1. Кривая имеет непрерывную касательную ($G^1$ - гладкая), если вершины векторов $\overrightarrow{P}_{3n-1}, \overrightarrow{P}_{3n}, \overrightarrow{P}_{3n+1}$ лежат на одной прямой.
2. Кривая имеет непрерывный вектор кривизны ,($G^2$ - гладкая) если вершины векторов $\overrightarrow{P}_{3n-2}, \overrightarrow{P}_{3n-1}, \overrightarrow{P}_{3n}, \overrightarrow{P}_{3n+1}, \overrightarrow{P}_{3n+2}$ лежат в одной плоскости.

Кривая Безье, таким образом, может являться сплайн-кривой только при определённом расположении вершин опорных векторов.

При построении кубической сплайн-кривой каждый её фрагмент также строится на 4-х опорных векторах, но формирование кривой соверешенно иное:
первый фрагмент строится на векторах $\overrightarrow{P}_0, \overrightarrow{P}_1, \overrightarrow{P}_2, \overrightarrow{P}_3$, то есть:
$\overrightarrow{P}_0^{(0)}=\overrightarrow{P}_0$,
$\overrightarrow{P}_1^{(0)}=\overrightarrow{P}_1$,
$\overrightarrow{P}_2^{(0)}=\overrightarrow{P}_2$,
$\overrightarrow{P}_3^{(0)}=\overrightarrow{P}_3$.

Следующий фрагмент на $\overrightarrow{P}_1, \overrightarrow{P}_2, \overrightarrow{P}_3, \overrightarrow{P}_4$, то есть:
$\overrightarrow{P}_0^{(1)}=\overrightarrow{P}_1$,
$\overrightarrow{P}_1^{(1)}=\overrightarrow{P}_2$,
$\overrightarrow{P}_2^{(1)}=\overrightarrow{P}_3$,
$\overrightarrow{P}_3^{(1)}=\overrightarrow{P}_4$.

И тд.
В случае кубической сплайн-кривой независимо от расположения опорных векторов обеспечивается $C^2$ - гладкость.
Существует метод преобразования опорных векторов кубической сплайн-кривой в набор опорных векторов для кривой Безье, обеспечивающий их совпадение. Подробнее см. Шикин Е.В., Плис А.И. Кривые и поверхности на экране компьютера. Руководство по сплайнам для пользователей. - М.: ДИАЛОГ-МИФИ, 1996.

Для определения опорных векторов по заданным точкам, через которые должна проходить кривая Безье, предлагаю следующее. Обозначим $\overrightarrow{r}_m, m=0,...,M-1$ - радиус-векторы исходных точек. Первый элементарный фрагмент кривой Безье будет проходить через вершины $\overrightarrow{r}_0,\overrightarrow{r}_1,\overrightarrow{r}_2,\overrightarrow{r}_3$. Потребуем, чтобы первый вектор соответствовал значению параметра $t=0$, второй вектор $t=\frac 1 3$, третий $t=\frac 2 3$, четвёртый $t=1$:
$\overrightarrow{r}_{0}(0)=$\overrightarrow{r}_0
$\overrightarrow{r}_{0}(\frac 1 3)=$\overrightarrow{r}_1
$\overrightarrow{r}_{0}(\frac 2 3)=$\overrightarrow{r}_2
$\overrightarrow{r}_{0}(1)=$\overrightarrow{r}_3

Причём, с учётом общих свойств кривых Безье, $\overrightarrow{P}_0^{(0)}=\overrightarrow{r}_0$ и $\overrightarrow{P}_3^{(0)}=\overrightarrow{r}_3$.
Решая записанную систему линейных уравнений получим опорные векторы $\overrightarrow{P}_0^{(0)}, \overrightarrow{P}_1^{(0)}, \overrightarrow{P}_2^{(0)}, \overrightarrow{P}_3^{(0)}$.
Опорные векторы следующего элементарного фрагмента $\overrightarrow{P}_0^{(1)}, \overrightarrow{P}_1^{(1)}, \overrightarrow{P}_2^{(1)}, \overrightarrow{P}_3^{(1)}$ определяются из аналогичной системы уравнений:
$\overrightarrow{r}_{1}(0)=$\overrightarrow{r}_3
$\overrightarrow{r}_{1}(\frac 1 3)=$\overrightarrow{r}_4
$\overrightarrow{r}_{1}(\frac 2 3)=$\overrightarrow{r}_5
$\overrightarrow{r}_{1}(1)=$\overrightarrow{r}_6,

причём $\overrightarrow{P}_0^{(1)} = \overrightarrow{P}_3^{(0)}=\overrightarrow{r}_3$ и $\overrightarrow{P}_3^{(1)}=\overrightarrow{r}_6$
и тд.

 Профиль  
                  
 
 Re: Взаимосвязь кубического сплайна и кривой Безье...
Сообщение24.02.2011, 15:36 


29/09/06
4552
knkd в сообщении #404021 писал(а):
Взаимосвязь кубического сплайна и кривой Безье... третьего порядка.

Кто-нибудь мог бы объяснить популярно взаимосвязь между этими кривыми?
Кубический сплайн (в смысле, кривая, проходящая строго через $N$ заданных точек, пстроенная по известному алгоритму, зависящему от граничных условий, итд) состоит из $N-1$ кривых Безье: одна кривая Безье для каждой соседней пары точек. Можно считать, что при построении сплайна на каждом участке вычисляются две новые (контрольные) точки. А можно считать, что при построении сплайна на каждом участке вычисляются коэффициенты полиномов
$$x(t)=a_0+a_1t+a_2t^2+a_3t^3,\quad y(t)=b_0+b_1t+b_2t^2+b_3t^3.$$ Эти два способа задания кривой эквивалентны, от одного можно перейти к другому, более удобному в конкретном контексте.

Цитата:
Аппроксимация точек кубическими сплайнами, задача тривиальная, но вот в плане перехода после этого к кривым Безье, как раз и заминка.
А это ещё тривиальнее: на каждой дуге сплайна (я не добавляю этой индексации) Вам надо перейти от
$$x(t)=a_0+a_1t+a_2t^2+a_3t^3\quad\text{к}\quad x(t)=x_0(1-t)^3+3x_1(1-t)^2t+3x_2(1-t)t^2+x_3t^3,$$и аналогично для $y$. Что довольно легко: распишите вторую правую часть и приравняйте к первой, т.е. приравняйте коэффициенты при одинаковых степенях $t$. Найденные $(x_1,y_1)$ и $(x_2,y_2)$ будут Вашими новыми контрольными точками на данном куске сплайна.

Если, конечно, я Вас правильно понял. Уж больно смущает эта странная фраза:
Цитата:
По сути ведь, кривая Безье является кубическим сплайном, с необычным способом задания.

 Профиль  
                  
 
 Re: Взаимосвязь кубического сплайна и кривой Безье...
Сообщение24.02.2011, 15:44 
Заслуженный участник


11/05/08
32166
Кривая Безье -- это не сплайн. Во-первых, это лишь кусочек сплайна. Во-вторых, сплайн в обычном понимании -- это скалярная функция, а кривая Безье задаётся векторной.

 Профиль  
                  
 
 Re: Взаимосвязь кубического сплайна и кривой Безье...
Сообщение14.06.2011, 12:31 


23/09/08
8
ewert в сообщении #416646 писал(а):
Кривая Безье -- это не сплайн. Во-первых, это лишь кусочек сплайна.

Я неудачно выразился.

В общем задача решена, всем спасибо за помощь.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group