#0110: Fungsi Interpolasi Linear & Bilinear pada Google Spreadsheet

Interpolasi bilinear

Last Update: 20140930, 30 sept. 2014, Fixing bug. See patch notes below.

Sabtu kemarin, saya baru menyelesaikan rangkaian latihan di codecademy untuk skill javascript. Sebenarnya saya cukup familiar dengan bahasanya, cuman yang bikin tertarik pada konsep OOPnya. Yah sekalian menyegarkan otak karena sudah lama tidak melakukan pemrograman, yah sekalian juga belajar javascript. Cukup niat untuk menyelesaikannya juga karena akhir-akhir ini saya mulai mengerjakan tugas perhitungan pada google spreadsheet (bagian dari google docs/drive). Rasanya untuk operasi yang sederhana cukup menggunakan google spreadsheet dibandingkan Microsoft excel. Skripsi saya yang sedang mengembangkan program untuk pemodelan NRECA juga mayoritas dapat dilakukan di Google Spreadsheet. Kesulitan yang saya alami saat penampilan grafiknya. Chartnya ntah kenapa terkesan terlalu sederhana. Mungkin bisa di-outsource di plot.ly (harus refreshing juga di bahasa python. -__-). Bagi yang langsung mau lihat kodenya dan teorinya saja, yah tinggal loncat bacanya kebawah, sudah saya sertakan juga referensi yang saya gunakan. 

Istilah interpolasi seharusnya sudah sering didengar bagi para pengguna matematik dalam analisis numerik. Sederhananya, interpolasi digunakan untuk memperoleh nilai di titik tertentu yang berada diantara 2 nilai. Definisi yang saya gunakan merupakan berdasarkan apa yang sedang kerjakan, belum saya lakukan penelitian lebih lanjutnya untuk apa interpolasi itu. Haha.


Interpolasi Linear

Saya mempelajari interpolasi karena kebanyakan informasi dalam bidang yang sedang tekuni hanya bermodalkan tabel dan sedikit yang disertakan formulanya. 1 tahun kemarin saat saya mengembangkan program (ga diselesaikan) ada tabel yang sebenarnya merupakan hasil dari perhitungan. Sedangkan yang ditampilkan hanya sekedar tabel seperti nilai y untuk x=10 adalah 20, dan x=20 adalah 30, dst. Ternyata ada alasannya kenapa formula tersebut tidak disertakan, karena formula yang digunakan merupakan formula tingkat tinggi dimana dibutuhkan ilmu statistik dewa untuk memahaminya. Ujung-ujungnya juga saya menggunakan library luar yaitu ALGLIB.

Singkat cerita, nilai x tidaklah selalu ada di tabel secara langsung. Untuk mudahnya, saya skenariokan kita ingin mencari nilai y berdasarkan x (y(x)). Biasanya merupakan nilai diantara 2 nilai terdekatnya. Dan untuk memperoleh nilai yang dibutuhkan tidak boleh pilih nilai yang terdekat harus dihitung kembali dengan mengasumsikan bahwa linear interpolasi berlaku. Biar kebayang berikut tabel hubungan antara suhu (T (^{o}C)) dengan tekanan uap air jenuh (ea (mbar)):

2014-09-29 15_20_52-Pemodelan NRECA - Google Sheets

Permasalahan yang dihadapi adalah nilai suhu tidaklah selalu berinterval 0.2, semisal dalam pengamatan diperoleh suhu sebesar 25.86 ^{o}C sedangkan ditabel tidak ada untuk suhu 25.86, yang mendekati adalah 25.80 dan 26.00. Meski perlu dipertanyakan lagi perolehan tabelnya, apakah fungsi linear berlaku untuk tabel ini atau tidak. Tapi biasanya diasumsikan linear/garis lurus. Biar lebih kebayang lagi saya sertakan gambar yang saya ambil dari Wikipedia:

Linear Interpolation

Jadi akhir cerita (ih, gak rame yah, tapi bingung mau bicara apalagi coba), saya bikin kode untuk melakukan fungsi interpolasi di google spreadsheet (bahasa pemrograman yang digunakan adalah javascript). Kodenya bisa lihat dibawah bagian Code. Sebelum asal copy-paste dari sini ke macronya g.spreadsheet baca dulu penjelasannya:

Fungsi Linear Interpolasi LiInter:

syntax: LiInter(value, x, y)
example: 
  =LiInter(C5,\$F\$9:\$F\$20,\$G\$9:\$G\$20)
  =LiInter(25.86,t,ea) :: contoh diatas. 
