De Kasteljau algoritam

De Kasteljau algoritam se koristi za određivanje tačke $\alpha (t)$ na Bezijerovoj krivoj, za neko $t\in [0,1]$. Naziv je dobio po Polu de Kasteljau. Ovaj algoritam se takođe može primeniti za podelu jedne Bezijerove krive na dve, u zavisnosti od parametra $t$, a može se primeniti i za određivanje tangente na Bezijerovu krivu u tački $\alpha (t)$.

De-Kasteljau algoritam

Određivanje tačke na Bezijerovoj krivoj stepena 3, za t=0.6

Osnovna ideja de Kasteljau-ovog algoritma je izbor tačke $C$ na duži $AB$ takve da $C$ deli duž u razmeri $t:(1-t)$. Tada je tačka $C$, koja deli duž $AB$ u tom odnosu, data sa:

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

Označimo kontrolne tačke na sledeći način: $P_{00}=P_{0},P_{01}=P_{1},...,P_{0n}=P_{n}$, gde prvi indeks označava broj iteracije (ovde je $0$, a kasnije će biti $1,2,...,n$).

Pretpostavimo da želimo da odredimo tačku $\alpha (t)$, ѕa fiksirano $t\in [0,1]$. Počinjemo od poligonalne linije $P_{00}-P_{01}-P_{02}-P_{03}-...-P_{0n}$ i koristeći formulu $(1)$ nalazimo tačku $P_{1i}$ koja deli duž određenu tačkama $P_{0i}$ i $P_{0(i+1)}$ u odnosu $t:(1-t)$. Na ovaj način dobijamo $n$ tačaka $P_{10},P_{11},P_{12},....,P_{1(n-1)}$ koje definišu novu poligonalnu liniju sastavljenu od $n-1$ duži. Primenjujući prethodni postupak na novu poligonalnu liniju dobijamo i drugu liniju od $n-1$ tačaka $P_{20},P_{21},...,P_{2(n-2)}$ i $n-2$ duži. Ponavljajući ovaj proces $n$ puta, dobijamo jednu tačku $P_{n0}$. De Kasteljau je dokazao da je upravo to tačka $\alpha (t)$ na krivoj koja odgovara parametru $t$.

Kodovi u programskom jeziku C

Iterativna implementacija de Kasteljau algoritma

     _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];
     }

Izvršavanje se vrši po principu ilustrovanom na slici.

Rekurzivna implementacija de Kasteljau algoritma

Prethodno izračunavanje može se izvršiti i rekurzivno. Neka su $P_{0j}$ kontrolne tačke $P_{j}$, za $j=0,1,...,n$. Svaka sledeća iteracija (broj iteracije označava prvi indeks) se računa prema sledećoj formuli: $P_{ij}=(1-t)P_{i-1j}+tP_{i-1j+1}$ Koristeći ovu ideju, formiramo rekurzivnu proceduru:

     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;
       }
     }

Iako procedura deluje jednostavno i kratko, veoma je neefikasna. Da bi izračunali $P_{n0}$, pozivamo funkciju deCasteljau(n,0), a ona se u ELSE delu poziva još dva puta. Problem je u tome što se skoro sve funkcije za računanje $P_{ij}$ pozivaju više od jednom. Složenost ovog izračunavanja istovetna je složenosti izračunavanja n-tog člana Fibonačijevog niza. Složenost se može popraviti tehnikom memoizacije, tako što bi se odgovorajuće vrednosti čuvale i više puta koristile u postupku izračunavanja.

Podela krive na dva dela

Podela Bezijerove krive na dva dela - kontrolna poligonalna linija levog dela krive

Podela Bezijerove krive na dva dela - kontrolna poligonalna linija desnog dela krive

Smisao podele krive je da "isečemo" datu Bezijerovu krivu u tački $\alpha (t)$, za neko $t\in [0,1]$, na dva dela, od kojih je svaki i dalje Bezijerova kriva. Rezultujuće Bezijerove krive moraju zadate su svojim kontrolnim tačkama, tako da se početni skup kontrolnih tačaka odbacuje. Pošto se početna kriva stepena $n$ deli na dve krive, od kojih je svaka podskup početne $n$-dimenzione Bezijerove krive, i rezultujuće krive moraju biti $n$-tog stepena.

