Де Кастељау алгоритам

Де Кастељау алгоритам се користи за одређивање тачке $\alpha (t)$ на Безијеровој кривој, за неко $t\in [0,1]$. Назив је добио по Полу де Кастељау. Овај алгоритам се такође може применити за поделу једне Безијерове криве на две, у зависности од параметра $t$, а може се применити и за одређивање тангенте на Безијерову криву у тачки $\alpha (t)$.

Де-Кастељау алгоритам

Одређивање тачке на Безијеровој кривој степена 3, за t=0.6

Основна идеја де Кастељау-овог алгоритма је избор тачке $C$ на дужи $AB$ такве да $C$ дели дуж у размери $t:(1-t)$. Тада је тачка $C$, која дели дуж $AB$ у том односу, дата са:

$C=A+t{\overrightarrow {AB}}=A+t(B-A)=(1-t)A+tB\qquad (1)$

Означимо контролне тачке на следећи начин: $P_{00}=P_{0},P_{01}=P_{1},...,P_{0n}=P_{n}$, где први индекс означава број итерације (овде је $0$, а касније ће бити $1,2,...,n$).

Претпоставимо да желимо да одредимо тачку $\alpha (t)$, ѕа фиксирано $t\in [0,1]$. Почињемо од полигоналне линије $P_{00}-P_{01}-P_{02}-P_{03}-...-P_{0n}$ и користећи формулу $(1)$ налазимо тачку $P_{1i}$ која дели дуж одређену тачкама $P_{0i}$ и $P_{0(i+1)}$ у односу $t:(1-t)$. На овај начин добијамо $n$ тачака $P_{10},P_{11},P_{12},....,P_{1(n-1)}$ које дефинишу нову полигоналну линију састављену од $n-1$ дужи. Примењујући претходни поступак на нову полигоналну линију добијамо и другу линију од $n-1$ тачака $P_{20},P_{21},...,P_{2(n-2)}$ и $n-2$ дужи. Понављајући овај процес $n$ пута, добијамо једну тачку $P_{n0}$. Де Кастељау је доказао да је управо то тачка $\alpha (t)$ на кривој која одговара параметру $t$.

Кодови у програмском језику C

Итеративна имплементација де Кастељау алгоритма

     _tacka DeCasteljau(_tacka P[],int n,int t)
     {
      _tacka Q[MAX];
      int k;
     
      for(i=0;i<n;i++)
        Q[i]=P[i];
     
      for(k=1;k<n;k++)
        for(i=0;i<n-k;i++)
        {
          Q[i].x=(1-t)*Q[i].x+t*Q[t+1].x;
          Q[i].y=(1-t)*Q[i].y+t*Q[t+1].y;
        }
     
      return Q[0];
     }

Извршавање се врши по принципу илустрованом на слици.

Рекурзивна имплементација де Кастељау алгоритма

Претходно израчунавање може се извршити и рекурзивно. Нека су $P_{0j}$ контролне тачке $P_{j}$, за $j=0,1,...,n$. Свака следећа итерација (број итерације означава први индекс) се рачуна према следећој формули: $P_{ij}=(1-t)P_{i-1j}+tP_{i-1j+1}$ Користећи ову идеју, формирамо рекурзивну процедуру:

     tacka deCasteljau(int i, int j, tacka P[])
     {
       if(i == 0)
         return P[j];
       else
       {
         pom1 = deCasteljau(i-1,j);
         pom2 = deCasteljau(i-1,j+1);
         tacka T;
         T.x = pom1.x * (1-t) + pom2.x * t;
         T.y = pom1.y * (1-t) + pom2.y * t;
         return T;
       }
     }

Иако процедура делује једноставно и кратко, веома је неефикасна. Да би израчунали $P_{n0}$, позивамо функцију deCasteljau(n,0), а она се у ELSE делу позива још два пута. Проблем је у томе што се скоро све функције за рачунање $P_{ij}$ позивају више од једном. Сложеност овог израчунавања истоветна је сложености израчунавања n-тог члана Фибоначијевог низа. Сложеност се може поправити техником мемоизације, тако што би се одговорајуће вредности чувале и више пута користиле у поступку израчунавања.

Подела криве на два дела

Подела Безијерове криве на два дела - контролна полигонална линија левог дела криве

Подела Безијерове криве на два дела - контролна полигонална линија десног дела криве