dengan,
value \{number\}: nilai (x) yang ingin dicari
x \{array\}: kolom yang digunakan untuk acuan nilai x (value)
y \{array\}: kolom fungsi dari x (y(x)).

Interpolasi Bilinear

Nah disini mulai menarik. Kalau tadi untuk memperoleh nilai y hanya berdasarkan 1 x, sekarang dibutuhkan 2. Biasanya disebut juga berdasarkan 2 fungsi x. Tapi dalam bentuk kode saya sebutnya x dan y dimana xyz(x,y), jadi jangan bingung pas lihat kodenya ada x dan y. haha. Males lagi ubah ke bentuk yang umum. Terlebih lagi saya pakai sumber internet semua, gak ada textbook nih. Kalau banyak baca sih, kebanyakan bilinear digunakan untuk gambar, ntah deh untuk ngapain selain memperbesar gambar. cmiiw.

Untuk algoritma dalam interpolasi bilinear saya mengacu yang ada di wikipedia. Formula yang saya gunakan tidak jauh dengan yang ada diwikipedia. Saya membutuhkan fungsi bilinear karena ternyata tabel di skripsi saya tidak sekedar mengacu pada 1 nilai tetapi mengacu lagi ke lain. Berikut tabelnya:

2014-09-29 16_16_30-Pemodelan NRECA - Google Sheets

Tabel ini digunakan untuk memperoleh nilai Rs yang mengacu pada nilai Ra dan n/N. Contohnya, saya memperoleh nilai Ra = 13.000 dan n/N = 51.780%, saya ingin mencari nilai Rs berdasarkan tabel. Permasalahan tersebut harus menggunakan interpolasi bilinear dimana ada 2 acuan/fungsi yang digunakan untuk mencari nilai. Berikut penjelasan mengenai fungsi yang saya buat:

Fungsi Bilinear Interpolasi BiInter:

syntax: BiInter(valx, valy, x, y, xyz)
example:
  =BiInter(N7,G7,\$B\$91:\$B\$112,transpose(\$C\$90:\$J\$90),\$C\$91:\$J\$112)
  =BiInter(13.000,51.780,tl4Ra,transpose(tl4NN),tl4Rs)
dengan:
valx \{number\}: nilai pertama (x) yang dijadikan acuan
valy \{number\}: nilai kedua (y) yang dijadikan acuan
x \{array\}: kolom yang digunakan untuk acuan nilai x (valx)
y \{array\}: baris yang digunakan untuk acuan nilai y (valx). Penggunaan transpose untuk array ini wajib agar bentuk array serupa dengan x. 
xyz \{array\}: blok sel yang digunakan untuk acuan nilai xdan y (valx & valy)

catatan:
  Penggunaan TRANSPOSE(y) WAJIB!

Sekian deh, jika ada pertanyaan atau apa-apa bisa hubungin saya via email di me@taruma.info. Capek nulisnya. haha!


Patch Notes

Patch 0.1.0 (20140929): Publikasi kode fungsi LiInter() dan BiInter().
Patch 0.1.1 (20140930): Fungsi BiInter, sudah dimodifikasi agar bisa mencari jika salah satu nilai maksimum.

Formula/Theory

Linear Interpolation:

y=y_{0}+(y_{1}-y_{0})\frac{x-x_{0}}{x_{1}-x_{0}} \huge

Bilinear Interpolation:

f(x,y)=[\frac{1}{(x_{2}-x_{1})(y_{2}-y_{1})}](f(Q_{11})(x_{2}-x)(y_{2}-y)+f(Q_{21})(x-x_{1})(y_{2}-y)+f(Q_{12})(x_{2}-x)(y-y_{1})+f(Q_{22})(x-x_{1})(y-y_{1}))


Code

