We discuss here a number of interpolation methods that we commonly nd in computer graphics and geometric modeling. Interpolation means to calculate a point or several points between two given points. For a given sequence of points, this means to estimate a curve that passes through every single point.
Linear interpolation is the simplest interpolation method. Applying linear interpolation to a sequence of points results in a polygonal line where each straight line segment connects two consecutive points of the sequence. Therefore, every segment (P; Q) is interpolated independently as follows:
P (t) = (1 t) :P + t :Q (1)
where t ∈ [0; 1]. By varying t from 0 to 1 we get all the intermediate points between P and Q. Note that P (t) = P for t = 0 and P (t) = Q for t = 1. For values of t < 0 and t > 1 result in extrapolation, that is, we get points on the line dened by P , Q, but outside the segment (P; Q).
As shown in Fig. ??, the curve resulting from Linear interpolation has discontinuities at each point. In certain circumstances, we need a smoother interpolating function, that is a function that allows for a smooth transition between consecutive segments. The cosine interpolation carries out a transition that looks smooth, though every segment is interpolated independently .
Linear Interpolation Let us now dene linear interpolation in more mathematical terms.
Denition 1. A linear interpolation is an affine transformation from an unit interval [0; 1] to a straight line segment in Rn , where f1 (t); : : : ; fn (t) are the function components of f along each coordinate axis.
See Lecture 1 for more details on affine transformations. By denition, an affine transformation preserves barycentric combinations. Therefore, if t ∈ [0; 1] is dened as a barycentric combination of the points 0; 1 ∈ R
t = α0 :0 + α1 :1; with α0 + α1 = 1
with α0 = 1 - t and α1 = t. This is illustrated in Fig.??, where we intuitively see that the linear interpolation preserves the ratio
Linear Interpolation and Barycentric Coordinates
Let us rst see the relation between collinearity and barycentric coordinates. Let P0 , P , P1 be three collinear points in R3 . Then, P is the barycentric combination of P1 and P2 given as follows:
where α0 and α1 are the barycentric coordinates of P with respect to P0 and P1 , that is
where D(; ) denotes the signed Euclidean distance between two points.
We are now at a position that allows to show that the linear interpolation is given by Eq. (1). Taking into consideration the above expressions for α0 and α1 , and the fact that a linear interpolation preserves barycentric coordinates, we have:
P (t) = (1 t) :P0 + t :P1
Linear Interpolation and Geometric Ratios
By de nition, the ratio of three collinear points P0 , P , and P1 is given by
Taking into account the expressions of the barycentric coordinates α0 , 1 given above, we have
We know that an affine transformation f : [0; 1] → Rn preserves barycentric coordinates; as a consequence, the ratio of barycentric coordinates is also preserved. Therefore, r(P0 ; P; P1 ) remains unchanged by affine transformations, that is,
In short, an affine transformation preserves the geometric ratio of collinear points, that is, the image of a straight line segment is a straight line segment.
Linear Interpolation over [a; b]
The interval [a; b] can be obtained from the affine transformation of the interval [0; 1]. With t ∈ [0; 1] and u∈ [a; b], this affine trnsformation is given by
so, replacing the expression of t into
P (t) = (1 t)P0 + tP1
Because a; u; b and 0; t; 1 have the same geometric ratio as P0 ; P; P1 , we end up showing that the linear interpolation is invariant under affine domain mappings. By affine domain mapping we mean an affine transformation from the real line to itself.
Piecewise Linear Interpolation
Piecewise linear interpolation involves not two points but a sequence of points P0 ; P1 ; : : : ; PN ∈ Rn such that a linear interpolation is applied to two consecutive points of this sequence. The result is a polyline P, called piecewise linear interpolant of all points P0 ; P1 ; : : : ; PN . This is illustrated in FIg. ??, where we determine a point in each segment for every t ∈ [0; 1].
If the points P0 ; P1 ; : : : ; PN are on a curve C , we say that the resulting polyline P is a piecewise linear interpolant of the curve C ; symbolically, we write P = P(C ).
The piecewise linear interpolation enjoys two properties, as described in the sequel.
Property L4.1 (affine Invariance )
If a curve C is sub ject to an affine transformation f , then a piecewise linear interpolant of f (C ) is an affine transformation of the original piecewise linear interpolant, that is,
P(f (C )) = f (P(C ))
Property L4.2 (Variance Diminishing )
Let P(C ) be a piecewise linear interpolant of the curve C , and π an arbitrary hyperplane that intersects both C and P(C ). Then, we have
that is, the number of intersection points between the plane and the interpolant is less or equal to the number of points resulting from the intersection between and the curve.
This is so because, unlike a straight line segment of the interpolant, the curve segment passing through the two endpoints of such a straight line segment is not necessarily convex.
The Menelaus Theorem
Let us now have a look at an important theorem in the context of piecewise linear interpolation.
Theorem 2. Let A; B ; C ∈ R2 be three points dening two straight lines that meet at B , and D; E ; F points in the lines dened by (B ; C ), (A; C ), and (A; B ), respectively, each one of which is distinct from the vertices of the triangle ΔAB C . Then, the points D; E ; F are said to be collinear if and only if
Proof Let us consider the piecewise linear interpolant of the points P0 ; P1 ; P2 . Let us apply the same linear interpolation to two points t; u ∈ [0; 1] ⊂ R in a way we get two image points P (t); P (u) in the straight line segment (P0 ; P1 ), and other two image points Q(t); Q(u) in the straight line segment (P1 ; P2 ) in R2 , as illustrated in Fig. ??.
We intend to prove that
For that purpose, we have only to determine the unknown third ratio , that is, we have to determine the barycentric coordinates of P . Taking into account that P is a barycentric combination of both straight line segments (P (u); Q(u)) and (P (t); Q(t)), we have
Now, let us substitute the expressions of
into (7) so that we get
By combining (7) and ((3)), we have
Substituting these barycentric coordinates in (7), we obtain
Finally, we can write down
Repeated Linear Interpolation
Let us now see how repeated linear interpolation allows for a procedure to construct parabolas. As we will see in lectures to come, the generalization of this procedure leads us to the construction of B'ezier curves.
So, let P0 ; P1 ; P2 be three points in R2 . Using piecewise linear interpolation, we determine two points for a given t ∈ R, one in the straight line dened by (P0 ; P1 ) and another dened by (P1 ; P2 ), as follows:
where the exponent 1 indicates the degree of the polynomial. By applying the same linear interpolation at t ∈ R to the new segment , we have
Substituting the expressions of given by (8) into (9), we obtain
which is a degree-2 polynomial representing a parabola. This construction procedure for parabolas uses repeated linear interpolation.
Property L4.3 (Convex Hull )
The construction of a parabola using repeated linear interpolation enjoys the following the convex hull property, because
Property L4.4 (Affine Invariance )
Taking into consideration the ratios
we conclude that the above construction of a parabola is invariant under affine transformations because the piecewise linear interpolation is affine invariant.