Description
1 Goal
A tracking device has been attached to a moving vehicle. The goal of this project is to construct the routes of
the vehicle, by interpolating the signals obtained from the tracking device.
2 Detailed description
2.1 Method
The tracking device records information about, among other parameters, their positions at different times as a
matrix of the form:
t0 x0 y0
t1 x1 y1
.
.
.
.
.
.
.
.
.
tn xn yn
(1)
The pair (xi
, yi) are xy coordinates of the vehicle at time ti
, and we want to find a parametric curve (x(t), y(t))
describing the path of the vehicle at any time t. To find it, we will use polynomial interpolation to get a
description of the evolution of the variables x and y with respect to t, and evaluate it at different times in the
interval [t0, tn].
2.2 Approach: Cubic Spline Interpolation
2.2.1 Definition of Cubic Spline
Here we want to use so-called cubic spline interpolation to interpolate the function f(t) given point values
f(ti) ≡ fi for t0 < t1 < . . . < tn. We consider a piecewise polynomial S(t) called the cubic spline, written in
the form
S(t) =
s1(t) t ∈ [t0, t1]
.
.
.
.
.
.
sn(t) t ∈ [tn−1, tn]
.
By the definition, the cubic spline S(t) satisfies the following conditions
a. The function S(t) restricted on each subinterval [ti−1, ti
], denoted by si(t), is a cubic polynomial of the form
si(t) = fi + bi(t − ti) + ci(t − ti)
2 + di(t − ti)
3
for i = 1, . . . , n. (2)
b. S(t), S
0
(t) and S
00(t) are continuous.
c. either (i) natural boundary condition:
S
00(t0) = S
00(tn) = 0,
or (ii) clamped boundary condition:
S
0
(t0) = f
0
0 and S
0
(tn) = f
0
n
are satisfied. If clamped boundary condition is used, then some numerical differentiation method is needed
to compute the derivatives f
0
0 and f
0
n
. In this project, we apply the natural boundary condition.
1
2.2.2 Solving Cubic Spline
We want to solve the coefficients bi
, ci
, di for i = 1, . . . , n in cubic spline representation (2). The solution process
can be formulated in two steps:
1. Solving the coefficients ci
.
It can be derived from the definition of cubic spline that ci(i = 1, . . . , n − 1) satisfy the equation
1
3
hici−1 +
2
3
(hi + hi+1)ci +
1
3
hi+1ci+1 =
fi+1 − fi
hi+1
−
fi − fi−1
hi
. (3)
In addition, if the natural boundary condition is applied, then
c0 = cn = 0.
2. Solving the other coefficients.
After applying the interpolation conditions and continuity of the spline at the interior nodes, we have
(
bi =
fi−fi−1
hi
−
hi(ci+2ci−1)
3
,
di =
ci−ci−1
3hi
.
(4)
Then we obtain the cubic splines si(t) for each subinterval [ti−1, ti
] as defined in (2). They join together to
define S(t) on the whole interval [t0, tn].
2.3 Application of cubic splines to the tracking problem
We consider cubic spline interpolation of (x(t), y(t)) for each time interval [ti−1, ti
]. More concretely, we construct
cubic splines S
x
(t) for x(t) and S
y
(t) for y(t) respectively. Then the parametric curve (S
x
(t), Sy
(t)) represents
the path of the vehicle.
3 What to submit
You are expected to submit to the CCLE page of the course a .zip file containing:
1. MATLAB/Octave files implementing the following algorithms:
(a) Construction of cubic splines as described in Section 2.2. The implementation should provide options
to use natural boundary condition and clamped boundary condition.
(b) Functions for solving the tracking problem as described in Section 2.1, using both natural boundary
condition and clamped boundary condition.
2. A .pdf file with a brief report of the project, including the following sections:
(a) User Guide: A concise description of all the routines and applications: what do they do, and meaning
of each input/output variable.
(b) Solutions: The data file is provided as “data.mat”, and you can load the data by using the command
“load(‘data.mat’)”. The variable “ip” are interpolating data points in the form of (1). Test your
code by plotting the path of the vehicle.
(c) Experiments: Calculate the velocity of the vehicle at each data point using the cubic splines, which
are denoted by u0, u1, . . . , un. As a comparison, calculate the the velocity using three-point mid-point
method (end points treated by appropriate methods), which are denoted by v0, v1, . . . , vn. Note that
the velocity of a vehicle is a 2D vector. Plot the velocity field u and v using the MATLAB/Octave
built-in “quiver” function.
2