Смисао поделе криве је да "исечемо" дату Безијерову криву у тачки $\alpha (t)$, за неко $t\in [0,1]$, на два дела, од којих је сваки и даље Безијерова крива. Резултујуће Безијерове криве морају задате су својим контролним тачкама, тако да се почетни скуп контролних тачака одбацује. Пошто се почетна крива степена $n$ дели на две криве, од којих је свака подскуп почетне $n$-димензионе Безијерове криве, и резултујуће криве морају бити $n$-тог степена.

Алгоритам за поделу Безијерове криве у тачки $\alpha (t)$ за фиксирано $t\in [0,1]$ се базира на де Кастељау алгориму за одређивање тачке $\alpha (t)$ на кривој.

Криву $\alpha$ делимо на две криве $\alpha _{1}$ и $\alpha _{2}$. Безијерова крива $\alpha _{1}$ је одређена конролним тачкама:

$\alpha _{1}:P_{0}=P_{00},P_{10},P_{20},...,P_{n0}=\alpha (t)$

Безијерова крива $\alpha _{2}$ је одређена конролним тачкама:

$\alpha _{2}:\alpha (t)=P_{n0},P_{(n-1)1},P_{(n-2)2},...,P_{0n}=P_{n}$

Подела криве има велики број примена. На пример, може се користити за одређивање пресека две Безијерове криве, рендеровање Безијерове криве, а и олакшава дизајн кривих.

Тангента на Безијерову криву

Де Кастељау алгоритам се може применити и за одређивање тангете на Безијерову криву у тачки $\alpha (t)$. Вектор правца тангенте представља вектор ${\overrightarrow {P_{(n-1)0}P_{(n-1)1}}}$.

Повећање степена криве

Повећање степена Безијерове криве

Однос на свакој дужи почетне полигоналне линије за n=3

Иако Безијерове криве вишег степена захтевају више времена за обраду, оне су погодније за дизајнирање различитих облика. Стога би било од велике помоћи да се повиси степен Безијерове криве без промене њеног облика. Очување облика криве је кључни захтев, јер, у супротном, повећање степена Безијерове криве не би имало практичног смисла.

Претпоставимо да имамо Безијерову криву степена $n$ одређену са $n+1$ контролних тачака $P_{0},P_{1},P_{2},...,P_{n}$ и да желимо да повисимо њен степен за $1$ без промене њеног облика. Како је Безијерова крива $n+1$-ог степена дефинисана са $n+2$ контролне тачке, потребно је да нађемо такав нови скуп контролних тачака. Нека је $Q_{0},Q_{1},Q_{2},...,Q_{n+1}$ нови скуп контролних тачака. Пошто почетак и крај криве остају фиксирани узимамо $Q_{0}=P_{0},Q_{n+1}=P_{n}$, а остале тачке се одређују користећи следећу формулу:

$Q_{i}={\frac {i}{n+1}}P_{i-1}+(1-{\frac {i}{n+1}})P_{i},\quad 1\leq i\leq n$

Свака дуж почетне полигоналне линије садржи тачно једну нову контролну тачку. Прецизније, дуж $P_{i-1}P_{i}$ садржи нову контролну тачку $Q_{i}$. Из формуле за рачунање нових контролних тачака, видимо да $Q_{i}$ дели дуж $P_{i-1}P_{i}$ у односу $(1-{\frac {i}{n+1}}):{\frac {i}{n+1}}$. За разлику од де Кастељау алгоритма, овај однос није константан већ зависи од вредности параметра $i$.

Кад добијемо скуп контролних тачака, почетни скуп може бити одбачен. Како свака дуж почетне полигоналне линије садржи нову контролну тачку, процес замене старог скупа новим може се посматрати као одсецање углова у почетним контролним тачкама.

Уколико желимо веће повећање степена криве, на пример за $k$, онда се овај поступак понавља $k$ пута. Степен криве може се повећавати док год то систем дозвољава, при чему се са повећањем броја контролних тачака полигонална линија приближава кривој.

Смањење степена Безијерове криве без промене њеног облика, у општем случају, није могуће. Степен криве је могуће смањити једино ако је степен претходно био повећан, тј. ако је та крива суштински крива мањег степена.

Литература

• Т. Шукиловић, С. Вукмировић (2015). Геометрија ѕа информатичаре. Математички факултет, Београд. стр. 143—147. ISBN 978-86-7589-106-2. 

Види још

• Безијерова крива
• Геометрија
• Крива
• Аналитичка геометрија

Спољашње везе

• де Кастељау алгоритам Архивирано на сајту Wayback Machine (27. јануар 2016)
• Повећање степена криве Архивирано на сајту Wayback Machine (3. фебруар 2016)