Linear interpolation is a process employed in mathematics, and numerous applications including computer graphics. It is a very simple form of interpolation. Euclid, detail from The School of Athens by Raphael. ... Computer graphics (CG) is the field of visual computing, where one utilizes computers both to generate visual images synthetically and to integrate or alter visual and spatial information sampled from the real world. ... In the mathematical subfield of numerical analysis, interpolation is a method of constructing new data points from a discrete set of known data points. ...

How to do linear interpolation

You know the coordinates (x₀, y₀) and (x₁, y₁). You want to pick points on this line with a given x in the interval [x₀, x₁]. By inspecting the figure we see that: Image File history File links Linear interpolation image, created as an example image and referred in the article on Linear interpolation. ...

Let us write α for the value equal to both sides. This is the interpolation coefficient—the proportion of the distance from x₀ to x₁ you have traversed at the point when you encounter x. Since you know the required value of x, you can find α from the formula

But it is also true that

which can be manipulated algebraically into either the form:

or if you prefer:

from which you can find y directly using your computed value of α. This formula is in fact valid even when x is not between x₀ and x₁, although α will then not be between 0 and 1 and therefore cannot be said to be a "proportion" in the usual sense of the word. In this case the method is called linear extrapolation—see extrapolation. In mathematics, extrapolation is a type of interpolation. ...

When y is known and x must be found, the procedure is identical with x and y interchanged.

Linear interpolation as approximation

In numerical analysis a linear interpolation of certain points that are in reality values of some function f is typically used to approximate the function f. Linear interpolation can be regarded as a trivial example of polynomial interpolation. The error of this approximation is defined as Numerical analysis is the study of algorithms for the problems of continuous mathematics (as distinguished from discrete mathematics). ... In the mathematical subfield of numerical analysis, polynomial interpolation is the interpolation of a given data set by a polynomial. ...

where p denotes the linear interpolation polynomial defined above In mathematics, a polynomial is an expression in which constants and powers of variables are combined using (only) addition, subtraction, and multiplication. ...

It can be proven using Rolle's theorem that if f has two continuous derivatives, the error is bounded by In calculus, Rolles theorem states that if a function f is continuous on a closed interval [a,b] and differentiable on the open interval (a,b), and f(a) = f(b) then there is some number c in the open interval (a,b) such that f (c) = 0. ...

As you see, the approximation between two points on a given function gets worse with the second derivative of the function that is approximated. This is intuitively correct as well: the "curvier" the function is, the worse is the approximations made with simple linear interpolation.

Applications

Linear interpolation is often used to fill the gaps in a table. Suppose you have a table listing the population of some country in 1970, 1980, 1990 and 2000, and that you want to estimate the population in 1994. Linear interpolation gives you an easy way to do this.

The basic operation of linear interpolation between two values is so commonly used in computer graphics that it is sometimes called a lerp in the jargon of computer graphics. The term can be used as a verb or noun for the operation. e.g. "Bresenham's algorithm lerps incrementally between the two endpoints of the line." Computer graphics (CG) is the field of visual computing, where one utilizes computers both to generate visual images synthetically and to integrate or alter visual and spatial information sampled from the real world. ... A verb is a part of speech that usually denotes action (bring, read), occurrence (decompose, glitter), or a state of being (exist, stand). Depending on the language, a verb may vary in form according to many factors, possibly including its tense, aspect, mood and voice. ... A noun, or noun substantive, is a part of speech (a word or phrase) which can co-occur with (in)definite articles and attributive adjectives, and function as the head of a noun phrase. ... The word operation can mean any of several things: The method, act, process, or effect of using a device or system. ... Bresenhams line algorithm is an algorithm that determines which points on a 2-dimensional raster should be plotted in order to form a close approximation to a straight line between two given points. ...

Lerp operations are built into the hardware of all modern computer graphics processors. They are often used as building blocks for more complex operations: for example, a bilinear interpolation can be accomplished in three lerps. Because this operation is cheap, it's also a good way to implement accurate lookup tables with quick lookup for smooth functions without having too many table entries. In mathematics, bilinear interpolation is an extension of linear interpolation for interpolating functions of two variables. ... In computer science, a lookup table is a data structure, usually an array or associative array, used to replace a runtime computation with a simpler lookup operation. ... In mathematics, a smooth function is one that is infinitely differentiable, i. ...

History

Linear interpolation has been used since antiquity for filling the gaps in tables, often with astronomical data. It is believed that it was used in the Seleucid Empire (last three centuries BC) and by the Greek astronomer and mathematician Hipparchus (second century BC). A description of linear interpolation can be found in the Almagest (second century AD) of Ptolemy. Radio telescopes are among many different tools used by astronomers Astronomy (Greek: αστρονομία = άστρον + νόμος, astronomia = astron + nomos, literally, law of the stars) is the science of celestial objects and phenomena that originate outside the Earths atmosphere, such as stars, planets, comets, auroras, galaxies, and the cosmic background radiation. ... This article or section does not cite its references or sources. ... Hipparchus. ... Almagest is the Latin form of the Arabic name (al-kitabu-l-mijisti, i. ... Claudius Ptolemaeus (Greek: ; c. ...

Extensions

In demanding situations, linear interpolation is often not accurate enough. In that case, it can be replaced by polynomial interpolation or spline interpolation. In the mathematical subfield of numerical analysis, polynomial interpolation is the interpolation of a given data set by a polynomial. ... In the mathematical subfield of numerical analysis, spline interpolation is a form of interpolation where the interpolant is a special type of piecewise polynomial called a spline. ...

Linear interpolation can also be extended to bilinear interpolation for interpolating functions of two variables. Bilinear interpolation is often used as a crude anti-aliasing filter. Similarly, trilinear interpolation is used to interpolate functions of three variables. Other extensions of linear interpolation can be applied to other kinds of mesh such as triangular and tetrahedral meshes. In mathematics, bilinear interpolation is an extension of linear interpolation for interpolating functions of two variables. ... In digital signal processing, anti-aliasing is the technique of minimizing aliasing (jagged or blocky patterns) when representing a high-resolution signal at a lower resolution. ... Trilinear interpolation is the process of taking a three-dimensional set of numbers and interpolating the values linearly, finding a point using a weighted average of eight values. ... A mesh is similar to fabric or a web in that it has many connected or weaved pieces. ...

References

• E. Meijering (2002). A Chronology of Interpolation. From Ancient Astronomy to Modern Signal and Image Processing. Proceedings of the IEEE 9 (3), 319–342.

See also

• bilinear interpolation
• de Casteljau's algorithm

In mathematics, bilinear interpolation is an extension of linear interpolation for interpolating functions of two variables. ... In the mathematical subfield of numerical analysis the de Casteljaus algorithm, named after its inventor Paul de Casteljau, is a recursive method to evaluate polynomials in Bernstein form or Bézier curves. ...

External links

• Equations of the Straight Line at cut-the-knot
• Lagrange Polynomials and Interpolation at cut-the-knot