De Casteljau算法

题目 在Bezier曲线上找到点:De Casteljau算法

翻译文章来自http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/Bezier/de-casteljau.html

在贝塞尔曲线绘制完成后，下一个重要的任务是选定特定u的情况下在曲线上找到点C(u)。一个简单的方法是把u插到每一个基函数上，计算每个其与基函数的乘积以及其相应的控制顶点，最后将其相加。虽然这种方法很好，但是缺乏数值稳定性（例如在计算Bernstein多项式的时候可能引进数值误差）。

在下文中，我们仅仅记下控制点的数字。例如00对应控制点P0,01对应P1,...,0i对应Pi,...,0n对应Pn。因此在这些数字中0s表示初始的或者是第0次迭代。在之后，0被其他数字1,2,3代替表示第1,2,3次迭代，等等。

Casteljau算法的基本观点是选择在AB中的一个点C，C将AB分为u:1-u(A到C的距离与AB之间的距离之比是u)，让我们找到决定C在哪里的方法

从A到B的向量是B-A。因为u是在0和1之间的比率，点C位于u(B-A)。将A的位置加以考虑，点C为A+u(B-A)=(1-u)A+uB。因此，对于给定的u，(1-u)A+uB是在A和B之间的点C，将AB分为u:1-u的两段

Casteljau算法的想法如下。假设我们想要找到C(u)，u在[0,1]中。由第一个多段线00-01-02-03...-0n开始，利用上面的法则找到在线段上的点1i，1i在0i到0(i+1)的连线上并且将这段线分为u:1-u的两部分。依次地，我们可以得到n个点10,11,12,...,1(n-1)，他们定义了一个新的多段线（polyline），一共有n-1段

在上图中，u是0.4,10是在00和01的线段，11是在01和02的线段,...,并且14是在04到05的线段，所有的新点都由蓝色的表示。

新点由1i进行标记，再次利用上面的规则我们可以得到第二个多段线，具有n-1个点（20,21,...,2(n-2)）和n-2条边。从这个多段线开始，进行第三次，得到新的多段线，由n-2个点30,31,...,3(n-3)和n-3条边组成。重复这个过程n次得到一个点n0，Casteljau已经证明在曲线上的点C(u)对应u

以上图举例，20是在10和11上将这段线分为u:1-u的点，类似地选取21在11和12上，22在12和13上，23在13和14上.第三个多段线是20,21,22,23.第三个多段线有四个点和三条边。继续做得到30,31,32组成的多段线，这是第四个多段线。继续得到有40和41组成的线段，再做一次得到50，为点C(0.4)。

这是de Casteljau算法的几何解释，是在曲线设计中最漂亮（elegant）的结果之一。

实际计算

给定了de Casteljau的几何解释之后，我们现在展示一个计算方法，由下图

首先，在如图中的最左边一列是给定的控制点