Гладки криви

Гладки криви

Видове

Често се налага в геометрията по дадени $n$ точки да се построи крива, която минава през или близо до точките, но не е начупена. Т.е в някава степен е гладка.

Най-често гладките криви се делят на 2 групи:

Интерполационни

Тези криви минават точно през изначално зададените точки. Хубав пример за това е Полиномът на Лагранж. »някой да сложи картинка« ( сложих ;) )

Апроксимационни

Тези криви не минават точно през зададените точки, но в някакъв смисъл минават близо до тях. Колко точно близко минават до точки и какви свойства притежават зависи от вида на кривата. Ще разгледаме Криви на Безие и Б-сплайн.

Криви на Безие

Примери

Да разгледаме пример за крива на безие по дадени 3 и 4 точки.

Формална дефиниция

Нека е дадено множество от $n + 1$ точки $P = \{ p_0, p_1, \cdots, p_n \}$. Дефинираме следната функция:

(1)

\begin{align} p(t) = \sum_{i=0}^{n} p_i \binom{n}{i} t^i (1-t)^{n-i} \end{align}

Та, Кривата на Безие (за $n + 1$ точки) се получава, като заместите във формулата $p(t)$ с всяко $t \in [0, 1]$.

Свойства

• Кривата започва от $p_0$ и завършва в $p_n$.

Просто заместете във формулата с $t = 0$ и $t = 1$ и ще получите точно това.

• Кривата е непрекъсната

Функцията е непрекъсната по всяка от координатите, следователно е непрекъсната самата крива. »по-подробно обяснение« (Ако има някой, който си е взел Анализ 2, може би ще помни, че функция на n аргумента наричаме непрекъсната, когато е непрекъсната по всеки един от аргументите си.)

• Кривата принадлежи на изпъкналата обвивка

Както виждате във формулата участва сума на точките $p_i$ умножени по някакъв коефициент $\lambda_i = \binom{n}{i} t^i (1-t)^{n-i}$. Умножаването и сбора на точка по коефициент е както си го знаем от алгебрата (т.е по координатно).
Тези коефициенти притежават интересното свойство, че сумата им е 1, т.е

(2)

\begin{align} \sum_{i=0}^{n} \lambda_i = \sum_{i=0}^{n} \binom{n}{i} t^i (1-t)^{n-i} = (t + (1 - t)) ^ n = 1 ^ n = 1 \end{align}

Използвахме формулата за развитие на бином от $n$-та степен с биномни коефициенти.

T.e $p(t)$ е линейна комбинация на точките, сбора от коефициентите пред които е точно 1. Ако си припомните какво е изпъкнала обвивка, ще видите, че точно това е дефиницията точка да принадлежи на изпъклата обвивка на дадени точки. Така получихме, че всички точки $p(t)$ принадлежат на изпъкналата обвивка на даденото множество.

• Допирателната към кривата в началото е колинеарна на вектора $\overrightarrow{p_0 p_1}$. Допирателната към кривата в края е колинеарна на вектора $\overrightarrow{p_{n-1} p_n}$. Да разпишем производната на функцията $p(t):$

(3)

