Problem C: Piecewise Linear Interpolation (20 points)

Sometimes time-dependent data that is gathered at irregular times needs to be estimated at more regular times. For example, a remote sensors readings might occur only at cer- tain times t = 0.0, .12, .25, .37, .50, .71, 1.0 when what you want is readings at times 0.0, 0.1, 0.2, 0.3, . . . , 1.0. One way to estimate what the intermediate readings would have been is to use piecewise linear interpolation.3 For example, suppose we want to esti- mate what the reading would have been at time t = 0.2. Let f(.12) be the reading at timet=.12,andf(.25)bethereadingattimet=.25. Thetimet=0.2is8/13oftheway from .12 to .25, so we can estimate the reading at t = 0.2 by the weighted average

??8????8??f(0.2) = 1 ? 13 f(.12) + 13

f(.25).

In general, to estimate the reading at time t, let a be the largest time less than t at which a reading was taken, and b be the smallest time after t at which a reading was taken. (For example, if t = .36, then in the example we would have a = .25 and b = .37.) Then the estimate for the reading at t is given by

??b?t?? ??t?a??f(t)= b?a f(a)+ b?a f(b).

Write a C++ program that does the following:

First, it should prompt the user for the input file name and open that file, exiting with an error message if the file cant be opened.

Then it should prompt the user for an output file name and open that file for writing, exiting with an error message if the file cant be opened.

3. Third, for each time t = 0.0, 0.1, 0.2, ..., (until the end value in the input file) it should

estimate f(t) and write a line consisting of t and f(t) to the output file. Both values should be written with two digits to the right of the decimal point, and they should be separated by a single space. (See the example output file below.)

4. When all the values have been written to the output file, both the input and output file should be closed.

3Piecewise linear interpolation is not the only way to estimate intermediate values. In general, whether it is a reasonable approach to use depends on the specific problem.

5

Note that, other than the two filenames, the program has no input: all the other input is from the input file. Similarly, the program does not output anything to the console window: all the output is written to the output file.

The input file has the following format: it consist of a number of lines, each of which has two values: the time, followed by whitespace, followed by the reading at that time. You will need to determine when you are at the end of the file by using the eof() function. To simplify the program, assume the first time in the file is always 0.0, and the last is always a value with a 0 fractional part (such as 6.0 or 8.00).

Here is an example input file:

0.0 4.00 .12 3.94 .25 3.88 .37 3.92 .50 4.12 .71 4.34 1.0 4.50 1.42 5.12 1.45 5.13 2.0 5.57 

Note that part of the challenge of this problem is that the time spacings in the input file are irregular. For example, note the following for the regular times 0.0, 0.1, . . . , 2.0: First, 0.0 is the same as the first time in the file, so the reading f(0.0) can just be copied, it does not need to be computed. Then, 0.1 is between the file times 0.0 and .12; 0.2 is between .12 and .25; 0.3 is between .25 and .37, and 0.4 is between .37 and .50. The time 0.5 is in the input file, so the reading f(0.5) can be copied. Then the times 0.6 and 0.7 are between .50 and .71. Then the times 0.8 and 0.9 are between .71 and 1.00. Then the time 1.0 is in the input file. Then 1.1, 1.2, 1.3 and 1.4 are between 1.0 and 1.42. Then 1.5, 1.6, 1.7, 1.8, and 1.9 are between 1.45 and 2.00. (Moreover, note that there are two consecutive times, 1.42 and 1.45, in the input file that dont have any of the regular times between them.) Finally, the last value 2.00 is in the input file.

For that example input, the resulting output file should be

0.00 4.00 0.10 3.95 0.20 3.90 0.30 3.90 0.40 3.97 0.50 4.12 0.60 4.22 0.70 4.33 0.80 4.39 0.90 4.44 1.00 4.50 

6

1.10 4.65 1.20 4.80 1.30 4.94 1.40 5.09 1.50 5.17 1.60 5.25 1.70 5.33 1.80 5.41 1.90 5.49 2.00 5.57 

Some important comments:

This should not be a long program. However, how to coordinate the regular times 0.0, 0.1, 0.2., . . . with the irregular input times is challenging. A related, challenging part is ensuring that you generate output lines all the way to, but not past, the last desired time value. Both of these challenges will require some thought and some care.

You may assume the input data file contains at least two lines of data.

Remember you should also assume the first time in the file is 0.00, and the last time is a whole number of seconds (i.e., the fractional part is 0).

Be careful about how you compute the regular times. An approach where, for example, you start with 0.0 and add 0.1 successively is likely to lead to frustrating round-off errors.

Your program should work not only on the example input file above, but on any input file of that type.

The solution to this problem does not require arrays. You may use arrays if you wish, but the simplest solution does not use arrays (we have not yet covered arrays in class and it is not expected that you understand how to use them yet).