Web 技术研究所

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

分段三次hermite插值

  既然插值可以带导数,那么只要让邻近两点的导数相同就可以得到平滑的曲线。而且这样的分段插值是数值稳定的,不会产生高次多项式带来的龙格现象。不过由于这里使用的三次hermite插值只是一阶连续的,所以虽然理论上是平滑曲线,但是视觉效果还是欠佳。
  之前的多项式插值也试过多点的插值,但是毕竟是多项式,龙格现象是无法避免的。现在用的最普遍的则是样条插值,也可以说是分段低次插值。对于一个分段函数,如果要使它看上去平滑就必须让它连续可导。上一篇中咱说了三次hermite插值,也就是带导数的插值,这样我们只要构造出一个分段函数,让分段点处的左右导数相等即可。
  但是hermite插值需要每个顶点的切线斜率,要是把这些数据全都作为参数就太麻烦了,于是咱做个简单的计算来自动求出个比较合适的顶点切线来。我们知道,每一个点与邻近的两点都能构成一个角,有了这个角就可以计算出一个比较合适的切线来,这里我使用了角平分线的垂线来作为切线。
  
  如果还觉得这个麻烦,甚至可以把某点的邻近两个点直接用线连接起来作为切线。比如这里的p₂点的切线可以是p₃-p₁,而不需要一堆normalize。其实现在不用纠结这个顶点切线的算法,因为我们讨论的是一阶导数连续的情况而已,这样曲线的平滑度本身就有点问题。所以这个问题放到以后讨论二阶连续时再来纠结。
  最后还有个问题,上面的思路中,每个点需要相邻的两个点作为计算切线的参考,但是头尾的点相邻的只有一个怎么办?这就是条件不足的问题,分段插值必定会遇到这样的问题,缺少两个边界条件。这两个条件当然需要自己给定,至于给定的方式也会有很多种。比如你可以直接指定头尾两个点的切线斜率,而不需要去计算它。但是这里我用了另一个方法,在给定的一组顶点的头尾添加两个用来定位边界的顶点,它们不被绘制出。这样所有需要绘制的顶点附近就都存在两个顶点了,因此可以正常的计算。
  下面是程序的核心代码部分 hermite.piecewise=function(){
  var i,s,p1,p2,p3,A,B,l;
  s=Array.prototype.slice.call(arguments,0);
  for(i=1;i<s.length-1;i++){
    //向量normalize
    p1=s[i-1],p2=s[i],p3=s[i+1];
    A=[p2[0]-p1[0],p2[1]-p1[1]],B=[p3[0]-p2[0],p3[1]-p2[1]];
    l=Math.sqrt(A[0]*A[0]+A[1]*A[1]),A[0]/=l,A[1]/=l,
    l=Math.sqrt(B[0]*B[0]+B[1]*B[1]),B[0]/=l,B[1]/=l;
    //计算切线斜率
    s[i]=[p2[0],p2[1],(A[1]+B[1])/(A[0]+B[0])];
  };
  //移除头尾用来定位边界的顶点
  s.shift(),s.pop();
  //计算每一段的三次hermite插值函数
  for(i=1;i<s.length;i++)
    s[i-1][2]=hermite.apply(null,s[i-1].concat(s[i]));
  //返回分段插值函数
  l=s.length-1;
  return function(e){
    for(var i=0;i<l;i++)if(e<s[i+1][0]||i==l-1)return s[i][2](e);
  };
};

  完整代码:分段三次hermite插值
网名:
54.198.108.*
电子邮箱:
仅用于接收通知
提交 悄悄的告诉你,Ctrl+Enter 可以提交哦
神奇海螺
[查看全部主题]
各类Web技术问题讨论区
发起新主题
本模块采用即时聊天邮件通知的模式
让钛合金F5成为历史吧!
次碳酸钴的技术博客,文章原创,转载请保留原文链接 ^_^