http___fmi.wikidot.com_okg-curves_1.xml
http___aga2012.wikidot.com_dimension-formula.xml
1.1 2.1 3.1 3.2 4.1 5.1 6.1 6.2 6.3 7.1 8.1 8.2 8.3 9.1 10.1 11.1 12.1 13.1 13.2 14.1 15.1 16.1 17.1 18.1 19.1 19.2 20.1 21.1 21.2 22.1 23.1 24.1 24.2 24.3 25.1 25.2 25.3 26.1 27.1 28.1 29.1 30.1 31.1 32.1 32.2 32.3 32.4 32.5 32.6 32.7 32.8 32.9 34.1 35.1 35.2 36.1 36.2 37.1 37.2 38.1 39.1 39.2 39.3 39.4 40.1 40.2 40.3 40.4 40.5 41.1 41.2 42.1 43.1 44.1 45.1 46.1 46.2 46.3 47.1 47.2
Гладки криви Видове Често се налага в геометрията по дадени $n$ точки да се построи крива, която минава през или близо до точките, но не е начупена. Т.е в някава степен е гладка. Най-често гладките криви се делят на 2 групи: Интерполационни Тези криви минават точно през изначално зададените точки. Хубав пример за това е Полиномът на Лагранж. »някой да сложи картинка« ( сложих ;) ) Апроксимационни Тези криви не минават точно през зададените точки, но в някакъв смисъл минават близо до тях. Колко точно близко минават до точки и какви свойства притежават зависи от вида на кривата. Ще разгледаме Криви на Безие и Б-сплайн. Криви на Безие Примери Да разгледаме пример за крива на безие по дадени 3 и 4 точки. Формална дефиниция Нека е дадено множество от $n + 1$ точки $P = \{ p_0, p_1, \cdots, p_n \}$. Дефинираме следната функция:(1) Та, Кривата на Безие (за $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, т.е Използвахме формулата за развитие на бином от $n$-та степен с биномни коефициенти. T.e $p(t)$ е линейна комбинация на точките, сбора от коефициентите пред които е точно 1. Ако си припомните какво е изпъкнала обвивка, ще видите, че точно това е дефиницията точка да принадлежи на изпъклата обвивка на дадени точки. Така получихме, че всички точки $p(t)$ принадлежат на изпъкналата обвивка на даденото множество. - Допирателната към кривата в началото е колинеарна на вектора $\overrightarrow{p_0 p_1}$. Допирателната към кривата в края е колинеарна на вектора $\overrightarrow{p_{n-1} p_n}$. Да разпишем производната на функцията $p(t):$ Сега остава да заместите в производната при $t = 0 / 1$:(4) - Кривите на Безие могат да се изчисляват и рекурентно (de Casteljau's algorithm): Да разгледаме уравнението на крива на Безие на $n + 1$ точки.(5) Което, какво виждате, е коефициент, умножен по формулата за крива на Безие на първите $n$ точки + коефициент по уравнението на кривата за последните $n$ точки. Употреба някой да обясни за какво се използва това и как се е стигнало до неговото въвеждане във тази му форма Това е най-универсалната крива в професионалната компютърна графика. Въведена е в практиката от Adobe при създаването на Postscript - независим от възпроизвеждащото устройство език за описание на страници. Всички важни предпечатни програми работят с криви на Безие - Adobe Illustrator, Corel Draw и т.н. Защо точно те? Защото са най-интуитивни. Използва вариант с 4 точки - начална и крайна плюс 2 междинни. Преимуществото е, че кривата минава през 2-те крайни, а междинните играят ролята на "магнити", с които лесно се управлява формата на кривата. Освен това всяка мислима крива може да се представи като краен брой свързани помежду си такива 4-точкови Безие криви и много лесно се управлява гладкостта в мястото на свързването. На практика всички надписи, лога и изобщо цялата векторна графика, която виждате по печатни материали, телевизия и т.н. е изградена от криви на Безие. Б-сплайн Тези криви доста приличат на кривите на Безие. По дадени $k+1$ точки в измерение $d$ (обикновенно 2 и 3):(6) Т.е имаме линейна комбинация на точките, като тук коефициентът е записан като $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) Формулата изглежда доста сложна, но в интерес на истината … не е. При криви на Безие всяка една точка от кривата зависеше от всички останали и кривите ставаха доста размити - губи се пълна представа за това къде са контролните точки. При Б-сплайн всяка една точка зависи точно от $m+1$ други ($m$ беше степента на сплайна - т.е колко размазан да бъде). Например при $m = 1$ всяка точка зависи от 2те между които се намира (в начупена линия). При $m = 2$ всяка точка ще зависи от точно 3 други, като по този начин кривите ще се загладят, защото точките ще 'гледат напред' и в тях ще има информация на къде ще завие сплайна 'в близко бъдеще'. Ще докажем, че точките от Б-сплайна лежат в изпъкналата обвивка на контролните точки (т.е сбора от коефициентите е 1). Нещо повече - тъй като коефициентите само пред $m+1$ последователни точки са различни от 0, то Б-сплайна винаги ще лежи в изпъкналата обвивка на $m+1$ точки, като при $t$ преминаващо през някое $t_i$ новите точки ще зависят от следващите $m+1$ контролни (т.е изпада една стара контролна и влиза една нова). Твърдение:(10) Доказателство: Да сумираме 2 произволни последователни коефициента: Може да обобщим за сума на няколко последователни:(12) Сега просто остава да съберем всички коефициенти и ще получим… сумата от всички коефициенти за по-малката степен $m - 1$. Правим това докато степента не стане 0. От дефиницията ясно личи, че сумата е 1. Да вярно в началото и края има малко боклук, но мисля че проблемът може да се реши като мислено си добавим фиктивни коефициенти в началото и края, които са 0. Или с Водка.
1.1 2.1 3.1 4.1 4.2 4.3 4.4
Find a formula for the dimension of the resultant polytope $\mathcal{A}$ in terms of $n$ and $m$. Hint: What is the dimension of the lineality space of the normal fan? Solution: The ambient space has dimension $m$, since this is the number of vertices in all the polytopes, each of which must be assigned a weight. There is a linear space of dimension 1 for each polytope which corresponds to translations of all the points. Additionally there is a linear space of dimension $n$ corresponding to linear transformations on all of the polytopes together in each of the $n$ directions. The resultant polytope therefore sits in a codimension $n+1+n$ subspace, so has dimension $m-2n-1$.