Geometrie/Racionální algoritmus de Boor

De Boor algoritmus

Bod na [[../Racionální B–spline křivka|racionální B-spline křivce]] můžeme stejně jako u racionálních Bézierových křivek spočítat hned dvěma způsoby.

1. Pomocí algoritmu de Boor pro racionální křivky:

Zvolíme-li $u\in ⟨u_i,u_{i+1}⟩$, pak bod na racionální B-spline křivce vypočteme opakovanou lineární interpolací:

$P_i^j\left(u\right)=(1-{\alpha }_i^j)\cdot \frac{{\omega }_{i-1}^{j-1}}{{\omega }_i^j}\cdot P_{i-1}^{j-1}+{\alpha }_i^j\cdot \frac{{\omega }_i^{j-1}}{{\omega }_i^j}\cdot P_i^{j-1}$,

kde

${\omega }_i^j\left(u\right)=(1-{\alpha }_i^j)\cdot {\omega }_{i-1}^{j-1}+{\alpha }_i^j\cdot {\omega }_i^{j-1}$

a

${\alpha }_i^j=\frac{u-u_i}{u_{i+k-j+1}}$, $i=1-k,\dots ,1$ a $P_i^0=P_i$.

Bod $P_1^k\left(u\right)=P\left(u\right)$ je hledaný bod racionální B-spline křivky.

Toto rozšíření algoritmu de Boor vzniklo obdobným způsobem jako rozšíření algoritmu de Casteljau pro Bézierovy křivky.

2. Převodem na neracionální křivku a zpětným promítnutím:

Převedeme racionální B-spline na neracionální (o jednu dimenzi výše), provedeme de Boor algoritmus pro neracionální křivku a výsledný bod převedeme (promítneme) zpět.

Algoritmizace

ComputeKnotVector(int n, int k)

Spočítá uzlový vektor.

Parametry:

• n - počet kontrolních bodů mínus 1
• k - stupeň de Boor bázové funkce

Vector GetPoint(double t)

Přetížená metoda třídy Curve. Spočítá a vrátí bod na křivce.

Parametry:

• t - parametr výpočtu