I have a non-grid-aligned set of input values associated with grid-aligned output values. Given a new input value I want to find the output:
(These are X,Y coordinates, calibrating an imprecise not-square eye-tracking input device to exact locations on screen.)
This looks like Bilinear Interpolation, but my input values are not grid-aligned. Given an input, how can I figure out a reasonable output value?
Answer: In this case where I have sets of input and output points, what is actually needed is to perform inverse bilinear interpolation to find the U,V coordinates of the input point within the quad, and then perform normal bilinear interpolation (as described in Nico's answer below) on the output quad using those U,V coordinates.
Bilinear interpolation formulaStart by performing two linear interpolations in the x-direction (horizontal): first at (x, y₁) , then at (x, y₂) . Next, perform linear interpolation in the y-direction (vertical): use the interpolated values at (x, y₁) and (x, y₂) to obtain the interpolation at the final point (x, y) .
Bilinear interpolation is performed using linear interpolation first in one direction, and then again in the other direction. Although each step is linear in the sampled values and in the position, the interpolation as a whole is not linear but rather quadratic in the sample location.
Name the cell containing the x- and y-values you entered in x and y, respectively. Select the row of x-values in the data table and name those “xvalues”. Select the column of y-values in the same table and name those “yvalues”. Next, select all the air velocity numbers (cells D7-L15) and name them “zvalues”.
You can bilinearly interpolate in any convex tetragon. A cartesian grid is just a bit simpler because the calculation of interpolation parameters is trivial. In the general case 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 the parameters, you have to solve a system of equations. Put your input values in the places of p1
through p4
and solve for alpha
and beta
.
Then put your output values in the places of p1
through p4
and use the calculated parameters to calculate the final interpolated output value.
For a regular grid, the parameter calculation comes down to:
alpha = x / cell width
beta = y / cell height
which automatically solves the equations.
Here is a sample interpolation for alpha=0.3
and beta=0.6
Actually, the equations can be solved analytically. However, the formulae are quite ugly. Therefore, iterative methods are probably nicer. There are two solutions for the system of equations. You need to pick the solution where both parameters 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 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))
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With