[ACCEPTED]-Bilinear interpolation with non-aligned input points-interpolation

You can bilinearly interpolate in any convex 21 tetragon. A cartesian grid is just a bit 20 simpler because the calculation of interpolation 19 parameters is trivial. In the general case 18 you interpolate as follows:

parameters alpha, beta
interpolated value = (1 - alpha) * ((1 - beta) * p1 + beta * p2) + alpha * ((1 - beta) * p3 + beta * p4)

In order to calculate 17 the parameters, you have to solve a system 16 of equations. Put your input values in the 15 places of p1 through p4 and solve for alpha and beta.

Then 14 put your output values in the places of 13 p1 through p4 and use the calculated parameters 12 to calculate the final interpolated output 11 value.

For a regular grid, the parameter 10 calculation comes down to:

alpha = x / cell width
beta  = y / cell height

which automatically 9 solves the equations.

Here is a sample interpolation 8 for alpha=0.3 and beta=0.6

Actually, the equations can be 7 solved analytically. However, the formulae 6 are quite ugly. Therefore, iterative methods 5 are probably nicer. There are two solutions 4 for the system of equations. You need to 3 pick the solution where both parameters 2 are in [0, 1].

First solution:

alpha = -(b e - a f + d g - c h + sqrt(-4 (c e - a g) (d f - b h) +
        (b e - a f + d g - c h)^2))/(2 c e - 2 a g)    
beta  = (b e - a f - d g + c h + sqrt(-4 (c e - a g) (d f - b h) + 
        (b e - a f + d g - c h)^2))/(2 c f - 2 b g)

where

a = -p1.x + p3.x
b = -p1.x + p2.x
c = p1.x - p2.x - p3.x + p4.x
d = center.x - p1.x
e = -p1.y + p3.y
f = -p1.y + p2.y
g = p1.y - p2.y - p3.y + p4.y
h = center.y - p1.y

Second 1 solution:

alpha = (-b e + a f - d g + c h + sqrt(-4 (c e - a g) (d f - b h) + 
        (b e - a f + d g - c h)^2))/(2 c e - 2 a g)
beta  = -((-b e + a f + d g - c h + sqrt(-4 (c e - a g) (d f - b h) + 
        (b e - a f + d g - c h)^2))/( 2 c f - 2 b g))

Here's my own technique, along with code 23 for deriving the resulting value. It requires 22 three lerps of the output values (and three percentage 21 calculations to determine the lerp percentages):

Note that this is not bilinear interpolation. It 20 does not remap the quad of input points 19 to the quad of output values, as some input points can result in output values outside the output quad.

Here I'm 18 showing the non-aligned input values on 17 a Cartesian plane (using the sample input 16 values from the question above, multiplied 15 by 10 for simplicity).

                     

To 14 calculate the 'north' point (top green dot), we 13 calculate the percentage across the X axis 12 as

  (inputX - northwestX) / (northeastX - northwestX)
= (-4.2 - -19) / (10 - -19)
= 0.51034

We use this percentage to calculate the 11 intercept at the Y axis by lerping between 10 the top Y values:

  (targetValue - startValue) * percent + startValue
= (northeastY  - northwestY) * percent + northwestY
= (-8 - -7) * 0.51034 + -7
= -7.51034

We do the same on the 'south' edge:

  (inputX - southwestX) / (southeastX - southwestX)
= (-4.2 - -11) / (9 - -11)
= 0.34

  (southeastY - southwestY) * percent + southwestY
= (7 - 4) * 0.34 + 4
= 5.02

Finally, we 9 use these two values to calculate the final 8 percentage between the north and south edges:

  (inputY - southY) / (northY - southY)
= (1 - 5.02) / (-7.51034 - 5.02)
= 0.3208

With 7 these three percentages in hand we can calculate 6 our final output values by lerping between 5 the points:

nw = Vector(-150,-100)
ne = Vector( 150,-100)
sw = Vector(-150, 100)
se = Vector( 150, 100)

north  = lerp( nw, ne, 0.51034)       --> (  3.10, -100.00)
south  = lerp( sw, se, 0.34)          --> (-48.00,  100.00)
result = lerp( south, north, 0.3208)  --> (-31.61,   35.84)

Finally, here is some (Lua) code 4 performing the above. It uses a mutable 3 Vector object that supports the ability 2 to copy values from another vector and lerp 1 its values towards another vector.

-- Creates a bilinear interpolator
-- Corners should be an object with nw/ne/sw/se keys,
-- each of which holds a pair of mutable Vectors
-- { nw={inp=vector1, out=vector2}, … }
function tetragonalBilinearInterpolator(corners)
  local sides = {
    n={ pt=Vector(), pts={corners.nw, corners.ne} },
    s={ pt=Vector(), pts={corners.sw, corners.se} }
  }

  for _,side in pairs(sides) do
    side.minX = side.pts[1].inp.x
    side.diff = side.pts[2].inp.x - side.minX
  end

  -- Mutates the input vector to hold the result
  return function(inpVector)
    for _,side in pairs(sides) do
      local pctX = (inpVector.x - side.minX) / side.diff
      side.pt:copyFrom(side.pts[1].inp):lerp(side.pts[2].inp,pctX)
      side.inpY = side.pt.y
      side.pt:copyFrom(side.pts[1].out):lerp(side.pts[2].out,pctX)
    end
    local pctY = (inpVector.y-sides.s.inpY)/(sides.n.y-sides.s.inpY)
    return inpVector:copyFrom(sides.s.pt):lerp(sides.n.pt,pctY)
  end
end

local interp = tetragonalBilinearInterpolator{
  nw={ inp=Vector(-19,-7),  out=Vector(-150,-100) },
  ne={ inp=Vector( 10,-8),  out=Vector( 150,-100) },
  sw={ inp=Vector(-11, 4),  out=Vector(-150, 100) },
  se={ inp=Vector(  9, 7),  out=Vector( 150, 100) }
}
print(interp(Vector(-4.2, 1))) --> <-31.60 35.84>