第五十三章 比例切割 算法初成(2 / 2)

,11,12,,1n1,他们定义了一个新的多段线,一共有n1段。

新点由1i进行标记,再次利用上面的规则我们可以得到第二个多段线,具有n1个点(20,21,,2n2)和n2条边。从这个多段线开始,进行第三次,得到新的多段线,由n2个点30,31,,3n3和n3条边组成。重复这个过程n次得到一个点n0。

以上想法只是给定了比例切割想法的几何解释,而实际计算需要一个具体的计算方法。

首先,对于每一对临近的控制点,可以画出一条右上方和右下方的箭头(类似于杨辉三角),并且在两个箭头的交点处写下一个新点。例如相邻的两个点分别为ij 和ij+1,新点是i+1j,右下方(相对应的左下方)的箭头表示将其尾数ij(相对应的为ij+1)乘以1u(相对应的乘以u),新的点是两个的和。

因此,从初始的第0列开始,我们计算第1列。之后从第1列得到第2列。最终,在n次计算之后我们最终到达了一个单个的点n0并且这个点就是在曲线上的点。下面的算法总结了上面我们讨论的内容,输入的是具有n+1个点的数列和在0到1之间的u,最终得到在贝塞尔曲线上的点cu。

这个计算过程可以用递归的方法表示,对于j0,1,,n用0,j表示j,也就是0,j是第0列的第j项元素,在第i列计算第j项如下i,j1ui1,j+ui1,j+1,i1,2,nj0,1,2,ni

元素i,j是1ui1,j(左上方元素)和 ui1,j+1(左下方元素)的和,最终的结果(在曲线上的点)是n,0在这种想法的基础上,通过编程就可以得到基本的算法程序。

在这个基本算法的基础上,陈东风还需要对螺旋线、球面螺旋线、双弧外摆线和星行线、心脏线、圆内螺旋线、正弦曲线、太阳线和费马曲线等等几百种曲线给出需要选定的控制点数量和控制比例u。这个工作如果没有计算机的帮助的话,估计他这辈子都得耗在这上面了。

“好在,通用的算法以及计算出来了,可能有迭代算法效率的不高的问题,但是计算机应该可以克服。”陈东风一边自言自语,一边站了起来,往窗外一看天快黑了,正好肚子有点饿,把桌子上堆成小山的草稿纸整理下后,就出了房间。