样条曲线(分段三次多项式形式)可以写成:
s = x - x[k]
y = y[k] + a[k]*s + b[k]*s*s + c[k]*s*s*s
其中x[k] < x < x[k+1]
,曲线通过每个(x[k], y[k])
点,a,b,c 是描述斜率和形状的系数数组。这一切都可以在浮点数中正常工作,并且有很多方法可以为不同种类的样条计算 a、b、c。然而...
这如何用整数算术近似?
棘手的部分之一是,理想情况下,任何近似值都应该是连续的,换句话说,使用x=x[k+1]
来自第 k 段的系数,结果应该是y[k+1]
舍入误差除外。换句话说,对于直线段,y[k+1] == y[k] + a[k]*(x[k+1] - x[k])
和弯曲段仅在中间偏离此,而在两端均不偏离。在浮点的情况下,这是通过构造来保证的,但即使是舍入后的很小的系数变化也可能会使其偏离很多。
另一个棘手的部分是,一般来说,高阶系数的幅度要小得多——但并非总是如此,尤其是。不在尖锐的“角落”。将它们按 s 的典型大小放大到它们的任何顺序的幂仍然是有意义的,因此它们不会作为整数四舍五入到零,但这似乎会以曲率分辨率换取最大可能的角锐度.
首先尝试整数版本:
y = y[k] + (a[k] + (b[k] + c[k]*s)*s)*s
然后使用整数乘法(用于 16 位值,32 位算术):
#define q (1<<16)
#define mult(x, y) ((x * y) / q)
y = y[k] + mult(mult(mult(c[k], s) + b[k], s) + a[k], s)
这在理论上看起来不错,但我不确定这是最好的方法,或者如何系统地告诉最好的方法是什么。