Algoritam za podelu Bezijerove krive u tački $\alpha (t)$ za fiksirano $t\in [0,1]$ se bazira na de Kasteljau algorimu za određivanje tačke $\alpha (t)$ na krivoj.

Krivu $\alpha$ delimo na dve krive $\alpha _{1}$ i $\alpha _{2}$. Bezijerova kriva $\alpha _{1}$ je određena konrolnim tačkama:

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

Bezijerova kriva $\alpha _{2}$ je određena konrolnim tačkama:

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

Podela krive ima veliki broj primena. Na primer, može se koristiti za određivanje preseka dve Bezijerove krive, renderovanje Bezijerove krive, a i olakšava dizajn krivih.

Tangenta na Bezijerovu krivu

De Kasteljau algoritam se može primeniti i za određivanje tangete na Bezijerovu krivu u tački $\alpha (t)$. Vektor pravca tangente predstavlja vektor ${\overrightarrow {P_{(n-1)0}P_{(n-1)1}}}$.

Povećanje stepena krive

Povećanje stepena Bezijerove krive

Odnos na svakoj duži početne poligonalne linije za n=3

Iako Bezijerove krive višeg stepena zahtevaju više vremena za obradu, one su pogodnije za dizajniranje različitih oblika. Stoga bi bilo od velike pomoći da se povisi stepen Bezijerove krive bez promene njenog oblika. Očuvanje oblika krive je ključni zahtev, jer, u suprotnom, povećanje stepena Bezijerove krive ne bi imalo praktičnog smisla.

Pretpostavimo da imamo Bezijerovu krivu stepena $n$ određenu sa $n+1$ kontrolnih tačaka $P_{0},P_{1},P_{2},...,P_{n}$ i da želimo da povisimo njen stepen za $1$ bez promene njenog oblika. Kako je Bezijerova kriva $n+1$-og stepena definisana sa $n+2$ kontrolne tačke, potrebno je da nađemo takav novi skup kontrolnih tačaka. Neka je $Q_{0},Q_{1},Q_{2},...,Q_{n+1}$ novi skup kontrolnih tačaka. Pošto početak i kraj krive ostaju fiksirani uzimamo $Q_{0}=P_{0},Q_{n+1}=P_{n}$, a ostale tačke se određuju koristeći sledeću formulu:

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

Svaka duž početne poligonalne linije sadrži tačno jednu novu kontrolnu tačku. Preciznije, duž $P_{i-1}P_{i}$ sadrži novu kontrolnu tačku $Q_{i}$. Iz formule za računanje novih kontrolnih tačaka, vidimo da $Q_{i}$ deli duž $P_{i-1}P_{i}$ u odnosu $(1-{\frac {i}{n+1}}):{\frac {i}{n+1}}$. Za razliku od de Kasteljau algoritma, ovaj odnos nije konstantan već zavisi od vrednosti parametra $i$.

Kad dobijemo skup kontrolnih tačaka, početni skup može biti odbačen. Kako svaka duž početne poligonalne linije sadrži novu kontrolnu tačku, proces zamene starog skupa novim može se posmatrati kao odsecanje uglova u početnim kontrolnim tačkama.

Ukoliko želimo veće povećanje stepena krive, na primer za $k$, onda se ovaj postupak ponavlja $k$ puta. Stepen krive može se povećavati dok god to sistem dozvoljava, pri čemu se sa povećanjem broja kontrolnih tačaka poligonalna linija približava krivoj.

Smanjenje stepena Bezijerove krive bez promene njenog oblika, u opštem slučaju, nije moguće. Stepen krive je moguće smanjiti jedino ako je stepen prethodno bio povećan, tj. ako je ta kriva suštinski kriva manjeg stepena.

Literatura

• T. Šukilović, S. Vukmirović (2015). Geometrija ѕa informatičare. Matematički fakultet, Beograd. str. 143—147. ISBN 978-86-7589-106-2. 

Vidi još

• Bezijerova kriva
• Geometrija
• Kriva
• Analitička geometrija

Spoljašnje veze

• de Kasteljau algoritam Arhivirano na sajtu Wayback Machine (27. januar 2016)
• Povećanje stepena krive Arhivirano na sajtu Wayback Machine (3. februar 2016)