\begin{eqnarray} p'(t) &=& \Big( \sum_{i=0}^n p_i \binom{n}{i} t^i (1-t)^{n-i} \Big)' \\ &=& \Big( p_0 \binom{n}{0} t^0 (1-t)^n + \sum_{i=1}^{n-1} p_i \binom{n}{i} t^i (1-t)^{n-i} + p_n \binom{n}{n} t^n (1-t)^0 \Big)' \\ &=& (p_0 . 1 . 1 . (1-t)^n)' + \Big( \sum_{i=1}^{n-1} p_i \binom{n}{i} t^i (1-t)^{n-i} \Big)' + (p_n . 1 . t^n . 1)' \\ &=& - n p_0 (1-t)^{n-1} + \sum_{i=1}^{n-1} p_i \binom{n}{i} \big[(t^i(1-t)^{n-i})'\big] + n p_n t ^ {n-1} \\ &=& - n p_0 (1-t)^{n-1} + \sum_{i=1}^{n-1} p_i \binom{n}{i} \big[i t^{i-1} (1-t)^{n-i} - (n-i)t^i(1-t)^{n-i-1}\big] + n p_n t ^ {n-1} \end{eqnarray}

Сега остава да заместите в производната при $t = 0 / 1$:

(4)

\begin{eqnarray} p'(0) &=& -n p_0 + n p_1 = n \overrightarrow{p_0 p_1} \\ p'(1) &=& np_n - np_{n-1} = n \overrightarrow{p_{n-1}p_n} \end{eqnarray}

• Кривите на Безие могат да се изчисляват и рекурентно (de Casteljau's algorithm):

Да разгледаме уравнението на крива на Безие на $n + 1$ точки.

(5)

\begin{eqnarray} p(t) &=& \sum_{i=0}^{n} p_i \binom{n}{i} t^i (1-t)^{n-i} \\ &=& (1-t)^n p_0 + \sum_{i=1}^{n-1} p_i \binom{n}{i} t^i (1-t)^{n-i} + t^n p_n \\ &=& (1-t)^n p_0 \binom{n-1}{0} + \sum_{i=1}^{n-1} p_i \left[\binom{n-1}{i} + \binom{n-1}{i-1} \right] t^i (1-t)^{n-i} + t^n p_n \\ &=& (1-t)^n p_0 \binom{n-1}{0} + \sum_{i=1}^{n-1} p_i \binom{n-1}{i} t^i (1-t)^{n-i} + \sum_{i=1}^{n-1} p_i \binom{n-1}{i-1} t^i (1-t)^{n-i} + t^n p_n \binom{n-1}{n-1}\\ &=& (1-t)\left[ \sum_{i=0}^{n-1} p_i \binom{n-1}{i} t^i (1-t)^{n-i-1}\right] \\ &+& t \left[ \sum_{i=1}^{n} p_i \binom{n-1}{i-1} t^{i-1}(1-t)^{n-i} \right] \end{eqnarray}

Което, какво виждате, е коефициент, умножен по формулата за крива на Безие на първите $n$ точки + коефициент по уравнението на кривата за последните $n$ точки.

Употреба

някой да обясни за какво се използва това и как се е стигнало до неговото въвеждане във тази му форма

Това е най-универсалната крива в професионалната компютърна графика. Въведена е в практиката от Adobe при създаването на Postscript - независим от възпроизвеждащото устройство език за описание на страници. Всички важни предпечатни програми работят с криви на Безие - Adobe Illustrator, Corel Draw и т.н. Защо точно те? Защото са най-интуитивни. Използва вариант с 4 точки - начална и крайна плюс 2 междинни. Преимуществото е, че кривата минава през 2-те крайни, а междинните играят ролята на "магнити", с които лесно се управлява формата на кривата. Освен това всяка мислима крива може да се представи като краен брой свързани помежду си такива 4-точкови Безие криви и много лесно се управлява гладкостта в мястото на свързването. На практика всички надписи, лога и изобщо цялата векторна графика, която виждате по печатни материали, телевизия и т.н. е изградена от криви на Безие.

«

Б-сплайн

Тези криви доста приличат на кривите на Безие. По дадени $k+1$ точки в измерение $d$ (обикновенно 2 и 3):

(6)

\begin{eqnarray} P = \{ p_0, p_1, \cdots, p_k \} \subseteq \mathbb R^d \end{eqnarray}

(7)

\begin{eqnarray} p(t) = \sum_{i=0}^{k} p_i N_{i, m}(t) \quad t \in [0, 1] \end{eqnarray}

Т.е имаме линейна комбинация на точките, като тук коефициентът е записан като $N_{i, m}(t)$. Както и при кривите на Безие коефициентът $t$ показва къде по линията ще се намира точката - т.е това е една функция, в която ако заместим с всяко $t \in [0, 1]$ ще получим всички точки от кривата.

Ще разбием интервала $[0, 1]$ на $m + k + 1$ части : $0 = t_0 < t_1 < \cdots < t_{m+k+1} = 1$. Ако частите имат еднаква дължина (т.е $t_{j+1} - t_j = h$) сплайнът се нарича равномерен.

Коефициентите

Остана да разгледаме най-важното - а именно какви точно са коефициентите във формулата на Б-сплайн-а. Ще ги дефинираме рекурентно спрямо параметъра $m$, който всъщност показва от коя степен е самият сплайн. Най-често се използват степени 2 и 3, но може и всяка друга. (заб. - при $m = 1$ се получава начупена линия).

(8)

\begin{eqnarray} N_{i, 0}(t) = \begin{cases} 1 & t_i \le t \le t_{i+1} \\ 0 & else \end{cases} \end{eqnarray}

(9)

\begin{eqnarray} N_{i, m}(t) = \begin{cases} \dfrac{t-t_i}{t_{i+m}-t_i} N_{i, m-1}(t) + \dfrac{t_{i+m+1}-t}{t_{i+m+1}-t_{i+1}} N_{i+1, m-1}(t) & t \in [t_i, t_{i+m+1}] \\ 0 & else \end{cases} \end{eqnarray}

Формулата изглежда доста сложна, но в интерес на истината … не е. При криви на Безие всяка една точка от кривата зависеше от всички останали и кривите ставаха доста размити - губи се пълна представа за това къде са контролните точки. При Б-сплайн всяка една точка зависи точно от $m+1$ други ($m$ беше степента на сплайна - т.е колко размазан да бъде). Например при $m = 1$ всяка точка зависи от 2те между които се намира (в начупена линия). При $m = 2$ всяка точка ще зависи от точно 3 други, като по този начин кривите ще се загладят, защото точките ще 'гледат напред' и в тях ще има информация на къде ще завие сплайна 'в близко бъдеще'.

Ще докажем, че точките от Б-сплайна лежат в изпъкналата обвивка на контролните точки (т.е сбора от коефициентите е 1). Нещо повече - тъй като коефициентите само пред $m+1$ последователни точки са различни от 0, то Б-сплайна винаги ще лежи в изпъкналата обвивка на $m+1$ точки, като при $t$ преминаващо през някое $t_i$ новите точки ще зависят от следващите $m+1$ контролни (т.е изпада една стара контролна и влиза една нова).

Твърдение:

(10)

\begin{align} \sum_i^k N_{i, m} (t) = 1 \end{align}

Доказателство:
Да сумираме 2 произволни последователни коефициента:

(11)

\begin{eqnarray} N_{i-1,m}(t) + N_{i, m}(t) &=& \frac{t - t_{i-1}}{t_{i+m-1} - t_{i-1}} N_{i-1,m-1}(t) + \frac{t_{i+m} - t}{t_{i+m} - t_i} N_{i, m-1}(t) \\ &+& \frac{t - t_{i}}{t_{i+m} - t_{i}} N_{i,m-1}(t) + \frac{t_{i+m+1} - t}{t_{i+m+1} - t_{i+1}} N_{i+1, m-1}(t) \\ &=& \frac{t - t_{i-1}}{t_{i+m-1} - t_{i-1}} N_{i-1,m-1}(t) + \underbrace{\left[ \frac{t_{i+m} - t}{t_{i+m} - t_i} + \frac{t - t_{i}}{t_{i+m} - t_{i}} \right]}_{1}N_{i, m-1}(t) + \frac{t_{i+m+1} - t}{t_{i+m+1} - t_{i+1}} N_{i+1, m-1}(t) \\ &=& \frac{t - t_{i-1}}{t_{i+m-1} - t_{i-1}} N_{i-1,m-1}(t) + N_{i, m-1}(t) + \frac{t_{i+m+1} - t}{t_{i+m+1} - t_{i+1}} N_{i+1, m-1}(t) \\ \end{eqnarray}

Може да обобщим за сума на няколко последователни:

(12)

\begin{eqnarray} \sum_{i=j}^{r} = \frac{t-t_i}{t_{j+m}-t_j}N_{j,m-1}(t) + \sum_{i=j+1}^{r} N_{i,m-1}(t) + \frac{t_{r+m+1}-t}{t_{r+m+1} - t_{r+1}} N_{r+1, m-1}(t) \end{eqnarray}

Сега просто остава да съберем всички коефициенти и ще получим… сумата от всички коефициенти за по-малката степен $m - 1$. Правим това докато степента не стане 0. От дефиницията ясно личи, че сумата е 1.
Да вярно в началото и края има малко боклук, но мисля че проблемът може да се реши като мислено си добавим фиктивни коефициенти в началото и края, които са 0. Или с Водка.