Methods of Interpolation - Interpolation and Extrapolation, Business Mathematics and Statistics | Business Mathematics and Statistics - B Com PDF Download

Introduction

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

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 dened by P , Q, but outside the segment (P; Q).

Cosine Interpolation

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 .

Cubic Interpolation
...

Hermite Interpolation
...

Linear Interpolation Let us now dene linear interpolation in more mathematical terms.
Denition 1. A linear interpolation is an affine transformation from an unit interval [0; 1] to a straight line segment in Rⁿ , where f₁ (t); : : : ; f_n (t) are the function components of f along each coordinate axis.
See Lecture 1 for more details on affine transformations. By denition, an affine transformation preserves barycentric combinations. Therefore, if t ∈ [0; 1] is dened as a barycentric combination of the points 0; 1 ∈ R 

t = α₀ :0 + α₁ :1; with α₀ + α₁ = 1

then,

with α₀ = 1 - t and α₁ = 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 P₀ , P , P₁ be three collinear points in R³ . Then, P is the barycentric combination of P₁ and P₂ given as follows:

where  α₀ and  α₁ are the barycentric coordinates of P with respect to P₀ and P₁ , 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 α₀ and α₁ , and the fact that a linear interpolation preserves barycentric coordinates, we have:

where

that is,

P (t) = (1 t) :P₀ + t :P₁

Linear Interpolation and Geometric Ratios

By de nition, the ratio of three collinear points P₀ , P , and P₁ is given by

Taking into account the expressions of the barycentric coordinates α₀ , 1 given above, we have

We know that an affine transformation f : [0; 1] → Rⁿ preserves barycentric coordinates; as a consequence, the ratio of barycentric coordinates is also preserved. Therefore, r(P₀ ; P; P₁ ) 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)P₀ + tP₁

we have

Because a; u; b and 0; t; 1 have the same geometric ratio as P₀ ; P; P₁ , 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 P₀ ; P₁ ; : : : ; P_N ∈ Rⁿ 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 P₀ ; P₁ ; : : : ; P_N . This is illustrated in FIg. ??, where we determine a point in each segment for every t ∈ [0; 1].
If the points P₀ ; P₁ ; : : : ; P_N 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 ∈ R² be three points dening two straight lines that meet at B , and D; E ; F points in the lines dened 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 P₀ ; P₁ ; P₂ . 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 (P₀ ; P₁ ), and other two image points Q(t); Q(u) in the straight line segment (P₁ ; P₂ ) in R₂ , 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

                 (2)

Now, let us substitute the expressions of

and

into (7) so that we get

            (3)

By combining (7) and ((3)), we have

                             (4)

that is,

                          (5)

or, equivalently,

                                                 (6)

Substituting these barycentric coordinates in (7), we obtain

                            (7)

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 P₀ ; P₁ ; P₂ be three points in R² . Using piecewise linear interpolation, we determine two points for a given t ∈ R, one in the straight line dened by (P₀ ; P₁ ) and another dened by (P₁ ; P₂ ), as follows:

                    (8)

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

                  (9)

Substituting the expressions of  given by (8) into (9), we obtain

             (10)

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.