function LiInter(value, x, y) {
function LiInter(value, x, y) {
 if(value > Math.max.apply(Math, x) || value < Math.min.apply(Math, x)) {
 throw "Tidak bisa diinterpolasi karena nilai yang dicari diluar tabel";
 return;
 }
 
var index;
 
 for (var i = 0; i < x.length; i++) {
 if (x[i][0] == value) {
 return y[i][0];
 } else {
 if (x[i][0] < value && x[i+1][0] > value ) {
 index = i;
 }
 }
 }
 
var yVal, yDiff, xDiff, xInt;
 
 yVal = y[index][0];
 yDiff = y[index+1][0]-y[index][0];
 xDiff = x[index+1][0]-x[index][0];
 xInt = value - x[index][0];
 
 return yVal + yDiff * (xInt / xDiff);
 
}
function BiInter(valx, valy, x, y, xyz) {

// Menentukan batas atas dan bawah untuk tiap absis dan ordinat.
var Minx = Math.min.apply(Math, x); 
var Maxx = Math.max.apply(Math, x);
var Miny = Math.min.apply(Math, y);
var Maxy = Math.max.apply(Math, y);
 
 if ( (valx < Minx || valx > Maxx ) || (valy < Miny || (valy > Maxy))) {
 throw "Tidak bisa diinterpolasi karena nilai yang dicari berada di luar batas tabel. Cek kembali nilainya!";
 return;
 } 

var xLen = x.length;
var yLen = y.length;
var indexx, indexy;

// Mencari nilai yang sama dengan x,y = valx,valy
 for (var j = 0; j < yLen; j++) {
 for (var i = 0; i < xLen; i++) {
 if ( x[i][0] == valx && y[j][0] == valy) {
 return xyz[i][j];
 } 
 }
 }

// Mencari index untuk yang tidak sama
 for (var i = 0; i < xLen; i++) {
 if ( x[i][0] == valx) {
 indexx = i;
 break;
 } else if ( x[i][0] < valx && x[i+1][0] > valx ) {
 indexx = i;
 }
 }

 for (var j = 0; j < yLen; j++) {
 if ( y[j][0] == valy) {
 indexy = j;
 break;
 } else if ( y[j][0] < valy && y[j+1][0] > valy ) {
 indexy = j;
 }
 }

// Menghitung interpolasi jika salah satu x/y maksimum (diujung tabel).
 
var idy = 0, idx = 0;
var d1 = 0, g = 0, g1 = 0, g2 = 0, d2 = 0;

 if (indexx == xLen-1 || indexy == yLen-1) {
 if (indexx == xLen-1) {
 idy = indexy;
 d1 = xyz[indexx][idy];
 g = valy;
 g1 = y[idy][0];
 g2 = y[idy+1][0];
 d2 = xyz[indexx][idy+1];
 return d1 + ((g-g1)/(g2-g1)) * (d2-d1)
 }
 if (indexy == yLen-1) {
 idx = indexx;
 d1 = xyz[idx][indexy];
 g = valx;
 g1 = x[idx][0];
 g2 = x[idx+1][0];
 d2 = xyz[idx+1][indexy];
 return d1 + ((g-g1)/(g2-g1)) * (d2-d1)
 }
 }

// Menghitung nilai interpolasi (valx,valy)

var Q11 = 0, Q12 = 0, Q21 = 0, Q22 = 0;
var x1 = 0, x2 = 0, y1 = 0, y2 = 0;
var FQ11 = 0, FQ12 = 0, FQ21 = 0, FQ22 = 0;
var xyDiff = 0;

x1 = x[indexx][0];
x2 = x[indexx+1][0];
y1 = y[indexy][0];
y2 = y[indexy+1][0];

Q11 = xyz[indexx][indexy];
Q12 = xyz[indexx][indexy+1];
Q21 = xyz[indexx+1][indexy];
Q22 = xyz[indexx+1][indexy+1];

FQ11 = Q11 * (x2 - valx) * (y2 - valy);
FQ21 = Q21 * (valx - x1) * (y2 - valy);
FQ12 = Q12 * (x2 - valx) * (valy - y1);
FQ22 = Q22 * (valx - x1) * (valy - y1);

xyDiff = 1 / ((x2-x1) * (y2-y1));

return xyDiff * (FQ11 + FQ21 + FQ12 + FQ22) ;

}

Referensi:

Anon, 2014a. Bilinear interpolation. Wikipedia. Available at: http://en.wikipedia.org/wiki/Bilinear_interpolation.
Anon, How to interpolate data in a range in Google Sheets. Available at: http://webapps.stackexchange.com/questions/63165/how-to-interpolate-data-in-a-range-in-google-sheets [Accessed September 29, 2014a].
Anon, 2014b. Linear interpolation. Wikipedia. Available at: http://en.wikipedia.org/wiki/Linear_interpolation.
Anon, Linear Interpolation. How to implement this algorithm in C ? (Python version is given). Available at: http://stackoverflow.com/questions/4459930/linear-interpolation-how-to-implement-this-algorithm-in-c-python-version-is [Accessed September 29, 2014b].
#0110: Fungsi Interpolasi Linear & Bilinear pada Google Spreadsheet