linearInterPolate

線形補間をJavaで実装してみました。

Cや、C++が使える環境であれば、

わざわざこんな基本的なアルゴリズムを実装する必要はないです。

Javaしか稼働しない、JNIも叩けないといったシチュエーションもあるっちゃあるし。

また、そういった環境では、Java1.4の機能しか使えないといったケースもままあるので、

1.4の機能で実装をしてみます。( ArrayListでジェネリクスが使えない...とか）

作成するプログラムのアウトライン

線形補間のアルゴリズムは、http://ja.wikipedia.org/wiki/%E7%B7%9A%E5%BD%A2%E8%A3%9C%E9%96%93

に記載があるとおりの線形内挿法を採用します。

補間する区間をサーチするために、バイナリサーチを少し改変しました。

バイナリサーチは、教科書どおりにいくならば、探したい要素がリスト内のどの位置にあるか？ですが、

ここでは、探したい要素が定義域のどの区間にあるか？を探りあてるよう改変しました。

ex.1

定義域 x = 10,20,30,40,50

探したい＆補間したい x = 22。

改変したバイナリサーチが返す結果は、

定義域における位置を示すインデックス。

インデックスは0から始まるとして、ここでは、”1”を返す。

ex.2

定義域 x = 10,20,30,40,50

探したい＆補間したい x = 42。

改変したバイナリサーチが返す結果は、

定義域における位置を示すインデックス。

インデックスは0から始まるとして、ここでは、”3”を返す。

バイナリサーチから返却されたインデックスとその値域の値、

補間したい x を 線形補間の公式にあてはめれば、補間完了。

あと、補間前のデータと、補間結果とのマージはコストが掛かるので、

遅延可能なように、線形補間計算メソッドとは分離してます。

プログラム

上の動作を実現するJavaソース、eclipseプロジェクトを⬇に貼付けます。

下記の環境で動作してます。

Mac OS X 10.9

eclipseで、プロジェクトをインポート後、InterPTestを実行すれば、テストコードが動作します。