Linear interpolation

From GDWiki

(Redirected from Linear Interpolation)
Jump to: navigation, search

Linear interpolation is a method for constructing new data points between two existing data points in a linear fashion (analytically speaking using linear polynomials, geometrically speaking on a stright line between two points).

[edit] Formula

The formula for such an interpolation is

\mathbf{p}(u) = \mathbf{a} + u \times (\mathbf{b} - \mathbf{a}) \;\;\;\; 0 \leq u \leq 1

where a and b are the two points to interpolate between and u indicates the ratio along the line from a to b of the desired point. If u lies outside the range [0, 1] this is known as extrapolation.

Image:Linear_interlopation_diagram.png

It may be helpful to note the following:

\mathbf{p}(0) = \mathbf{a} \;\;\;\; \mathbf{p}(1) = \mathbf{b}

This formula applies to points of any dimensionality.

For example, in R3:

\mathbf{a} = (x_0, y_0, z_0) \;\;\;\; \mathbf{b} = (x_1, y_1, z_1)
x(u) = x_0 + u \times (x_1 - x_0)
y(u) = y_0 + u \times (y_1 - y_0)
z(u) = z_0 + u \times (z_1 - z_0)

A new point p at distance u would then be

\mathbf{p}(u) = (x(u), y(u), z(u))

Sometimes it is necessary to find both coordinates of a point on a line when only one coordinate is known (in addition to two points on the line). This can be accomplished by expanding the two-dimensional case. Given the desired x coordinate, we can find the corresponding y value:

\mathbf{a} = (x_0, y_0) \;\;\;\; \mathbf{b} = (x_1, y_1)
x(u) = x_0 + u \times (x_1 - x_0)
y(u) = y_0 + u \times (y_1 - y_0)

Solving the first equation for u in terms of x:

u(x) = \frac{x - x_0}{x_1 - x_0}

and substituting into the second equation:

y(x) = y_0 + (x - x_0) \frac{y_1 - y_0}{x_1 - x_0}
TODO: Insert image to demonstrate usage.

[edit] Applications

Image:40px-important_orange.png This article or section is incomplete and may require expansion and/or cleanup.
Please improve this article or discuss the issue on the talk page.

Linear interpolation has a few common applications. It is frequently used as a way to interpolate between values in a table. It can also be used as a way to animate an object moving between two points by using time as the ratio u.

TODO: Discuss bilinear interpolation.

[edit] See also

Retrieved from "http://wiki.gamedev.net/index.php/Linear_interpolation"
Personal tools