Web 技术研究所

我一直坚信着,Web 将会成为未来应用程序的主流

曲线与插值

  经常会看到拿出一些奇怪的数字来找规律的题目,这样的题目都是坑爹的!给定有限个数字可以找到无限个符合那些数字函数,只要用上插值算法就可以计算。当然,数列只是一维的东西。但是我们可以把这些算法扩展到二维或三维中来计算曲线和曲面的数据。
  假如有两个点,需要画出他们之间的一条路径,只要把这两个点用一条线段连接起来就可以了。这个过程其实就是线性插值,我们给这两点之间的路径补上了无数个点,让它成为一条线。已知条件是两个点的坐标,从这个条件只能知道线的开始和结束位置,所以使用了线性插值。现在在这两点之间又多个一个点,而且这个点并不在线性插值时的位置上怎么办呢?我们必须让函数满足所有给定的点,线性插值是一次函数,它是一条直线,无法满足我们给定的点。我们可以使用二次插值来画出需要的线条。因为二次函数有三个系数,我们可以通过控制每个系数来匹配每个顶点,以得到一条经过给定点的曲线了。至于具体怎么找出这个二次函数,那就是二次插值本身的工作了。二次函数之后是三次、四次,以及更高次的函数,可以根据给定中间点的数量来确定具体使用什么函数,他们统称为多项式插值。
  虽然多项式插值可以得到一条满足所有给定点的平滑曲线,但是它的计算太复杂了。如果只是用来做做找规律的题目还好说,但如果要在绘图中使用显然不现实。一个随机曲面需要的顶点数量多的惊人,不算上多项式本身的计算,光找出这些多项式都需要计算一大堆高阶的行列式,这当然不适合绘图时使用了。我们需要找到一种能做到类似效果,而且计算方便的方法。在做找规律的题目时候我总是这么想,这货要是一个分段函数不是坑死人吗?如果找规律的题中我随便写个分段函数把所有给定的数字都单独定义了呢?出题人见到这么答题的肯定会很恼火吧,也许找规律的题还要加上一个“使用连续函数”的条件吧。使用分段函数的方法在找规律的题目中是行不通了,但是在做我们需要的绘图工作时也许可以用上。因为出题的是上帝,我猜它应该不会耍赖吧?
  分段函数确实可以很容易的满足所有给定的点,但是它并不是我们需要的平滑曲线。不过有了分段函数这个东西,我们就可以把复杂的函数简单化了。原来需要构造的高次多项式,现在只需要用多个低次多项式来替代就行。一般情况下我们会在这些样条中使用三次函数,因为它可以让曲线更平滑而且计算简单。也许这样把原来的高次多项式切开了以后你会担心在分段相接的地方曲线会变得不平滑吧?确实有这个问题,不过它是可以解决的。一条曲线为什么会平滑呢?那是因为它的增量连续,也就是一阶导数连续。而这个样条的分段本身是三次函数,这就意味着每一段的二阶导数都是线性的。所以只要整个函数是二阶可导的就能保证一阶导数的连续。由于函数是分段的,要让整个函数二阶可导就必须让顶点处左右两边曲线的二阶导数在顶点位置的值都相同。这样,我们就可以得到最终的平滑曲线了。这个使用分段函数的方法就是传说中的样条法。
  这篇文章只是稍微说了一些概念上的东西。其实已经有很多现成的好算法可以用了,不需要自己去设计个多么优秀的曲线算法。不过,无论是自己设计还是使用别人的,概念的理解永远是最重要的。
网名:
3.80.32.*
电子邮箱:
仅用于接收通知
提交 悄悄的告诉你,Ctrl+Enter 可以提交哦
神奇海螺
[查看全部主题]
各类Web技术问题讨论区
发起新主题
本模块采用即时聊天邮件通知的模式
让钛合金F5成为历史吧!
次碳酸钴的技术博客,文章原创,转载请保留原文链接 ^_^