Linear interpolation for arrays

[six1]

I would really appreciate if someone could take a look and give some advice or help.

I got a 2D array and based on it I can figure out a value based only on those coordinates. What I am trying to do though is to use a y=mx+b equation to find the values in between the points. I am having lots of issues writing a code that would say, figure out the value of the two closest points (that surround the value).

For example if I have-

a graph associated with the array that looks like this:
____y__| 3 | 4 | 5 | 6 | 7 |
x
-------------------------------
1______| 1 | 2 | 3 | 4 | 5 |
--------------------------------
2______| 3 | 5 | 8 | 10| 14 |
-------------------------------
4______| 5 | 7 | 12| 16| 19|
-------------------------------
6______| 8 | 9 | 13| 18| 23|
--------------------------------

Then in code this is:

array[4][5] = { {1, 2, 3, 4, 5} }
{ {3, 5, 8, 10, 14} }
{ {5, 7, 12, 16, 19} }
{ {8, 9, 13, 18, 23} }

// I can plug in indirectly for points using-

if (x=1)
{a=0}
if (x=2)
{a=1}
if (x=4)
{a=2}
if (x =6)
{a=3}


b = y-3

cout << array[a][b];


But if I plug in, for example, x=4.7 and y = 6, how should I write a code that would figure out that 4.7 is between x=4 and x=6 or between a =2 and a=3 and then take the coordinates at x=4 or 6 or a=2 or 3 and plug it into an y=mx+b equation?

Thank you for taking your time to help me with this!

[keskiverto]

I don't see any y=mx+b in your example.

I do see a 2D table of values.
I do see a 1D table that maps "x" into "row".
I do see a 1D table that maps "y" into "column".

I do see that when input is a (x,y) pair, the 1D tables are used to retreive an element from the 2D table.

That is more like a 3D data point. (x,y,z) where z is the value in the 2D table.


You seem to ask how to interpolate. That can use up to four elements from the 2D table. For example, with input (2.8,4.1) should get a value that is an interpolation from

5  8
7 12

That does seem non-trivial.

[48T7M4Gy]

If x = 4.7 then use (int)(4.7) to calculate nearest integer coordinate below the value in question.
So if x(4), x(6) are the known x values then the interpolation is:
x(4.7) = 0.7/2 * ( x(6) - x(4) ) + x(4)

[Duthomhas]

Google "Bresenham's Line Algorithm".

Good luck!
[edit] Ah, I misunderstood. I thought he was looking to snap to the closest value.[/edit]

[htirwin]

You don't need to / shouldn't use the standard equation for a line in most cases, in general, when programming, as it fails, and or loses acuracy when the slope gets very large as it approaches infinity.

Anyways, here is linear interpolation in general,

 
f(q0)=v0                 f(q)=v          f(q1)=v1
  q0                       q               q1
   |---------d1------------|-------d2-------|
   |--------------------d-------------------|

v=(d2/d)*v0 + (d1/d)*v1

or equivalently,

v=(1-d1/d)*v0 + (d1/d)*v1

or equivalently,

v=(d1/d)*(v1-v0) + v0

Where q is a vector of arbitrary finite dimension, and v is a vector of arbitrary finite dimension, and v=f(q), d=distance(q0, q1), d1=distance(q0, q)

[48T7M4Gy]

v=(d1/d)*(v1-v0) + v0

x(4.7) = 0.7/2 * ( x(6) - x(4) ) + x(4)

[ne555]

> You seem to ask how to interpolate. That can use up to four elements from the 2D table.
> That does seem non-trivial.
https://en.wikipedia.org/wiki/Bilinear_interpolation