スプライン (区分的 3 次多項式) は次のように記述できます。
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 を計算する方法はたくさんあります。でも...
これを整数演算でどのように近似できますか?
トリッキーな部分の 1 つは、理想的には近似が連続的であることです。つまり、k 番目のセグメントの係数を使用すると、結果は丸め誤差を除いたものにx=x[k+1]なるはずです。y[k+1]言い換えれば、直線セグメントの場合、y[k+1] == y[k] + a[k]*(x[k+1] - x[k])、および曲線セグメントは、中央でのみ逸脱し、両端では逸脱しません。これは、浮動小数点の場合の構造によって保証されていますが、丸めによる小さな係数の変更でさえも、かなりずれることがあります。
もう 1 つのトリッキーな部分は、一般に、高次の係数の大きさがはるかに小さいことです。ただし、常にそうとは限りません。鋭い「角」ではありません。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)
これは理論的には良さそうに見えますが、それが最善のアプローチであるかどうか、または可能な最善のアプローチが何であるかを体系的に伝える方法についてはわかりません。